Theory of computation (C4) Flashcards
(22 cards)
Describe the halting problem and state why it is not possible to create a Turing machine which solves it?
- Whether it’s possible or not to determine if a program without running the problem.
- The halting problem is non-computable, no algorithm can solve it.
Characteristics of finite state machines
- They have a start node, denoted by an arrow coming from nowhere.
- One or more states can be an accept state, denoted by a double circle.
- States are joined by transitions, represented by arrows.
- Each transitional arrow must have a transition condition.
What is a mealy machine?
- A finite state machine with an output.
- Output determined by current state/input.
- Same other rules as FSM (one possible transition).
What is Big O notation?
A way of classifying how quickly an algorithm runs and how much memory it takes up in relation to its input (n).
What is an algorithms complexity?
- How quickly the algorithm runs and how much memory it takes up, and how they grow as the size of the input increases.
What is the permutation of a set of objects?
- The number of ways you can arrange those objects (factorial).
What are the different Big O complexities?
- O(1): Constant
- O(log n): Logarithmic
- O(n): Linear
- O(n²): Polynomial
- O(2ⁿ): Exponential
Describe the complexity of:
Constant
Log
Linear
Polynomial
Exponential
- Constant: Regardless of dataset, executes in same time. Best case.
- Logarithmic: Halves dataset in each pass, opposite to exponential, efficient with large datasets, good overall.
- Linear: Performance is proportional to size of dataset, decent.
- Polynomial: Performance proportional to the square of the side of dataset. Significantly decreasing efficiency with increasing size of dataset. Poor.
- Exponential: Doubles with each addition to the dataset in each pass. Opposite of logarithmic, extremely inefficient, worst type.
What is the complexity of an algorithm with a nested for loop for a 2D array?
- O(n²): Polynomial or quadratic
Describe linear search and its Big O
- Inefficient for large lists, efficient on smaller datasets.
- Works on unordered data.
- Time complexity: O(n)
- Space complexity O(1)
Describe binary search and its efficiency
- Requires dataset to be ordered.
- Effective for large lists.
- Time complexity: O(log n)
- Space complexity: O(1)
Efficiency of bubble sort
- Usually O(n²): Polynomial
- Time complexity: O(n)
- Space complexity: O(1)
Efficiency of merge sort
- Time complexity: O(n log n)
- Space complexity: O(n)
Explain what a turing machine is and define it.
- A theoretical finite state machine with the ability to read/write to an infinite tape.
- Tape contains an infinite number of cells, and is the memory.
- The acceptable symbols are known as the alphabet.
- There must be a read/write head.
- The machine can halt at any point if it reaches the halting state or all input is processed.
What things do you need to represent a program in a turing machine?
- A finite set of states
- A start state
- A tape
- Read/write head
- Halting states
- Current state
- An alphabet
- A set of transition rules
What is a universal turing machine?
- A turing machine which has the ability to execute the behaviour of any other turing machine
- Instructions and input for the turning machine are stored on the universal turing machines tape.
Name 3 things which affect an algorithms Big O
- Number of loops
- Recursion Depth
- Input size
Why are turing machines more powerful than any computer you can purchase?
- They have unlimited memory
What is representational abstraction?
Removing unnecessary details from a problem to make it simpler to solve.
What is abstraction by generalisation?
Group data by common characteristics to form a hierarchal ‘kind-of’ relationship.
What is the purpose of the end state in turing machines?
Move the read/write head back to the start state.
Define algorithm
A specific sequence of steps which can be followed to complete a task and that always terminates.
