# 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