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
Why is it not possible to create a Turing machine that solves the Halting Problem?
There is no algorithm that solves the Halting Problem
Why is a universal Turing machine more powerful than any other computer?
It has infinite tape
What type of object is enclosed in angle brackets in Backus-Naur Form?
Non-Terminal
What name is given to an object in Backus-Naur form that can’t be broken down any further?
Terminal
In Finite State Machine what is the double circle?
Valid halting state
When it is valid to stop
How does a finite state machine differ from a Turing machine?
Don’t have to worry about tape
Or header
What is meant by the term reject state?
No escape from that state -no way out
Rule won’t be valid if you stop there
What are finite state machines used for?
Used to validate an input
Represent regular expressions in a computer
A less powerful Turing machine
What is a heuristic algorithm?
An algorithm that makes a guess/estimate based on experience
Used to tackle intractable problems.
What’s the relationship between a Turing machine and an Algorithm?
A Turing Machine can compute any algorithm.
What’s the purpose of a Turing Machine?
To provide a theoretical model which helps us understand how computers solve problems step by step.
What is the time complexity of a merge sort?
O(nlogn)
The log(n) comes from dividing each array into halves
Then the (n) comes from sorting them by merging
What is meant by the ‘cartesian product of two sets’ ?
Two sets A and B, written AB, is the set of all ordered pairs (a,b) where a is a member of A and b is a member of B.
e.g.,
A= {1,3,5} B ={ 12,25,40 } Set C is defined as AB
C = {(1,12), (1,25), (1,40), (3,12), (3,25), (3,40), (5,12), (5,25), (5,40)}
What is the time complexity of a bubble sort?
O(n^2)
Nested Forloop
What is an example of an algorithm with a Factorial time complexity?
Travelling Salesman
What is Problem abstraction?
Removing details from a problem until it can be represented in a way that is possible to solve because the problem reduces to one that has already been solved.”
What is a finite state machine?
A computing machine that has a fixed set of possible states, a set of inputs that change the state and a set of possible outputs.
Transition function format
δ(Current State, Input) = (Next State, Output, Movement Dir)
Symbol for Integers
Z
What is meant by a Proper Subset?
⊂
A subset is made up entirely of elements of another set but there is at least one element in the original set not included in this set.
What is meant by a subset?
⊆
The subset can contain ALL the elements of the other set
