4.4 Theory of Computation Flashcards
Algorithm (definition)
A set of step by step instructions to solve a specific problem that always terminates and can be represented by a Turing Machine
Representational Abstraction (definition)
Removing unnecessary details
Decomposition (definition)
Act of breaking down a problem into a number of more manageable sub problems
Finite State Machines can be used to test
if a string belongs to a regular language
In Mealy Machines
Outputs are associated with transitions
A Finite State Machine is described by (5)
- a set of states
- a start state
- a set of final/accepted states
- transition functions
- input alphabet
Each Transition Diagram has (3)
- a start state
- a halting/dead/trap state
- transitions
Regular Language (definition)
A language (set of strings) that can be expressed as a regular expression or finite state machine
A Regular Language is comprised of two components:
- alphabet: finite set of symbols
- syntax rules: how the symbols must be ordered
?
0 or 1 occurrence of previous character
*
Min 0 occurrences of previous character
+
Min 1 occurrences of previous character
|
or
Set (definition)
An unordered list of elements in which each element occurs at most once
Cardinality =
Empty set:
a measure of the number of elements in a set
{} or ∅
Infinite Sets are either
- Countable (e.g. rational)
- Non countable (e.g. real, irrational)
Subset (definition)
- allowed to be the same as the original set
- proper subset is not
Cartesian Product
- Is found by ‘joining’ two sets together
- X = {2,5,3} Y = {7,9}
- X cross Y = {(2,7), (2,9), (5,7), (5,9), (3,7), (3,9)}
Backus Naur diagrams
Syntax / railroad diagrams
Types of Complexity
- Time complexity is a function that describes how long an algorithm takes in terms of quantity of input
- Memory complexity is a function the describes how much space an algorithm takes in terms of quantity of input
- Often improving one decreases the other
Big O Notation Explanations for:
- Bubble Sort
- Binary Search, Binary Tree Search, Merge Sort
- Bubble Sort:
- In each pass through the list, n items will be examined
- There will be at most n passes through the list
- 2 for loops and so O(n2)
- Binary Search, Binary Tree Search, Merge Sort:
- Each comparison halves the size of the list that has to be searched through
- if the size of the list doubles then the number of comparisons needed only increases by 1
Intractable (Definition)
The problem is computable but cannot be solved within a polynomial (or less) time
Travelling Salesman Problem (Process + 3)
- Select a node to start from
- Choose the nearest neighbour to that node
- Continue choosing the nearest neighbour until all the nodes have been visited
- If not all nodes are visited then choose another starting point and start again
- Problem: find a route that visits all nodes with the shortest distance
- Only way to get the best solution is to try all combinations (brute force)
- Is intractable
The Halting Problem (Problem + Importance)
- The Halting Problem determines if a program will halt without running the program given its particular inputs
- Provides proof that there are problems that are unsolvable/non computable
