Transcript Prezentace

Department of Computer Science
Faculty of Civil Engineering, Brno University of Technology
Information Technology 2
Software (introduction),
Data Representation
1
Basic Definitions
• Algorithm – a finite ordered set of well-defined
rules for the solution of a problem.
• Program – a specific set of ordered operations
for a computer to perform.
• Programming language – an artificial language
for expressing programs (Pascal, C, C++, Java,
VisualBasic, Fortran, …).
• Instruction – order given to a computer
processor by a computer program.
• Assembly language – the native language of
a microprocessor.
2
Algorithm
The word algorithm derives from the name of the
Arabic mathematician Abu Ja'far Muhammad
ibn Musa al-Khwarizmi (about 780 – 850).
Al-Khwarizmi wrote on Hindu-Arabic
numerals and was the first to use
zero as a place holder in positional
base notation.
There are two standard ways
to represent an algorithm:
pseudocode and flowchart.
3
4
Flowchart – an example
YES
NO
Does the thing
work?
YES
Don‘t mess with it
PROBLEM SOLVING
FLOWCHART
Did you mess
with it?
NO
You fool
NO
Does anyone
know?
Hide it
Has this been
successful?
YES
No problem
Will you catch
hell?
YES
YES
NO
NO
You poor fool
Can you blame
someone else?
YES
NO
Trash it
START
x! = 1  2  …  (x – 1)  x
a=1
5! = 1  2  3  4  5 = 120
f=1
Corresponding C code:
a5
YES
f=f·a
a=a+1
NO
a = 1;
STOP
Program
Flowchart
Algorithm, Program (in C) – factorial
5
f = 1;
while (a <= 5)
{
f = f * a;
a = a + 1;
}
At the end of the program's execution, the variable f contains the value 120.
6
Set of Assembly Language Instructions
(dummy example)
LOADA mem
LOADB mem
CONB con
SAVEB mem
SAVEC mem
ADD
SUB
MUL
DIV
COM
JUMP addr
JEQ addr
JNEQ addr
JG addr
JGE addr
JL addr
JLE addr
STOP
-
Register A
Register B
Register C Reg. Test
Load register A from memory address
Load register B from memory address
Load a constant value into register B
Save register B to memory address
Memory
Save register C to memory address
Add A and B and store the result in C
Subtract A and B and store the result in C
Multiply A and B and store the result in C
Divide A and B and store the result in C
Compare A and B and store the result in Test
Jump to an address
Jump, if equal, to address
Jump, if not equal, to address
Jump, if greater than, to address
Jump, if greater than or equal, to address
Jump, if less than, to address
Jump, if less than or equal, to address
Stop execution
Assembly Language – factorial
A C compiler translates the C code into assembly language:
// Assume a is at address 128
// Assume f is at address 129
0
CONB 1
// a = 1;
1
SAVEB 128
2
CONB 1
// f = 1;
3
SAVEB 129
4
LOADA 128
// if a > 5 then jump to 17
5
CONB 5
6
COM
7
JG 17
8
LOADA 129
// f = f * a;
9
LOADB 128
10 MUL
11 SAVEC 129
12 LOADA 128
// a = a + 1;
13 CONB 1
14 ADD
15 SAVEC 128
16 JUMP 4
// loop back to if
17 STOP
(dummy example)
a = 1;
f = 1;
while (a <= 5)
{
f = f * a;
a = a + 1;
}
7
Data Representation
NUMERICAL DATA – NUMBERS
• integers
• real numbers
– fixed point
– floating point
NONNUMERICAL DATA – CHARACTERS
• string – sequence of characters
8
Number Systems
Each positive integer (natural number) can be written
in the polynomial form
an  bn + an-1  bn-1 + … + a0  b0 ,
where b is an integer greater than 1 – the base (radix)
of the number system,
and coefficients ai are natural numbers – the digits
of the number system, 0  ai  b.
The shortened notation is usually used:
(anan-1 … a0)b, or
anan-1 … a0.
To avoid confusion, we often use a suffix (subscript)
to indicate the number base.
9
10
Decimal Number System
• base = 10
• uses ten digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
• we are familiar with decimal number representation
• numbers are expressed by ones (100),
tens (101), hundreds (102), thousands (103), etc.
• for example, the number 6307 can be expressed as:
6307
6  1000 + 3  100 + 0  10 +
6  103 + 3  102 + 0  101 +
71
7  100 = 6307,
thus a3  b3 + a2  b2 + a1  b1 + a0  b0, where b = 10 (base),
a0 = 7, a1 = 0, a2 = 3, a3 = 6, a4, a5, a6, … = 0 (digits)
Binary Number System
11
• base = 2
• uses two digits (0, 1)
• in computers best used
• the decimal number 11 can be expressed as the binary
number 1011:
1  23 + 0  22 + 1  21 + 1  20
1  8 + 0  4 + 1  2 + 1  1 = 11 … decimal
(1011)2 = (11)10
Hexadecimal Number System
• base = 16
• uses sixteen digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A,
B, C, D, E, F), where letters A, B, C, D, E, F
correspond to numbers 10, 11, 12, 13, 14, 15
• used for convenience while using binary numbers
• the decimal number 967 can be expressed as
the hexadecimal number 3C7:
3  162 + C  161 + 7  160
3  256 + 12  16 + 7  1
= 967 … decimal
(3C7)16 = (967)10
12
Conversions among Number Systems
13
Example: Convert the decimal numbers 10 a 23
to binary.
Divide the number by 2, then divide what's left by 2,
and so on until there is nothing left (0). Write down
the remainder (which is either 0 or 1) at each division
stage.
result after remadivision by 2 inder
10 : 2 = 5
0
5:2=2
1
2:2=1
0
1:2=0
1
(10)10 = (1010)2
result after remadivision by 2 inder
23 : 2 = 11
1
11 : 2 = 5
1
5:2= 2
1
2:2= 1
0
1
(23)10 = (10111)2 1 : 2 = 0
Conversions among Number Systems
14
Example: Convert the binary number 101110
to decimal.
The binary number 101110 can be expressed as
1  25 + 0  24 + 1  23 + 1  22 + 1  21 + 0  20
1  32 + 0  16 + 1  8 + 1  4 + 1  2 + 0  1 = 46
(101110)2 = (46)10
Conversions among Number Systems
Example: Convert the decimal number 586
to hexadecimal.
First, convert the decimal number 586 to binary. Each
hexadecimal digit represents 4 bits. Split the binary
number into groups of 4 bits, starting from the right
(the least significant) bit. Convert each group of 4 bits
into the corresponding hexadecimal digit.
…
10 = A,
13 = D,
…
11 = B,
14 = E,
…
12 = C,
15 = F.
15
Conversions among Number Systems
result after
division by 2
remainder
586 : 2 = 293
293 : 2 = 146
146 : 2 = 73
0
1
0
73 : 2 = 36
1
36 : 2 = 18
18 : 2 = 9
9:2= 4
0
0
1
4:2=
2:2=
1:2=
2
1
0
0
0
1
(586)10 = (1001001010)2
10 0100 1010
0010 0100 1010
2
4
10
2
4
A
(586)10 = (24A)16
16
Conversions among Number Systems
Example: Convert the hexadecimal number 2AC7
to decimal.
Express the number (2AC7)16 in the form:
2  163 +
A  162 + C  161 + 7  160
2  163 + 10  162 + 12  161 + 7  160
2  4096 + 10  256 + 12  16 + 7  1 = 10951
(2AC7)16 = (10951)10
Hexadecimal numbers are often written in the form:
3BCh
$2AF
… in Turbo Pascal
0x7AF2
… in C, JavaScript
17
Conversions among Number Systems
Dec.
Bin.
Hex.
Dec.
Bin.
Hex.
Dec.
Bin.
Hex.
0
00000000
0
16
00010000
10
32
00100000
20
1
00000001
1
17
00010001
11
33
00100001
21
2
00000010
2
18
00010010
12
34
00100010
22
3
00000011
3
19
00010011
13
35
00100011
23
4
00000100
4
20
00010100
14
36
00100100
24
5
00000101
5
21
00010101
15
37
00100101
25
6
00000110
6
22
00010110
16
38
00100110
26
7
00000111
7
23
00010111
17
39
00100111
27
8
00001000
8
24
00011000
18
40
00101000
28
9
00001001
9
25
00011001
19
41
00101001
29
10
00001010
A
26
00011010
1A
42
00101010
2A
11
00001011
B
27
00011011
1B
43
00101011
2B
12
00001100
C
28
00011100
1C
44
00101100
2C
13
00001101
D
29
00011101
1D
45
00101101
2D
14
00001110
E
30
00011110
1E
46
00101110
2E
15
00001111
F
31
00011111
1F
47
00101111
2F
18
ASCII Table
19
• American Standard Code for Information Interchange
• a standard character set defined in 1968 (by ANSI)
• in its original form 7-bit (27 = 128 characters),
today 8-bit (28 = 256 characters)
• only the first 128 characters (0 – 127) are common
among all computers – basic part
• the upper half of the ASCII table is dependent on
regional settings (accented and additional characters)
– so-called extended part (characters 128 – 255)
• to enter a character that your PC keyboard does not
have, while pressing down the left ALT key, enter the
ASCII code with the number keys in the number key
pad section. When you release the ALT key, the
character is entered (character "@": ALT + 64).
ASCII Table – Basic Part (0 – 127)
20
ASCII tabulka – problémy s češtinou
21
• pro češtinu existuje několik způsobů kódování
(znakových sad):
• ISO-8859-2 (ISO Latin 2)
• Windows 1250 (CP1250)
• CP852 (PC Latin 2)
• bratří Kamenických
• KOI8-CS
• ...
• všechny tyto znakové sady se liší horní polovinou
ASCII tabulky (znaky 128 – 255) a nejsou tedy
navzájem kompatibilní
• další zajímavé informace naleznete na www.cestina.cz
ASCII Table – Significancy
• code page Windows 1250
22
• each character is represented as one byte
• end of line – two
characters: CR, LF
23
ASCII Art
• making pictures using ASCII characters only
• funny "ASCII-SMS"
ASCII–SMS
Unicode
24
www.unicode.org
• a 16-bit character encoding standard
• contains all of the characters (216= 65 536 different
characters) in common use in the world’s written
languages, including
Russian, Japanese etc.
• includes a large set of
technical symbols, math
operators and so on
• problems with the
backward (8-bit)
compatibility
Unicode – Significancy
• in Notepad, select Unicode while saving the file
• one character ~ two bytes
25
References
26
• Precht, M. – Meier, N. – Kleinlein, J.:
EDV-Grundwissen: Eine Einführung in Theorie und
Praxis der modernen EDV. Addison-Wesley, 1996.
• Hlavenka, J. a kol.: Výkladový slovník výpočetní
techniky a komunikací. Computer Press, Praha, 1997.
• http://www.asciitable.com
• http://www.unicode.org
• http://www.cestina.cz