Paper 1 Flashcards
[PPQ] What is representational abstraction?
Removing unnecessary details until the problem is represented in a way that is possible to solve
[PPQ] What is abstraction by generalisation?
Grouping by common characteristics
For which type of graph would the bottom half of the matrix also need to be used?
Directed graph
What is a Turing machine?
A machine that reads a tape one square at a time. The tape encodes a problem that must be solved
Describe the basic operation of a Turing machine
The tape is divided into a number of cells, and is used as memory
Each cell contains a symbol (blank is denoted by a square)
Acceptable symbols are known as the alphabet
The read-write head can read the cell, write to it, or erase it
The machine enters the halting state when the entire input has been processed
How do you draw a Turing machine diagram?
Like an FSM but A,B,C on the arrows
A = current state
B = write
C = direction
So 0,1,R means if 0 is read, write 1 and move to the right
This can also be written as a table (current state, read symbol, write symbol, move, next state)
What is a transition function?
Another way of expressing state transitions
δ(current state, input symbol) = (next state, output symbol, movement)
What is a universal Turing machine?
A machine that reads the description M of a Turing machine and executes the same instructions that Turing machine would. M is written at the beginning of the tape, followed by D. Anything a Turing machine can compute, a real computer can compute, so it provides a definition of what is computable
What is decomposition?
Breaking a problem into a number of sub-problems
What is automation?
Models are put into action to solve problems
What is composition?
Combining procedures into compound procedures
Syntax for creating a new class in Python
class Tile:
def \_\_init\_\_(self, status, position):
## insert code here. This is called whenever a new Tile is created
def statusSwitch(self, newStatus):
## insert code here
Tile(0, 0) ## Creates a new file
Advantage of using constants
Makes program clearer and easier to understand
What is the definition of “algorithm”?
A sequence of steps that can be followed to
complete a task and that always terminates.
What is a tractable problem?
A problem solvable by a polynomial-time algorithm. Untractable problems can be solved, but take an unreasonable amount of time. Problems cannot change from being tractable to untractable
[PPQ] What approaches could be taken to “solve” an untractable problem?
Heuristics (an experienced-based educated guess) that provides an approximation of the solution
Relax some of the constraints on the solution
[PPQ] What is a universal Turing machine?
A Turing machine that can simulate the behaviour of any other Turing machine, and perform the same operations on data that the original machine does
Which Backus-Naur Form rules cannot be defined using a regular expression?
Ones which contain recursive self-references to the rule itself
[PPQ] Explain why a linear-search has the order of time complexity O(n)
As the size of the list increases the time taken to search for an item increases at the same rate
A linear search checks each item in the list in turn until the target is found, so if there are n items in the list the worst case would be n comparisons
[PPQ] Advantage of Reverse Polish Notation over infix notation
Easier for a computer to evaluate and does not require brackets
Complexity of merge sort
O(nlog(n))
Complexity of bubble sort
O(n^2)
[PPQ] What is the difference between a static and a dynamic data structure?
Static data structures have storage size determined when the program is compiled, meaning they can waste memory if they’re not holding much data
Dynamic data structures require memory to store pointers to the next items. They do not store data in consecutive memory locations
[PPQ] What is the halting problem?
Determining if a program will halt for a specific input, without running the program. No algorithm exists that can do this
Name the components of a Turing machine
Read/write head, transition rules, tape, alphabet
Why can a Universal Turing Machine be considered to be more powerful than any computer that you can purchase?
It has an infinite amount of tape
Why are Turing machines important?
Turing machines provide a (general/formal) model of computation and provide a definition of what is computable.
What is a regular language?
It can be represented with a regular expression and understood by an FSM
Backus-Naur form
::= “A” | “B” | “C” …..
::= |
::= |
What is procedural abstraction?
Abstracting away the actual values used in a computation, to get a procedure
What is functional abstraction?
Taking a procedure and disregarding the particular computational method to get a function
What is data abstraction?
The details of how data is stored are hidden, allowing new kinds of data objects to be constructed from previously defined types of data objects. For example, a stack could be implemented as an array and a pointer for top of stack
What are the operations of a stack?
pop: Remove an item from the front
push: Add an item to the back
peek: Look at the first item without removing it
Check if stack is empty
Check if stack is full
RegEx
* (0 or more repetitions) \+ (1 or more repetitions) ? (0 or 1 repetitions, ie optional) | (alternation, ie or) ( ) to group regular expressions.
