Algoritmy a datové struktury

Úvod Základní datové struktury Celá čísla Reálná čísla Znaky Konec Konec

Algoritmy a datové struktury Data a datové typy

1 / 28


Obsah přednášky

I

Základní datové typy

I

Celá čísla

I

Reálná čísla

I

Znaky

2 / 28


Organizace dat

I

Výběr vhodné datvé struktry I I

I

různá paměťová náročnost různá časová náročnost

Datová struktura I I

data operace nad daty

3 / 28


Datové typy I

Data v počítači – pomocí bitů

I

Datové typy dávají bitům konkrétní význam Většina jazyků – standardní sada typů

I

I I I

I

celá čísla (integer) čísla s pohyblivou řádovou čárkou (floating point number) znaky (char)

Pro datové typy jsou definovány operace I I

výsledek operace nad konkrétním typem je konkrétního typu např. I

desetinné číslo / desetinné číslo = desetinné číslo

4 / 28


Datové typy I


I


I

I I I

I



výsledek operace nad konkrétním typem je konkrétního typu např. I I

desetinné číslo / desetinné číslo = desetinné číslo celé číslo / celé číslo = celé číslo

4 / 28


Datové typy I


I


I

I I I

I




I


zkuste si: I

System.out.println(5.0/2.0);

4 / 28


Datové typy I


I


I

I I I

I




I


zkuste si: I I

System.out.println(5.0/2.0); System.out.println(5.0/2);

4 / 28


Datové typy I


I


I

I I I

I




I


zkuste si: I I I

System.out.println(5.0/2.0); System.out.println(5.0/2); System.out.println(5/2); 4 / 28


Datové typy I

Pro reprezentaci konkrétního datového typu I I

I

pevný počet bitů – závisí naplatformě nepsaný standard

Typy

5 / 28


Datové typy I


I


Typy I

celočíslené I I I I

byte – 8 bitů short – 16 bitů int – 32 bitů long – 64 bitů

5 / 28


Datové typy I


I


Typy I


I

byte – 8 bitů short – 16 bitů int – 32 bitů long – 64 bitů

pohyblivá čárka I I I

norma IEEE 754 float – 32 bitů double – 64 bitů

5 / 28


Datové typy I


I


Typy I


I

pohyblivá čárka I I I

I

byte – 8 bitů short – 16 bitů int – 32 bitů long – 64 bitů norma IEEE 754 float – 32 bitů double – 64 bitů

znaky I I I

ne už tak standardní 8 bitů – problém s národními znaky 16 bitů – unicode 5 / 28


Dvojková soustava

I I

Výsledné číslo: c = an · 2n + an−1 · 2n−1 + · · · + a0 · 20 Příklad: 100101

6 / 28


Dvojková soustava

I I

Výsledné číslo: c = an · 2n + an−1 · 2n−1 + · · · + a0 · 20 Příklad: 100101 I

1 · 25 + 0 · 24 + 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20

6 / 28


Dvojková soustava

I I

Výsledné číslo: c = an · 2n + an−1 · 2n−1 + · · · + a0 · 20 Příklad: 100101 I I

1 · 25 + 0 · 24 + 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20 32 + 4 + 1

6 / 28


Dvojková soustava

I I

Výsledné číslo: c = an · 2n + an−1 · 2n−1 + · · · + a0 · 20 Příklad: 100101 I I I

1 · 25 + 0 · 24 + 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20 32 + 4 + 1 37

6 / 28


Dvojková soustava

I I


I

1 · 25 + 0 · 24 + 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20 32 + 4 + 1 37

Zkuste si I

1101b

6 / 28


Dvojková soustava

I I


I

1 · 25 + 0 · 24 + 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20 32 + 4 + 1 37

Zkuste si I

1101b = 11d

6 / 28


Dvojková soustava

I I


I

1 · 25 + 0 · 24 + 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20 32 + 4 + 1 37

Zkuste si I

1101b = 13d

6 / 28


Dvojková soustava

I I


I

1 · 25 + 0 · 24 + 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20 32 + 4 + 1 37

Zkuste si I I

