4 Theory of computation

Representational abstraction

A representation of a problem arrived at by removing unnecessary details.

Abstraction by generalisation / categorisation

Simplifying a problem by grouping together common characteristics to arrive at a hierarchical / "is a kind of" relationship.

Information hiding

The process of hiding all details of an object that do not contribute to its essential characteristics.

Procedural decomposition

Breaking a problem into smaller sub-problems; each of which solves an identifiable task; and each of which might be further subdivided.

When is an adjacency matrix more appropriate than an adjacency list? (3)

• When there are many edges between vertices (the graph is not sparse)

• when edges are frequently changed

• when the presence/absence of specific edges needs to be tested frequently.

Set Cardinality

The number of elements/items in a set.

What is the difference between a subset and a proper subset?

A set is a subset of itself, but not a proper subset. A proper subset must have at least one value missing from the original set.

Regular expression '*' (Asterisk)

Zero or more repetitions of the preceding element/character.

Regular expression '?' (Question mark)

Zero or one repetitions of the preceding element/character (makes the preceding element optional).

Regular expression '|' (Pipe)

Alternation. It means either the element immediately before or the element immediately after.

Regular expression '+' (Plus)

One or more repetitions of the preceding element/character.

What is the relationship between Regular Languages and Finite State Machines (FSMs)?

All regular languages can be represented using a finite state machine without outputs.

Can all languages be represented by Regular Expressions?

No. Regular expression cannot express nested recursion.

Why is recursion used in Backus-Naur Form (BNF)?

Because BNF does not natively support iteration. Recursion allows a non-terminal to be defined in terms of itself to represent sequences of indefinite length.

Tractable problem

A problem that can be solved algorithmically in polynomial time (or less).

Intractable problem

A problem that can be solved, but cannot be solved in polynomial time. It takes an unreasonable amount of time to solve.

Heuristic approach

The use of experience/approximation to make a guess. It provides a close-to-optimal solution when an exact solution takes an unreasonable amount of time to calculate.

What is the Halting Problem?

The unsolvable problem of determining whether any given program will eventually stop (halt) for a particular input.

What is the significance of the Halting Problem?

It demonstrates that there are some well-defined problems that cannot be solved by a computer / cannot be solved algorithmically.

Time Complexity: Linear Search

O(n)

Time Complexity: Binary Search

O(log n)

Time Complexity: Merge Sort

O(n log n)

Time Complexity: Bubble Sort

O(n^2)

What does it mean if an algorithm is O(n)?

As the size of the input increases, the time taken to execute the algorithm increases at the same rate (directly proportional).

Turing Machine

A formal model of computation consisting of a finite state machine, a read/write head, and a tape that is infinitely long in one direction.

Universal Turing Machine (UTM)

A Turing machine that can execute/simulate the behaviour of any other arbitrary Turing machine.

How does a Universal Turing Machine (UTM) work?

The description/instructions for the Turing Machine (and its input) are stored on the tape. The UTM reads this description and acts as an interpreter.

Why is the tape of a Turing Machine conceptually important?

It provides the machine with an infinite amount of memory.

What is the overall significance of Turing Machines?

They provide a formal model of computation and a definition of what is computable. They prove that there are problems which cannot be solved by computers.

Algorithm

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

Procedural abstraction

Simplifying a problem by breaking it down into a series of procedures/subroutines. The actual values used in a computation are abstracted away.

Functional abstraction

Disregarding the particular computation method. The result of a procedural abstraction is a procedure; abstracting further results in just a function.

Data abstraction

Hiding the specific details of how data is actually represented, allowing new kinds of abstract data types to be created from previously defined data structures.

Problem abstraction / reduction

Removing details from a problem until it is represented in a way that is identical to a previously solved problem.

Composition abstraction

Combining procedures to form compound procedures, or combining data objects to form compound data structures.

Automation

The process of putting abstractions of real-world phenomena (models) into action to solve problems by creating algorithms, implementing them in code/data structures, and executing them.

Mealy Machine

A type of finite state machine (FSM) that determines its outputs from both the present state and the current inputs.

Countably infinite set

A set that can be counted off by the natural numbers (i.e., it has the same cardinality as some subset of the natural numbers).

Non-countable set

A set that contains a larger infinity of numbers than the natural numbers, such as the real numbers.

Cartesian product of sets

The set of all ordered pairs (a, b) where 'a' is a member of the first set (A) and 'b' is a member of the second set (B). Written as X x Y.

Set Comprehension

The creation of a set by mathematically defining the rules/elements that qualify to be in the set, rather than listing out all its elements individually.

Set Union (∪)

An operator that produces a set containing all the elements present in both initial operand sets (with duplicates removed).

Set Intersection (∩)

An operator that produces a set containing only the elements that are present in both initial operand sets.

Set Difference (A \ B or A - B)

An operator that produces a set containing items exclusive to one set (e.g., elements in A that are not in B).

Time Complexity

A measure of the amount of time needed by an algorithm to solve a particular problem of a given input size.

Space Complexity

A measure of the amount of memory space needed by an algorithm to solve a particular problem of a given input size.

O(1)

Constant time/space complexity: The algorithm takes the same amount of time/memory regardless of the input size.

O(2^n)

Exponential time complexity: The execution time doubles with each addition to the input data set. An intractable complexity.

O(n!)

Factorial time complexity: The execution time grows by a multiple of the input size. An intractable complexity (e.g., the Travelling Salesman problem).

Transition Function

A function that determines how a Turing Machine moves from one state to another. Written in the format: δ(current state, read) = (new state, write, move).