# A-level Computing 2009/AQA/Problem Solving, Programming, Operating Systems, Databases and Networking/Definitions

## Problem Solving [edit]

**Interface** - A boundary between the computer and the user

**Abstraction** - Representation that is arrived by removing unnecessary detail

**Algorithm** - A sequence of instructions to solve a problem that is independent from a language

**Complexity of a Problem** - worst-case complexity of the most efficient algorithm that solves a problem

**Computational Complexity** - How economical the algorithm is with time and space

**Time Complexity** - Indicates how fast an algorithm runs

**Space Complexity** - How much memory an algorithm needs

**Basic operation** - The operation that most contributes to total running time

**Order of Growth** - Assess by what factor execution time increases when the size of input is increased

**Asymptotic Behaviour** - The behaviour of a function for very large input values

**Big O** - O(g): Represents the class of functions that grow no faster than g

**Order of Complexity** - The Big O complexity of a problem

**Exponential Time Algorithm** - An algorithm whose execution time grows exponentially with input size

**Polynomial Time Algorithm** - An algorithm whose execution time grows polynomially with input size

**Exponential Growth** - Growth that has the form: kⁿ

**Polynomial Growth** - Growth that has the form nᵏ

**Linear Time Algorithm** - A polynomial time algorithm that executes in O(n) time

**State Transition Diagram** - A directed graph whose nodes represent states and edges represent transitions

**Finite State Machine** - Has a set of input signals which uses a finite set of Transitions and States to possibly generate an output

**Transition Function** - Maps{Input Symbol: Current State} to {Output Symbol: Next State}

**Transition Table** - Tabulates the Mappings of the Transition Table

**Deterministic FSM** - A FSM that only has 1 Next state for each

**Non-Deterministic FSM** - A FSM that has several next states for each pair of input symbols

**Halting State** - A state that has no outgoing transition, thus being the final state

**Finite State Automaton** - An FSM without output while processing the input

**Mealy Machine** - An FSM that determines its outputs from the current state and inputs

**Moore Machine** - An FSM that determines its outputs from the present state only

**Turing Machine** - An FSM controlling 1 or more tapes where at least 1 is infinitely long

**Equivalent Turing Machine** - All other types of computer are reducible into an equivalent Turing Machine

**Power of a Turing Machine** - No computer can be more powerful than a Turing Machine as a Turing Machine can solve any solvable algorithm

**Universal Turing Machine** - A Turing Machine that can execute and simulate the behaviour of any other Turing Machine

**Principle of Universality** - A Universal Machine is capable of simulating any other machine

**Interpreter** - Works its way through a set of instructions, identifying the next instruction and executing it

**Non-Computable** - A problem that can't be solved or it is not possible to construct the necessary algorithm

**Decision Problem** - A yes/ no algorithmic problem

**Decidable** - Describes a decision problem that has a yes/ no answer

**Undecidable** - A decision algorithm that in non-computable

**Tractable** - Describes a problem that can be solved in reasonable (polynomial) time

**Intractable Describes a problem for which no reasonable (polynomial) time solution is known** -

**Heuristic** - An approach that uses know-how and experiences to make informed guesses that assist in finding a polynomial time solution to intractable problems

**The Halting Problem** - Is it possible to make a program that can tell whether a program will halt or not, given the program and its inputs

## Programming concepts [edit]

**Class** - A routine with procedures and functions to create objects

**Object** - An instance of a class

**Recursive Definition** - A definition that is defined in terms of itself (calls itself)

**Paradigm** - A typical example or pattern of something; a pattern or model

**Instantiation** - Defining an object based on a class

**Class definition** - A pattern or template that can be used to create objects of that class

**Encapsulation** - Combining a record with the procedures and functions that manipulate it to form a new class

**Abstract(/ˈæbstrækt/)** - Apart from practice or reality; not concrete; ideal; vague; theoretical; impersonal

**Dynamic(/daɪˈnæmɪk/)** - Able to change and to adapt, happening at runtime instead of at compile time

**Linear List** - A static abstract data type. The amount of data does not change at run time

**Linked List** - Dynamic Abstract Data Type. Uses pointers to vary memory used at run time

**Heap** - A large pool of unused memory used to allocate space for new data items

**Graphs** - Diagrams modelling relationships between objects of a certain collection, consisting of edges (lines) and vertices (dots)

**Simple Graphs** - An undirected graph that has no loops and no more than one edge between any two different vertices

**Trees** - A tree is a connected undirected graph with no cycles

**Collision** - When two or more hash keys result in the same hash value

**Simulation** - A mathematical representation of reality

## Real Numbers [edit]

A number which you can count to using your fingers and toes

## Operating systems [edit]

**System programs** - Programs that manage the behaviour of a computer

**Virtual machine** - Hides the complexities of the hardware from the user with layers of software

**Application programming interface** - What allows software to use services of the operating system

**Interactive operating system** - An operating system where the user is in constant direct two-way communication.

**Real-time operating system** - An operating system that works under a timely manner so that the source of the input will be determined from an input

**Networked operating system** - An extra layer of software added to the operating system used to handle networking protocols

**Embedded computer system** - An operating system that runs in real-time, that used to mainly work autonomously with little to no user input

**Desktop operating system** - An interactive operating system that allows user to carry out a wide range of tasks

**Client-server operating system** - An operating system that requests resource and services from a server operating system

**Server operating system** - An operating system that's optimised to to provide specialised services to networked clients

**Device operating system** - An interactive operating system that mobile

**Sandbox** - A tightly controlled set of resources for guest programs to run in

## Databases [edit]

**Primary key** - A primary key is a field in a table that contains unique data.

**Composite key** - Collection of attributes uniquely identify a tuple rather than just one

## Communications and networking [edit]

**Data Transmission** - Movement of data from one another

**Serial data Transmission** - single bits are sent one after another along a single wire

**Parallel data Transmission** - bits are sent down several wires simultaneously

**Baud rate** - the rate at which the signals on a wire may change

**1 baud** - one signal change per second

**Bit rate** - the number of bits transmitted per second

**Bandwidth** - the range of signal frequencies that may be transmitted

**Data Transmission** - Movement of data from one another

**Asynchronous serial data transmission** - arrival of data cannot be predicted; a start bit is used to signal to arrival of data

**Communication Protocol** - set of pre-agreed signals, rules for data exchange between computers

**Handshake** - Establishing a connection and getting ready to send and receive

**Baseband system** - system that uses single data channel

**Broadband system** - system that uses multiple data channels