1101b = 13d 1100b

6 / 28


Dvojková soustava

I I


I

1 · 25 + 0 · 24 + 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20 32 + 4 + 1 37

Zkuste si I I

1101b = 13d 1100b = 12d

6 / 28


Dvojková soustava

I I


I

1 · 25 + 0 · 24 + 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20 32 + 4 + 1 37

Zkuste si I I I

1101b = 13d 1100b = 12d 1011b

6 / 28


Dvojková soustava

I I


I

1 · 25 + 0 · 24 + 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20 32 + 4 + 1 37

Zkuste si I I I

1101b = 13d 1100b = 12d 1011b = 11d

6 / 28


Převod do dvojkové soustavy

I

Postupně dělit číslo číslem dvě I I

I

pokud je zbytek 1, zapsat 1 pokud je zbytek 0, zapsat 0

Příklad: číslo 10d =

7 / 28



I


I


Příklad: číslo 10d = I

0b

10/2 = 5(0)

7 / 28



I


I


Příklad: číslo 10d = I I

10b

10/2 = 5(0) 5/2 = 2(1)

7 / 28



I


I


Příklad: číslo 10d = 010b I I I

10/2 = 5(0) 5/2 = 2(1) 2/2 = 1(0)

7 / 28



I


I


Příklad: číslo 10d = 1010b I I I I

10/2 = 5(0) 5/2 = 2(1) 2/2 = 1(0) 1/2 = 0(1)

7 / 28



I


I


I

pokud je zbytek 1, zapsat 1 pokud je zbytek 0, zapsat 0 10/2 = 5(0) 5/2 = 2(1) 2/2 = 1(0) 1/2 = 0(1)

Zkuste si I

15d

7 / 28



I


I


I


Zkuste si I

15d = 1111b

7 / 28



I


I


I


Zkuste si I I

15d = 1111b 16d

7 / 28



I


I


I


Zkuste si I I

15d = 1111b 16d = 10000b

7 / 28



I


I


I


Zkuste si I I I

15d = 1111b 16d = 10000b 17d

7 / 28



I


I


I


Zkuste si I I I

15d = 1111b 16d = 10000b 17d = 10001b

7 / 28


Převod do hexadecimální soustavy

I

Z dvojkové soustavy I I

I

seskupit bity do čtveřic každá čtveřice představuje jednu hexadecimální cifru

Příklad I

5d = 0000 0101b = 05h

8 / 28



I


I


Příklad I I

5d = 0000 0101b = 05h 15d = 0000 1111b = 0Fh

8 / 28



I


I


Příklad I I I

5d = 0000 0101b = 05h 15d = 0000 1111b = 0Fh 16d = 0001 0000b = 10h

8 / 28



I


I

Příklad I I I

I

seskupit bity do čtveřic každá čtveřice představuje jednu hexadecimální cifru 5d = 0000 0101b = 05h 15d = 0000 1111b = 0Fh 16d = 0001 0000b = 10h

Zkuste si I

0d

8 / 28



I


I

Příklad I I I

I


Zkuste si I

0d = 00000000b

8 / 28



I


I

Příklad I I I

I


Zkuste si I

0d = 00000000b = 00h

8 / 28



I


I

Příklad I I I

I


Zkuste si I I

0d = 00000000b = 00h 128d

8 / 28



I


I

Příklad I I I

I


Zkuste si I I

0d = 00000000b = 00h 128d = 10000000b

8 / 28



I


I

Příklad I I I

I


Zkuste si I I

0d = 00000000b = 00h 128d = 10000000b = 80h

8 / 28



I


I

Příklad I I I

I


Zkuste si I I I

0d = 00000000b = 00h 128d = 10000000b = 80h 255d

8 / 28



I


I

Příklad I I I

I


Zkuste si I I I

0d = 00000000b = 00h 128d = 10000000b = 80h 255d = 11111111b

8 / 28



I


I

Příklad I I I

I


Zkuste si I I I

0d = 00000000b = 00h 128d = 10000000b = 80h 255d = 11111111b = FFh

8 / 28


Celá kladná čísla

I

