AQA A2 Computing - Unit 3

Interface: A boundary between the implementation of a system and the world that uses it. It provides an abstraction of the entity behind the boundary thus separating the methods of eternal communication from internal operation.

Information Hiding: Hiding the design details behind a standard interface.

Abstraction: A representation that is arrived at by removing unnecessary details.

There are two possible ways of achieving abstraction as listed below:

Abstraction by generalisation:

• Objects are grouped together by identifying common characteristics.
• Starting at the top of the abstraction diagram and then descening through succesive refinements to arrive at the details of the solution. This allows the problem to be decomposed.

Abstraction by representation:

• Details are removed until it becomes possible to represent the problem in a way it can be solved

Algorithm: A description, independent of ant programming language, of a process that achieves some task. It is a rep-by-step procedure for solving a problem

Algorithm Computational Complexity: Measures how economical the algorithm is with time and space.

Algorithm Time Complexity: Indicates how fast an algorithm executes.

Algorithm Space Complexity: Indicates how much memory is required by an algorithm.

Problem Complexity: Taken to be the worst-case complexity of the most efficient algorithm which solves a given problem.

Basic Operation: The operation contributing the most to the total running time.

Order Of Growth: Assesses by what factor the execution time of an algorithm increases when he size of the input is increased.

Asymptomatic Behaviour Of F: The behaviour of the function F(n) for very large values of n.

O(g): Called big O of g, represents the class of functions that grow no faster than g.

Order Of Complexity: This is the big O complexity of a problem.

Exponential Growth: Growth that has the form K^n, e.g. 2^n where k = 2 and n = 1, 2, 3, etc.

Exponential Time Algorithm: An algorithm whose execution time grows exponentially with input size.

Polynomial Growth: Growth that has the form n^k, e.g n^3 where k = 3 and n = 1, 2, 3, 4, etc.

Polynomial Time Algorithm: An algorithm whose execution time grows as a polynomial of input size.

Linear Time Algorithm: A polynomial time algorithm that executes in O(n) time.

State Transition Diagram: A directed graph whose nodes represent the states.

Finite State Machine (FSM): Conists of a set of input symbols and if it produces an oputput, a set of output symbols. A finite set of states and a transition function thatmaps a state-symbol pair to a state and possibly generates an ouput depending on the type of FSM.

Transition Function: Maps inputs symbols and current state to output symbol and next state.

Transition Table: Tabulates the transitions functions.

Deterministic FSM: An FSM that has just one next state for each pair of state and input symbol.

Non-Deterministic FM: An FSM that may have several possible next states for each pair of state and input symbol.

Halting State: A state that has no outgoing transition.

Mealy Machine: An FSM that determines its outputs from the current state and the inputs.

Moore Machine: An FSM that determines its outputs from the current state only.

Finite State Automation (FSA): An FSM that produces no output while processing the the input but which responds YES or NO when it has finished processing the input. 

Key Point: An edge leading from state s to state t is called a transition and is labelled with a symbollic code, e.g. a | b. The 'a' part of the label is called the transition's trigger and denotes the input symbol. The b part, which is optional, denotes the output symbol.

Key Point: An FSM represents a system as a set of states, the transition between the states along with the associated inputs and outputs drawn from the machine's alphabet of symbols. One state is designated the start state.

Key Point: An FSM may be constructed to perform an action at the output stage instead of outputting a symbol.

Key Point: The input symbol may be replaced by a signal that signals an event.

Key Point: FSAs solve boolean/dicession problems.

Key Point: Accepting states cause FSA to produce a YES response and the rest of the states cause the FSA to produce a NO response.

Key Point: Deterministic FSAs are often called deterministic finite automota (DFA); non-deterministic FSAs are often called non-deterministic finite automota (NFA).

Turing Machine (TM): An FSM that controls one or more tapes, where at least one is of unbounded length (i.e. infinitely long).

Key Point: 

THESE CARDS ARE INCOMPLETE AND WILL BE UPDATED CONSTATLY (Daily or every other day)!