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

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Problem Solving 75% developed[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 25% developed[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 0% developed[edit]

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

Operating systems 100% developed[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 0% developed[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 50% developed[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