4.4 Theory of computation Flashcards
What is representational abstraction?
A representation arrived at by removing unnecessary details
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.
What is information hiding?
The process of hiding all details of an object that do not contribute to its essential characteristics
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 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
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
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
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
What is (procedural) composition?
The process of combining procedures to form compound procedures
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.
When can a language be called regular?
If and only if it can be recognised by a FSA (or represented using a regular expression)
What is a finite state automaton?
A special case of an FSM, with exactly one start state and at least one accepting state
What is meant by the language recognised by an FSA?
The set of strings accepted by it
What is a set?
A set is an unordered collection of values in which each value occurs at most once
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)
- ⊂
A\B
Set difference between A and B
What is a finite set?
One whose elements can be counted off by natural numbers up to a particular number
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.
What can the Cartesian product be used for?
Defining function types
What is a countable set?
A set with the same cardinality as some subset of the natural numbers
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
n!
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, … }
