Topic 4 - Theory of computation - Complete

Question 1

Define top-down design? (Stepwise refinement)

Answer 1

Is used to plan a solution based on a top-down strategy.

Breaking down the problem into smaller steps.

Question 2

4 advantages of top-down design?

Answer 2

• Breaking problem into parts helps clarify what needs to be achieved.
• Each stage creates smaller sub-problems, so easier to solve.
• Some functions or parts of the solution might be reusable.
• Breaking a design into parts allows more than one person to work on the solution.

Question 3

Define an algorithm?

Answer 3

Is a step-by-step approach to solving a problem.

Written in pseudocode.

Question 4

Define abstraction?

Answer 4

Is the process of including only the important features when solving a problem.

This reduces the complexity of the system by removing unnecessary details.

Question 5

Define representational abstraction?

Answer 5

Is where all unnecessary details are removed, leaving only the information required to solve the problem.

Question 6

Define generalisation abstraction?

Answer 6

Is where a problem is simplified by grouping similar parts into a hierarchal structure.

Question 7

Define information hiding?

Answer 7

Is the principle that the details of the implementation of a class or software component are hidden or not accessible by the user.

Question 8

Define procedural abstraction?

Answer 8

Are large programs are written by breaking them into smaller subprograms, this approach applies to all languages.

Question 9

Define functional abstraction?

Answer 9

The exact computational method used is hidden, unlike procedural abstraction, the use of built-in or library functions is an example of functional abstraction.

Question 10

Define data abstraction?

Answer 10

Is where the details of how a compound data object is constructed are isolated from how the data object is used.

Therefore, the primitive data objects that make up a user-defined data structure are hidden from the user.

Question 11

Define problem abstraction?

Answer 11

Is where the details of the problem are successively removed or reduced until the problem is represented in a way that is straightforward to solve.

Once the unnecessary details are removed, the problem can be more clearly identified.

Question 12

Define procedural decomposition?

Answer 12

is the process of breaking down a problem into a series of sub-problems, where each sub-problem archives an identifiable task.

Question 13

Define composition?

Answer 13

Is the process of creating a system by combining the tasks identified in the decomposition abstraction.

Is the opposite of decomposition

Question 14

3 step process of composition?

Answer 14

• Writing procedures for each of the tasks and sub-tasks identified in the decomposition.
• Linking these procedures to create compound procedures.
• Creating the necessary data structures to support the compound procedures.

Question 15

Define composition abstraction?

Answer 15

Compound procedures can be created by combining other procedures to be built.

Compound data objects can be created by combining data primitive objects of programming language to build a data abstraction.

Question 16

State the processes of automation?

Answer 16

• Creation of algorithms
• Implementing the algorithms in program code
• Implementing the models in data structures
• Executing the code

Question 17

Define finite state machine (FSM)?

Answer 17

Is an abstract machine that can be in any one of a finite number of states. FSM’s can only be in one state at a time and a transition to a new state is triggered by an event.

Question 18

Define state transition diagrams?

Answer 18

Are used to describe an FSM in a graphical format, where each state is shown as a circle and each transition is connected to a circle by an arrowed line with a description of the input that causes the transition.

Question 19

Define state transition tables?

Answer 19

Are a method used to record all the sates and transition possible from finite state machine.

Question 20

Define decision ables?

Answer 20

Can be used to model logic sequences in a compact way.

Question 21

Define Mealy machine?

Answer 21

Is a finite state machine with outputs.

The output from a mealy machine is determined by its present state as well as its present input.

Question 22

Define a set?

Answer 22

A collection of elements - such as objects or numbers, each element is unique within the set.

Question 23

What would set A and B look like?

Answer 23

A = {1,2,3,4,5,6}
B = {-1,1,3,5,7,9}

Question 24

What does the set comprehension to define a set look like?

Answer 24

B = { x | x ∊ N ^ n < 5 }
- The vertical bar | 	means “such that”
- The ∊ symbol indicates membership so x ∊ N is 
   read as “x belongs to N”
- The ^ symbol means “and”

Question 25

Define finite set?

Answer 25

Is a set with a finite number of elements, the number of elements of a finite set is a natural number.

{1,2,3,4,5,6}

Question 26

Define cardinality?

Answer 26

Is the number of elements in a list

{1,2,3,4,5,6} = cardinality of 6
{} = cardinality of 0

Question 27

Define infinite set?

Answer 27

A set of infinite elements, examples include integers (Z), natural numbers (N) and real numbers (R).

Maybe countable or uncountable.

Question 28

Define Cartesian product of two sets?

Answer 28

The Cartesian set contains an infinite number of elements, which cannot be mapped one-to-one to the set of natural numbers. The set of real numbers (R) is an infinite uncountable set.

Question 29

Define subset?

Answer 29

is a set where all the elements of one set are elements of another set. A ⊆ B

A = {1,2,4,6}
B = {4,6,1,2}

Question 30

Define proper set?

Answer 30

Is a set that does not include all the elements of the set to which it belongs. A ⊂ B

A = {1,2,4,6}
B = {4,6,1,2,9,13}

Question 31

What are the 4 set operations used to define the relationship between two or more sets?

