4: Theory of Computation Flashcards
Representation Abstraction
A representation arrived at by removing unnecessary details
Abstraction by Generalisation or Categorisation
Grouping by common characteristics to arrive at a hierarchal relationship of the ‘is a kind of’ type
Information Hiding
The process of hiding all 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 computational method - a procedure
Functional Abstraction
The result of a procedural abstraction is a procedure, not a function. To get a function requires yet another abstraction, which disregards the particular computation method
Data Abstraction
Details of how data are actually represented are hidden, allowing new kinds of data objects to be constructed from previously defined types of data objects
Problem Abstraction / Reduction
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
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
Automation
Putting models (abstraction of real-world objects / phenomena) into action to solve problems
Finite Set
One whose elements can be counted off by natural numbers up to a particular number
Infinite Set
One whose elements cannot be counted off by natural numbers up to a particular number
Countably Infinite Set
One that can be counted off by the natural numbers
Cardinality of Finite Set
The number of elements in the set
Cartesian Product of Sets
X x Y (X cross Y) is the set of all ordered pairs (x, y) where x is a member of X and y is a member of Y
Proper Subset
If A ⊂ B then B contains everything in A, but there is at least one element in B that is not in A
Subset
⊆ includes both ⊂ and =
Countable Set
A set with the same cardinality as some subset of natural numbers
Set Difference Operation
A\B = {x : x ∈ A and x ∉ B}
Regular Expressions Metacharacters (5)
- * means 0 or more repetitions
- + means 1 or more repetitions
- ? means 0 or 1 repetitions (i.e. optional)
- | means alternation
- () used to group regular expressions
Relationship between Regular Expressions & FSMs
They are equivalent ways of defining a regular language
Regular Language
A language is regular if it can be represented by a regular expression
BNF Production Rules (4)
- Chevrons denote a non-terminal symbol, which has another set of production rules to define it
- Symbols without chevrons are terminal
- The pipe symbol is a metacharacter denoting alternatives
- <fullname> :: =<title> Moloney|<title> Pope
<title> :: =Mr|Mrs
BNF Syntax Diagram for <date> ::= <day-name><month-name>|<day-name><month-name><year>
BNF vs Regular Expressions (3)
- All regular languages are context-free but the reverse is not true
- Any regular expression can be converted to a set of BNF production rules
- As an FSM has a finite number of states, a context-free language is required when an infinite number of elements in a string must be counted
Mathematical Concept of a Function
A mapping from one set of values, the domain, to another set of values, drawn from the co-domain
Order of Complexity (5)
- Constant time
- Logarithmic time
- Linear time
- Polynomial time
- Exponential time
Tractable
Problems that have a polynomial (or less) time solution
Intractable
Problems that have no polynomial (or less) time solution
Heuristic Methods
Often used when tackling intractable problems
Halting Problem
The unsolvable problem of determining whether any program will eventually stop if given particular input
Significance of Halting Problem for Computation
The Halting problem demonstrates that there are some problems that cannot be solved by a computer
Turing Machine
A computer with a single fixed program
Components of Turing Machine (4)
- 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
Importance of Turing Machines to Subject of Computation
Turing machines provide a general / formal model of computation and provide a definition of what is computable
Universal Turing Machine
A Turing machine that can solve any computable problem where the transition functions as well as the data are stored on the tape
