# AQA A2 Computing - Unit 3

- Created by: Naqash Tanzeel
- Created on: 10-05-13 14:27

## Information Hiding & Abstraction

**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

## Comparing Algorithms

**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.

## Comparing Algorithms - Big O Notation

**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.

## Finite State Machines

**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.

## Finite State Machines

**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 Machines

**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:

## Notice!

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

## Comments

No comments have yet been made