Výpočet binárního logaritmu a entropie informace

Dovedete vypočítat logaritmy bez použití vědecké kalkulačky?

Výpočet logaritmů býval neobyčejně pracnou záležitostí. Napier počítal logaritmy přibližnou integrací diferenciálních rovnic, později byly objeveny způsoby vyčíslení logaritmů jako součtů nekonečných geometrických řad. Logaritmické tabulky byly výsledkem celoživotní práce řady matematiků a jako takové se i cenily.

Dnes jsou zastaralé, kalkulačka vyčíslí logaritmus mžikem, rychleji, než jej vyhledáme v tabulkách.

Dokážete však sami, jen pomocí základních matematických úkonů, vyčíslit logaritmus 3 o základu 2 s přesností alespoň 1 %?

Řešení:

Některé vlastnosti logaritmu o základu 2 má délka hrany v binárním rozhodovacím stromu.

Od kořene takového stromu vedou dvě větve, které se vždy dělí na další dvě (jako obrácený rodokmen).

Větve odpovídají počtu odpovědí na otázky potřebných k určení čísla (m-1) a odpovědi lze označit čísly 0 a 1. Pro mocniny čísla 2 je výsledek přesný, na příklad pro 8 jsou to 3. U ostatních čísel je průměrný počet rozhodnutí L(m) aproximací, která je tím lepší, čím je číslo bližší mocnině čísla 2. Pro číslo 9 by to byl strom

Hladina

Počet objektů

Otázka

0

 

 

 

 

9

 

 

 

 

Je číslo menší než 5?

1

 

 

5

 

 

 

4

 

 

Je číslo menší než (7) (2)?

2

 

3

 

2

 

2

 

2

 

Je číslo menší než (8) (6) (4) (2)?

3

2

 

1

1

1

1

1

1

1

Je číslo menší než (9)?

4

1

1

1

1

1

1

1

1

1

 

Řešení

9

8

7

6

5

4

3

2

1

 

 

Označení listů bude: 0000, 0001, 001, 010, 011, 100, 101, 110 a 111. Všimněte si, že se nejedná o binární čísla, ale indexy obsahují nadbytečné nuly.

L(9) = 7 x 3 + 2 x 4 = 29:9 = 3.222. Děleno mocninou (9 = 32) dá výsledek 1.611. Strom přímo pro číslo 3 dá L(3) = 1.66.

Pro 35 = 243 dostaneme strom

128 x 8 = 1024

64 x 8 = 512

32 x 8 = 256

16 x 8 = 128

2 x 6 = 12

1 x 5 = 5

Součet = 1937. Průměr 7.971, děleno 5. mocninou dá 1.594. Logaritmus 3 o základu 2 je 1.585.

Kdybychom volili stále vyšší mocniny čísla k a dbali na to, aby byly současně co nejblíže mocnině čísla 2, dostali bychom stále přesnější výsledky logaritmu. Lze tvrdit, že limitou L(m) je logaritmus o základu 2.

Entropie informace

Jak jsme si ukázali, pro označení m objektů pomocí binárního rozhodovacím stromu potřebujeme mL(n) číslic.

Pokud máme o daných objektech nějakou informaci, třeba to, že jsou předem označeny n symboly nějaké abecedy, postačí nám k identifikaci objektů menší počet číslic, protože budou označeny kombinací písmene a číslice. Rozhodovací strom se rozpadne na les rozhodovacích stromů (1). Například pro 8 neoznačených objektů potřebujeme 24 číslic: 000, 001, 010, 011, 100, 101, 110 a 111.

Pokud budou objekty označeny, třeba jako : a, a, a, a, b, b, c, d,

postačí k jejich identifikaci indexace: 00a, 01a, 10a, 11a, 0b, 1b, c, d. Tedy jenom 10 číslic. Rozdíl počtu číslic (24 - 10 = 14) budeme považovat za míru informace, kterou o objektech máme. Abychom tuto hodnotu zbavili závislosti na velikosti souboru, podělíme ji počtem objektů m a označíme ji písmenem H. H = 14 : 8 = 1,75.

Eliminujeme i další závislost na velikosti hodnot mj (j = 1, 2 ...n), když nahradíme počet číslic binárními logaritmy a potom budeme moci nazvat funkci H entropií

Bude mít tvar H = S (mj/m) log2 (mj/m).

Několik poznámek o entropii

Jak jsme ukázali, entropie informace měří jen informaci, kterou máme o nějakých objektech. Těmito objekty mohou být symboly nějaké zprávy, kde jsou navíc indexovány přirozeným pořádkem v textu, ale mohou to být i rozsypané litery. Funkce H tento rozdíl nezaznamená. Funkce H byla použita před 50 léty Shannonem v jeho teorii komunikace (2). Shannon řešil problémy spojené s přenosem zpráv a tady jeho definice zcela vyhovuje. Funkce H však neměří význam informace ani její obsah.

J. Von Neumann poradil Shannonovi (3): "Měl byste to nazvat entropií ze dvou důvodů. Za prvé Vaše funkce nejistoty byla použita ve statististické mechanice pod tímto jménem a tedy už má jméno. Za druhé, a to je důležitější, nikdo neví co entropie opravdu je, takže v debatě budete mít vždy výhodu".

Entropie se vždy považovala za funkci tajemnou a existuje celá řada spekulací o jejím klíčovém významu pro vývoj vesmíru. Možná její znázornění prostým grafem a tím její degradace na obyčejné kupecké počty pomůže odstranit aspoň některé omyly.

Literatura

1. M. Kunz: Entropies and information indices of star forests, Coll. Czech. Chem. Commun., 51 (1986) 1856-1863.

2. C. E. Shannon, The Mathematical Theory of Communication, Bell System Technical Journal, 1948, 27, 379, 623.

3. M. Tribus, E. C. McIrvine, Energy and Information, Scientific American, 1971, 225, 3, 179.