4.4 - Theory of computation

Question 1

What is information hiding?

Answer 1

Information hiding is part of abstraction, it involves removing unnecessary information which isn’t relevant to the current problem.

Question 2

What is procedural abstraction?

Answer 2

A type of abstraction applied in programming where you take a procedure and remove parts of it so that the procedure is more generalized, it can then be used in multiple scenarios instead of just one.

Question 3

What is functional abstraction?

Answer 3

A type of abstraction applied in programming in which functions are separated from the main working program, meaning you don’t need to know how a function works to be able to use it, you give the function the required inputs and it returns the outputs.

Question 4

What is problem/representational abstraction?

Answer 4

Problem abstraction is applied by breaking down a problem and using information hiding and decomposition to remove unnecessary data from the problem which makes it easier to solve.

Question 5

Examples of problem abstraction?

Answer 5

For example finding the shortest path for a data packet, you won’t need to know the type of cable, if the cable is in the sea or land…

Question 6

What is decomposition?

Answer 6

Decomposition is the first step of problem abstraction, taking a problem and breaking it down into smaller parts to allow you to solve each part individually or decide if it is necessary to solve.

Question 7

What is composition?

Answer 7

This is the process of building the solution from the individually solved parts to create a full solution to a certain problem.

Question 8

Example of a problem where abstraction can be applied?

Question 9

What is automation?

Answer 9

The process of modelling a problem to predict future changes.

Question 10

Example of automation?

Answer 10

You can create a model to predict climate change by modelling the rate of C02 increase in the atmosphere.

Question 11

What are the metacharacters in regular expression and what do they mean?

Answer 11

• (0 or more repetitions)
  + (1 or more repetitions)
  ? (0 or 1 repetitions)
  | (or)
  ( ) to group regular expressions

Question 12

How is regular expression and FSM related?

Answer 12

Regular expressions and FSMs are equivalent ways of defining a regular language.

Question 13

How is Backus-Naur form represented?

Answer 13

<digit> -> 0|1|2|3|4|5|6|7|8|9
<natural> -> <digit>|<digit><natural>

This represents any natural number, where a digit is defined by the numbers 0-9 and it uses recursion to represent any length of these digits.
</natural></digit></digit></natural></digit>

Question 14

What is a tractable problem?

Answer 14

Problems that have a polynomial (or less) time solution.

Question 15

What is an intractable problem?

Answer 15

Problems that do not have a polynomial (or less) time solution. Heuristic techniques are used to solve these problems.

Question 16

What is the halting problem?

Answer 16

This states that there are some problems that cannot be solved by a computer.

Question 17

What is a set?

Answer 17

A set is an unordered collection of values with no duplicates.

Question 18

Difference between a proper subset and a non-proper subset?

Answer 18

Proper subset means items in one set are all part of the original set but not all of the values e.g {0, 1, 2, 3} is a subset of {0, 1, 2, 3, 4}. A non-proper subset would be {0, 1, 2, 3} is a subset of {0, 1, 2, 3}

Question 19

What is cardinality of a set?

Answer 19

Cardinality means the number of elements in the set.

Question 20

What is the symbol for difference between two sets?

Answer 20

\ or -

Question 21

What is the symbol for union of two sets?

Answer 21

U

Question 22

What is the symbol for intersection of two sets?

Answer 22

n

Question 23

What is the regular expression symbol for 0 or 1?

Answer 23

?

Question 24

What is the regular expression symbol for 1 or more?

Answer 24

+

Question 25

What is the regular expression symbol for 0 or more?

Answer 25

*

Question 26

What is the regular expression symbol for an altercation (or)?

Answer 26

|

Question 27

What does a double circle mean on an FSM?

Answer 27

Accepting state

Question 28

What steps would you take to solve an intractable problem?

Answer 28

Use a heuristic. Break down the problem/Solve a simpler version of the problem.

Question 29

What is a universal Turing Machine?

Answer 29

A Turing machine which can compute any computable sequence.

Question 30

What is abstraction by generalisation?

Answer 30

Grouping by common characteristics.