AQA A-Level Computer Science

Functional abstraction

Functional abstraction

A mapping from one set of values to another. The result of this mapping is unique to a given set of inputs, and a value must always be returned

Procedural abstraction

Using a procedure to carry out a sequence of steps for achieving some task

Information hiding

Where data is not directly accessible and can only be accessed through defined procedures/functions

Decomposition

Breaking down a complex problem into a number of sub-problems, each of which performs an identifiable task

Composition

Combining procedures to form compound procedures (e.g. BuildHouse, BuildStreet). It can also mean combining objects to form compound data, for example records or a data structure such as a queue, tree or list.

Automation

Building and putting into action models to solve problems

Finite state machine

Abstract model of computation used to design computer programs and sequential logic circuits. It can be in one of a finite number of states and changes from one state to the next state when triggered by some condition or input (say, a signal from a timer).

In a finite state machine:

• The machine can only be in one state at a time

• It can change from one state to another in response to an event or condition; this is called a transition. Often this is a switch or a binary sensor.

• The Finite State Machine (FSM) is defined by a list of its states and the condition for each transition

Finite state automaton

Finite state machine which has no output

Deterministic final state automaton

In a finite state machine, when you are in a particular state, and the next state is uniquely determined by the input

Integer (ℤ)

Any whole number

Natural number (ℕ)

A whole number used in counting

Rational number (ℚ)

Any value that can be expressed as a ratio, or fraction, including all integer values

Irrational number

A value that cannot be expressed as a fraction and has an endless series of non-repeating digits

Ordinal numbers

Describe the numerical positional of objects

Parity bit

Additional bit that is used to check that the other bits transmitted are likely to be correct

Odd parity

The total number of 1s in each bye, including the parity bit, equals an odd number

Even parity

The total number of 1s in each bye, including the parity bit, equals an even number

Majority voting

System that requires each bit to be sent three times. If a bit value is flipped erroneously during transmission over a noisy line, the recipient computer would use the majority rule and assume that the two bits that have not changed were therefore correct

Checksum

Mathematical algorithm that is applied to a ‘unit’ or packet of data. The data in the block is used to create a checksum value which is transmitted with the block. The algorithm is applied to the block after transmission and if the two checksums match, the transmission is deemed to have been successful.

Check digit

Similar to a checksum. An additional digit at the end of a string of other numbers designed to check for mistakes in input or transmission.

Unsigned binary number

Can represent only positive numbers

Signed binary number

Can represent both positive and negative numbers

Two’s complement

One representation of a signed binary number

Fixed point binary number

A way to represent fractions in binary. A binary point is used to separate the whole place values from the fractional part.

Bitmap/raster images

Contain pixels that make up an image

Pixel

A smallest identifiable area of an image, attributed a binary value which represents a single colour

Resolution

Width in pixels * height in pixels

PPI

Pixels per inch

Pixels per inch

Indicates the density of pixels within an image

Colour depth

The number of bits per pixel, which determines the number of colours that a pixel can represent

Metadata

Data about data

Image metadata

• Width/height in pixels

• Colour depth

• GPS coordinates where the image was taken

• Camera or device used to take the image

• Exposure time

• Focal length

Vector graphics

Images made up of geometric shapes or objects. The file contains only the necessary details about each shape in order to redraw the object when the file loads.

Properties of each object include:

• Position

• Radius

• Fill colour

• Line colour

• Line weight

Sampling rate

The frequency with which you record the amplitude of the sound

Sound sample size

Number of samples per second * Number of bits per sample * Length of the sample in seconds

Analogue signal

A continuous signal which represents physical measurements

Digital signal

Discrete time signals generated by digital modulation

Analogue representation

Uses a continuous range of values to represent information

Digital representation

Uses discrete or discontinuous values to represent information

Analogue to digital conversion

1. Microphone converts sound energy into electrical energy

2. ADC (analogue to digital converter) samples the analogue data at a given frequency, measuring the amplitude of the wave at each point and converting it into a binary value according to the resolution or audio bit depth being used for each sample

Digital to analogue conversion

1. Binary values for each sample point are translated back into analogue signals or voltage levels

2. These are sent to an amplifier connected to a speaker, producing sound

Frequency

The speed of oscillation or vibration of a wave, measured in Hertz (Hz)

Nyquist’s theorem

In order to produce an accurate recording, the sampling rate must be at least double that of the highest frequency in the original signal

MIDI

Musical Instrument Digital Interface

Musical Instrument Digital Interface (MIDI)

A technical standard that describes a protocol, digital interface, and connectors which can be used to allow computers and electronic musical instruments to connect and communicate

MIDI controller

• Carries event messages that:

  • Specify:

    • Pitch and duration of a note

    • Timbre

    • Vibrato

    • Volume changes

  • Synchronise tempo between multiple devices

MIDI file

List of instructions that tell it to synthesise a sound based on pre-recorded digital samples and synthesised samples of sounds

Lossy compression

Unnecessary information is removed from the original file

Lossless compression

All the information required to replicate the original file exactly is retained

RLE

Run Length Encoding

Run Length Encoding (RLE)

A method of lossless compression whereby repetitive and consecutive data is replaced with counts of how many are in a row

Dictionary-based compression

A method of

Encryption

The transformation of data from one form to another to prevent an unauthorised third party from being able to understand it.

Plaintext

The original data or message before encryption

Ciphertext

The encrypted data

Key

The secret information to lock or unlock the message

Caesar cipher/shift cipher

A type of substitution cipher that works by shifting the letters of the alphabet along by a given number of characters, the number of characters being the key

