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

< A-level Computing | AQA | Problem Solving, Programming, Operating Systems, Databases and Networking

Jump to navigation
Jump to search
## Problem Solving [edit | edit source]

**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 [edit | edit source]

**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 | edit source]

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

## Operating systems [edit | edit source]

**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 | edit source]

**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 | edit source]

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