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

Problem Solving

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

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

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

Operating systems

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

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

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