Vernam cipher

A type of one-time pad cipher that offers perfect security. A Boolean XOR operation is carried out between the binary representation of each character of the plaintext and the corresponding character of the one-time pad

One-time pad

To provide perfect security, the encryption key must be:

• equal to or longer in characters than the plaintext

• truly random

• used only once.

The sender and recipient must meet in person to securely share the key and subsequently destroy it after encryption and decryption.

Not susceptible to cryptanalysis due to its truly random distribution of characters.

Hardware

The electrical or electro-mechanical parts of a computer and its input, output, and storage devices

Software

All the programs that are written to make computers function

System software

The software needed to run the computer’s hardware and application programs

Operating system

A set of programs that lies between applications software and the computer hardware.

It provides an Application Programming Interface (API) for hardware and software to communicate.

Its functions include:

• Resource management

  • Memory management

  • Processor scheduling

  • Backing store management

  • Management of all input and output

• Provision of a user interface

Resource management

Managing all the computer hardware including the CPU, memory, disk drives, keyboard, monitor, printer, and other peripheral devices

Provision of a user interface

Enables users to perform tasks like:

• Running application software

• Changing settings on the computer

• Downloading and installing new software

Memory management

The allocation and deallocation of memory space for processes, programs, and data.

Virtual memory may be used.

Processor scheduling

Allocating processor time to each process in the most efficient way possible, allowing for multi-tasking

Roles of the scheduler

• Maximise throughput

• Be fair to all users on a multi-user system

• Provide acceptable response time to all users

• Ensure hardware resources are kept as busy as possible

Backing store

A secondary storage device that holds data and programs that are not currently in use by the main memory

Backing store management

• Allocating space on the backing store

• Transferring data and programs between the main memory and the backing store

• Keeping track of the location and status of each file on the backing store

• Keeping track of free areas of storage so new files or applications can be saved

• Allowing users to move files and folders, delete files, and protect others from unauthorised access

Peripheral management

Using device drivers to control the sending and receiving of data to and from peripheral input and output devices. The operating system also ensures peripherals are allocated to processes without causing conflicts.

Interrupt

A signal from a peripheral or software program that causes the operating system to stop processing its current list of instructions

Interrupt handling

When an error occurs and a process interrupted, the operating system must detect the interrupt signal and display an appropriate error message (if appropriate) before deciding what to do next. Interrupts are what allows multi-tasking to take place.

Utility programs

System software designed to optimise the performance of the computer or perform tasks like:

• backing up files

• restoring corrupted files from backup

• compressing or decompressing data

• encrypting data before transmission

Disk defragmenter

Program that will reorganise a hard disk so that files which have been split up into blocks and stored all over the disk will be recombined into a single series of sequential blocks

Virus checker

Checks your hard drive, incoming emails, and internet downloads for viruses, and removes them

Library programs

Ready-compiled programs that can be run when needed

Software libraries

Groups of library programs. Most compiled languages have their own libraries of pre-written functions that can be invoked in a defined manner from within the user’s program.

Translators

A translator than translates program code written by a programmer into machine code which can be run by the computer

Compiler

A translator that translates a high-level language into machine code. It considers the entire code and converts it at once, instead of translating code line-by-line.

Interpreter

A translator that contains subroutines to carry out each high-level instruction. It looks at each line of the source program, analyses it, and, if it contains no syntax errors, calls the appropriate subroutine within its own program code to execute the command.

Bytecode

An intermediate representation of a program’s source code combining compiling and interpreting. It is low-level code that is designed for a software interpreter, compiled to run on a virtual machine instead of a CPU.

Advantage of bytecode

Platform independence

Java Virtual Machine (JVM)

An example of a bytecode interpreter that understands Java bytecode and converts it into the machine code for the particular computer it runs on

Advantages of a compiler over an interpreter

• The object code can be saved on disk and run whenever required without the need to recompile

• The object code executes faster than interpreted code

• The object code produced by a compiler can be distributed or executed without having to have the compiler present

• The object code is more secure, as it cannot be read without ‘reverse engineering’

Situations where a compiler would be more appropriate

• When a program is to be run regularly or frequently, with only occasional changes

• When the object code produced by the compiler is going to be distributed or sold to users outside the company that produced the software (as source code is not present)

Advantages of an interpreter over a compiler

• It is useful for program development as there is no need for lengthy recompilation every time an error is discovered

• It is easier to partially test and debug programs

Situations where an interpreter would be more appropriate

• During program development

• In a student environment when students are learning code, as they can test parts of a program before coding it all

Assembler

Translates an assembly language program (source code) into the 0s and 1s of the corresponding machine code instruction (object code) line-by-line.

Application software

Programs that perform specific user-oriented tasks

General-purpose software

Application software that can be used for many different purposes, e.g.:

• word processors (Word)

• spreadsheet packages (Excel)

• graphics software (Photoshop)

Special-purpose software

Application software that performs a single specific task or a set of tasks, e.g.

• payroll and accounts packages

• hotel booking systems

• fingerprint scanning systems

• browser software

Can be bought ‘off-the-shelf’, ready to use, or can be specially written by a team of programmers for a particular organisation.

NOT gate

Inverts the input

AND gate

The output is only 1 when both A and B are 1

OR gate

The output is only 1 when either A, B, or both A and B are 1

XOR

Exclusive or; the output will be true if one or other input is true, but not both

NAND

Inverts the output of the AND gate

NOR

Only produces an output of true when both inputs are false

De Morgan’s first law

NOT(A + B) = NOT(A) • NOT(B)