Theory of Computation Flashcards
What is Abstraction?
Process of filtering out the details we don’t need in order to concentrate on those that we do – removing unnecessary details
Define Representational Abstraction.
Removing unnecessary details
What is abstraction by Generalisation?
Grouping by common characteristics to get a hierarchical relationship
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?
Breaking down a complex model into a series of reusable procedures; finds the generic method.
E.g.
(4*3) + 7 becomes
ab + c
What is functional abstraction?
Procedural abstraction results in a procedure. Abstracting further disregards the method of a procedure and results in just a function which takes inputs and produces a specific output.
What is Data Abstraction?
The reduction of a particular body of data to a simplified representation of the whole. For example, a stack could be implemented as an array and a pointer for the top of the stack.
What is Automation?
Process of putting abstractions of models into action to solve problems
What is Decomposition?
Process of breaking down a complex problem into parts that are easier to understand
What is Procedural Decomposition?
Breaking a problem down into smaller sub-problems
Each of which solves an identifiable task
Each of which might be further split up
What is Complexity of a linear search?
O(n)
As the size of the list increases, time taken increases at the same rate
‘n’ is worst case
What is the complexity of a binary search?
O(log n)
As time taken increases the size increase, but by less and less each time
Halves tree/graph each time
What is meant by the time complexity of an algorithm? ign
The number of clock cycles taken for the CPU to execute the algorithm
Expressed using ‘big O notation’
Describe the Halting Problem?
The unsolvable problem determining whether a program will halt, given a certain input, without running the given program.
What is a Tractable Problem?
Problem that can be solved in an acceptable amount of time [polynomial time]
What is an Intractable Problem?
Problem which cannot be resolved in polynomial time
What is meant by the term Heuristic?
A method for producing a ‘rule of thumb’ to produce an acceptable solution to intractable problems
Better than n factorial
E.g,. Store your shortest path that you have so far and check another. Making approximation for the shortest path
How to identify Polynomial?
Nested loops are always polynomial
How to identify a Logarithmic Algorithm?
Halves the number of items each term
What is meant by the term ‘Intractable Complexities’?
Ones more complex than polynomial
State the Complexity Rules.
Remove all terms except one with largest factor/exponents
Remove any constants
3n^2 + 4n + 2 =
3n^2 =
n^2 =
O(n^2)
Order of Algorithm Complexities:
Constant – O(c)
Logarithmic O( log(n) )
Linear O(n)
Linear Logarithmic O(n log(n) )
Polynomial O(n^2)
Exponential O(2^n)
Factorial O(n!)
Charlie Loves Licking Luscious Penis Every Friday !
What does a Turing Machine consist of?
A finite state machine
A set of transition rules
A sensing read/write head
Start state
Set of accepting/ halting states
A tape that is infinitely long in one direction
State register/Current register
The finite alphabet of symbols that it can use
Explain what a Universal Turing machine is
Turing machine that can simulate the behaviour of any other Turing machine
Faithfully executes operations on the data precisely as the simulated Turing Machine does
Acts as an interpreter
