TOPIC 4 MAIN

Abstraction by generalisation

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

(Procedural) Decomposition

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.

Explain the functionality of the * metacharacter when it is used in a regular expression.

Zero or more

Explain the functionality of the ? metacharacter when it is used in a regular expression

Zero or one

Explain the difference between a subset and a proper subset.

A set is a subset of itself but not a proper subset of itself; There will be at least one value in a set that is not in a proper subset of that set

Cardinality of a finite set

The cardinality of a finite set is the number of elements in a set.

Explain the functionality of the | (vertical bar) metacharacter when it is used in a regular expression.

OR

Universal Turing machine

A universal Turing machine can simulate any other Turing machine

The UTM acts as an interpreter

State one reason why there are some problems that no real computer can solve that the Universal Turing Machine could solve.

It has an infinite amount of memory

Non-terminal (BNF)

An item enclosed in angle brackets in Backus–Naur form;

it can be replaced using production rules

Terminal (BNF)

An item in Backus–Naur form that cannot be broken down further

Why can BNF can represent more than regular expressions?

BNF supports recursion, so it can represent some languages regular expressions cannot

Three primary components of a Turing machine

Read/write head; Finite state machine; Infinite tape

What name is given to the set of symbols that a Turing machine can recognise?

Alphabet

What is the importance of Turing machines on the subject of computation?

Turing machines prove that there are problems which cannot be solved by computers.

Information hiding

Information hiding is the principle of hiding an actual implementation of a module and allowing access through a known interface. Or hiding all the details of an object that do not contribute to its essential characteristics.

Procedural abstraction

The result of abstracting away the actual values used in any particular computation, is a computational pattern or method (is the general method used to solve it) – a procedure.

Functional abstraction

A further level of abstraction, which disregards the particular computation method, which is hidden. We know what a function should do but we have abstracted (hidden) the implementation.

Data abstraction

Data abstraction is a methodology that enables us to isolate how a compound data object is used from the details of how it is constructed. For example, a stack could be implemented as an array and a pointer for top of stack.

Problem abstraction

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.

Composition abstraction

A composition abstraction is built by combining procedures to form compound procedures or combining data objects to form compound data (for example, a tree data structure).

Automation

Automation requires putting models (abstraction of real world objects/phenomena) into action to solve problems.

This is achieved by:

creating algorithms;

implementing the algorithms in program code (instructions);

implementing the models in data structures;

executing the code.

Empty set (symbols)

The empty set is {} and an alternative symbol is Ø

Set difference

The difference of two sets is those elements that belong in the first set but not in the second.

Countably infinite set

A countably infinite set is one that can be counted off by the natural numbers.

Regular expression + metacharacter

• means “one or more repetitions”

Regular language

A language that can be defined by the use of a regular expression.

A regular language is any language that a finite state machine (FSM) will accept.

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

Regular expression and FSM relationship

Regular expressions and FSMs are equivalent ways of defining a regular language (you can convert between them)

Algorithm

A sequence of steps that can be followed to complete a task and that always terminates.

Abstraction

The process of removing unnecessary details from a problem.

Representational abstraction

Removing unnecessary details.

Finite state machine (FSM)

A FSM is a model of computation for a machine that is always in one of a fixed number of states.

The state of the machine can be changed according to transition rules, based upon the input that it receives and its current state.

Some FSMs produce output as they carry out transitions, while others simply produce a yes/no response at the end of processing their input.

Set

A set is an unordered collection of unique elements.

Finite set

A finite set is one whose elements can be counted off by natural numbers up to a particular number, for example as: 1st element, 2nd element, …, 20th (and final) element.

Infinite set

A set which is not finite.

The set of natural numbers, ℕ and the set of real numbers, ℝ are examples of infinite sets.

Cartesian product of two sets

The Cartesian product of two sets, X and Y, written X x Y and read 'X cross Y', is the set of all ordered pairs (a, b) where a is a member of A and b is a member of B.

Subset

If every element of a set A belongs to a set B then A is a subset of B. The empty set is a subset of all sets.

Proper subset

If every element of a set A belongs to a set B, but there is at least one element of B that is not in A, then A is a proper subset of B.

Countable set

A countable set is a set with the same cardinality (number of elements) as some subset of natural numbers.

Set membership

With a set A = { 1, 2, 3 } we can say that 1∈ A (1 is a member of A) and that 4 ∉ A (4 is not a member of A).

Set union

The union of two sets is all of the elements that belong to the two sets.

Set intersection

The intersection of two sets is all of the elements that belong to both of the two sets.

Regular expression

Is a way of describing a set (allowed strings). Regular expressions allow particular types of languages to be described in a convenient shorthand notation.

Context-free language

A context-free language can be described by a context-free grammar or a set of rules for deriving strings in a language. Backus-Naur Form and syntax diagrams are two ways of defining the grammar for a context-free language.

Backus-Naur Form (BNF)

Backus-Naur Form can be used to define a context-free grammar which can be used to define the syntax rules of a programming language. BNF allows us to write production rules that use terminal and non-terminal symbols. Recursion is used in BNF production rules to allow the definition of ‘one of more’ of a symbol.

Syntax diagram

A syntax diagram is another method that can be used to define a context-free grammar.

Big-O notation

Algorithmic complexity is a means of comparing the efficiency of an algorithm. Complexity can be measured in terms of the time taken to complete the algorithm (time complexity) or in terms of the memory space needed (space complexity). Complexity is usually found to vary in terms of the size of the input and can be expressed using Big-O notation. Big-O notation allows for the comparison of algorithms.

Mathematical definition of a function

A mapping from one set of values, the domain, to another set of values, drawn from the co-domain, for example ℕ → ℕ.

Permutation

The number of ways a particular set can be arranged.

Tractable

Problems that are computable and have a polynomial (or less) time solution are called tractable problems.

Intractable

Problems that are computable but have no polynomial (or less) time solution are called intractable problems.

Heuristic

An approach that uses experience to make informed guesses that assist in finding a polynomial time ’solution’ to an intractable problem. The solution may be non-optimal.

Computable

The ability to solve a problem with the use of an algorithm.

Non-computable

A problem for which there is no algorithm that can be used to solve it.

Halting problem

The unsolvable problem of writing a computer program that can tell whether a given program and its inputs will halt, without running the given program. The Halting problem demonstrates that there are some problems that cannot be solved by a computer.

State transition table

A state transition table shows which state a finite state machine will move to based on the current state and inputs.

State transition diagram

A state transition diagram can graphically represent a finite state machine. States are represented by nodes. Edges represent transitions between states and are normally directed and labelled with the input, and sometimes output, symbols. Any accepting state(s) are drawn as double circles.

Transition rule

A Turing machine’s transition rule defines the behaviour when reading a specific symbol from the tape in a current state. The rule defines what to write to the tape, how to move the tape and the next state.

Transition function

A transition function is a mapping from a current state and input to the next state and any output. δ(SCurrent , input) = (SNext , output)

Turing machine

A Turing machine can be viewed as a computer with a single fixed program, expressed using:

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.

Start state and halting state

In a Turing machine, one of the states is called a start state, and states that have no outgoing transitions are called halting states.