Computer literacy, today, is as important as reading and writing.
Computing has literally permeated everything -
from TVs, phones, washing machines, music players, cars and medical
equipment to spacecrafts and robots. However, most people are still
only passive users of computing tools. Imagine the time when only
a small percent of the people were able to read and write
and the rest had to ask for someone else to do it for them.
This is how the current situation looks like with respect to computing.
Learning how to program opens a whole range of new possibilities
comparable only to the change that someone would experience once
he becomes a fluent reader and writer. The following is a nice
video on the topic:
The goal of this course is to learn how
think computationally (i.e. how to write) and how to understand code
(i.e. to read). In addition you should understand the limits
of computation and you should be able to map scientific problems from
your own field into a computational solution.
In computer science we talk a lot about algorithms. The word for
algorithm is as old as the concept of algebra. They both stem from
the work of the Arabic mathematician Muḥammad ibn Mūsā al-Khwārizmī:
It is thanks to him that the Western world now uses
the decimal positional number system. He is also known for
"The Compendious Book on Calculation by Completion and Balancing"
which he wrote in year AD 820. There he provided
the first detailed rules for solving linear and quadratic equations.
The word "Algebra" is derived from al-jabr, one of the two operations
he used for solving quadratic equations. This rules are also the earliest
example of what we call an algorithm. The word "algorithm" itself
stems from his Latinized name Algoritmi.
An algorithm is a sequence of simple steps that can be executed
mechanically to achieve a specific goal. No creativity or thinking
should be necessary for the successful accomplishment of the goal.
The beginning of modern computing started with Charles Babbage's
design of the first mechanical computer (the difference engine) in 1822.
It was supposed to driven by steam power and to be able to compute polynomial
functions. This was very important because until then all computations
were done by human computers who tend to make mistakes. This is a
problem when for instance these computations are needed for
the accurate navigation of a ship. Charles Babbage's proposed and
designed his difference engine to automatize the task and to avoid
errors. Unfortunately he never finished a working prototype.
Following the original plans, the Computer History museum
in Mountain View built the real engine:
The first working computer was designed and built in 1939
during World War II by Alan Turing: It was used to decode the encripted messages from the German Enigma machine.
The contemporary computers are orders of magnitutes smaller and faster
but they still follow the same fundamental principles set by Turing.
Both Babbage's and Turing's machines are mechanical, but modern
computers are electronic. They are composed of billions of tiny
electronic components which are orchestrated together to perform
a computation. Another difference is that while the Babbage's engine
was designed to compute directly with decimal numbers, modern
computers use a different representation for numbers called binary numbers.
The reason is that if we want to perform decimal arithmetics, we
would need electrical circuits that can reliably represent ten different
states, i.e. one for each possible digit. This is possible but
a lot more difficult and more expensive. It turns out that everything
is a lot simple if we can compute with only two digits 0 and 1.
In the circuits, this is represented as a signal with either high
or low electrical potential. For example the following
picture illustrates how a sequence of zeros and ones can be represented
with a electrical signal:
If the current digit is 0 then for a fixed period of time
the signal has low potential. Similarly if the digit is 1 then
the potential is high (usually +5 V). A digit that can be only
0 or 1 is called bit (from Binary digIT). By convention a sequence
of eight bits is also called byte.
Every decimal number is representable as a binary number and vice versa.
There is a simple conversion. From basic school we know that
a number like 97 is equal to the sum of its digits weighted with
the powers of ten, i.e.
97 = 9 * 101 + 7 * 100.
The same holds for binary numbers except that we should use
the powers of two instead of ten. Take for instance the binary number
"01100001". Its value is:
0*27 + 1*26 + 1*25 + 0*24 + 0*23 + 0*22 + 0*21 + 1*20 =
1*64 + 1*32 + 1*1 =
97
This means that "01100001" is the binary representation of
the decimal number 97. The reverse conversion is also possible.
If we want to convert 97 to a binary number then we can use the
gready method. Find the highest power of two which is smaller than
97, i.e. 64=26. This means that the bit at position 6
must be one. Substract 64 from 97, we get 97-64=33. This time
the highest power of two smaller than 33 is 32=25 -
we should have bit 1 at position 5. Finally 33-32=1, the highest
power is 20=1 and we set the bit at position 0 to one.
Since 1-1=0 there are no more non-zero bits. We just have to set
all bits other bits to zero.
The usual arithmetic operations can be performed on binary numbers as
well as on decimal numbers. All arithmetics on a computer are done
with binary numbers. Only when a numbers needs to be printed
on the screen then for human convenience the number is converted
to a decimal number.
In programming we can model everything if we could represent it
with numbers.
This was first realized by Ada Lovelace, the first computer programmer,
who wrote:
[The Analytical Engine] might act upon other things besides number, were objects found whose mutual fundamental relations could be expressed by those of the abstract science of operations, and which should be also susceptible of adaptations to the action of the operating notation and mechanism of the engine...
Supposing, for instance, that the fundamental relations of pitched sounds in the science of harmony and of musical composition were susceptible of such expression and adaptations, the engine might compose elaborate and scientific pieces of music of any degree of complexity or extent.
For example, we can represent text if we assign a numeric code to each
letter of the alphabet. The code for the letter
'a', for instance, is 97 in the Unicode standard. A string of text is then just a sequence of
numbers. We could also represent pictures if we assign different
numbers for all possible colours. A picture then is a matrix of
numbers where each number represents the colour of the corresponding
pixel.
At a glance the architecture of a computer consists of two main
components the Central Processing Unit (CPU)
and the memory:
The CPU is the component that do all computations.
The memory is nothing else but a sequence of cells where each cell
can store a number. The cells are identified by their address (location).
For example in the picture, the cell with address 0 currently
contains the number "10001010". During the computations, the different
cells in the memory can change their values.
What exactly needs to be computed is also stored in the memory.
The CPU reads a sequence of instructions encoded as numbers and
depending on the current instruction it performs a different operation.
A typical instruction might be to read the numbers stored
in two different cells and to store their sum in another cell.
A more realistic computer architecture would include
several external devices in addition to the CPU and the memory.
For example there might be a computer display, a keyboard,
a hard drive, a network adapter, or some other devices:
It is still the CPU that performs the computations but now it
can communicate with more devices by sending or receiving information
from them. All the communication is again represented as a stream of
binary numbers.
Programming on the level of instructions and binary numbers is very tedious.
Fortunately this is no longer necessary. Nowadays, a typical programmer
uses a high-level programming language which makes programming easier
and abstracts away from many low-level details. The high-level program
is easier to understand for humans, but it is harder to execute by a computer.
For that reason the high-level program first needs to be translated
to a low-level sequence of instructions. This is done by using another
program which is called "compiler". The compiler takes the text of
the program and generates instructions that can be efficiently executed
by the CPU.
It is also possible to execute the high-level program
directly. In that case the execution is not
done directly by the CPU but by using a special program
called "interpreter". The interpreter can read the high-level code and it
knows how to interpret it. This is usually less efficient, but is still used for
some programming languages.
This is how a typical high-level program might look like:
x = 14
x = x + 1
Instead of machine level instructions it consists of a sequence
of high-level human readable commands (or statements as we also call them).
On that level we are allowed to use usual mathematical operations
like "+" and "-" to perform computations. We can also use the more
usual decimal numbers. More importantly, we don't have to work with
memory adresses directly. Instead we use symbolic variable names like "x".
A variable is nothing else but a human-readable name for a
memory location. Since in most cases the exact address
is irrelevant for us, we just let the compiler to allocate
an arbitrary address to it. The first line uses the operator "=",
which causes the number 14 to be stored in the memory cell
for the variable x. It is important to remember that unlike in
math, where "=" indicates equality, here, the same symbol is used
to change the value of a variable. To the left of the operator
there is a variable name and to the right an expression.
The expression is computed and its value is assigned to the variable.
For example, the second line contains the expression "x + 1".
This means that we must read the current value of x and then add one.
The final result is then stored back in x. At the end the new value for x will be 15.
This short video explains the assignment statement nicely:
Remember that we always execute all statements in a program sequentially
from top to bottom. If the same program was written directly
as a sequence of instructions, then each of the lines may correspond
to several instructions. Moreover, we would be expected to code
the program as a sequence of zeros and ones.
There are many different
programming languages with different strenghts and weaknesses. In
this course we will use the programming language called Java.
Java is also a high-level programming language which is
compiled to a sequence of instructions. This instructions,
however, are not the instructions that are executed by the CPU.
Instead this are instructions for an abstract machine called JVM
(Java Virtual Machine). In order to execute them
we still need an interpreter which can read and interpret them.
In that sense Java has a hybrid model which uses both a compiler
and an interpreter. The advantage of this solution is that
one and the same Java program can be run of different
computer architectures as long as there is a JVM interpreter
for it. The modern Java implementations can also use a just-in-time
compiler (JIT) instead of an interpreter. The role of the JIT is to
convert the JVM instructions to instructions for the actual
CPU just before the actual code needs to be executed. This
still allows platform independent Java programs but at the same
time it offers the speed of natively compiled programs.
Exercises
What will be the final values of variables A and B after executing
the program:
