Paper 1 terms Flashcards
Algorithm
A sequence of steps that can be followed to complete a task. An algorithm always terminates rather than going on forever in a loop
Assignment
The process of giving a variable or constant a value
Sequence
Instructions that follow on one from the other
Selection
Choosing an action to take place based on the result of a comparison, IF, ELIF, ELSE
Iteration
Looping a process. This can be finite (a set number of times - FOR), or infinite (repeating for an undefined, potentially infinite number of times - WHILE)
Abstraction
The process of omitting unnecessary details from a problem, in order to simplify it to make the solution easier. There are two types of abstraction: representational abstraction, and abstraction by generalisation/categorisation
Representational abstraction
A representation of the problem arrived at by removing unnecessary details
Abstraction by generalisation/categorisation
Grouping parts of the problem by common characteristics to arrive at a hierarchical relationship of the “is a kind of” type
Information hiding
The process of hiding all details of an object that do not contribute to its essential characteristics
Procedural abstraction
Breaking down a complex model into a series of reusable procedures (involves removing actual values used to achieve a computational model)
Functional abstraction
The step following procedural abstraction: this involves disregarding the particular method of a procedure and results in just a function
Data abstraction
Specific details of how data is actually represented are abstracted away, allowing new kinds of data structure to be created from previously defined data structures
Problem abstraction/reduction
Details are removed from a problem until it is represented in a way that is solvable
Decomposition
Dividing a problem into a series of smaller sub-problems, which can be solved individually or further divided until all parts of the original problem have been solved
Composition
Combining procedures to form a larger system. This is used in abstract data types, where a complex
abstract data type is formed from smaller and simpler data types
Automation
The process of putting abstractions of real world phenomena (known as models) into action to solve problems
Set
An abstract data type containing unordered unique (can’t have the same one twice) values. Sets can contain other sets
Set comprehension
A way of creating sets which doesn’t define each individual term but rather what we want from a more general set, e.g. {x | x->N ^ x>3} = {4, 5, 6, …}
Empty set notation
{} or Ø
Compact set representation
A space-efficient, short-hand way of describing sets, which can describe multiple instances of a number, e.g. {0n 1n | n ≥ 1} = {01, 0011, 000111, 00001111, … } (where n is an index)
Finite sets
Contains a finite number of items
Cardinality
Refers to the number of items in a finite set
Infinite sets
Contain an infinite number of items. There are two types of infinite sets: countable and non-countable
Countably infinite sets
Where items can be counted off by the natural numbers (e.g. Integers - Z, and Natural numbers - N)
Non-countable sets
Contain a larger infinity of items which can’t be paired with natural numbers to “count” them (e.g. the Real numbers - R)
Subset
Set A is a subset of Set B if it only contains items from Set B. The symbol for a subset is ⊆. So if A is a subset of B, the notation would be A ⊆ B, e.g. {2,4,6} ⊆ {1,2,3,4,5,6}. If two sets are the same, they are a subset of each other
Proper subsets
A set is a proper subset of another if it only contains items from that set but NOT ALL OF THEM. If two sets are the same, they are subsets of each other, but NOT proper subsets
Countable sets
Include finite sets and countably infinite sets. A countable set has the same cardinality as any subset of the Natural numbers
Membership sign (set notation)
Indicates an item is in a set, e.g. 3 ∈ R
“Not a member of” sign (set notation)
Indicates an item is not part of a set, e.g. -3.2 ∉ N
Set operations
Things you can do to sets to construct new sets. The operations include union, intersection and difference
Union (set operation)
Creating a new set by combining two other sets. The symbol for union is ∪. The values from each set are taken and added to the new set. Where a value appears in each set, it will only appear once in the new set
Set A ∪ Set B is the same as Set B ∪ Set A
Intersection (set operation)
Creating a new set with only the values that appear in BOTH of the other sets (see it an an intersection of a Venn diagram). The symbol for intersection is ∩
Difference (set operation)
Creating a new set with the values that are exclusive to ONE set. The symbol for intersection is ∩
Regular expressions
Short-hand ways of describing sets using metacharacters such as +, |, ?. For every regular expression set, there is an equivalent FSM
- (metacharacter)
O or more repetitions, e.g. ab* = {a, ab, abb, abbb, …}
- (metacharacter)
1 or more repetitions, e.g. a+b = (ab, aab, aaab, …)
? (metacharacter)
Previous character optional, e.g. pink? = {pin, pink}
| (metacharacter)
(metacharacter)
Or, e.g. g|h = {g, h}
() (regular expressions)
Groups regular expressions, e.g. (de)|(fg)h = {deh, fgh}
Context-free language
A set of strings and symbols that follow the rules of a context-free grammar
Context-free grammar
Describes which strings are and are not possible in a language by laying out production rules
Backus-Naur form
A way of notating context-free languages. It uses statements in which the left hand side is defined by the right hand side
Non-terminals (Backus-Naur form)
Text which is placed inside of angle brackets. Non-terminals can be broken down into more non-terminals, terminals or a combination of the two, e.g. for the non-terminal <FullName>:</FullName>
<FullName> ::= <Title><Forename><Surname>
</Surname></Forename></Title></FullName>
Terminals (Backus-Naur form)
Text without any brackets, which can’t be broken down any further and has a literal written value, e.g. the non-terminal <Number> could be described with terminals:</Number>
<Number> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
| Remember | means OR
</Number>
Recursion in Backus-Naur form
Backus-Naur form can make use of recursion by using a non-terminal which can be defined in terms of itself. Regular expressions cannot support recursion like Backus-Naur form can, BN form can represent some languages that reg exps can’t. E.g. recursion to define an integer:
<Integer> ::= <Digit>|<Digit><Integer>
<Digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
</Digit></Integer></Digit></Digit></Integer>
Syntax diagrams
A visual representation of a regular language which uses rectangles to represent non-terminals and ellipses to represent terminals (joined by arrows to show how strings can be formed from these)
Constant (time complexity)
O(C)
E.g. y = 3 (time of algorithm is unrelated to the output - it is a set value regardless)
I.e. determining whether a number is odd or even
Linear (time complexity)
O(n)
E.g. y = 3x (straight diagonal line going up, increases proportionately to input, i.e. if input 5, time 10, if input 10, time 20)
I.e. linear search
Logarithmic (time complexity)
O(logn)
E.g. y = log(x) (line goes up a bit and then sharp right and then stays horizontal, halves the number of items each iteration)
I.e. binary search
Polynomial (time complexity)
O(n^2) or O(n^3)
E.g. y = x^2 (line curves upwards over whole graph but curves up more the further it goes, for an algorithm a loop inside a loop)
I.e. bubble sort
Linear logarithmic (time complexity)
O(nlogn)
No graph example (N/A)
I.e. merge sort
Factorial (time complexity)
O(n!)
No graph example (intractable algorithms which can’t be solved in a useful amount of time)
I.e. travellers problem
Exponential (time complexity)
O(2^n) or O(3^n)
E.g. y = 3^x (sudden sharp curve up which basically turns into a vertical line, intractable algorithms which can’t be solved within a useful amount of time)
I.e. recursively calculating fibonacci numbers
Big O notation
Describes the complexity of an algorithm for the WORST CASE scenario. Describes input in terms of n (e.g. O(n) or O(logn))
The order of Big O functions (least to most time complex)
Constant
Logarithmic
Linear
Linear logarithmic
Polynomial (n^2 and then n^3)
Exponential (intractable)
Factorial (intractable)
Tractable problems
Can be solved in a useful time period. Polynomial time complexity or less
Intractable problems
Can’t be solved in a useful time period using today’s technology but are theoretically solvable. Known as “insoluble” due to the limits of computation. Heuristic methods may be used for these problems (approximate solutions)
The halting problem
It is impossible to write an algorithm to determine if another algorithm will finish with a given input. The halting problem demonstrates that there are some problems which cannot be solved by computers/algorithmically
Turing machines
A model of computation consisting of:
- a finite state machine (FSM)
- a read/write head
- a tape that is infinitely long in one direction
The tape is divided into cells which are blank or contain a symbol. Cells are written to/blanked using the read/write head. The set of symbols used is called the alphabet and is finite.
Turing machines run a single program, defined by an FSM. They stop once they’ve reached the halting state and are more powerful than FSMs because they can utilise a greater range of languages and their tape is infinitely long in one direction
Finite state machines (FSM)
Has a start state and a number of states from which there are no transitions (halting states)
Turing machine graphical representation
A Turing machine can be represented graphically as a series of cells, each containing a symbol, and a triangular pointer which represents the position of the machine’s read/write head. A □ symbol signifies an empty cell
Transition functions
Rules that a Turing machine follows (equivalent to FSM transition rules), written in the form:
δ(current state, read) = (new state, write, move)
E.g. if the transition function is: δ (S0, □) = (S1, 1, R), this means
if the machine is in state S0 and reads an empty cell, the machine should write a 1, move to state S1 and move its read/write head to the right
Universal Turing machines
Normal Turing machines are limited to just one FSM, so they are specific to one computational problem. Universal Turing machines can represent any FSM, and can act as interpreters since they read instructions in sequence before executing operations on input data
Importance of Turing machines
They provide a formal model of computation and therefore a definition of what is computable. Turing machines can prove that there are problems which cannot be solved by computers
