theory of computation (FSMs and problem solving)

Question 1

What is an algorithm?

Answer 1

• A sequence of steps that can be followed to complete a task
• always terminate rather than looping

Question 2

Pseudo code selection

Answer 2

IF name = ‘Emma’ THEN
—- OUTPUT ‘Hello Emma’

key points:
* single equals
* most functions are in caps

Question 3

Iteration in pseudo code

Answer 3

FOR number ← 6 to 12
———OUTPUT number / 2
END FOR

WHILE number < 18
———-Number ← number + (number / 4)
END WHILE

Question 4

What is abstraction?

Answer 4

• Getting rid of unnecessary detail from a problem, making it easier to solve

represental abstraction:
removing unneccesary details
generalisation/categorisation:
grouping by common characteristics

Question 5

Information hiding

Answer 5

• Hiding all details of an object that do not form its main features
• simplifies a problem without changing the essence of it

Question 6

Functional abstraction

Question 7

Procedural abstraction

Question 8

Data abstraction

Question 9

Problem abstraction/ reduction

Question 10

Decomposition

Question 11

Composition

Question 12

Automation

Question 13

Finite state machines: what are they, rules they follow

Answer 13

• Always in a fixed state
• Have a finite number of states
• Can only ever be in one state
• State changes based on current state and input data

Question 14

State transition diagrams: what are, rules they follow

Answer 14

• Visual representation of a finite state machine
• Have states (circles) joined by transitions (arrows)
• Have a start state (indicated w leading arrow)
• Have an accepting state (double circle)
• Transition functions shown as an arrow between states

Question 15

State transition tables

Answer 15

Columns usually hold current state, input and next state