(4) Computation Flashcards
What does the Regular expression ‘a | b ‘ mean?
Any string that contains a or b
What does the Regular expression ‘abb?’ mean?
The ? indicates that there is zero or one of the char right next to ?
E.g. abb or ab
What does the Regular expression ‘ a+ ‘ mean?
Any string that contains one or more a
What does the Regular expression ‘ a* ‘ mean?
Any string that consists of zero or more a’s
What does the Regular expression ‘ ab ‘ mean?
Any string that contains an ‘a’ followed by ‘b’
What does the Regular expression ‘ a ‘ mean?
Any string that contains a single ‘a’
What are the two measures of efficiency?
- Time required to solve the problem
- Memory space required to solve the problem
What does the following Big O notations mean and rank them from best to worst?: O(n) ,O(1) , O(2^n) , O(n^2), O(log n)
O(1): Constant complexity - BEST O(log n): Logarithm complexity - GOOD O(n): Linear complexity - DECENT O(n^2) : Quadratic complexity - POOR O(2^n): Exponential complexity - WORST
What is Regular Expression?
A notation that determines when a string is valid without listing all valid strings
What is a Set?
-An unordered collection of values where each value occurs once.
What is Universal Turing Machine?
A Turing machine that can execute the behaviour of any other Turing
machine // can compute any computable sequence
What is an algorithm?
A step-by-step description of how to complete a task for solving a problem
What is information hiding?
The process of hiding the complexities of a program from the end user
Why can the turning machine model can be used to recognise a greater range of languages then an FSA?
Because the turning machine has unlimited memory
Why is the Turning Machine more powerful than the Finite State Automation (FSA)
Can be used to recognise a greater range of languages as it has unlimited memory
What is a tractable problem?
A problem that is solvable within a reasonable amount of time on a computer
What is a intractable problem?
A problem that is solvable but takes an unreasonable amount of time
What can a programmer do to ‘solve’ an intractable problem?
An algorithm could make an educated guess based on previous data
How can a Universal Turning machine be considered as a interpreter?
It reads instructions one at a time and executes the instructions
What is representational abstraction?
Removing (unnecessary) details;
What is abstraction by generalisation?
Grouping by common characteristics // a hierarchical / ‘kind-of’ relationship;
Explain the circumstances when it would be more appropriate to use an adjacency
matrix instead of an adjacency list.
Adjacency matrix appropriate when there are many edges between vertices
When graph/matrix is not sparse;
When edges frequently changed;
When presence/absence of specific edges needs to be tested frequently;
What is BNF (Backus-Naur Form)?
A formal mathematical way of defining syntax unambiguously
Describe the relationship between regular expressions and FSMs.
Regular language can be defined as any language that a FSM will accept