Jaké tedy mohou být rozsahy celých kladných čísel I

na 8 bitech

9 / 28



I


na 8 bitech = 28

9 / 28



I


na 8 bitech = 28 = 256

9 / 28



I

Jaké tedy mohou být rozsahy celých kladných čísel I I

na 8 bitech = 28 = 256 na 16 bitech

9 / 28



I


na 8 bitech = 28 = 256 na 16 bitech = 210 · 26

9 / 28



I


na 8 bitech = 28 = 256 na 16 bitech = 210 · 26 = 1024 · 64 = 64k = 65 536

9 / 28



I

Jaké tedy mohou být rozsahy celých kladných čísel I I I

na 8 bitech = 28 = 256 na 16 bitech = 210 · 26 = 1024 · 64 = 64k = 65 536 na 32 bitech

9 / 28



I


na 8 bitech = 28 = 256 na 16 bitech = 210 · 26 = 1024 · 64 = 64k = 65 536 na 32 bitech = 230 · 22

9 / 28



I


na 8 bitech = 28 = 256 na 16 bitech = 210 · 26 = 1024 · 64 = 64k = 65 536 na 32 bitech = 230 · 22 = 4G = 4 294 967 296

9 / 28



I

Jaké tedy mohou být rozsahy celých kladných čísel I I I I

na na na na

8 bitech = 28 = 256 16 bitech = 210 · 26 = 1024 · 64 = 64k = 65 536 32 bitech = 230 · 22 = 4G = 4 294 967 296 64 bitech

9 / 28



I


na na na na

8 bitech = 28 = 256 16 bitech = 210 · 26 = 1024 · 64 = 64k = 65 536 32 bitech = 230 · 22 = 4G = 4 294 967 296 64 bitech = 260 · 24

9 / 28



I


na na na na

8 bitech = 28 = 256 16 bitech = 210 · 26 = 1024 · 64 = 64k = 65 536 32 bitech = 230 · 22 = 4G = 4 294 967 296 64 bitech = 260 · 24 = 6E = 18 446 744 073 709 551 616

9 / 28



I


I

na na na na


Jaký je tedy rozsah?

9 / 28



I


I

na na na na


Jaký je tedy rozsah? I

pro 8 bitů – 0. .255

9 / 28



I


I

na na na na


Jaký je tedy rozsah? I I

pro 8 bitů – 0. .255 pro 16 bitů – 0. .65355

9 / 28



I


I

na na na na


Jaký je tedy rozsah? I I I

pro 8 bitů – 0. .255 pro 16 bitů – 0. .65355 ...

9 / 28


Celá čísla

I

Co se zápornými čísly? I I I I

I

přímý kód kód s posunutou nulou doplňkový kód inverzní kód

Rozsah se zřejmě zmenší na polovinu

10 / 28


Přímý kód

I

Nejvyšší bit (první z leva) určuje znaménko

I

Zbytek čísla je normální dvojkové číslo

I

Nula lze teoreticky zapsat dvěma způsoby (+0, -0) Příklad

I

I I

I

5d = 00000101b −5d = 10000101b

Rozsah I I

1 1111111b = −127d 0 1111111b = 127d

11 / 28


Kód s posunutou nulou

I

K výslednému číslu se přičte hodnota I

I

Příklad I I I

I

Většinou polovina rozsahu 0d = 0 + 127 = 01111111b 5d = 5 + 127 = 10000100b −5d = −5 + 127 = 01111010b

Rozsah I I

11111111b = 255 − 127 = 128d 00000000b = 0 − 127 = −127d

12 / 28


Inverzní kód

I I

Kladná čísla beze změny Nekladná – doplněk do nejvyššího čísla I

I

Příklad I I I I

I

lze vyrobit bitovou inverzí 0d = 00000000b 5d = 00000101b −0d = 11111111b −5d = 11111010b

Rozsah I I

−127d = 10000000b 127d = 01111111b

13 / 28


Doplňkový kód

I I

Kladná čísla beze změny Nekladná – doplněk do nejvyššího čísla +1 I

I

Příklad I I I

I

