4.4 Theory of computation

Abstraction and automation

Problem-solving

Content	Additional information
Be able to develop solutions to simple logic problems.
Be able to check solutions to simple logic problems.

Following and writing algorithms

Content	Additional information
Understand the term algorithm.	A sequence of steps that can be followed to complete a task and that always terminates.
Be able to express the solution to a simple problem as an algorithm using pseudo-code, with the standard constructs: sequence assignment selection iteration.
Be able to hand-trace algorithms.
Be able to convert an algorithm from pseudo-code into high level language program code.
Be able to articulate how a program works, arguing for its correctness and its efficiency using logical reasoning, test data and user feedback.

Abstraction

Content	Additional information
Be familiar with the concept of abstraction as used in computations and know that: representational abstraction is a representation arrived at by removing unnecessary details abstraction by generalisation or categorisation is a grouping by common characteristics to arrive at a hierarchical relationship of the 'is a kind of' type.

Content

Additional information

Be familiar with the concept of abstraction as used in computations and know that:

representational abstraction is a representation arrived at by removing unnecessary details
abstraction by generalisation or categorisation is a grouping by common characteristics to arrive at a hierarchical relationship of the 'is a kind of' type.

Information hiding

Content	Additional information
Be familiar with the process of hiding all details of an object that do not contribute to its essential characteristics.

Procedural abstraction

Content	Additional information
Know that procedural abstraction represents a computational method.	The result of abstracting away the actual values used in any particular computation is a computational pattern or computational method - a procedure.

Functional abstraction

Content	Additional information
Know that for functional abstraction the particular computation method is hidden.	The result of a procedural abstraction is a procedure, not a function. To get a function requires yet another abstraction, which disregards the particular computation method. This is functional abstraction.

Data abstraction

Content	Additional information
Know that details of how data are actually represented are hidden, allowing new kinds of data objects to be constructed from previously defined types of data objects.	Data abstraction is a methodology that enables us to isolate how a compound data object is used from the details of how it is constructed. For example, a stack could be implemented as an array and a pointer for top of stack.

Content

Additional information

Know that details of how data are actually represented are hidden, allowing new kinds of data objects to be constructed from previously defined types of data objects.

Data abstraction is a methodology that enables us to isolate how a compound data object is used from the details of how it is constructed.

For example, a stack could be implemented as an array and a pointer for top of stack.

Problem abstraction/reduction

Content	Additional information
Know that details are removed until the problem is represented in a way that is possible to solve, because the problem reduces to one that has already been solved.

Decomposition

Content	Additional information
Know that procedural decomposition means breaking a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided.

Composition

Content	Additional information
Know how to build a composition abstraction by combining procedures to form compound procedures.
Know how to build data abstractions by combining data objects to form compound data, for example tree data structure.

Automation

Content	Additional information
Understand that automation requires putting models (abstraction of real world objects/phenomena) into action to solve problems. This is achieved by: creating algorithms implementing the algorithms in program code (instructions) implementing the models in data structures executing the code.	Computer science is about building clean abstract models (abstractions) of messy, noisy, real world objects or phenomena. Computer scientists have to choose what to include in models and what to discard, to determine the minimum amount of detail necessary to model in order to solve a given problem to the required degree of accuracy. Computer science deals with putting the models into action to solve problems. This involves creating algorithms for performing actions on, and with, the data that has been modelled.

Content

Additional information

Understand that automation requires putting models (abstraction of real world objects/phenomena) into action to solve problems. This is achieved by:

creating algorithms
implementing the algorithms in program code (instructions)
implementing the models in data structures
executing the code.

Computer science is about building clean abstract models (abstractions) of messy, noisy, real world objects or phenomena. Computer scientists have to choose what to include in models and what to discard, to determine the minimum amount of detail necessary to model in order to solve a given problem to the required degree of accuracy.

Computer science deals with putting the models into action to solve problems. This involves creating algorithms for performing actions on, and with, the data that has been modelled.

Regular languages

Finite state machines (FSMs) with and without output

Content	Additional information
Be able to draw and interpret simple state transition diagrams and state transition tables for FSMs with no output and with output (Mealy machines only).

Maths for regular expressions

