Transcript chapter1

Intro to Computer Science I
Chapter 1
Introduction to Computation
Algorithms, Processors, and Programs
1
Algorithm



BGA
A sequence of unambiguous steps for
accomplishing some task or process.
In theory an algorithm can have an infinite
number of steps but in practice algorithms
must have a finite number of steps.
Example: calculating 2 requires an infinite
number of steps (infinite non-repeating
decimal expansion).
2
Finite Algorithm for 2
x0  1
x1  ( x0  2 / x0 ) / 2
x2  ( x1  2 / x1 ) / 2
x3  ( x2  2 / x2 ) / 2
x4  ( x3  2 / x3 ) / 2
x5  ( x4  2 / x4 ) / 2
RETURN x5
BGA
3
Processor


BGA
Any device, calculator, computer, virtual
machine, or human being that can process
or execute an algorithm.
Each type of processor understands a
language (e.g., machine language) and
algorithms must be expressed in this
language in order for the processor to be
able to execute them.
4
Memory words, addresses
Memory words contain
data. Each memory word
has an address which is
used to locate this data. A
common size for a word is
8 bits (byte). One or more
bytes is required to store
each data item (an integer
for example) or machine
language instruction.
BGA
Addresses
Memory Words
0001100...000
11100111
0001100...001
00000110
0001100...010
01011101
0001100...011
10010010
0001100...100
01110111
0001100...101
10100000
5
Block diagram of a computer
Registers
Main Memory
Input
Devices
Control Unit
Secondary
Memory
Output
Devices
ALU
BGA
6
Program


BGA
A representation of an algorithm as a
sequence of instructions that can be
understood and executed by a processor to
complete the task, problem or process
described by the algorithm.
For a CPU the program is a sequence of
machine language instructions stored in
memory in binary form
7
Computer Languages


Machine language (Lowest level)
Assembly language


High level language


BGA
mnemonic form of machine language
C, C++, Java
Closer to the human level of problem solving
8
An addition problem

BGA
Pseudo-code
i  6
j  7
k  511
sum  i + j + k
(assign
(assign
(assign
(assign
6 to i)
7 to j)
511 to k)
sum to sum)
9
Machine Language (PC)

Following string of 112 bits
1010
0011
0000
0100
BGA
0001
0000
0011
1010
0000
0110
0000
0011
0000
0000
0110
0000
0000
0000
0000
0000
0000
0000
0000
0000
0000
0010
0000
0110
10
Assembly language (PC)
BGA
mov
add
add
mov
ax, i
ax, j
ax, k
sum, ax
i
j
k
sum
dw
dw
dw
dw
6
7
511
0
11
Java, C++
int
int
int
int
BGA
i =
j =
k =
sum
6;
7;
511 ;
= i + j + k;
12
The compilation process
High Level Language
Program Source Code
Compiler
Machine Language
Program Object Code
The compiler translates the high level language source
code program into a machine language object code
program that can be understood by the computer's CPU.
BGA
13
The interpretation process
High Level Language
Program Source Code
Statement
Interpreter
Back for next statement
The interpreter translates one statement at a time and has it
executed by the CPU before returning to translate another
statement
BGA
14
The Java Virtual Machine
(a)
Java Source Code
(b)
Bytecode
(class file)
Java Compiler
Java Interpreter
Bytecode
(class file)
Java Virtual Machine
Real Machine
BGA
15
Java translation example
BGA
Assembly
Language
Bytecode
(hexadecimal)
Bytecode
(binary)
bipush 6
istore_1
bipush 7
istore_2
sipush 511
istore_3
iload_1
iload_2
iadd
iload_3
iadd
istore 4
10
3C
10
3D
11
3E
1B
1C
60
1D
60
36
0001
0011
0001
0011
0001
0011
0001
0001
0110
0001
0110
0011
06
07
01 FF
04
0000
1100
0000
1101
0001
1110
1011
1100
0000
1101
0000
0110
0000 0110
0000 0111
0000 0001 1111 1111
0000 0100
16