4 - Theory of Computation Flashcards
What does the term algorithm mean?
An algorithm is a sequence of steps that can be followed to complete a task and that can be completed in finite time.
What does a double circle indicate in a FSA?
Accepting state.
Explain the functionality of the * metacharacter when it is used in a regular expression.
Zero or more of the preceding value.
Explain the functionality of the ? metacharacter when it is used in a regular expression.
Zero or one of the preceding value.
Describe the significance of the Halting problem for commutation.
The Halting problem demonstrates that there are some problems that cannot be solved by a computer.
What is the question posed by the by the Halting problem?
Is it possible in general to write a program that can tell, given any program and its inputs, and without running the program, whether the given program with its given inputs will halt?
Why is it not possible to create a Turing machine that solves the Halting problem?
The Halting problem is non-computable
What is a finite state machine?
It is a model of computation
What is a Turing machine
A hypothetical machine capable of solving any problem that can be represented algorithmically
What does a Turing machine define
defines the limits of computers
What are the components of a Turing machine. (5)
An infinitely long tape divided into squares/ finite alphabet of symbols/ A read/write head/ finite set of states and a set of transition rules
What does “|” mean in a finite state machine
Acts as a break point to show input on the left out put on the right
What is the Universal Turning Machine
A Turing machine that can execute other Turing machines by stimulating their behavior.
What are the two parts of the Turing machine instruction
Data and standard description
What is the standard description of a turing machine
describes the turing machine that is being inputted allowing the UTM to accurately interpret the turing machine
what is a regular expression?
A compact notation that can describe a set of strings that make up a regular language.
What is the significance of a Universal Turing machine to the theory of computation?
it is possible for a single machine to compute anything that is computable.
What 2 ways can we measure complexity
time complexity/ space complecity
Why is time complexity important
allows us to measure efficiency of algorithm runtime.
Why is space complexity important
allows us to measure the usage of resources by the computer by any given algorithm.
What is meant by the worst case
The maximum amount of time that an algorithm can run for before reaching its answer
What is meant by the best case
Time taken for only one iteration of the algorithm to execute.
What is meant by the average case
mean number of computational time taken.
What is Big O notation?
a formal expression of an algorithm’s complexity in relation to growth of the input size
What is the classification for this Big O expression: O(1)
Constant time
What is the classification for this Big O expression: O(log n)
Logarithmic time
What is the classification for this Big O expression: O(n)
Linear Time
What is the classification for this Big O expression: O(n^2)
Polynomial time
What is the classification for this Big O expression: O(2^n)
Exponential time
What is the classification for this Big O expression: O(n!)
Factorial time
What is the basic operation of an algorithm
operation contributing most to the total running time/ most executed line of code
What is the dominant term
part of the time complexity of a problem will dominate over the other parts
What is a permutation
a set of objects is the number of different ways to arrange them when order matters.
What is a tractable problem
A problem with a polynomial-time solution
What is an intractable problem
A problem that can be solved, but does not have a polynomial-time solution
What is a heuristic algorithm
they return solutions that are are not entirely accurate/ optimal/ or complete/ but are fit for purpose and achievable in a reasonable time frame.
What is the halting problem
‘Is it possible to write a program that can tell given any program and its inputs and without executing the program/ whether it will halt?’
Why is the halting problem significant?
It proves that there are problems that cannot be solved computationally.
In regular expressions what does this mean: a*
zero or more “a”s
In regular expressions what does this mean: a?b?
0 or 1 “a”s followed by 0 or 1 “b”s
In regular expressions what does this mean: a+[ba]*
1 or more “a”s followed by zero or more of either “b” or “a”
In regular expressions what does this mean: \d
matches any digit [0-9]
In regular expressions what does this mean: \D
matches any digit that is not [0-9]
In regular expressions what does this mean: \w
matches any word
In regular expressions what does this mean:\W
Matches any non words
What is a regular language
A language that can be represented by a regular expression and will be accepted by a FSM