Content	Additional information
Be familiar with the concept of a set and the following notations for specifying a set: A = {1, 2, 3, 4, 5 } or set comprehension: A = {x \| x ∈ ℕ ∧ x ≥ 1 } where A is the set consisting of those objects x such that x ∈ ℕ and x ≥ 1 is true. Know that the empty set, {}, is the set with no elements. Know that an alternative symbol for the empty set is Ø.	A set is an unordered collection of values in which each value occurs at most once. Several languages support set construction. In Python, for example, use of curly braces constructs a set: {1, 2, 3 }. \| means such that. x ∈ ℕ means that x is a member of the set ℕ consisting of the natural numbers, ie {0, 1, 2, 3, 4, … }. The symbol ∧ means AND. The term ∧ x > = 1 means AND x is greater than or equal to 1. In Python, {2 ∗ x for x in {1, 2, 3 }} constructs {2, 4, 6 }. This is said to be a set comprehension over the set {1, 2, 3 } .
Be familiar with the compact representation of a set, for example, the set {0ⁿ1ⁿ \| n ≥ 1}. This set contains all strings with an equal number of 0 s and 1s.	For example, {0ⁿ1ⁿ \| n ≥ 1} = {01, 0011, 000111, 00001111, … }
Be familiar with the concept of: finite sets infinite sets countably infinite sets cardinality of a finite set Cartesian product of sets.	A finite set is one whose elements can be counted off by natural numbers up to a particular number, for example as: 1st element, 2nd element, …, 20th (and final) element. The set of natural numbers, ℕ and the set of real numbers, ℝ are examples of infinite sets. A countably infinite set is one that can be counted off by the natural numbers. The set of real numbers is not countable. The cardinality of a finite set is the number of elements in a set. Cartesian product of two sets, X and Y, written X x Y and read 'X cross Y', is the set of all ordered pairs (a, b) where a is a member of A and b is a member of B.
Be familiar with the meaning of the term: subset proper subset countable set.	{0, 1 , 2 } ⊂ ℕ where ⊂ means proper subset of, that is ℕ contains everything in {0, 1, 2 } but there is at least one element in ℕ that is not in {0, 1, 2 }. {0, 1 , 2 } ⊆ {0, 1, 2, 3 } where ⊆ means subset of. ⊆ includes both ⊂ and =, for example {0, 1, 2, 3 } ⊆ {0, 1, 2, 3 } is also true, because {0, 1, 2, 3 } = {0, 1, 2, 3 }. A countable set is a set with the same cardinality (number of elements) as some subset of natural numbers.
Be familiar with the set operations: membership union intersection difference.	The set difference A\B (or alternatively A-B) is defined by A\B = {x : x ∈ A and x ∉ B}

Content

Additional information

Be familiar with the concept of a set and the following notations for specifying a set:

A = {1, 2, 3, 4, 5 }

or set comprehension:

A = {x | x ∈ ℕ ∧ x ≥ 1 }

where A is the set consisting of those objects x such that x ∈ ℕ and x ≥ 1 is true.

Know that the empty set, {}, is the set with no elements.

Know that an alternative symbol for the empty set is Ø.

A set is an unordered collection of values in which each value occurs at most once.

Several languages support set construction.

In Python, for example, use of curly braces constructs a set:

{1, 2, 3 }.

| means such that.

x ∈ ℕ means that x is a member of the set ℕ consisting of the natural numbers, ie {0, 1, 2, 3, 4, … }.

The symbol ∧ means AND.

The term ∧ x > = 1 means AND x is greater than or equal to 1.

In Python, {2 ∗ x for x in {1, 2, 3 }} constructs {2, 4, 6 }.

This is said to be a set comprehension over the set {1, 2, 3 } .

Be familiar with the compact representation of a set, for example, the set {0ⁿ1ⁿ | n ≥ 1}. This set contains all strings with an equal number of 0 s and 1s.

For example,

{0ⁿ1ⁿ | n ≥ 1} = {01, 0011, 000111, 00001111, … }

Be familiar with the concept of:

finite sets
infinite sets
countably infinite sets
cardinality of a finite set
Cartesian product of sets.

A finite set is one whose elements can be counted off by natural numbers up to a particular number, for example as:

1st element, 2nd element, …, 20th (and final) element.

The set of natural numbers, ℕ and the set of real numbers, ℝ are examples of infinite sets.

A countably infinite set is one that can be counted off by the natural numbers.

The set of real numbers is not countable. The cardinality of a finite set is the number of elements in a set. Cartesian product of two sets, X and Y, written X x Y and read 'X cross Y', is the set of all ordered pairs (a, b) where a is a member of A and b is a member of B.

Be familiar with the meaning of the term:

subset
proper subset
countable set.

{0, 1 , 2 } ⊂ ℕ where ⊂ means proper subset of, that is ℕ contains everything in {0, 1, 2 } but there is at least one element in ℕ that is not in {0, 1, 2 }.

{0, 1 , 2 } ⊆ {0, 1, 2, 3 } where ⊆ means subset of.

⊆ includes both ⊂ and =, for example

{0, 1, 2, 3 } ⊆ {0, 1, 2, 3 } is also true, because

{0, 1, 2, 3 } = {0, 1, 2, 3 }. A countable set is a set with the same cardinality (number of elements) as some subset of natural numbers.

Be familiar with the set operations:

membership
union
intersection
difference.

The set difference A\B (or alternatively A-B) is defined by A\B = {x : x ∈ A and x ∉ B}

Regular expressions

