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

Problem Solving 75% 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 25% 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 0% A number which you can count to using your fingers and toes Operating systems 100% 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 0% 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 50% 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