Providing an interface between a device and the external world to hide the device's complexity. This could be hardware e.g. a keyboard, the enigma machine, or software e.g. a GUI.
In software development parts of a program may be hidden from view so that they cannot be viewed or changed e.g. for security: the Ada language was developed to implement hiding of data and was much used by the military.
Abstraction means refining or simplifying something until it can be represented in a model or data structure. One example of this is the taxonomy of animals and plants, which has general terms at the top and specific terms below. Abstract nouns provide a form of abstraction e.g. furniture is an abstraction of chair and table and you can draw a kind of class hierarchy diagram of furniture: bedroom, dining room, garden, etc.
The London underground map is also an abstraction. Imagine starting out with a map of the underground that was complete in every detail, all the curves and joins where tracks meet or are shared. This complexity has been abstracted to the point where a simplified map can be drawn so that passengers can easily plan journeys around it and computer scientists could find ways to represent it in data structures. Every problem undertaken (of a certain size and degree of complexity) should involve abstraction of the data structures from the complex reality so that reality can be represented by structures such as graphs or normalised data tables.
An algorithm is a sequence of unambiguous instructions for solving a problem.
This is a measure of how economical an algorithm is with time and resources. Time complexity deals with how long it takes to run a particular algorithm; space complexity deals with the resources, especially memory, that an algorithm requires to run.
Worst-case complexity - the data that produces the greatest workload
Best-case complexity - the data that produces the least workload
Average-case complexity - average the times for every possible input
This is to do with the time complexity of algorithms as the size of input increases. The three main types of growth are linear, polynomial and exponential. Simple examples are n, n^2 and 2^n.
Linear growth means that the time taken to complete grows in linear proportion to the size of n e.g. if n= 20 takes 20 seconds then n=40 will take 40 seconds and so on.
Polynomial growth means that the time taken will grow in proportion to the highest power in the polynomial e.g. (n^2 + n) / 2 grows at n^2 because the +n is insignificant at large values. The bubble sort grows at (n^2-n)/2 or n^2. For n=5 a bubble sort does 10 comparisons; for n=10 a bubble sort does 45 comparisons; for n=100 a bubble sort does 4950 comparisons.
Exponential growth means that the time taken will grow in proportion to 2^n, 3^n, k^k and so on. Factorial (!) is exponential.
Linear growth may be summarised as O(n) or O(n/2), polynomial as O(n^2) and exponential as O(2^n) or O(n!).
FSM has:
A deterministic FSM has one outgoing transition for each trigger. A non-deterministic FSM has more than one outgoing transition for a given trigger e.g. input 1 to state 3 may have two outputs: which should be followed? The short answer is: both; separate traces must be followed until one of them is resolved.
Traffic lights including pedestrain crossing: inputs from button and timer. Define the traffic light combinations as states:
Green / Red (cars/pedestrians)
Amber / Red
Red / Green (leaves out a step of Red/Red)
Flashing Amber / Flashing Green
Green/Red
(Approximately - there may be differences between different sets of lights)
Vending machine: takes different coins and outputs the amount entered so far.
Produce no output while processing the input. Solve decision problems and output Yes/No or True/False.
Often used to analyse string input e.g. to check if a binary number contains an odd or even number of 1s.
A Turing machine is an automaton that includes:
Transitions are based on the current state and the symbol under the read-write head. Each transition involves:
Turing machines are useful in deciding whether an algorithm exists for a particular problem and input. If an algorithm does exist then a Turing machine can be built to implement it; and if a Turing machine can be built to implement an algorithm then the algorithm is computable. This is the Church-Turing thesis. Some algorithms are not computable e.g. the halting problem (when a program is given as the data to Turing machine will it run to completion under all input values? No, it won't.)
A universal Turing machine is a Turing machine that can simulate other Turing machines. The instructions for the simulated Turing machine are placed on the UTM, followed by the data that the simulated program requires. The UTM then carries out the instructions of the simulated TM by carrying out its instructions and fetching the required data.
Thus a UTM is like an interpreter such as the Java machine in a browser. This laid the foundation for the development of the electronic computer: computers are UTMs. Program instructions and data are the same thing to a UTM or a computer, just symbols.
Tiling Problems
Can a finite area of any size and with integer dimensions be covered with tiles that follow a particular rule such as adjacent side must be of the same colour? It is possible to show that a given set of tiles will cover a floor and that another set of tiles will not. However, it is not possible to write a program that will accept finite sets of tiles and say whether a room of any size can be covered by the tiles and conform to the rules of the pattern. This is non-computable or undecidable.
Problems that can be solved in a reasonable amount of time are said to be tractable. These often have polynomial growth rates. Problems with exponential growth rates (such as the Tower f Hanoi: 2^n-1 - 7 moves for 3 rings, 15 for 4 rings, 31 for 5 rings, and so on) are generally intractable for large n. The TSP formula is (n-1)!/2 so this too is intractable for large values of n. Problems with exponential time complexity may be solved by finding a sub-optimal solution that works; demonstrating that a solution works may be easy e.g. the school timetables problem is exponential in time complexity but sub-optimal solutions can be found in a matter of hours and these allow the schools to operate fairly effectively. Likewise staff rostering in large organisations e.g. flight crew for an airline. Guessing a solution that works is called heuristics (posh word for guessing!)
Is it possible to write a program that will take another program as input and say whether it will halt under all input conditions? No, it is not.
An example is provided by code that does the following:
input x e.g. 5
while x <> 1 do
if x is even divide by 2
if x is odd set x to 3x + 1
Regular expressions are used for matching strings of text. A regular expression for currency might be:
A pound sign immediately followed by one or more digits, and then optionally a period and exactly two more digits (for example "£10", or "£245.99").
Special characters include:
The currency regular expression:
£ \d+ (\. \d \d)?
Pound symbol followed by 1 or more digits followed by zero or 1 decimal point and 2 further digits.
Regular expressions may be used for searching. To find all instances of colour and color in a document you would search with the regular expression <colou?r>. This will find both colour and color. This might also be used in a file search to find all files with a particular name and content. Searching with regular expressions should be more accurate than using wild card characters e.g. col* which would find all files that begin with col such as collar.
Backus Naur Form provides a symbolic language for grammars such as those used in programming languages. A grammatical rule in BNF is called a production rule
e.g. digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (::= means 'is defined as' and '|' means or)
This particular definition provides the lowest level as these are terminal symbols - there is no further way to decompose or define these symbols. Some symbols may be non-terminal, that is they can be broken down further
e.g. whole_number ::= digit | digit whole_number
The second definition means that a whole number is either a single digit or a single digit followed by a whole number, which is either... This definition uses recursion to extend the number of digits infinitely.
An integer can be positive or negative so its definition (using the terms above) might be:
integer ::= whole_number | + whole_number | - whole_number (this was acceptable as the answer to a question on the June 2010 COMP3 paper).
Reverse Polish Notation is used in computing to define expressions as they will be processed by the ALU. The ALU takes two input values (operands) and applies an operation to them; the more common infix method takes one operand, an operator and then a second operand. If you say 'What is 2 + ...' then someone would probably say '2 + what?'; the brain takes the two operands and then applies the operator, just like an ALU (this may not be the full story for addition according to neuro-science!).
In RPN or post-fix the operator is placed after the two operands that it connects. Thus:
2 + 2
becomes 2 2 +
and 2 + 2 x 2
becomes 2 2 2 x +
while (2 + 2) x 2
becomes 2 2 + 2 x
The distinction between these two expressions is important.
Floating point
Answers should be in 2's complement binary. Remember that 2's complement provides a way of showing a negative number in binary; positive numbers in 2's complement are still positive and their representation doesn't change; only negative numbers use the 2's complement convention of inversion so they start with a 1.
decimal to binary: 73.0625
binary=01001001.1001
decimal to binary: 7.875
decimal to binary: -6.375
binary to decimal mantissa/exponent: 01011011 0011 (mantissa and exponent in 2's complement so a leading 1 makes it negative)
answer: 5.6875 - but how do you find it?
binary to decimal mantissa/exponent: 01011011 1101 (mantissa and exponent in 2's complement so a leading 1 makes it negative)
answer - something small! (0.0888671875)
binary to decimal mantissa/exponent: 10100101 0011 (mantissa and exponent in 2's complement so a leading 1 makes it negative)
answer: -5.6875 - but how do you find it?
binary to decimal mantissa/exponent: 10100101 1101 (mantissa and exponent in 2's complement so a leading 1 makes it negative)
answer - something small! (-0.0888671875)