1 of 33

Teorie informací

Maskot

říjen 221

2 of 33

Žlutá Bible praví: "Shannonova teorie poskytuje jedinou přesvědčivou kvantitativní míru informace, která kdy byla odvozena."

Společně si odvodíme základní kostru, na které Shannon svou teorii informací staví: zakódujeme počasí v Prudké, budeme házet nevyváženými mincemi a dozvíte se, co má společného Morseovka s entropií.

Program vhodný i pro osoby s traumatem z matematiky.

Jak to bude vypadat: mám připravený matematický workshop na středoškolské úrovni, která postupuje od koncepce bitu a míry nejistoty k Huffmanovu kódování a pak se přemostí k Shannonově entropii a na příkladech demystifikuje onen chaotický vzorec. Tzn něco málo povídání a hodně drobných přemýšlecích úkolů.

3 of 33

25 %	25 %	25 %	25 %

Počasí v Obůrce

4 of 33

Binární abeceda

Hledáme binární abecedu. Jakým způsobem svému kamarádovi sdělíte, jaké je právě počasí v Obůrce tak, abyste použili co nejméně znaků?

Binární abeceda

Abeceda, která obsahuje právě dva znaky.
Je to například morseovka (·−) nebo binární soustava (01).

Počasí v Obůrce

5 of 33

0 0	0 1	1 0	1 1

Počasí v Obůrce

6 of 33

0 0	0 1	1 0	1 1

bit

Počasí v Obůrce

7 of 33

bit (z anglického binary digit) je základní a současně nejmenší jednotkou dat

8 of 33

100 %	0 %	0 %	0 %

Počasí v Češkovicích

9 of 33

Nemusím sdělovat nic.

10 of 33

25 %	12,5 %	50 %	12,5 %

Počasí v Těchově

11 of 33

Počasí v Těchově

Hledáme binární abecedu. Jakým způsobem svému kamarádovi sdělíte, jaké je právě počasí v Těchově tak, abyste použili co nejméně znaků?

12 of 33

10	101	0	111

Počasí v Těchově

13 of 33

Lze dokázat, že efektivnější kódování již nelze nalézt.

14 of 33

V jakém městě máme o počasí více informací?

15 of 33

Kolik zjišťovacích otázek musím položit, abych s jistotou věděla, jaké je ve městě počasí?

16 of 33

Počasí v Obůrce

Je slunečno nebo prší?

Je aktuální počasí mezi možnostmi {slunečno, prší}?

Ano.

Ne.

Je slunečno, nebo prší?

Je polojasno, nebo zataženo?

17 of 33

Počasí v Těchově

Je polojasno?

Ano.

Ne, je slunečno?

Ne. Prší, nebo je zataženo?

18 of 33

O počasí v Těchově mám míň informací, jelikož lze lépe predikovat.

19 of 33

Abeceda

Mějme danou binární abecedu. Rozluštěte následující slova.

11011110

0110101000

01010100110

A 11
B 010
C 0111
D 00
E 10
F 0110

Dekódování slov

20 of 33

Kódování slov

Hledáme binární abecedu. Jakým způsobem svému kamarádovi sdělíte slovo MISSISSIPPI tak, abyste použili co nejméně znaků?

21 of 33

Řešení

22 of 33

23 of 33

24 of 33

25 of 33

Formalizace

26 of 33

Funkce nepravděpodobnosti

Délku znaku můžeme přeformulovat jako „jak moc hluboko ve stromu jsme“?

27 of 33

Zavedení nepravděpodobnosti

Budou-li mít všechny stavy stejnou pravděpodobnost, funkce H bude maximální.
Výsledek funkce H(p₁, p₂, … p_n) nezávisí na pořadí p.
Vždy platí H(p₁, p₂, … p_n) ≥ 0, přičemž rovnost nastává pokud p_i = 1 pro nějaké i.
H(p₁, . . . , p_n, 0) = H(p₁, . . . , p_n).
H(1/n, . . . , 1/n) ≤ H(1/(n + 1), . . . , 1/(n + 1)).
H je spojitá funkce.
H(1/mn, . . . , 1/mn) = H(1/m, . . . , 1/m) + H(1/n, . . . , 1/n).

28 of 33

Entropie H

29 of 33

Entropie vrhu mincí

30 of 33

31 of 33

Důsledky

Tvrzení. Nechť H(x) je entropie a L průměrná délka kódových slov popisující určitou veličinu. Pak vždy platí, že L ≥ H(x).

Definice. Efektivitu kódování zaveďme jakožto podíl L/H(x).
Pak čím více se efektivita blíží 1, tím efektivnější kódování je.

32 of 33

menší entropie ≈ větší komprese
větší entropie ≈ menší komprese

33 of 33

Použité prameny a další literatura

C. E. Shanon: A Mathematical Theory of Communication, 1948 [online] https://ieeexplore.ieee.org/document/6773024
R. Lecamwasam: Entropy as a 'volume' - the geometric interpretation [online] https://ruvi.blog/posts/entropygeometric/entropy01geo/

Předmět PřF:M8170 Teorie kódování