lze vyrobit bitovou inverzí a přičíst 1 0d = 00000000b 5d = 00000101b −5d = 11111011b

Rozsah I I

−128d = 10000000b 127d = 01111111b

14 / 28


Zkuste si

I

I

Pomocí funkce DataOutputStream.writeByte zapsat do souboru několik různých hodnot Pomocí hexadecimálního prohlížeče si čísla prohlédnout I

I

http://www.simdesign.nl/binview.html

Zjistěte I I I I

maximální číslo minimální číslo jak lze zapsat 0 jaké kódování se používá

15 / 28


Semilogaritmický tvar

I

Vyjádření čísla: X = m · z e I I I

I

m – mantisa; přesnost čísla z – základ exponentu; v počítači je 2 e – exponent; rozsah čísla

Příklad I I I

3.1415 = 0.31415 · 101 = 314.15 · 10−2 0.0004 = 0.4 · 103 ...

16 / 28


Semilogaritmický tvar

I

Normalizovaný tvar mantisy I I

I

mantisa musí být 1 ≥ m < z odstaňuje nejednoznačnosti v zápisu

Vyjádřitelná čísla I

např. mantisa 3 řády a znaménko exponent 2 řády a znaménko základ 10

-9.99e2

-9.99e-2

0 9.99e-2

9.99e2

17 / 28


Jak to je s desetinným binárním číslem? I

Podobně jako s celým I

I

Převod I I I

I

jednotlivé řády i označují násobky 2−i číslo postupně násobíme 2 když je výsledek menší než 1, napíšeme 0 jinak odečteme 1 a napíšeme 1

Příklad: číslo 0.6d = 0.

b

18 / 28




I

Převod I I I

I


Příklad: číslo 0.6d = 0.1 I

b

0.6 · 2 = 1.2(1)

18 / 28




I

Převod I I I

I


Příklad: číslo 0.6d = 0.10 I I

b

0.6 · 2 = 1.2(1) 0.2 · 2 = 0.4(0)

18 / 28




I

Převod I I I

I


Příklad: číslo 0.6d = 0.100 I I I

b

0.6 · 2 = 1.2(1) 0.2 · 2 = 0.4(0) 0.4 · 2 = 0.8(0)

18 / 28




I

Převod I I I

I


Příklad: číslo 0.6d = 0.1001 I I I I

b

0.6 · 2 = 1.2(1) 0.2 · 2 = 0.4(0) 0.4 · 2 = 0.8(0) 0.8 · 2 = 1.6(1)

18 / 28




I

Převod I I I

I


Příklad: číslo 0.6d = 0.10011b I I I I I

0.6 · 2 = 1.2(1) 0.2 · 2 = 0.4(0) 0.4 · 2 = 0.8(0) 0.8 · 2 = 1.6(1) 0.6 · 2 = 1.2(1)

18 / 28




I

Převod I I I

I

číslo postupně násobíme 2 když je výsledek menší než 1, napíšeme 0 jinak odečteme 1 a napíšeme 1


I

jednotlivé řády i označují násobky 2−i

0.6 · 2 = 1.2(1) 0.2 · 2 = 0.4(0) 0.4 · 2 = 0.8(0) 0.8 · 2 = 1.6(1) 0.6 · 2 = 1.2(1)

Zkuste si I

0.5d

18 / 28




I

Převod I I I

I



I


0.6 · 2 = 1.2(1) 0.2 · 2 = 0.4(0) 0.4 · 2 = 0.8(0) 0.8 · 2 = 1.6(1) 0.6 · 2 = 1.2(1)

Zkuste si I

0.5d = 0.1b

18 / 28




I

Převod I I I

I



I


0.6 · 2 = 1.2(1) 0.2 · 2 = 0.4(0) 0.4 · 2 = 0.8(0) 0.8 · 2 = 1.6(1) 0.6 · 2 = 1.2(1)

Zkuste si I I

0.5d = 0.1b 0.625d 18 / 28




I

Převod I I I

I



I


0.6 · 2 = 1.2(1) 0.2 · 2 = 0.4(0) 0.4 · 2 = 0.8(0) 0.8 · 2 = 1.6(1) 0.6 · 2 = 1.2(1)

