Měření stromů a informací
- Spočítat, kolik možností lze rozlišit pomocí daného počtu otázek a naopak.
- V jakých jednotkách se informace měří, co je to jeden bit informace.
- Spočítat množství informace v dané zprávě.
Množství informace už umíš porovnávat
Už umíš porovnat, která ze dvou zpráv ti dá víc informace („je 8:12“ ti řekne víc, než „je ráno“). Umíš také posoudit, pomocí jaké otázky se pravděpodobně dozvíš nejvíc (raději se ptát „už bylo poledne?“, nežli „je přesně 8:12?“)A samozřejmě, pokud je možná delší odpověď, ptáme se prostě „kolik je hodin?“).
V téhle kapitole zjistíš, jak lze množství informace ve zprávě vyčíslit přesně. Odhalíš také několik nejdůležitějších poznatků teorie informace. Nejdřív si rozmyslíme, jaké od měření informace očekáváme vlastnosti. Následně s pomocí příkladu na určování denní doby prozkoumáme několik způsobů počítání a postupně dojdeme k tomu správnému.
Tahle kapitola není zrovna čtení do tramvaje a může se stát, že nepochopíš všechno hned. Nic si z toho nedělej a po čase se k textu vrať. Když už budeš vědět, kudy, kam a proč směřuje, bude se ti číst a rozumět mnohem snáz. V každém případě je nutno nakonec vědět, jak se tedy množství informace počítá.
Na konci kapitoly využijeme matematickou funkci logaritmus. Pokud jste ji ještě neprobírali, příslušné pasáže přeskoč a vrať se k nim později.
Obsah
Kolik otázek na kolik možností?
Pokud postupujeme nejlépe, jak to jde, odhalíme jednu z šestnácti možností pomocí čtyř otázek. (Kdo si není jistý proč, zastaví se, vráti k předchozí kapitole a prozkoumá, proč právě 4 otázky na 16 možností.)
Z kolika nanejvýš možností si můžeme troufnout zjišťovat správnou, když budeme mít k dispozici o jednu víc, tedy 5 otázek? Vyber správnou možnost a její zdůvodnění.
- 16/2=8; Každá další otázka sníží počet zbývajících možností na polovinu, možností bylo 16, z toho polovina je 8.
- 16+1=17; Jedna otázka navíc nám umožní zjistit jednu možnost navíc.
- (16/4)⋅5=20; Jednou otázkou umíme zjistit nanejvýš 16/4=4 možnosti, otázek máme pět, takže celkem 4*5=20 možností k zjišťování.
- 5⋅5=25; Mezi šestnácti možnostmi se rozhodneme pomocí čtyř otázek, což je druhá odmocnina. Pro pět otázek tedy dostáváme 25 možností.
- 16⋅2=32; Každá další otázka sníží počet zbývajících možností na polovinu. Díky otázce navíc proto můžeme pracovat s dvojnásobkem možností.
- Jiná možnost - jaká, proč?
- Nemusíš pracovat jen s představami, potřebné stromy si klidně nakresli.
- Zformuluj vlastní výsledek a vlastní zdůvodnění, to pak porovnej s nabídkou.
- Zkontroluj, jestli vybrané zdůvodnění funguje správně i pro jiné (menší) případy - jednu, dvě a tři otázky.
- Zkus si sestrojit příslušný optimální rozhodovací strom s pěti otázkami. Uvědom si, že není nutně potřeba doplňovat konkrétní otázky a možnosti. Už z pouhého tvaru stromu dokážeš spočítat, kolik je vespod možností odpovědí.
Řešení
E. 16⋅2=32; Každá další otázka sníží počet zbývajících možností na polovinu, takže díky otázce navíc můžeme pracovat s dvojnásobkem možností.
Stejná situace z druhé strany: S kolika otázkami si troufneš hádat jednu možnost z 256 (to je 162)? Vyber správnou možnost.
- 4+4=8; 256 možností si můžeme rozdělit na 16 skupin po 16 možnostech. Čtyřmi otázkami určíme jednu ze skupin a dalšími 4 otázkami potom správnou možnost v této skupině.
- √256=16; Když byly potřeba 4 otázky pro 16 možností, bude pro 162 možností potřeba 42 otázek.
- 4⋅16=64; Když byly potřeba 4 otázky pro 16 možností, bude potřeba 16krát víc otázek pro 16krát víc možností.
- 256/2=128; Každá otázka ubere polovinu možností, polovina z 256 je 128.
- 4+(256-16)=244; Když byly potřeba 4 otázky pro 16 možností, bude pro dalších 240 možností potřeba dalších 240 otázek.
- 256-1=255; Strom pro 16 možností obsahuje 15 otázek, strom pro 256 možností bude obsahovat 255 otázek.
- Jiná možnost - jaká, proč?
Použij obdobu postupů z předchozí otázky. Navíc můžeš použít i zjištěnou odpověď.
Řešení
A. 4+4=8; Šestnáct možností je třeba rozpůlit čtyřikrát, 256 možností je třeba navíc půlit ještě čtyřikrát.
Od začátku bylo jasné, že z čím většího počtu čísel hledáme to myšlené, tím více bude asi potřeba otázek. Jaký přesně ale ten vztah je? Je nějaký maximální počet možností, který dovedeme rozlišit daným počtem otázek? Dá se vypočítat? Nebo naopak, když známe počet možností, mezi kterými potřebujeme rozlišovat (např. hádáme číslo 0-15, nebo 1-256, nebo jedno z 512 zvířat), můžeme vypočítat, kolik otázek budeme potřebovat?
Vytvoř v tabulkovém procesoru pomůcku na určování počtu rozlišitelných možností podle počtu otázek. Např. v jednom sloupci může postupně narůstat počet otázek, ve vedlejším sloupci bude příslušný počet možností.
Začni od nejmenších případů, tedy od jedné otázky. Kolik možností rozliším jednou otázkou? Postupně pokračuj větším hodnotám. Kolik možností rozlišíš dvěma, třemi, čtyřmi otázkami? Pokud potřebuješ, nakresli si potřebné rozhodovací stromy. Postupně si všimneš pravidla, které ti umožní do editoru zadat vzorec. Pak už ani nebude nutno hodnoty počítat ručně.
Kdo poctivě sestrojoval stromy, bezpečně odhalil, jak přijít od počtu otázek k počtu možností a naopak. Jedna otázka rozliší dvě možnosti. Se dvěma otázkami už rozlišíme čtyři možnosti. Každá otázka navíc znamená jedno rozpůlení možností navíc, a umožňuje tak začít s dvojnásobkem možností.
Máme-li k dispozici n otázek, můžeme při optimálním postupu rozlišit nanejvýš 2n možností.
V informatice někdy při počítání značíme "počet" znakem "#", anglicky někdy "number sign". Značka se ale hodí třeba i při psaní poznámek z výuky. Někdy nám totiž ušetří zavádění nového značení. Abychom například nemuseli psát, že n značí počet otázek, můžeme s pomocí # napsat:
#možností = 2#otázek
Zápis je delší, ale srozumitelnější.
Chceme-li naopak zjistit počet potřebných otázek k uhodnutí čísla z daného rozsahu, můžeme spočítat, kolikrát rozsah (počet možností) vydělíme dvěma, než se dobereme k jediné zbývající možnosti.
Zajímá nás, kolik otázek k uhodnutí stačí jistě — tedy i v případě, že se nám vůbec nedaří. Pro příklad uvažujme 23 možností. Kolik je potřeba otázek k uhodnutí jednoho čísla z 23 možných?
Řešení
Při 23 možnostech bude půlení postupovat takto:
- 23=11+12
- 12=6+6
- 6=3+3
- 3=1+2
- 2=1+1
Možnosti jsme půlili pětkrát, potřebujeme tedy 5 otázek.
Když budem mít štěstí, může se počet možností snižovat takto: 23 → 11 → 5 → 2 → 1. V takovém případě by tedy stačily čtyři otázky. Na štěstí se ale spoléhat nechceme, proto budeme raději počítat s otázkou navíc.
Zamyslete se: Připadá vám zvláštní, že máte dva rodiče, čtyři prarodiče, osm praprarodičů atd.? Není žádná generace, ve které byste měli třeba 3, 5 nebo 7 přímých předků. Na tohle jsme ve skutečnosti zvyklí. Je to přitom totéž. V rozhodovacím stromu, stejně jako v rodokmenu, prvky v další generaci pokaždé zdvojujeme. Jen ve stromech je přidáváme dolů, kdežto v rodokmenech obvykle nahoru.
Tušení, že se možnosti „navíc“ musí někde projevit (i když nejvyšší počet potřebných otázek se neliší), je ale správné. Rozdíl se projeví v počtu potřebných otázek při opakovaném hraní.
Všimni si toho nepoměru: přidání jediné otázky umožní zdvojnásobit počet zjistitelných možností. Na 16 možností jsou potřeba 4 otázky, na 32 je třeba 5 otázek. Na 1000 možností stačí 10 otázek, na milion možností stačí 20 otázek. Přitom naivní tipování by otázek vyžadovalo v průměru půl milionu, a s trochou smůly skoro celý milion! Tak jako leckde jinde, i v informatice se chytré postupy nejlépe projeví ve velkých měřítkách.
Množství informace a počet vyloučených možností
Podobně se mění množství informace v téže zprávě přijaté opakovaně stejným příjemcem. Prvním přijetím zprávy se něco nového dozví, množství získané informace je kladné. Když ovšem zprávu přijímá znovu, nic nového se v ní nedozví (její obsah už zná z dřívějška), takže je množství přijaté informace nulové.
Už toho o informacích víme poměrně hodně: co jsou zač, jak je efektivně získávat, a jak dlouho to kdy trvá. Jak tedy poměřujeme, která zpráva přináší více informace? Lze množství informace nějak vyčíslit? Kolik jsme se toho dozvěděli přijetím zprávy, můžeme posoudit jako rozdíl mezi tím, kolik jsme toho nevěděli před přijetím zprávy, a tím, kolik toho nevíme po jejím přijetí. Můžeme mluvit o neurčitosti jako o míře, nakolik něco nevíme, neboli kolik možností nám ještě zbývá k vyloučení. Čím více možností, tím méně víme, tím vyšší neurčitost. Budeme tedy hledat vzoreček ve tvaru:
„množství informace“ = „neurčitost před zprávou“ — „neurčitost po zprávě“
Šel jsem spát neskutečně unavený, spal jsem nevím jak dlouho a probral se v místnosti bez telefonu, hodin, oken či jiného způsobu, jak určit denní dobu. Zajímá mne čas s přesností na minuty.
Otázka: Kolik je možností pro denní dobu s přesností na minuty?
Otázka vlastně zní: kolik různých denních dob existuje? Nenapadne-li tě nic lepšího, budeš si je muset všechny vypsat. 00:00 00:01 00:02 00:03 00:04 ... V průběhu třeba objevíš, jak si při tom ušetřit práci a dojít k výsledku rychleji.
Řešení
Den má 24 hodin, každá z nich má 60 minut. 24⋅60 = 1440.
Otázka: Kolik dobrých otázekTakových, co vedou k výsledku nejkratší cestou. se dvěma možnými odpověďmi jistě stačí k určení denní doby s přesností na minuty?
Použij stejný princip jako u čísel a zvířat. Kolikrát je třeba zbývající možnosti omezit na polovinu, než zbyde jediná poslední?
Řešení
Postupně dělíme 1440 možností na poloviny a zapisujeme si mezivýsledky. V případě lichého počtu možností zaokrouhlujeme nahoru.
Mezivýsledky: 1440, 720, 360, 180, 90, 45, 23, 12, 6, 3, 2, 1
Celkem jsme uskutečnili 11 dělení, k určení denní doby je tedy potřeba položit nanejvýš 11 dobrých otázek.
Uvažujme následující zprávy:
Kolik možností uberou jednotlivé dvojice zpráv? Kolik větší skupinky?
Například dvojice „Je po poledni“ a „Je sudá hodina“ uberou celkem 1080 možností a ponechají jich 360.
- Je po poledni.
- V místní škole ještě probíhá výuka.
- Je tři čtvrti na (nějakou) celou.
- Je sudá hodina.
- Je před Večerníčkem.
- Je víc minut než hodin.
- Je mezi půl desátou dopoledne a půl šestou večer.
- Je tři čtvrti na tři.
Otázka: Které zprávě odpovídá který obrázek? Ciferníky jsou 24hodinové, zelená označuje možnou denní dobu podle dané zprávy.
Řešení
1F, 2A, 3E, 4H, 5D, 6G, 7B, 8C.
Otázka: Kolik možností uberou jednotlivé výše uvedené zprávy?
Ubrané možnosti odpovídají bílé ploše na cifernících. Někdy je snazší spočítat, kolik možností zbyde. U zprávy B (doba výuky) odpověď odhadni podle místních podmínek. K počítání se hodí kalkulátor, třeba tabulkový.
Řešení
Např. zpráva Je tři čtvrti na (nějakou) celou omezuje možnou denní dobu na 24 možností, všechny ostatní tedy ubrala. 1440-24=1416 ubraných možností. Zpráva Je mezi půl desátou dopoledne a půl šestou večer zahrnuje 8 hodin, vylučuje jich tedy 16. Každá hodina představuje 60 možností (zajímáme se o čas s přesností na minuty), 16⋅60=960 ubraných možností.
| Ciferník se zprávou | ||||||||
|---|---|---|---|---|---|---|---|---|
| Počet vyloučených možností | 720 | 990Uvažovali jsme výuku od 8 do 15:30. | 1416 | 720 | 315Večerníček začíná v 18:45 | 300Není 0:00, 1:00, 1:01, 2:00, 2:01, 2:02, ..., 23:22, 23:23. Ubylo tedy 1+2+3+...+23+24 možností. | 960 | 1439 |
Otázka: Jaký podíl zbývajících možností uberou jednotlivé výše uvedené zprávy?
Nezapomeň využít předchozí výsledky. K počítání se hodí kalkulátor, třeba tabulkový.
Řešení
| Ciferník se zprávou | ||||||||
|---|---|---|---|---|---|---|---|---|
| Počet vyloučených možností | 720 | 990Uvažovali jsme výuku od 8 do 15:30. | 1416 | 720 | 315Večerníček začíná v 18:45 | 300Není 0:00, 1:00, 1:01, 2:00, 2:01, 2:02, ..., 23:22, 23:23. Ubylo tedy 1+2+3+...+23+24 možností. | 960 | 1439 |
| Podíl vyloučených možností | 1/2 | 99/144=0,6875 | 59/60≈0,9833 | 1/2 | 315/1440≈0,2188 | 300/1440≈0,2083 | 2/3 | 1439/1440≈0,9993 |
Nezávislé zprávy
Jak tedy měřit množství informace? Mohli bychom zkusit použít přímo počty vyloučených možností. Zpráva „Je tři čtvrti na celou“ by tak nesla 1416 „jednotek informace“Protože den má 24*60=1440 minut a zpráva vyloučila všechny kromě 24, které jsou právě „ve tři čtvrti“: 1440-24=1416. Rychle se ale ukáže, že takový postup nefunguje dobře.
Příklad:
Uvažujme zprávy „Je po poledni“ a „Je tři čtvrti na celou.“ Ty dvě zprávy na sobě nejsou nijak závislé: Z toho, že je po poledni, se nedozvím vůbec nic o tom, jestli je tři čtvrtě, a naopak. Nic na tom nemění, že i po poledni nastane několikrát okamžik „tři čtvrtě“ (ani že několik z možných „tři čtvrtě“ se odehraje po poledni).
Závislé jsou naopak zprávy „Je po poledni“ a „V místní škole ještě probíhá výuka.“ Z jedné můžeme aspoň přibližně usuzovat o platnosti druhé. Probíhá-li vyučování, je pravděpodobně spíš dopoledne, než odpoledne, protože dopoledne probíhá větší část vyučování. A naopak, je-li po poledni, ještě silněji než před tímto zjištěním teď předpokládáme, že vyučování spíš neprobíhá.
Uvažujme nezávislé zprávy z příkladu a měření informace počtem vyloučených možností. „Je po poledni“ by neslo 720 nějakých jednotek informace, '„Je tři čtvrti na celou“ by jich neslo 1416. Nebo ne? Pokud už víme, že je po poledni, vyloučí zpráva „Je tři čtvrti na celou.“ nikoliv 1416, ale už jen 708 možností. Takže by najednou nesla jen 708 jednotek informace. To je ale problém. Nechceme přece, aby se množství informace ve zprávě měnilo s tím, jak se dozvídáme něco s tou zprávou nesouvisejícího.
Požadované vlastnosti měřítka na informace
Měření informace tedy patrně musí splňovat některé požadavky, aby výsledky dávaly dobrý smysl a odpovídaly našim přirozeným představám. Mezi takové požadavky patří především:
- Dolní mez
- Množství informace, jako každé jiné množství, musí být nezáporné. Ve zprávě, která neubere žádné možnosti, je množství informace nulové.
- Horní mez
- Toho dosáhne taková zpráva, ze které se dozvíme vše, neboli zbyde jediná možnost.
- Úměra
- Čím více možností zpráva ubere, tím více obsahuje informace (úměra ale nemusí být přímá!).
- Vyplývající zprávy
- Jestliže z jedné zprávy (např. „Je to savec.“) přímo vyplývá zpráva druhá (např. „Je to obratlovec“), je v první zprávě přinejmenším tolik informace, kolik je v té druhé.
- Nezávislé zprávy
- Informační hodnota nezávislých zprávJedna z druhé ani částečně nevyplývá, např. „Je po poledni“ a „Je tři čtvrti na celou.“ nezáleží na pořadí jejich získání. Navíc když získáme obě zprávy, množství celkově získané informace je přesně rovno součtu množství informace v obou zprávách.
- Kvantita, nikoliv kvalita
- Množství informace záleží pouze na počtech možností, nikoliv na tom, které konkrétní možnosti ubyly. Zpráva „Je po poledni“ nese stejné množství informace jako zpráva „Je sudá hodina.“
Podobně se množství informace nemá měnit se změnou komunikačního kanálu. Musí být jedno, jestli informaci získáme z videa na YouTube nebo z mezopotámské hliněné destičky.
- Převoditelnost
- My pro jednoduchost připouštíme jen dvě možné odpovědi na otázku. V principu ale můžeme pracovat i s otázkami bohatšími. Naměřené množství informace v různých situacích přitom musí být buď stejné, nebo vzájemně jednoznačně převoditelné (podobně jako např. rychlost větru v m/s na km/h či imperiální na metrické jednotky).
- Závislé zprávy
- Pokud obsahy dvou zpráv souvisíPřijetím jedné zprávy se pro nás změní množství informace ve druhé zprávě., mělo by platit: Celkové množství informace získané oběma zprávami je rovno součtu množství informace v obou zprávách zmenšenému o množství informace, které obě zprávy sdílí. Jinými slovy odečteme to, co bychom jinak započetli dvakrát. Obdobně počítáme velikost sjednocení množin s neprázdným průnikem.
Uvedené vlastnosti jsou poměrně přirozené, proč je tedy tak podrobně probíráme? Protože díky jejich přesnému určení snáze odhalíme jediný možný způsob, jak množství informace měřit.
Jak změřit, kolik toho nevíme?
Zde uvedený výklad se pokud možno vyhýbá pojmu logaritmu. Je to proto, že se s ním studenti leckde seznamují poměrně pozdě, a ani potom mu dobře nerozumí.
Pokud jsou pro ně ovšem následující vztahy přirozené, nebo aspoň srozumitelné, lze měření množství informace vyložit přímočařeji a dostat se při tom hlouběji:
- Logaritmus je inverzní k exponenciální funkci. Odpovídá na otázku „na kolikátou mám umocnit základ, abych dostal daný výsledek?“
- Výška optimálního rozhodovacího stromu je vzhledem k počtu listů logaritmická (o základu 2). Např. 8 prarodičů máme o log(8)=3 generace zpět.
- Logaritmus převádí násobení na sčítání, pravidlo log(a⋅b)=log(a)+log(b) není jen nahodilost určená k úpravám výrazů.
Pokud si naopak vystačíme i se vzájemným porovnáváním množství informace ve zprávách a nebudeme jej chtít vyčíslit, obejdeme se bez logaritmu úplně.
Následující tabulka zachycuje čtyři situace postupného přijímání zpráv „Je tři čtvrti na celou“ a „Je sudá hodina“: Buď na začátku nevíme nic, a obdržíme jednu ze zpráv, nebo už jednu ze zpráv máme, a obdržíme tu druhou. Otázkou je, kolik možností se ve kterém případě vyloučí, což by mělo nějak souviset s množstvím informace v jednotlivých zprávách. To by se navíc nemělo nijak změnit podle toho, jestli už máme druhou zprávu, protože jsou obě zprávy nezávislé.
Doplň chybějící hodnoty.
| Co vím předem | Možnosti předtímPočet možností před přijetím zprávy | Otázky předtímKolik otázek (resp. odpovědí ANO nebo NE) potřebuji k určení správné možnosti z daného počtu | Co se dozvímJakou zprávu dostávám: „Je tři čtvrti na celou“ nebo „Je sudá hodina.“ | Možnosti potomPočet možností zbylých po přijetí zprávy | Otázky potomPočet otázek (resp. odpovědí ANO nebo NE) nutných k vyloučení možností zbylých po přijetí zprávy | Vyloučené možnostiPočet možností, které jsme mohli vyloučit po přijetí zprávy | Podíl vyloučených možnostíPodíl počtu vyloučených a původních možností | Úbytek otázekPočet otázek, které díky zprávě nebudeme muset položit | ||
|---|---|---|---|---|---|---|---|---|---|---|
| 1440 | 11 | 24 | 1416/1440 = 59/60 | |||||||
| 10 | ||||||||||
| 1440 | 720 | 720 | ||||||||
| 4 | 12 | 1 |
Řešení
| Co vím předem | Možnosti předtímPočet možností před přijetím zprávy | Otázky předtímKolik otázek (resp. odpovědí ANO nebo NE) potřebuji k určení správné možnosti z daného počtu | Co se dozvímJakou zprávu dostávám: „Je tři čtvrti na celou“ nebo „Je sudá hodina.“ | Možnosti potomPočet možností zbylých po přijetí zprávy | Otázky potomPočet otázek (resp. odpovědí ANO nebo NE) nutných k vyloučení možností zbylých po přijetí zprávy | Vyloučené možnostiPočet možností, které jsme mohli vyloučit po přijetí zprávy | Podíl vyloučených možnostíPodíl počtu vyloučených a původních možností | Úbytek otázekPočet otázek, které díky zprávě nebudeme muset položit | ||
|---|---|---|---|---|---|---|---|---|---|---|
| 1440 | 11 | 24 | 5 | 1416 | 1416/1440 = 59/60 | 6 | ||||
| 720 | 10 | 12 | 4 | 708 | 708/720 = 59/60 | 6 | ||||
| 1440 | 11 | 720 | 10 | 720 | 720/1440 = 1/2 | 1 | ||||
| 24 | 5 | 12 | 4 | 12 | 12/24 = 1/2 | 1 |
Znovu vidíme, že počet vyloučených možností k vyjádření množství informace ve zprávě použít nelze. Liší se totiž podle toho, co už víme z jiné, nezávislé zprávy. Co se tedy v tabulce pro jednotlivé zprávy nemění?
Poměr vyloučených a původních možností
| Zpráva | ||||
|---|---|---|---|---|
| Jak by vypadalo měření „množství informace“ pomocí poměru vyloučených možností |
1/2 = 0,5 | 59/60 ≈ 0,983 | 1/2+59/60 = 89/60 ≈ 1,483 To je víc než 1! |
1439/1440 ≈ 0,999 |
Poměr vyloučených a původních možností se nemění. Bude tedy pro nás patrně užitečnější, než samotný konkrétní počet možností. To odpovídá i naší snaze při hádání myšleného čísla. Informace se chceme dozvídat plynule, ne tak, aby se ke konci dotazování zmenšoval informační přínos jednotlivých odpovědí s tím, jak ubývají možnosti. A každou otázkou se snažíme ubrat polovinu možností, tedy nikoliv konkrétní počet, nýbrž konkrétní podíl možností.
Nemůžeme ale říct, že by zpráva „Je sudá hodina.“ obsahovala 1/2 nějaké hypotetické "jednotky" informace a zpráva „Je tři čtvrti na celou“ potom 59/60 jednotky informace. Sečtení množství informace obsažené v obou zprávách (což odpovídá zprávě „Je tři čtvrti na nějakou lichou hodinu“) by dávalo 89/60 jednotky informace. To je ovšem nesmysl, protože to je víc, než případných 1439/1440 jednotky informace, které už plně určují denní dobu! Čistě pomocí podílu vyloučených možností tedy informace měřit nepůjde, musíme hledat dál.
Rozdíl v počtu potřebných otázek
Kromě podílu se v tabulce nemění také rozdíl v počtu otázek potřebných k určení přesného času před a po přijetí zprávy. Můžeme tedy pro měření informace použít právě tento rozdíl?
Příklad: Měření množství informace prostřednictvím rozdílu v počtu potřebných otázek
| Zpráva | ||||
|---|---|---|---|---|
| Otázky předtímPočet otázek (resp. odpovědí) ANO nebo NE nutných k vyloučení počátečních možností | 11 | 11 | 11 | 11 |
| Otázky potomPočet otázek (resp. odpovědí) ANO nebo NE nutných k vyloučení možností zbylých po přijetí zprávy | 10 | 5 | 4 | 0 |
| Množství informace (ušetřené otázkyPočet otázek, které díky zprávě nebudeme muset položit.) | 11-10 = 1 | 11-5 = 6 | 11-4 = 7 | 11-0 = 11 |
Z předchozích výpočtů už víme následující:
Na začátku jsme o přesném čase věděli tak málo, že bychom k jeho určení potřebovali položit 11 otázek. Po přijetí zpráv „Je sudá hodina.“ a „Je tři čtvrti na celou.“ bychom se potřebovali doptat na 4 otázky. To odpovídá celkovému úbytku 1+6 = 7 otázek prostřednictvím těch dvou zpráv. Sčítání množství informace v nezávislých zprávách zde tedy funguje.
Měření neurčitosti počtem potřebných otázek splňuje naše podmínky. Navíc dává dobrý smysl: Množství informace ve zprávě odpovídá počtu otázek, které díky zprávě při vylučování možností ušetříme (nebudeme je muset položit). Jinými slovy, pokud chceme příslušný údaj zjistit pokládáním otázek, musíme jich položit právě tolik, kolik je ve zprávě informace.
„množství informace“ ≈ „otázky předtím“Počet otázek nutných k vyloučení počátečních možností - „otázky potom“Počet otázek nutných k vyloučení možností zbylých po přijetí zprávy
Pozorný čtenář si všiml, že v zelenomodré tabulce pracujeme s počtem otázek, který jistě stačí k určení času při daných znalostech. Protože ale zbývající možnosti nejsou mocninou čísla 2, bude někdy stačit otázek méně. Naše výpočty jsou tedy zatím pouze přibližné.
Základní jednotka informace
Už víme, jak informaci měřit, ale neřekli jsme si, v jakých jednotkách. Je to ale nasnadě: V počtu odpovědí na otázky. Přitom máme na mysli otázky, které umožňují právě dvě odpovědi. Z hlediska množství informace je jedno, jestli jsou to odpovědi ano a ne, < a ≥, pravda a nepravda, sluníčko a obláček, zapnuto a vypnuto či číslice 1 a 0. Právě ty číslice jsou ale poměrně praktické. Jsou krátké, a lze je podle potřeby používat jako logické hodnoty (pravda a nepravda, technicky potom zapnuto a vypnuto) nebo jako čísla, reprezentující cokoliv, co jsme naměřili nebo očíslovali. Příslušnou jednotku informace už jistě znáš z dřívějška.
Základní jednotkou informace je bit, z anglického binary digit. Značíme ji malým tiskacím písmenem b. Bit je jedna dvojková číslice, představuje tedy rozhodnutí mezi dvěma možnostmi(nebo skupinami jednotlivých možností). Jeden bit informace vyloučí právě polovinu zbylých možností. (Dva bity(tedy dvě číslice, nebo také dvě odpovědi (ano nebo ne) vyloučí polovinu možností a ze zbytku opět polovinu, takže z původních možností zbyde čtvrtina.)
O bitech se hovoří také v souvislostí s pamětí počítače: bit je místo pro uchování jedné číslice 0 nebo 1, tedy bitu. Je to podobná zkratka, jako když řekneš, že lahev má litr, když chceš říct, že je v ní prázdné místo pro litr nějaké tekutiny. Není to úplně přesné, ale souvislost je jasná a porozumění to nijak nebrání.
Přesné měření
Někteří si možná během úloh ušetřili spoustu práce. Uvědomili si, že počet potřebných otázek (neboli výšku optimálního stromu) nemusí zjišťovat ručně jako počet postupných dělení dvěma. To za nás přece dovede spočítat funkce logaritmus!
Pokud jsi to ještě nezkusil(a), přesvědč se o tom. Vyřeš některou z předchozích úloh s pomocí dvojkového logaritmu.
Např. jsme řešili, kolik otázek je třeba k určení denní doby, tedy jedné z 24*60=1440 možností. Stačí spočítat dvojkový logaritmus:
log(1440) ≈ 10,49
Těžko položíme 10,49 otázky, potřebujeme tedy 11 otázek. Logaritmus nám ušetřil nutnost postupného dělení dvěma.
Při použití logaritmu v informatice je třeba dávat pozor na použitý základ. Např. na kalkulačkách obvykle najdeme přirozený a dekadický logaritmus, ale nikoliv dvojkový. To dává smysl, většina lidí nejsou informatici. Nezapomeňte tedy výsledky převést na logaritmus o správném základu.
Základ 2 používáme právě proto, že pracujeme se dvěma hodnotami. Výsledky tak přirozeně vycházejí v bitech. Logaritmus je v informatice dvojkový tak často, že už jej všichni předpokládají a není třeba jej uvádětPokud ale používáme logaritmus mimo informatiku, je třeba se buď ujistit, že se na základu všichni shodují, nebo ho jasně uvést.. Logaritmus nám navíc dá smysluplné výsledky i v případech, kdy počet možností není celočíselnou mocninou dvou.
Příklad: Informace ve zprávě „Je tři čtvrti na celou“
Vyjdeme ze vztahu uvedeného výše, množství informace je rozdíl mezi počtem otázek potřebných před a otázek potřebných po přijetí zprávy. Místo počítání otázek postupným dělením použijeme logaritmus. Na začátku máme 1440 možností, po přijetí zprávy už jen 24:
log(1440) - log(24) ≈ 10,49 - 4,58 ≈ 5,91 b
Zpráva „Je tři čtvrti na celou“Samozřejmě jen v dané situaci, tedy když nás zajímá denní doba s přesností na minuty a před přijetím zprávy netušíme nic. tedy nese přibližněMůžeme použít libovolnou přesnost, se kterou dovedeme počítat logaritmy. 5,91 bitů informace.
Logaritmus pro leckoho není zrovna intuitivní funkce. Máme jistotu, že bude vše správně fungovat i pro kombinování nezávislých zpráv? Opravdu se množství informace získané přijetím dvou nezávislých zpráv rovná součtu množství informace v jednotlivých zprávách i v případě, že počítáme pomocí logaritmu?
Využijeme toho, že množství informace ve zprávě je rovno logaritmu z poměru počtu možností před a po přijetí zprávy. Jsou-li zprávy a a b nezávislé, poměry počtů možností označené Pa a Pb zůstávají zachovány nezávisle na přijetí či nepřijetí druhé zprávy. Pokud přijmeme obě zprávy (v libovolném pořadí), je celkový poměr počtu možností před a po přijetí obou zpráv roven součinu dílčích poměrů Pa⋅Pb (to si promysli!).
Chceme tedy ověřit, jestli platí, že celková získaná informace je součtem informací z dvou nezávislých zpráv:
log(Pa⋅Pb) = log(Pa)+log(Pb)
Když se ale na vztah trochu pečlivě zadíváme, zjistíme, že není co ověřovat. Už víme, že platí, je to totiž základní vlastnost logaritmu. Vidíme tedy, že sčítání a logaritmy společně dávají smysluplné výsledky. Informatici na logaritmy nedají dopustit.
Příklad: Množství informace ještě úsporněji
Nakonec na stejném příkladu ukažme, jak ušetřit práce ještě víc. Opět uvažujeme zprávu „Je tři čtvrti na celou.“, 1440 počátečních možností a 24 možností koncových. Tentokrát si ale navíc vzpomeneme na užitečnou vlastnost logaritmů:
log(a⋅b) = log(a)+log(b), neboli log(a)-log(b) = log(a/b)
Dostaneme tak:
log(1440) - log(24) = log(1440/24) = log(60) ≈ 5,91 b
Logaritmus tedy stačí počítat jen jeden. Všimni si navíc poměru 1440/24=60. Tedy před přijetím zprávy jsme měli 60krát víc možností, než po něm. Pokud u zprávy známe tento poměr, není třeba jednotlivé možnosti počítat vůbec!
Množství informace ve zprávě je rovno logaritmu z poměru počtu možností před a po přijetí zprávy.
Po dlouhé cestě jsme se dopracovali k překvapivě jednoduchému vztahu. Ovšem jen díky tvému vlastnímu vytrvalému úsilí víš, co se za vzorečkem skrývá a jak se k němu dojde.
Shrnutí
Máme-li k dispozici n otázek, můžeme při optimálním postupu rozlišit nanejvýš 2n možností.
Množství informace odvozujeme od rozdílu v tom, co jsme věděli před jejím přijetím, a co víme po jejím přijetí.
Základní jednotkou informace je bit (značený b), neboli binárnídvojková číslice. Jeden bit informace vyloučí právě polovinu zbývajících možností. Množství informace v bitech odpovídá počtu otázekOptimálních (půlících) otázek s odpovědí ANO nebo NE., které díky dané informaci nebudeme muset položit.
Množství informace ve zprávě je rovno logaritmu z poměru počtu možností před a po přijetí zprávy.
