4.4 Theory of computation Flashcards by Tom FORSTER

What is representational abstraction?

A representation arrived at by removing unnecessary details

How well did you know this?

Not at all

Perfectly

What is abstraction by generalisation or categorisation?

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

How well did you know this?

Not at all

Perfectly

What is information hiding?

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

How well did you know this?

Not at all

Perfectly

What is procedural abstraction?

Procedural abstraction involves breaking down a complex model into a series of reusable procedures.
The actual values used in a computation are abstracted away and a computational method is achieved

How well did you know this?

Not at all

Perfectly

How is functional abstraction different from procedural abstraction?

Functional abstraction requires yet another abstraction from procedural abstraction
While the result of a procedural abstraction is a computational method, the function disregards the particular computation method

How well did you know this?

Not at all

Perfectly

What is data abstraction? Give an example

The process of isolating how a compound data object is used from the details of how it is constructed. Data abstraction forms the basis of abstract data types
For example, a stack could be implemented as an array and a pointer for the top of the stack

How well did you know this?

Not at all

Perfectly

What is problem abstraction/reduction?

The process of removing details until the problem is represented in a way that is possible to solve, because the problem reduces to one that has already been solved

How well did you know this?

Not at all

Perfectly

What is (procedural) decomposition?

The process of breaking a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided

How well did you know this?

Not at all

Perfectly

What is (procedural) composition?

The process of combining procedures to form compound procedures

How well did you know this?

Not at all

Perfectly

What is automation? How is it achieved?

The process of putting models (abstractions of real world objects/phenomena) into action to solve problems. This is achieved by:
1. 📝 creating algorithms
2. 👨‍💻 implementing the algorithms in program code
3. 🔢 implementing the models in data structures
4. 🤖 executing the code.

How well did you know this?

Not at all

Perfectly

When can a language be called regular?

If and only if it can be recognised by a FSA (or represented using a regular expression)

How well did you know this?

Not at all

Perfectly

What is a finite state automaton?

A special case of an FSM, with exactly one start state and at least one accepting state

How well did you know this?

Not at all

Perfectly

What is meant by the language recognised by an FSA?

The set of strings accepted by it

How well did you know this?

Not at all

Perfectly

What is a set?

A set is an unordered collection of values in which each value occurs at most once

How well did you know this?

Not at all

Perfectly

What does proper subset mean? What is its symbol?

Equality not allowed
(a set is a subset of itself but not a proper subset of itself)
⊂

How well did you know this?

Not at all

Perfectly

A\B

Set difference between A and B

How well did you know this?

Not at all

Perfectly

What is a finite set?

One whose elements can be counted off by natural numbers up to a particular number

How well did you know this?

Not at all

Perfectly

What is the Cartesian product of A and B?

The set of all ordered pairs (a, b) where a is a member of A and b is a member of B.

How well did you know this?

Not at all

Perfectly

What can the Cartesian product be used for?

Defining function types

How well did you know this?

Not at all

Perfectly

What is a countable set?

A set with the same cardinality as some subset of the natural numbers

How well did you know this?

Not at all

Perfectly

What are regular expressions?

Metalanguage for defining all valid strings of a regular language

What is the purpose of regular expressions?

Allow for regular languages to be described in a convenient shorthand notation

RegEx : zero or more

RegEx : one or more

RegEx : zero or one lots of

What are | ? * + called in RegEx?

Metacharacters

Context free languages are a __________ of regular languages

Superset

Why are context-free languages needed? (2*)

- RegEx doesn’t have enough **expressive power** - This is because regular languages can be expressed in terms of a finite state machine, and a finite state machine only has finitely many states

What is BNF?

- Backus-Naur form - A metalanguage for describing the syntax used by a context-free language

General statement in BNF

LHS ::= RHS

What is a function?

- A function is a mapping of values from a domain to a set of values from a co-domain. - Not all of the co-domains members needs to be outputs.

Hierarchy of complexities (polynomial, logarithmic, constant, exponential, linear)

constant < logarithmic < linear < polynomial < exponential

Permutations of n distinct objects

When is a problem "computable"?

If there is an algorithm (in principle) that solves the problem

When is a problem "non-computable"?

If no algorithm can **ever** exist which solves the problem

What is a intractable problem?

A **computable** problem for which a polynomial time (or better) algorithm does not exist

How do programmers find "solutions" to intractable problems?

By developing tractable **heuristic algorithms and methods**, which find **approximate** (but not necessarily optimal) solutions.

What is the trade-off that must be considered when developing heuristic algorithms?

speed vs correctness

What is an undecidable problem? Give an example

- A decision problem that is non-computable - e.g. the halting problem

What is the halting problem?

The undecidable problem of determining whether any program will eventually halt on given particular input without running the program

What is the significance of the halting problem?

The halting problem demonstrates that some problems are **non-computable**, meaning they cannot be solved by a computer

Why can a Universal Turing Machine be considered to be more powerful than any computer that you can purchase?

Because it has an infinite amount of memory

Name one example of a model of computation

Turing machine

Describe the importance of Turing machines

* Turing machines provide a **formal model of computation** and provide a **definition of what is computable** * They can be used to prove that there are problems which cannot be solved by computers

What makes up a Turing machine?

- Finite set of states - Set of transition rules - Finite set of symbols - Infinite tape with marked off squares - Sensing read-write head that can travel along the tape, one square at a time

What is a halting state in a Turing machine?

A state with no outgoing transitions

What is meant by a Universal Turing machine?

- A Turing machine that can **simulate the behaviour of any other Turing machine**, by acting as an interpreter - It faithfully executes operations on the data precisely as the simulated TM does - Both the transition rules for the TM as well as the input data would be stored on the tape

What is another way to represent the state transition diagram of a Turing machine?

* Transition function * δ (current state, input symbol) = (next state, output symbol, movement)

One example of where composition is used

In abstract data types, where a complex abstract data type is formed from smaller and simpler data types

Notation for *"the set difference between sets A and B"*

A\B

Set comprehension for all even natural numbers less than 10

{2x | x ∈ ℕ ∧ x<5} (| means such that, ∧ means AND)

{0ⁿ1ⁿ| n ≥ 1}

{ 01, 0011, 000111, 00001111, ... }