4.4 Theory of Computation AQA A-Level Computer Science

Computational thinking

A method of problem-solving that helps computer scientists prepare problems for digital solutions, the ability to think logically about a problem and apply techniques for solving it

Decomposition

Breaking down a problem into sub-problems, which are more manageable. We can then solve each sub-problem individually.

Abstraction

Reducing information and detail to focus on essential characteristics, removing unneccessary detail, e.g. London Underground Map.

Pattern recognition

The process of identifying patterns in a data set, e.g. in driving, to respond to traffic patterns, e.g. we might recognise that an upcoming traffic light is yellow, so we will recognise that it will turn red next and prepare to stop. We can apply this pattern every time we come up to a traffic light. In medicine, symptoms are compared to existing patterns to determine which illness the patient may have.

Simulation

The process of designing a model of a real system in order to understand the behaviour of the system, and to evaluate various strategies for its operation.

Applications of simulation

Financial risk analysis

Amusement park rides

Population prediction

Managing inventory problems

Queueing problems

Enumeration

A listing of all of the elements of a set. Can be used in brute force attacks to go through all the possible options for a password, or in something like an anagram solver. It can take a very long time to go through all the possibilities.

Trial and error

A problem-solving strategy that involves attempting different solutions and eliminating those that do not work.

Theoretical approach

Using mathematical and logical methods to solve a problem or calculate possible outcomes.

Creative solution

Finding a creative and previously unknown solution.

Decrease and conquer

- Reduce the problem instance to a smaller instance of the same problem

- solve the smaller instance

- extend the solution of the smaller instance to obtain a solution to the original instance

Algorithm

A sequence of steps that can be followed to complete a task and always terminates.

Sequence

One or more statements following one after the other. The statements are executed in order.

Selection

A generic term for a type of programming statement (usually an if-statement) that uses a Boolean condition to determine, or select, whether or not to run a certain block of statements.

Iteration

Repetition; a set of steps is carried out again and again, either a fixed number of times or based on a condition.

WHILE statement

An indefinite loop, which runs the internal code as long as the condition is true. The condition is tested before entering the loop.

FOR statement

A loop that directs program flow through a group of statements a fixed number of times.

REPEAT...UNTIL statement

Used to repetitively execute a subject statement until a condition is true. The condition is checked after the subject statement is executed. Therefore, the subject statement is always executed at least once.

Structured programming

A method of programming which follows rules about selection, sequence, and iteration control structures. The programmer uses top down analysis for problem-solving, modularization for program structure and organisation, and structured code for the individual modules.

Hierarchy chart

A diagram that illustrates modules' relationships to each other, starting with the whole program, then breaking it down into smaller sub-problems until each box is a singular task.

Benefits of structured programming

Programs are more easily and quickly written - large problems are broken down into smaller modules that are easier to program and manage.

Modules can be reused - in the same program, or saved to a library and used in other programs.

Programs are more reliable and have fewer errors - it's easier to find errors in self-contained modules.

Programs take less time to test and debug - each module can be tested individually.

New features can be added by adding more modules.

Good programming practice

Use meaningful names for variables and subroutines.

Add lots of comments to explain each module.

Each module should perform a singular task.

Selection and iteration structures should have single entry and exit points.

Keep each module self-contained by passing parameters and using local variables in subroutines

High level language structures

Structured programming is only possible because the structures are built into programming languages like Python, Java, VB, and C#.

Early programming languages have no iterative statements.

An iteration statement could only be written like this:

IF (condition) GO TO label

This lead to spaghetti programs which were very difficult to follow.

Examples of problems solved by algorithms

Routing problems:

- Routing packets of data around the Internet by the shortest route

- Finding the shortest route for a salesman to cover his territory

Timetabling commercial aircraft crews so that they don't exceed their permitted flight hours

Searching information on the internet or from a database

Encrypting communications so that they cannot be hacked

Sorting large amounts of data

Writing a compiler program to translate a high-level language to machine code

Properties of a good algorithm

Has clear and precisely stated steps that produce the correct output for any set of valid inputs

Should allow for invalid inputs - exception handling

Must always terminate at some point

Should be efficient and execute in as little steps as possible

Should be designed in such a way that other people will be able to understand it and modify it if necessary

Flowchart

A diagram that represents an algorithm, work flow, or process, and uses geometric symbols connected by arrows to show the direction of the flow of action.

Pseudocode

A non-language-specific way of writing code. Can be used to write out how an algorithm will work without having to worry about specific rules or syntax.

Testing

Used to ensure that the program runs and that it functions without errors. Finding errors is common, e.g. syntax errors, logic errors.

Syntax error

An error that results when an instruction does not follow the syntax rules or grammar of the programming language.

Logic error

An error in a program that makes it do something other than what the programmer intended.

Runtime error

An error that will make the program crash as it is running (e.g. dividing by 0).

Module testing

Making sure each subroutine works correctly

Program testing

Making sure each program in the system works correctly

System testing

Testing the entire system as one entity to ensure that it is working properly

Normal data

Entering data that should be acceptable to the solution.

Boundary data

Data either side of the range extremes. For example in a range of 1 to 10 boundary data will include 0, 1, 10 and 11

Erroneous data

Inputs that the program should not accept.

Hand tracing algorithms

Running through a program manually, as if you were the computer, taking each line at a time and writing down any changes in the values of the variables. A trace table can be used.

Representational abstraction

The process of removing unnecessary details so that only information that is required to solve the problem remains. This uses infomation hiding. e.g. the London Underground Map

Abstraction by generalisation

Grouping by common characteristics to arrive at some kind of hierarchy. Common characteristics are identified.

Problem abstraction

Removing details until the problem is represented in a way that it is possible to solve because it reduces to one which has already been solved.

Automation

Building models of real world objects or phenomena in order to solve a problem.

Computer scientists have to decide what details are relevant to the problem and discard anything else.

Algorithms and data structures can then be designed to solve the problem.

The algorithms is then implemented in program code and executed.

Composition

Combining procedures to form a compound procedure. Combining data to form compound data objects such as a tree or a stack.

Procedural abstraction

Used to keep the actual values used in a computation separate from the overall design.

In simple terms, this involves writing procedures and passing parameters.

Functional abstraction

Abstraction to what a section of code will do rather that the details of how it does it. A function definition allows for abstracting the contained code to a function call.

Data abstraction

Managing complexity in programs by giving a collection of data a name without referencing the specific details of the representation.

Finite state machine

A sequential logic function consisting of a set of inputs and outputs, a next-state function that maps the current state and the inputs to a new state, and an output function that maps the current state and possibly the inputs to a set of asserted outputs.

Uses of finite state machines

Robotics

Video games industry

Design of digital hardware systems

Design of compilers and network protocols

Definition of languages, and to decide whether a particular word is allowed in a language

Finite state automation

A finite state machine that produces no output whilst processing. It responds YES or NO when processing of the input data has finished.

State transition tables

A tabular representation of a FSM that contains the current state, inputs and their consequent successor state.