4: Theory of Computation

Question 1

Representation Abstraction

Answer 1

A representation arrived at by removing unnecessary details

Question 2

Abstraction by Generalisation or Categorisation

Answer 2

Grouping by common characteristics to arrive at a hierarchal relationship of the ‘is a kind of’ type

Question 3

Information Hiding

Answer 3

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

Question 4

Procedural Abstraction

Answer 4

The result of abstracting away the actual values used in any particular computation is a computational pattern or computational method - a procedure

Question 5

Functional Abstraction

Answer 5

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

Question 6

Data Abstraction

Answer 6

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

Question 7

Problem Abstraction / Reduction

Answer 7

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

Question 8

Decomposition

Answer 8

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

Question 9

Automation

Answer 9

Putting models (abstraction of real-world objects / phenomena) into action to solve problems

Question 10

Finite Set

Answer 10

One whose elements can be counted off by natural numbers up to a particular number

Question 11

Infinite Set

Answer 11

One whose elements cannot be counted off by natural numbers up to a particular number

Question 12

Countably Infinite Set

Answer 12

One that can be counted off by the natural numbers

Question 13

Cardinality of Finite Set

Answer 13

The number of elements in the set

Question 14

Cartesian Product of Sets

Answer 14

X x Y (X cross Y) is the set of all ordered pairs (x, y) where x is a member of X and y is a member of Y

Question 15

Proper Subset

Answer 15

If A ⊂ B then B contains everything in A, but there is at least one element in B that is not in A

Question 16

Subset

Answer 16

⊆ includes both ⊂ and =

Question 17

Countable Set

Answer 17

A set with the same cardinality as some subset of natural numbers

Question 18

Set Difference Operation

Answer 18

A\B = {x : x ∈ A and x ∉ B}

Question 19

Regular Expressions Metacharacters (5)

Answer 19

• * means 0 or more repetitions
• + means 1 or more repetitions
• ? means 0 or 1 repetitions (i.e. optional)
• | means alternation
• () used to group regular expressions

Question 20

Relationship between Regular Expressions & FSMs

Answer 20

They are equivalent ways of defining a regular language

Question 21

Regular Language

Answer 21

A language is regular if it can be represented by a regular expression

Question 22

BNF Production Rules (4)

Answer 22

• Chevrons denote a non-terminal symbol, which has another set of production rules to define it
• Symbols without chevrons are terminal
• The pipe symbol is a metacharacter denoting alternatives
• <fullname> :: =<title> Moloney|<title> Pope
  <title> :: =Mr|Mrs

Question 23

BNF Syntax Diagram for <date> ::= <day-name><month-name>|<day-name><month-name><year>

Answer 23

https://isaaccomputerscience.org/api/v3.4.3/api/images/content/computer_science/computer_systems/translators/figures/isaac_cs_sys_trans_syntax_dgm_dates.svg

Question 24

BNF vs Regular Expressions (3)

Answer 24

• All regular languages are context-free but the reverse is not true
• Any regular expression can be converted to a set of BNF production rules
• As an FSM has a finite number of states, a context-free language is required when an infinite number of elements in a string must be counted

Question 25

Mathematical Concept of a Function

Answer 25

A mapping from one set of values, the domain, to another set of values, drawn from the co-domain

Question 26

Order of Complexity (5)

Answer 26

• Constant time
• Logarithmic time
• Linear time
• Polynomial time
• Exponential time

Question 27

Tractable

Answer 27

Problems that have a polynomial (or less) time solution

Question 28

Intractable

Answer 28

Problems that have no polynomial (or less) time solution

Question 29

Heuristic Methods

Answer 29

Often used when tackling intractable problems

Question 30

Halting Problem

Answer 30

The unsolvable problem of determining whether any program will eventually stop if given particular input

Question 31

Significance of Halting Problem for Computation

Answer 31

The Halting problem demonstrates that there are some problems that cannot be solved by a computer

Question 32

Turing Machine

Answer 32

A computer with a single fixed program

Question 33

Components of Turing Machine (4)

Answer 33

• 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

Question 34

Importance of Turing Machines to Subject of Computation

Answer 34

Turing machines provide a general / formal model of computation and provide a definition of what is computable

Question 35

Universal Turing Machine

Answer 35

A Turing machine that can solve any computable problem where the transition functions as well as the data are stored on the tape