Unit 4

Question 1

Sequence

Answer 1

a control structure in which a set of instructions is executed once in the order that they were written

Question 2

Assignment

Answer 2

giving a variable a value

Question 3

Selection

Answer 3

a control structure in which an option of various statements is provided and a variable is used to decide which statements (if any) are executed

Question 4

Iteration (Repetition)

Answer 4

a control structure in which a group of statements is executed repeatedly until a condition is met

Question 5

definite vs indefinite iteration

Answer 5

definite gets repeated a certain number of times, indefinite until a condition is met

Question 6

Representational Abstraction

Answer 6

a representation arrived at by removing unnecessary details

Question 7

information hiding

Answer 7

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

Question 8

Representational Abstraction

Answer 8

representational abstraction is a representation arrived at by removing unnecessary details (creating a model)

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, used a lot in OOP

Question 10

Procedural Abstraction

Answer 10

Where the particular processes of a computational method is hidden, abstracting it into a procedure

Question 11

Functional abstraction

Answer 11

abstracts it into a function

Question 12

Data abstraction

Answer 12

details of how data are actually represented are hidden, allowing new kinds of data objects

Question 13

Composition abstraction

Answer 13

opposite of Decomposition, usually built by combining procedures to form compound procedures or by combining data objects to form compound data

Question 14

regular expression

Answer 14

a way of describing a set of data or a pattern of data

Question 15

regular language

Answer 15

can be represented by a regular expression

Question 16

Metacharacters

Answer 16

the characters used in regular expression

Question 17

*

Answer 17

0 or more repetitions of the preceding element

Question 18

+

Answer 18

1 or more repetitions of the preceding element

Question 19

?

Answer 19

0 or 1 repetitions of the preceding element

Question 20

|

Answer 20

or for regular expressions

Question 21

Backus-Naur Form

Answer 21

somewhat like regular expression but recursive, make statement to say it can be +|-

Question 22

Tractable

Answer 22

problems that have a polynomial (or less) time solution are called tractable problems

Question 23

Intractable

Answer 23

problems that can be solved BUT have no polynomial (or less) time solution are called intractable problems; the solution is exponential time or worse

Question 24

Heuristic methods

Answer 24

are often used when tackling intractable problems

Question 25

Non-computable

Answer 25

problems are not able to be solved

Question 26

heuristic method

Answer 26

produces a solution in a reasonable time frame that is good enough for solving the problem at hand

Question 27

Travelling Salesman Problem

Answer 27

intractable

Question 28

Halting Problem

Answer 28

non-computable

Question 29

turing machine main points

Answer 29

has a starting and stopping state, infinite memory, a processor with read/write head, cells with symbols in it that are part of the alphabet of the machine, a single fixed program with state transition rules and usually indication of current state for ex in a state register

Question 30

transition function turing machine

Answer 30

δ (Current State, Input Symbol) = (Next State, Output Symbol, Movement)