Theory of Computation

Question 1

Problem solving

Answer 1

The process of finding a solution to a difficult or complex issue

Question 2

Algorithms

Answer 2

• A sequence of steps that can be followed to complete a task
• They always terminate rather than going on forever in a loop

Question 3

Assignment

Answer 3

The process of giving a value to a variable or constant

Question 4

Sequence

Answer 4

Instruction that are executed sequentially

Question 5

Selection

Answer 5

The process of choosing an action to take based on the result of a comparison of values

Question 6

Iteration

Answer 6

The process of repeating an operation

Question 7

Abstraction

Answer 7

The name given to omitting unnecessary details from a problem, simplifying the solution

Question 8

Representational abstraction

Answer 8

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

Question 9

Abstraction by generalisation

Answer 9

A grouping by common characteristics to arrive at a hierarchical relationship of the
“is a kind of” type

Question 10

Information hiding

Answer 10

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

Question 11

Procedural abstraction

Answer 11

• Breaking down a complex model into a series of reusable procedures
• The actual values used are abstracted away to achieve a computational method

Question 12

Functional abstraction

Answer 12

Abstracting the result of procedural abstraction, disregarding the particular method to leave just a function

Question 13

Data abstraction

Answer 13

Specifies details of how data is actually represented, allowing for new kinds of data structures to be created

Question 14

Problem abstraction

Answer 14

Details are removed from a problem until it is represented in a way that is solvable

Question 15

Decomposition

Answer 15

A problem is divided into a series of smaller sub-problems that can be solved individually or further divided

Question 16

Composition

Answer 16

Used to combine procedures to form a larger system

Question 17

Automation

Answer 17

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

Question 18

Set

Answer 18

An abstract data type that contains unordered, unique values (that can be other sets)

Question 19

Set comprehension

Answer 19

An alternative way of creating a set that selects the kind of values it wants from a larger set, instead of specifying each item individually

Question 20

Empty sets

Answer 20

Sets that contain 0 elements. A = {}

Question 21

Finite sets

Answer 21

A set with a limited number of elements

Question 22

Infinite sets

Answer 22

A set with an unlimited number of elements

Question 23

Countably infinite sets

Answer 23

An infinite set where you can list the elements in a sequence

Question 24

Uncountably infinite sets

Answer 24

An infinite set where the elements cannot be listed in a sequence

Question 25

Subset

Answer 25

Set A is a subset of Set B if it only contains items from Set B

Question 26

Proper subset

Answer 26

Set A is a proper subset of set B if it only contains items from set B, but not all of them

Question 27

Countable sets

Answer 27

Sets that have the same cardinality as some subset of natural numbers

Question 28

Union

Answer 28

The union of two sets is the set of all elements that are in either set or in both

Question 29

Intersection

Answer 29

The intersection of two sets is the set of elements that are presented in both sets

Question 30

Difference

Answer 30

The difference of two sets is the set of elements that are in the first set but not in the second

Question 31

Regular expressions

Answer 31

Shorthand ways of describing sets

Question 32

*

Answer 32

0 or more repetitions

Question 33

+

Answer 33

1 or more repetitions

Question 34

?

Answer 34

Previous character is optional

Question 35

|

Answer 35

Or

Question 36

()

Answer 36

Used to group regular expressions

Question 37

Context free languages

Answer 37

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

Question 38

Context-free grammar

Answer 38

Production rules that describe which strings are and are not possible

Question 39

Backus-Naur form

Answer 39

A context-free language where the left hand side is defined by the right hand side

Question 40

Non-terminals

Answer 40

Text placed inside <>

Question 41

Terminals

Answer 41

- Text without any brackets - Cannot be broken down any further

Question 42

Recursion in Backus-Naur form

Answer 42

A non-terminal can be defined in terms of itself, allowing for recursion to occur

Question 43

Syntax diagrams

Answer 43

- A visual representation of a regular language - Non-terminals are represented by rectangles - Terminals are represented by ellipses - The shapes are joined by arrows which indicate how strings can be formed from the definitions

Question 44

Big O notation

Answer 44

Defines the time complexity of an algorithm

Question 45

Constant time

Answer 45

- O(C) - Time is independent of input

Question 46

Logarithmic time

Answer 46

- O(log2(n)) - Halves the number of items each iteration

Question 47

Linear time

Answer 47

- O(n) - In a worst case scenario must go through each item once

Question 48

Polynomial

Answer 48

- O(n^2) - A loop inside a loop

Question 49

Exponential

Answer 49

- O(n^3) - Intractable

Question 50

Factorial

Answer 50

- O(n!) - Intractable

Question 51

Intractable problems

Answer 51

They are theoretically solvable but cannot be solved within a useful amount of time

Question 52

Tractable problems

Answer 52

A problem can be solved within a useful period of time

Question 53

Turing machines

Answer 53

Formal models of computation that consist of: - a FSM - a read/write head - an infinitely long tape consisting of cells that can be blank or contain a symbol They must have a single start state and a number of halting states

Question 54

Alphabet

Answer 54

- The set of symbols used - It must be finite with a Turing machine

Question 55

Transition functions

Answer 55

- Used to define the rules followed by Turing machines - Have an equivalence with transition rules in a state transition diagram - Written in the form: δ(current state, read) = (new state, write, move)

Question 56

Universal Turing Machines

Answer 56

- Can represent any finite state machine - Read a description of a finite state machine from the same tape as the input data - They read their instructions in sequence before executing operations

Question 57

Importance of Turing machines

Answer 57

- Turing machines provide a definition of what is computable - Turing machines can be used to prove that there are problems which cannot be solved by computers