INFORMATICS 1
4. COMPUTERS, ALGORITHMS
AND SOFTWARE
Wolfgang Schauer 1
4. COMPUTERS, ALGORITHMS AND SOFTWARE
The relationship between tasks, computers, algorithms and software
The task The algorithm
The task is analysed and one or more algorithms are invented, which are
able to do the required job.
The algorithm depends strongly on the task. There can be many
approaches for suited algorithms.
The algorithm is
converted into
software code.
The complexity of The concrete
the task decides implementation
on the depends on the
specifications of programming
the machine. Not language,
all computers can however, (most
do all jobs. probably) all
programming
In the past, programming language and computers depended strongly languages could
on each other. However, modern computers can interpret a variety a be used.
languages (on the higher levels) and some high level software layers are
completely independent of the used machine. Nevertheless, each
processor can only understand its machine code (which represents the
lowest level).
The machine The software
(aka computer) (often layered)
Wolfgang Schauer 2
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.1 John von Neumann, Principles, Architecture
John von Neumann Principles
a. Data and instructions are both stored in main memory (stored program concept).
b. The content of the memory is addressable by its location.
c. Instructions are executed sequentially, i.e. from one instruction to the next, unless
the order is explicitly modified.
d. The organization (architecture) consists of:
The central processing unit (CPU) containing: the control unit (CU) which
coordinates the execution of instructions, and the arithmetic / logic unit (ALU)
which performs all arithmetic and logical operations, the main memory (RAM).
e. Computers are general-purpose computers. They can solve different problems
depending on the program they execute.
John von Neumann (1903 – 1957)
Wolfgang Schauer 3
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.1 John von Neumann, Principles, Architecture
Basic Components of a Computer, Von-Neumann-Architecture
Bus
CU Input/Output
Main Memory
Control Unit
Keyboard
Screen
Printer
Mass Storage Device …
ALU
Arithmetic Logic Unit
Registers
CPU
Central Processing Unit
Wolfgang Schauer 4
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.2 Processing an „Assembly Language“ Program
Machine code (just a very simple example)
Source:
Op-Code Operand Description
J.1Glenn Brookshear: Computer Science
RXY LOAD–the
Anregister
Overview, 11th
R with ed,pattern
the bit Addison-Wesley, 2010 cell whose address is XY.
found in the memory
2 RXY LOAD the register R with the bit pattern XY.
3 RXY STORE the bit pattern found in register R in the memory cell whose address is XY.
4 0RS MOVE the bit pattern found in register R to register S.
5 RST ADD the bit patterns in registers S and T as though they were two’s complement representations and leave the
result in register R.
6 RST ADD the bit patterns in registers S and T as though they represented values in floating-point notation and leave
the floating-point result in register R.
7 RST OR the bit patterns in registers S and T and place the result in register R.
8 RST AND the bit patterns in registers S and T and place the result in register R.
9 RST EXCLUSIVE OR the bit patterns in registers S and T and place the result in register R.
A R0X ROTATE the bit pattern in register R one bit to the right X times. Each time place the bit that started at the low-
order end at the high-order end.
B RXY JUMP to the instruction located in the memory cell at address XY if the bit pattern in register R is equal to the bit
pattern in register number 0. Otherwise, continue with the normal sequence of execution. (The jump is
implemented by copying XY into the program counter during the execute phase.)
C 000 HALT execution.
Wolfgang Schauer 5
4. COMPUTERS, ALGORITHMS AND SOFTWARE Source:
J. Glenn Brookshear: Computer Science – An Overview, 11th ed, Addison-Wesley, 2010
4.2 Processing an „Assembly Language” Program
Task: adding two numbers and store the result…
1. Load a value from the memory (position 13) into register 0
2. Load another value from the memory (position 14) into register 1
3. Add the two registers (assuming we have two-complement data) and leave the result in register 0
4. Store the result in another memory position (position 15)
5. End the programm
Wolfgang Schauer 6
4. COMPUTERS, ALGORITHMS AND SOFTWARE Source:
J. Glenn Brookshear: Computer Science – An Overview, 11th ed, Addison-Wesley, 2010
4.2 Processing an „Assembly Language” Program
All commands consist of op-code and operand
Wolfgang Schauer 7
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.2 Processing an „Assembly Language” Program
Part 1
Source: Bus
00 LOAD REG0 13 CU
J.02
GlennLOAD
Brookshear: Computer Science – An Overview, 11th ed, Addison-Wesley, 2010 Input/Output
REG1 14 Control Unit
04 ADD REG0 REG0 REG1
06 STORE REG0 15
08 HALT REG Register
IR Instruction Register
ALU
13 4 MAR Memory Address Register
Arithmetic Logic Unit MDR Memory Data Register
14 2 PC Program Counter
15 …
FE … REG 0 - F
FF …
IR
MAR
MDR
PC
CPU … Central Processing Unit
Memory
Wolfgang Schauer 8
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.2 Processing an „Assembly Language“ Program
Part 1
Source: Bus
00 1 0 1 3 CU
J.02
Glenn1Brookshear: Computer Science – An Overview, 11th ed, Addison-Wesley, 2010 Input/Output
1 1 4 Control Unit
04 5 0 0 1
06 3 0 1 5
08 C 0 0 0 REG Register
IR Instruction Register
ALU
13 0 4 MAR Memory Address Register
Arithmetic Logic Unit MDR Memory Data Register
14 0 2 PC Program Counter
15 …
REG 0 - F
FE … IR
FF …
MAR
MDR
PC
CPU … Central Processing Unit
Memory
Wolfgang Schauer 9
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.2 Processing an „Assembly Language“ Program
Part 1
00
Source: 0001 0000 Bus
01 0001 0011 CU
J.02
Glenn0001
Brookshear: Computer Science – An Overview, 11th ed, Addison-Wesley, 2010 Input/Output
0001 Control Unit
03 0001 0100
04 0101 0000
05 0000 0001 REG Register
06 0011 0000 IR Instruction Register
ALU
07 0001 0101 MAR Memory Address Register
Arithmetic Logic Unit MDR Memory Data Register
08 1100 0000 PC Program Counter
09 0000 0000
13 0000 0100 REG 0 - F
14 0000 0010
15 … IR
MAR
FE … MDR
FF …
PC
CPU … Central Processing Unit
Memory
Wolfgang Schauer 10
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.2 Processing an „Assembly Language“ Program
Instruction Cycle
1. Fetch an instruction from the memory at the address pointed to by the Program Counter (PC). Store this instruction in the
Instruction Register (IR).
2. Increment the value stored in the PC to point to the next instruction in the sequence of instructions to be executed (so in our case
by two counts as our op-code plus operand have two byte!).
3. Decode the instruction in the IR to determine the operation to be performed and the addressing modes of the operands.
4. Calculate any address values needed to determine the locations of the source operands and the address of the destination.
5. Read the values of the source operands.
6. Perform the operation specified by the op-code.
7. Store the results at the destination location.
8. Go to Step 1 to repeat this entire process for the next instruction.
Wolfgang Schauer 11
4. COMPUTERS, ALGORITHMS AND SOFTWARE Source:
J. Glenn Brookshear: Computer Science – An Overview, 11th ed, Addison-Wesley, 2010
4.2 Processing an „Assembly Language“ Program
The Machine Cycle
Wolfgang Schauer 12
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.2 Processing an „Assembly Language“ Program
STEP 00
00 0001 0000 Bus
01 0001 0011 CU
Input/Output
02 0001 0001 Control Unit
03 0001 0100
04 0101 0000
05 0000 0001 REG Register
06 0011 0000 IR Instruction Register
ALU
07 0001 0101 MAR Memory Address Register
Arithmetic Logic Unit MDR Memory Data Register
08 1100 0000 PC Program Counter
09 0000 0000
13 0000 0100 0000
REG 00100
–F REG 0
14 0000 0010
15 … IR REG 1
0001 0000 0001 0011
MAR IR
FE … 0001 0011
MDR MAR
FF …
0000PC0100 MDR
02 PC
Memory
Wolfgang Schauer 13
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.2 Processing an „Assembly Language“ Program
STEP 01
00 0001 0000 Bus
01 0001 0011 CU
Input/Output
02 0001 0001 Control Unit
03 0001 0100
04 0101 0000
05 0000 0001 REG Register
06 0011 0000 IR Instruction Register
ALU
07 0001 0101 MAR Memory Address Register
Arithmetic Logic Unit MDR Memory Data Register
08 1100 0000 PC Program Counter
09 0000 0000
13 0000 0100 0000
REG 00100
–F REG 0
14 0000 0010
15 … 0000IR0010 REG 1
0001 0001 0001 0100
MAR IR
FE … 0001 0100
MDR MAR
FF …
0000PC0010 MDR
04 PC
Memory
Wolfgang Schauer 14
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.2 Processing an „Assembly Language“ Program
STEP 02
00 0001 0000 Bus
01 0001 0011 CU
Input/Output
02 0001 0001 Control Unit
03 0001 0100
04 0101 0000
05 0000 0001 REG Register
06 0011 0000 IR Instruction Register
ALU
07 0001 0101 MAR Memory Address Register
Arithmetic Logic Unit MDR Memory Data Register
08 1100 0000 PC Program Counter
09 0000 0000
13 0000 0100 0000
REG 00110
–F REG 0
14 0000 0010
15 … 0000IR0010 REG 1
0101 0000 0000 0001
MAR IR
FE … MDR MAR
FF …
PC MDR
06 PC
Memory
Wolfgang Schauer 15
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.2 Processing an „Assembly Language“ Program
STEP 03
00 0001 0000 Bus
01 0001 0011 CU
Input/Output
02 0001 0001 Control Unit
03 0001 0100
04 0101 0000
05 0000 0001 REG Register
06 0011 0000 IR Instruction Register
ALU
07 0001 0101 MAR Memory Address Register
Arithmetic Logic Unit MDR Memory Data Register
08 1101 0000 PC Program Counter
09 0000 0000
13 0000 0100 0000
REG 00110
–F REG 0
14 0000 0010
15 0000 0110 0000IR0010 REG 1
0011 0000 0001 0101
MAR IR
FE … 0001 0101
MDR MAR
FF …
0000PC0110 MDR
08 PC
Memory
Wolfgang Schauer 16
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.2 Processing an „Assembly Language“ Program
STEP 04
00 0001 0000 Bus
01 0001 0011 CU
Input/Output
02 0001 0001 Control Unit
03 0001 0100
04 0101 0000
05 0000 0001 REG Register
06 0011 0000 IR Instruction Register
ALU
07 0001 0101 MAR Memory Address Register
Arithmetic Logic Unit MDR Memory Data Register
08 1100 0000 PC Program Counter
09 0000 0000
13 0000 0100 0000
REG 00110
–F REG 0
14 0000 0010
15 0000 0110 0000IR0010 REG 1
1100 0000 0000 0000
MAR IR
FE … MDR MAR
FF …
PC MDR
10 PC
Memory
Wolfgang Schauer 17
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.2 Processing an „Assembly Language“ Program
Program vs. Data
• Note again (1st von Neumann principle): data and program are not distinguishable. They both consist of 1s and 0s
• It is used as program, if it is fetched into the instruction register and then interpreted
• Data can therefore turn into “program code” if the program counter approaches fields containing data
• This can lead to random actions
Wolfgang Schauer 18
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.3 Algorithms
Definition of Algorithm
“Note that the definition requires that the set of steps in an algorithm be
ordered in terms of the order of their execution …
An algorithm must consist of executable steps. Computer scientists use the
term effective. That is, to say a step is effective means that it is doable.
… an algorithm is an ordered set of
The information in the state of the process must be sufficient to determine
uniquely and completely the actions required by each step. In other words, the unambiguous, executable steps that defines a
execution of each step does not require creative skills (and there is no element terminating process.
of chance).
Eventually the execution of an algorithm must lead to an end (and should be
as generic as possible).”
Wolfgang Schauer 19
4. COMPUTERS, ALGORITHMS AND SOFTWARE Source:[Link]
[Link]/originals/a1/42/03/[Link]
4.3 Algorithms
An Old Coffee Machine: Braun KF 21 Aromaster, 1976
Dust Cover
Water Reservoir
Lighted On/Off Switch
Filter Basket
Jug
Cup Markings
Warming Plate
Wolfgang Schauer 20
4. COMPUTERS, ALGORITHMS AND SOFTWARE Source: [Link]
4.3 Algorithms
Programmable Calculator: Commodore PR 100, 1978
Wolfgang Schauer 21
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.3 Algorithms
Algorithm Primitives – Recurring Semantic Structures
Procedure procedure name ( parameters )
… gives an algorithm a name so that it can be referenced. Parameters are controlling the algorithm.
Assignment name ← expression
Saving of computed values not using the address in main memory but a symbolic name.
Selection if ( condition ) then ( activity )
Decision if an activity should happen or not; “if true then do!”.
if ( condition ) then ( activity )
else ( activity )
Decision between two options.
Loop while ( condition ) do ( activity )
Repeating an activity as long as the condition is true.
Wolfgang Schauer 22
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.3 Algorithms
Algorithm Representation
As long as the value of neither X nor Y is zero,
…continue dividing the larger of the values by the
smaller and assigning X and Y the values of the
divisor and remainder, respectively.
The final value of X is the greatest common divisor.
Wolfgang Schauer 23
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.3 Algorithms
Algorithm Representation
Wolfgang Schauer 24
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.3 Algorithms
Algorithm Representation
Wolfgang Schauer 25
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.3 Algorithms
Computer Science or Is There an Algorithm to Find Arithmetic Algorithms?
Wolfgang Schauer 26
4. COMPUTERS, ALGORITHMS AND SOFTWARE
4.3 Algorithms
Self-reference
Theorem, 1931
An Homage to Kurt Gödel‘s Incompleteness
The
Statement
Below
Is False
The
Statement
Above
Is True
Wolfgang Schauer 27