Answer 31

• Membership
• Union
• Intersection
• Difference

Question 32

Define membership?

Answer 32

Is a set operation used to check whether an element is a member of a particular set.

Question 33

Define Union?

Answer 33

Union of two sets is the set that contains all the elements of these sets.

Union of A U B:
A = {1,2,4,6} B = {1,4,8,9,13}
A U B = {1,2,4,6,8,9,13}

Question 34

Define Intersection?

Answer 34

The intersection of two sets is the set that contains only the elements which are in both sets.

Intersection of A ⋂ B:
A = {1,2,4,6} B = {1,4,8,9,13}
A ⋂ B = {1,4}

Question 35

Define difference?

Answer 35

The difference of two sets A - B is the set that contains all the elements of A that are not in B.

Difference of A - B:
A = {1,2,4,6} B = {1,4,8,9,13}
A - B = {2,6}

Question 36

Define a regular expression?

Answer 36

Is a notation used to describe a pattern of characters in an object or a set.

Question 37

What are the 5 regular expression rules using a & b?

a - pattern matches the string ‘a’.
b - pattern matches the string ‘b’.

Answer 37

ab - Concatenation where the pattern matches the string ‘a’ followed by ‘b’.
a+ - Pattern matches one or more ‘a’. {a, aa, aaa}
a* - Pattern matches zero or more ‘a’. {0, a, aa, aaa}
ab?c - Matches the preceding character one or zero times. {ac, abc}
a|b - Pattern matches symbol ‘a’ or ‘b’

Question 38

What is the order for regular expression notation?

() + ? | *

Answer 38

(), *, +, ?, |

Question 39

Define regular language?

Answer 39

Is a formal language that can be represented by regular expressions, it is a language that is acceptable for use by an FSM.

Question 40

Define context-free language?

Answer 40

is a formal system that is used to describe a language where the syntax is complex.

Have an infinite range of components, they are used in parsing and logical syntactic analysis.

Question 41

Define Backus-Naur form (BNF)?

Answer 41

Is a notation that is used to describe the syntax or grammar used within a programming language.

BNF functions use recursive techniques as there is no method available for the program to loop or repeat.

Question 42

What are the 5 notations for BNF?
Syntax elements
<>
\::=
|
[]
{}

Answer 42

<> - Enclose a synactic element.
::= - Indicate the definition of a syntactic element.
| - Symbol indicates an OR choice between two syntactic elements.
[] - Enclose an optional part of the rule.
{} - Enclose a content that can be repeated any number of times.

Question 43

Heres some examples of BNF.

Answer 43

::= |

::= 0|1|2|3|4|5|6|7|8|9

Question 44

Define syntax diagrams?

Answer 44

Are used to give a representation of context-free language, they can be used to display BNF syntax and rules by an alternative graphical method.

Question 45

What 2 factors determine the efficiency of an algorithm?

Answer 45

Time complexity - the amount of time taken to process the task.

Space capacity - the amount of memory or space that is used to process the task.

Question 46

Define Big-O notation?

Answer 46

Used to determine the time complexity or run-time of the code as the volume of input data increases.

Input size (N) of the algorithm is used in Big-O notation.

Constant, linear, polynomial, exponential, logarithmic

Question 47

What are the 6 notations for Big-O notation?

Answer 47

O(1)
O(LogN)
O(N)
O(N LogN)
O(N^K)
O(K^N)

Question 48

Define tractable?

Answer 48

Problems can be solved in a reasonable time frame, they have a polynomial-time solution that can be solved practically using a computer.

Question 49

Define intractable?

Answer 49

Problems cannot be solved in a reasonable time frame, they do not have a polynomial-time solution and so cannot be solved practically using a computer.

Question 50

Define heuristics?

Answer 50

Is a technique designed to solve a problem based on experience or an ‘educated guess’,
It may not produce an exact solution but are used to tackle intractable problems.

Question 51

Define computable?

Answer 51

Computable problems are problems that have an effective procedure or algorithm to solve them.

A program containing a finite set of instructions is executed to determine the correct output for a given input.

Question 52

Define non-computable?

Answer 52

Noon-computable problems are problems that have no effective procedure or algorithm to solve them.

These problems are unsolved irrespective of the amount of computer power available or the time allocated to solve them.

Question 53

Define halting problem?

Answer 53

Is used to determine whether it is possible to create a program to determine whether a program given an associated input will halt when executed with that input or will it continue forever.

Question 54

Define the Turing machine?

Answer 54

Is a machine that controls an infinitely long read/write tape which can be used as an input device, and an infinitely long storage device.

Question 55

What does the start and halt state on the Turing machine do?

Answer 55

Start - Start state is the initial state of a Turing machine.
Halt - Halt state is the point at which a Turing machine stops processing

Question 56

Define transition function for the Turing machine?

Answer 56

Is a set of rules to indicate how a Turing machine moves between states and how the related tape data changes.

Question 57

Define a universal machine?

Answer 57

Is a machine that simulates a Turing machine by reading a description of the functionality of the machine and the inputs associated with it.

It combines a range of individual machines, allowing the option to perform complex calculations.