Topic 4 - Theory of computation

Abstraction

Removing unnecessary details from a problem

Representational abstraction

A representation of a problem arrived at by removing unnecessary details from the problem

Abstraction by generalisation/categorisation

A grouping by common characteristics to arrive at a hierarchical relationship

Decomposition

Dividing a problem into a series of smaller sub-problems

Composition

Combining procedures to form a larger system

Automation

The process of putting abstractions of real world phenomena into action to solve problems

Set

An abstract data type that contains unique unordered values

Regular expressions: *

0 or more repetitions

Regular expressions: +

1 or more repititions

Regular expressions: ?

Optional character

Regular expressions: |

A choice between 2 things

Regular expressions: ()

Used to group regular expressions

Context free language

A set of strings and symbols that follow the rules of a context-free grammar

Backaus Naur form (BNF)

A way of notating context-free languages

Write a BNF for Integer that can contain either a digit or a digit followed by an integer, where a digit can be between 0-9

<Integer> ::= <Digit> | <Digit><Integer>
<Digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Big O notation - Constant

O(C)

Big O notation - Logarithmic

O(log2(n))

Big O notation - Linear

O(n)

Big O notation - Linear logarithmic

O(nlog(n))

Big O notation - polynomial

O(n^2) / O(n^3)

Big O notation - Exponential

O(2^n)

Big O notation - Factorial

O(n!)

Turing Machine

A formal model of computation that consists of a finite state machine, a read/write head, and an infinitely long tape

Transition functions

The way rules that a turing machine follows can be laid out

Universal Turing machines

Turing machines that are capable of representing any finite state machine