Content	Additional information
Know that a regular expression is simply a way of describing a set and that regular expressions allow particular types of languages to be described in a convenient shorthand notation.	For example, the regular expression a(a\|b)* generates the set of strings {a, aa, ab, aaa, aab, aba, …}.
Be able to form and use simple regular expressions for string manipulation and matching.	Students should be familiar with the metacharacters: * (0 or more repetitions) + (1 or more repetitions) ? (0 or 1 repetitions, ie optional) \| (alternation, ie or) ( ) to group regular expressions. Any other metacharacters used in an exam question will be explained as part of the question.
Be able to describe the relationship between regular expressions and FSMs.	Regular expressions and FSMs are equivalent ways of defining a regular language.
Be able to write a regular expression to recognise the same language as a given FSM and vice versa.	A student's ability to write very simple regular expressions and FSMs will be assessed.

Regular language

Content	Additional information
Know that a language is called regular if it can be represented by a regular expression.	Also, a regular language is any language that a FSM will accept.

Context-free languages

Backus-Naur Form (BNF)/syntax diagrams

Content	Additional information
Be able to check language syntax by referring to BNF or syntax diagrams and formulate simple production rules.
Be able to explain why BNF can represent some languages that cannot be represented using regular expressions.

Classification of algorithms

Comparing algorithms

Content	Additional information
Understand that algorithms can be compared by expressing their complexity as a function relative to the size of the problem. Understand that the size of the problem is the key issue.
Understand that some algorithms are more efficient: time-wise than other algorithms space-wise than other algorithms.	Efficiently implementing automated abstractions means designing data models and algorithms to run quickly while taking up the minimal amount of resources such as memory.

Maths for understanding Big-0 notation

Content	Additional information
Be familiar with the mathematical concept of a function as a mapping from one set of values, the domain, to another set of values, drawn from the co-domain, for example ℕ → ℕ.
Be familiar with the concept of: a linear function, for example y = 2x a polynomial function, for example y = 2x² an exponential function, for example y = 2^x a logarithmic function, for example y = log₁₀ x.
Be familiar with the notion of permutation of a set of objects or values, for example, the letters of a word and that the number of permutations of n distinct objects is n factorial (n!).	n! is the product of all positive integers less than or equal to n.

Content

Additional information

Be familiar with the mathematical concept of a function as a mapping from one set of values, the domain, to another set of values, drawn from the co-domain, for example ℕ → ℕ.

Be familiar with the concept of:

a linear function, for example y = 2x
a polynomial function, for example y = 2x²
an exponential function, for example y = 2^x
a logarithmic function, for example
y = log₁₀ x.

Be familiar with the notion of permutation of a set of objects or values, for example, the letters of a word and that the number of permutations of n distinct objects is n factorial (n!).

n! is the product of all positive integers less than or equal to n.

Order of complexity

Content	Additional information
Be familiar with Big-O notation to express time complexity and be able to apply it to cases where the running time requirements of the algorithm grow in: constant time logarithmic time linear time polynomial time exponential time.
Be able to derive the time complexity of an algorithm.

Content

Additional information

Be familiar with Big-O notation to express time complexity and be able to apply it to cases where the running time requirements of the algorithm grow in:

constant time
logarithmic time
linear time
polynomial time
exponential time.

Be able to derive the time complexity of an algorithm.

Limits of computation

Content	Additional information
Be aware that algorithmic complexity and hardware impose limits on what can be computed.

Classification of algorithmic problems

Content	Additional information
Know that algorithms may be classified as being either: tractable - problems that have a polynomial (or less) time solution are called tractable problems. intractable - problems that have no polynomial (or less) time solution are called intractable problems.	Heuristic methods are often used when tackling intractable problems.

Content

Additional information

Know that algorithms may be classified as being either:

tractable - problems that have a polynomial (or less) time solution are called tractable problems.
intractable - problems that have no polynomial (or less) time solution are called intractable problems.

Heuristic methods are often used when tackling intractable problems.

Computable and non-computable problems

Content	Additional information
Be aware that some problems cannot be solved algorithmically.

Halting problem

Content	Additional information
Describe the Halting problem (but not prove it), that is the unsolvable problem of determining whether any program will eventually stop if given particular input.
Understand the significance of the Halting problem for computation.	The Halting problem demonstrates that there are some problems that cannot be solved by a computer.

A model of computation

Turing machine

Content	Additional information
Be familiar with the structure and use of Turing machines that perform simple computations.
Know that a Turing machine can be viewed as a computer with a single fixed program, expressed using: a finite set of states in a state transition diagram a finite alphabet of symbols an infinite tape with marked-off squares a sensing read-write head that can travel along the tape, one square at a time. One of the states is called a start state and states that have no outgoing transitions are called halting states.	Exam questions will only be asked about Turing machines that have one tape that is infinite in one direction.
Understand the equivalence between a transition function and a state transition diagram.
Be able to: represent transition rules using a transition function represent transition rules using a state transition diagram hand-trace simple Turing machines.
Be able to explain the importance of Turing machines and the Universal Turing machine to the subject of computation.	Turing machines provide a (general/formal) model of computation and provide a definition of what is computable.

Previous
4.3 Fundamentals of algorithms

Next
4.5 Fundamentals of data representation