Zkuste si I I

0.5d = 0.1b 0.625d = 0.101b 18 / 28




I

Převod I I I

I



I


0.6 · 2 = 1.2(1) 0.2 · 2 = 0.4(0) 0.4 · 2 = 0.8(0) 0.8 · 2 = 1.6(1) 0.6 · 2 = 1.2(1)

Zkuste si I I I

0.5d = 0.1b 0.625d = 0.101b 1.75d 18 / 28




I

Převod I I I

I



I


0.6 · 2 = 1.2(1) 0.2 · 2 = 0.4(0) 0.4 · 2 = 0.8(0) 0.8 · 2 = 1.6(1) 0.6 · 2 = 1.2(1)

Zkuste si I I I

0.5d = 0.1b 0.625d = 0.101b 1.75d = 1.11b 18 / 28


Počítačový zápis I

IEEE standard I I I I I

I

základ 2 exponent – kód s posunutou nulou mantisa – přímý kód (znaménko oddělené) jednoduchá přesnost – 32 bitů (8 bitů exponent, 23 bitů mantisa) dvojitá přesnost – 64 bitů (11 bitů exponent, 52 bitů mantisa)

Normování mantisy I I

první nenulový bit před desetinnou tečku (nepíše se) příklad: 0.0101 → .01 +/31

exponent 30

+/63

23

mantisa 22

0

exponent 62

mantisa 52

51

0

19 / 28


Rozsah reálných čísel

I

Rozsah v jednoduché přesnosti (float) I

I

±10−45 až ±103 9 s přesností na 6 míst

Rozsah v dvojité přesnosti (double) s přesností na 15 I

±10−323 až ±103 08

20 / 28


Zkuste si

I

I

Pomocí funkce DataOutputStream.writeFloat zapsat do souboru několik různých hodnot Pomocí hexadecimálního prohlížeče si čísla prohlédnout I

I

Zjistěte I I I

I

http://www.simdesign.nl/binview.html maximální číslo minimální číslo jak lze zapsat 0

Podívejte se na http://www.h-schmidt.net/FloatApplet/IEEE754.html

21 / 28


Kódování znaků – 8 bitů

I I

Při použití 1 byte jsou jednotlivé znaky uloženy v tabulce Nejznámější norma – ASCII (American Standard Code for International Interchange) I

I

I

prvních 127 znaků – číslice, písmena anglické abecedy, matematické symboly, řídící znaky,. . . zbytek obsahuje rámečky, akcentovaná písmena, . . .

Národní znaky a jiné radosti I I

umisťují se od 127 výš nelze zachovat všechny znaky

22 / 28


Ascii tabulka

23 / 28


Nešťastná čeština

I

mnoho různých kódování – iso-8859-2, cp1250, . . .

I

nutnost znát kódování v kterém byl text napsán ve windows 1250:

I

I I I

cp1250 (windows): Příliš žluťoučký kůň úpěl ďábelské ódy iso-8859-2 (linux): Přília ľluoučký kůň úpěl ďábelské ódy cp852 (dos): Pýˇlic ¸ §lu´ sou´ zkě kĺ LpŘl Ô belsk’ ˘dy

24 / 28


Kódování znaků – 16 bitů

I

Unicode – 2562 = 65536 I

nejnovější norma dokonce 31 bitů – přes 2 miliardy znaků

I

Lze zobrazovat všechny znaky najednou

I

Text zabírá dvojnásobek místa Většina evropských znaků se nachází ve spodní části

I

I I

kódování UTF-8 různá délka znaku od 1 do 3 bytů

25 / 28


Zkuste si

I

I

Pomocí funkce DataOutputStream.writeChar zapsat do souboru několik různých znaků Pomocí hexadecimálního prohlížeče si znaky prohlédnout I

I

http://www.simdesign.nl/binview.html

Zjistěte I I

jaké kódování používá java jaké kódy odpovídají znakům české abecedy

26 / 28


Konec

27 / 28


Konec

28 / 28

Algoritmy a datové struktury

Recommend Documents