Theory of Computation Flashcards
What name is given to the rules that define how symbols can be replaced by other symbols?
Production rules
What type of object is enclosed in angle brackets in BNF?
Non-terminal
Why can BNF represent some languages that regular expressions can’t?
BNF supports recursion & languages with counting
What is the halting state in a Turing machine?
The state(s) with no outgoing transitions
What is the starting state in a Turing machine?
The state that you start at
What are the two states within a Turing machine?
Current state and next state
Three components of a Turing machine?
- Infinite tape (in one direction)
- Read/write head
- Control unit
What is the alphabet of a Turing machine?
1, 0 and blank.
What makes a task computable?
If a Turing machine can complete it - every algorithm can be represented as a Turing Machine.
What is a Universal Turing Machine?
A Turing Machine that faithfully executes operations exactly how the simulated Turing Machine would with the same process.
What is the Halting problem?
The Halting problem is non-computable - no algorithm will solve it.
What is a Heuristic?
It offers an approximate solution to intractable problems within polynomial times - not the most optimal solution.
What is an intractable problem?
A problem that cannot be solved within polynomial time.
What is the time complexity of an intractable problem?
a^n, n! or worse.
What is a tractable problem?
A problem that can be solved in polynomial time or better.
What is a computable problem?
A problem that can be solved with an algorithm - must always terminate and produce the correct output.
What is a non-computable problem?
A problem in which no algorithm exists to solve the problem.
What is Big-O notation?
A way of classifying algorithms by how their computation time grows as input size grows.
What is the order of magnitude?
The term in the function that increases fastest (eg number w/ largest power)
What is the time complexity of the linear search?
O(n)
What is the time complexity of the bubble sort?
O(n^2)
What is the time complexity of the merge sort?
O(nlogn)
- Linear logarithmic.
What is the time complexity of the binary search?
O(logn)
What do we assume with the time complexity of an algorithm?
Always assume the worst case scenario.
What is the space complexity of an algorithm?
A measure of the amount of working storage space an algorithm needs.
What is time complexity?
The amount of time it takes to run a program.
What is automation?
Models being put into actions to solve real-life problems.
What are the steps of automation?
- Creating algorithms
- Implementing the algorithms in program code (instructions)
- Implementing the models in data structures
executing the code.
What is psuedocode?
Code that can’t be ran into a programming language, used to help a programmer lay out code without having to conform to the rules of a language.
What is composition?
Combining procedures to form new compound procedures.
What is decomposition?
Breaking down a problem into smaller, easier to solve sub-problems.
What are the two main types (not only types) of abstraction?
Representational abstraction and abstraction by generalisation.
What is abstraction by generalisation?
Grouping common characteristics in a hierarchical (is like) relationship.
What is representational abstraction?
Filtering out unnecessary details.
What is problem abstraction?
Simplifying into a problem into one that has already been solved and using that answer to solve the original problem.
What is information hiding?
Hiding the details that are non-essential characteristics.
What is data abstraction?
The simplification of a body of data to a simplified whole.
What is procedural abstraction?
Abstracting the values away from a computational procedure.
Result = PROCEDURE
What is functional abstraction?
Identifying and representing a task with reusable functions/procedures.
What is an algorithm?
A set of instructions to follow to perform a different task.
