M269 Glossary
410 flashcards · Computer Science · by mathewcsims
uncountable
Any set which is not countable.
subprogram
A self-contained program unit that a main program delegates a specific task to. Subprograms may take arguments and have return values. In Python, subprograms are functions or methods.
subset
For two sets, A and B, A is a subset of B if and only if every element in A is also an element in B. The symbol is ⊆.
sibling
Nodes in a tree that are children of the same parent are said to be siblings.
simulation
A working model of a process or a system which changes over time.
compound statement
A Python statement consisting of more than one line.
single-objective (optimisation problem)
An optimisation problem the objective of which is to optimise a single value.
slicing
Extracting a portion of a list, string or other mutable collection.
slot
A location within a hash table in which data items are stored.
sound (proof system)
A proof system is sound if in that system proofs can only be derived for valid arguments.
spanning tree
A sub-graph of a graph that is a tree connecting all the vertices together.
sparse (graph)
A graph in which few of the vertices are connected by edges.
stack frame
A copy of the program environment, including the values of all local variables, that is maintained for each call of a recursive function.
standardised variables
In predicate logic, the variables are standardised if distinct variables are always represented by different variable symbols.
statement
In programming, a piece of code complete enough for it to be excutable.
qubit
Just like the bit, the qubit is an abstraction. It is a single unit of data that can be in a state, a superposition, in which the possibilities 1 and 0 are represented simultaneously. Additionally, if one combines two qubits, the resulting system can represent all possible sequences of 0 and 1 of length 2 at once. Thus, qubits can store exponentially more information than the same number of bits. There are several entities that can physically realise a qubit, including photons and electrons.
query
A statement made to a database which returns a table.
range
The range of a function f(n) is the subset of the f(n)’s co-domain that contains the values that are paired with every n in f(n)’s domain. Less formally, it is the set of the outputs of f(n) for every n.
rate of growth
The speed at which a function f(n) grows as n increases.
rational number
Any number which can be represented as the ratio of two integers.
real number
All positive and negative numbers which can be expressed in decimal form as a sequence of digits containing a decimal point, where the sequence after the decimal point is potentially infinite.
recombination
In biology, the shuffling of genes between DNA strings. In genetic algorithms, the swapping of bits between genomes by means of crossover.
recursive function
A function (or method) is recursive when it obeys the 3 laws of recursion: there is one or more base cases that are handled without recursion; the function calls itself; each recursive call makes progress towards a base case.
reduction
A reduction of one problem A to another problem B is a demonstration that a solution for problem B (if such a solution should exist) can be used to solve the original problem A.
rehashing
The re-application of a hash function to an item in the event of a collision.
relation
A set of tuples, which can be used to represent the relationships between the objects in those tuples.
relational database
A system for storing information in tables.
return statement
A statement that specifies a return value.
return value
A value that a function or method or subprogram more generally passes back to the main program it was called from.
root
The root of a tree is the only node in the tree that has no incoming edges.
run-time complexity
Another term for the complexity of an algorithm.
Russell, Bertrand
Bertrand Russell (1872-1970) was British philosopher and originator of the Russell Paradox.
complexity (problem)
The complexity of the most efficient algorithm (that is possible) for solving the problem.
Russell Paradox
A paradox concerning the set of all sets that are not members of themselves. Let's call this set U. Russell asked: Is U a member of itself? If it is, then it can't be. If it isn't, then it has to be.
safety critical system
A system which could cause severe injury or death if it were to malfunction.
SAT
The decision problem whether there is an interpretation that makes a WFF (or CNF) of propositional logic true.
satisfiable
A set of logical formulas is satisfiable if it is possible to find an interpretation in which all the formulas are true.
satisfy
An interpretation in which a set of one or more formulas are all true is said to satisfy the formulas.
scope
A variable in predicate logic occurs in the scope of a quantifier if the values that the variable can take are dictated by that quantifier.
scope (programming)
Those areas of a program from within which an entity such as a variable or function can be accessed.
scripted mode
In contrast to interactive mode, in which statements are executed one at a time, a programming style in which an entire program is entered before any of it is executed.
selection
A control structure in which different paths are followed depending on some condition.
selection sort
A straight-sorting strategy, in which each element is moved directly to its correct place in the sorted list.
semi-decidable
A semi-decidable problem is not computable. However, for any semi-decidable problem there is an algorithm which works for those inputs for which the answer is ‘yes’. The algorithm will return 1 for those inputs. If the answer is ‘no’ (i.e. 0), the algorithm will on some occasions go into an infinite loop. As a result, if we have an algorithm for a semi-decidable problem and apply it to a particular input, sometimes the algorithm won’t halt.
sentence (logic)
A well-formed formula of predicate logic, in which no variable is free.
sequence
Any ordered list of objects, such as numbers, strings, etc.
set
A collection of distinct, unordered objects.
shift distance
In string-searching algorithms, the number of characters the target string may be shifted after a mismatched character is encountered.
shift table
In string-searching algorithms, a table storing the shift distances of every character in the search string’s alphabet.
shortest path problem
In a graph, the problem of finding a path between two vertices where the sum of the weights of its constituent edges is minimised.
suite
In a Python compound statement, the lines of code that follow the header and make up the rest of the compound statement. The suite is indented relative to the header.
superposition
A qubit can be in a special state, called a superposition, where it represents the states 0 and 1 at the same time.
super-Turing computer
A physical device that can ‘compute’ functions that are not computable by a Turing Machine.
syntax error
When a program statement does not follow the rules of the programming language. Comparable to a grammatical error in a natural language.
syntax (logic)
The rules which determine whether or not an expression of logic is a well-formed formula.
table
A data structure containing data held in a database.
tape (Turing Machine)
Part of the specification of a Turing Machine.
tautology
A well-formed formula which is true in all interpretations.
ternary (function, predicate, relation)
A ternary function, predicate or relation has an arity of 3.
Timsort
A sorting algorithm devised by Tim Peters, combining elements of merge sort and insertion sort. Timsort is the built-in sorting algorithm of Python.
TM(DPN)
The set of Turing Machines that solve instances of DPN.
topological sort
A linear ordering of the vertices of a directed graph, such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. Note that a directed graph can be topologically sorted if and only if it is a directed acyclic graph.
topsort
See topological sort.
Totality Problem
The problem of deciding whether an algorithm halts on all inputs.
tour
In the Travelling Salesperson Problem, a visit to all cities once only, returning to the starting point.
tractable problem
A computational problem that can be solved in a reasonable amount of time, i.e. with an algorithm that has worst-case time complexity of O(nc).
Travelling Salesperson Problem (TSP)
An optimisation problem studied in theoretical computer science. A hypothetical salesperson has a list of cities to visit, with the distance between each pair of cities specified. The problem is to find the shortest route that visits each city exactly once and returns to the starting point.
traversal (of a tree)
A visitation of the nodes in a tree is called a tree traversal. There are three commonly used patterns for traversing trees: preorder, inorder and postorder. For binary trees these are defined as follows: In a preorder traversal we visit the root node first, then recursively do a preorder traversal of the left subtree, followed by a recursive preorder traversal of the right subtree. In an inorder traversal, we recursively do an inorder traversal on the left subtree, visit the root node, and fin…
tree
Definition 1 (nodes and edges): A set of nodes and a set of edges with the following properties: One node, provided the tree is non-empty, is designated the root node. Every node, except for the root, has exactly one parent. There is a unique path to each node from the root node. Definition 2 (recursive): A tree is either empty or consists of a root and zero or more subtrees (each subtree is itself a tree).
decision problem
A problem, usually stated in formal logic, for which the answer is either yes or no, for each of its instances. A decision problem corresponds to a mathematical function whose domain is some set A and whose co-domain is the set {0, 1}.
truth function
A function which, given a sequence of truth values, returns another truth value. The domain of a truth function is {True, False} × ⋯ × {True, False}, and the co-domain is {True, False}.
truth table
A means of precisely defining logical operators and of evaluating the truth or falsity of compound logical expressions.
truth value
True or False.
tuple (programming)
Similar to the list ADT but immutable. Tuples are used for so-called structured data: data consisting of more than one item and where, because of the meaning, modification would not make sense, for example ('Ada', 'Lovelace').
tuple (sets)
A finite, ordered collection of elements.
Turing, Alan
Many of the key ideas behind M269 originated with the British mathematician and logician Alan Turing (1912–1954).
Turing completeness
An algorithm is Turing complete if it can be used to simulate any other algorithm. A programming language is Turing complete if it has an interpreter (or compiler) that is Turing complete.
Turing Machine
A (deterministic) Turing Machine is the mathematically precise definition of an algorithm, as proposed in Alan Turing’s seminal paper of 1936. It consists of a set of instructions. Each instruction specifies, for a specific state and content of the current square on a tape, how to update the state and the contents of the current square, and which square of the tape to move to next. (Compare with non-deterministic Turing Machine.)
unary (function, predicate, relation)
A unary function, predicate or relation has an arity of 1.
unbounded knapsack
A variant of the knapsack problem in which as many copies of each kind of item as required may be included.
uncomputable
A problem that is not computable is one for which it is not possible to build an algorithm that solves every instance of the problem in a finite number of steps.
decision TSP
The decision Travelling Salesperson Problem is defined as follows: Given a weighted complete graph and an integer k, decide whether there is a cycle that visits every node exactly once, except that the starting and endpoint are the same node, and whose total weight is at most k.
decrease-and-conquer algorithm
An analogue of a divide-and-conquer algorithm which works by progressively decreasing a numeric input.
dedent
Shift a line or block of code left. (Compare with indent.)
defensive programming
An approach to computer programming that consists of placing checks and guards throughout the code, in order to ensure that it continues running in all circumstances.
De Morgan’s laws
For propositions P and Q: ¬(P ∨ Q) is logically equivalent to (¬P ∧ ¬Q). and ¬(P ∧ Q) is logically equivalent to (¬P ∨ ¬Q).
dense (graph)
A graph that has close to the maximum possible number of edges.
depth first search (DFS)
A form of algorithm for traversing trees or graphs in which all the nodes of a particular branch are explored before backtracking to an earlier state.
descendant
A node in a tree is a descendant of another node if there is a path from the latter to the former.
expression
A sequence of symbols of some language, such as the alphabet (for English) or propositional variables and logical connectives (for propositional logic).
design by contract
An approach to the design of program entities, such as abstract data types, functions, etc., that treats the interaction between these entities and their clients as a form of contract, with guarantees from both client and entity expressed in terms of preconditions, postconditions and invariants.
deterministic
A property of any algorithm or system, such that the same input to the system will always produce the same output.
diagonalisation argument
A mathematical argument which uses the diagonal values on a grid to prove that a set is uncountable.
dictionary
An ADT in which key–value pairs are stored.
difference (sets)
A–B contains the elements of A that are not in B.
digraph
See directed graph.
directed acyclic graph (DAG)
A form of graph in which the edges have directions, but no cycles: following the edges from any node, according to their proper directions, will never return to a node visited earlier.
directed graph
A graph the edges of which are directional.
disjoint
Two sets are disjoint if they have no elements in common.
disjunction
The disjunction A ∨ B is TRUE if and only if A is TRUE, B is TRUE, or both A and B are TRUE. Alternatively, A ∨ B is FALSE if and only if A is FALSE and B is FALSE.