Měření stromů a informací

Z Základy informatiky pro střední školy
Přejít na: navigace, hledání

Rozhodovací stromy a chytré otázky · Data a význam


ikona boxu
Co se naučíš:
  • 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ě.
ikona boxu
Návrh průběhu hodiny a metodické poznámky

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.

Kolik otázek na kolik možností?

ikona boxu
Úloha: Víc otázek, víc možností
ikona boxu
Výška stromu
Drobné připomenutí: nejvyšší počet otázek potřebných k rozhodnutí podle daného stromu nazýváme také výška stromu. Pokud je strom optimální, odpovídá výška stromu optimálnímu počtu otázek.

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í.

  1. 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.
  2. 16+1=17; Jedna otázka navíc nám umožní zjistit jednu možnost navíc.
  3. (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í.
  4. 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í.
  5. 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í.
  6. Jiná možnost - jaká, proč?

ikona boxu
Nápověda
  • 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í.

ikona boxu
Úloha: Víc možností, víc otázek

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.

  1. 4+4=8; Čtyřmi otázkami určíme jeden ze 16 dílů o 256/16=16 možnostech, v tomto dílu najdeme správnou možnost opět pomocí 4 otázek.
  2. √256=16; Když byly potřeba 4 otázky pro 16 možností, bude pro 162 možností potřeba 42 otázek.
  3. 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í.
  4. 256/2=128; Každá otázka ubere polovinu možností, polovina z 256 je 128.
  5. 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.
  6. 256-1=255; Strom pro 16 možností obsahuje 15 otázek, strom pro 256 možností bude obsahovat 255 otázek.
  7. Jiná možnost - jaká, proč?

ikona boxu
Nápověda

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?

ikona boxu
Úloha: Jaký je vztah mezi počtem potřebných otázek a počtem rozlišitelných možností?

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í.

ikona boxu
Nápověda

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ě.

ikona boxu
Zkratka
Vztah mezi počtem možností a počtem potřebných otázek umíme popsat jako počet postupných vydělení počtu možností dvěma. Znáš matematickou funkci, která právě tohle vyjadřuje?

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í.

ikona boxu
Pamatuj si:

Máme-li k dispozici n otázek, můžeme při optimálním postupu rozlišit nanejvýš 2n možností.

ikona boxu
Hashtag?

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.

ikona boxu
Úloha: Jak počítat potřebný počet otázek, když máme možností lichý počet?

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?

ikona boxu
Nápověda
Můžeme mít smůlu, a vyloučit "menší polovinu" možnosti. Pro další půlení proto musíme vždy počítat s tou "větší polovinou".

Ř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.

ikona boxu
Jak může pro různé počty možností vyjít stejný počet otázek?
23 možností vyžaduje 5 otázek, stejně jako 32 možností (a stejně jako libovolný jiný počet v rozsahu 17-32). Někomu možná připadá zvláštní, že různý počet možností vyžaduje stejný počet otázek. Vyplývá to ze struktury rozhodovacího stromu. Zamyslete se: Připadá někomu z vás 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 6 nebo 7 přímých předků.

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í.

ikona boxu
Jiné vyjádření
Kromě „s jednou otázkou navíc rozeznáme dvojnásobek možnosti“ můžeme říct také „s dvojnásobkem otázek rozeznáme druhou mocninu původního počtu možností“.

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.

Graf růstu výšky stromu.svg

Vztah výšky optimálního stromu k počtu listů. Je ti tvar toho grafu povědomý?


Množství informace a počet vyloučených možností

ikona boxu
Množství informace závisí na příjemci
Množství informace ve zprávě není jen vlastnost té zprávy. Je to vlastnost zprávy spolu s příjemcem (stavem jeho znalosti). Když tedy dva různí příjemci uvažují s různými možnostmi (každý ví o skutečnosti něco trochu jiného), může pro ně být informační hodnota stejné zprávy velmi rozdílná. Pokud vím, že je po poledni, neřekne mi už zpráva „Je po Večerníčku“ tolik, jako mému kamarádovi, který to neví.

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:

ikona boxu
Pamatuj si:

„množství informace“ = „neurčitost před zprávou“ — „neurčitost po zprávě“

ikona boxu
Úloha: Nemám tušení, kolik je hodin

Š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?

ikona boxu
Nápověda

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?

ikona boxu
Nápověda

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:

ikona boxu
Možnost dalšího procvičení

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.
  1. V místní škole ještě probíhá výuka.
  2. Je tři čtvrti na (nějakou) celou.
  3. Je sudá hodina.
  4. Je před Večerníčkem.
  5. Je víc minut než hodin.
  6. Je mezi půl desátou dopoledne a půl šestou večer.
  7. Je tři čtvrti na tři.

Cifernik probiha vyuka.png

A

Cifernik 9 30 17 30.png

B

Cifernik 14 45.png

C

Cifernik pred vecernickem.png

D

Cifernik tri ctvrti.png

E

Cifernik po poledni.png

F

Cifernik vic minut nez hodin.png

G

Cifernik suda hodina.png

H

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?

ikona boxu
Nápověda

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

Cifernik po poledni.png

Po poledni.

Cifernik probiha vyuka.png

Probíhá výuka.

Cifernik tri ctvrti.png

Tři čtvrti.

Cifernik suda hodina.png

Sudá hodina.

Cifernik pred vecernickem.png

Před Večerníčkem.

Cifernik vic minut nez hodin.png

Víc minut než hodin.

Cifernik 9 30 17 30.png

9:30-17:30.

Cifernik 14 45.png

14:45
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?

ikona boxu
Nápověda

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

Cifernik po poledni.png

Po poledni.

Cifernik probiha vyuka.png

Probíhá výuka.

Cifernik tri ctvrti.png

Tři čtvrti.

Cifernik suda hodina.png

Sudá hodina.

Cifernik pred vecernickem.png

Před Večerníčkem.

Cifernik vic minut nez hodin.png

Víc minut než hodin.

Cifernik 9 30 17 30.png

9:30-17:30.

Cifernik 14 45.png

14:45
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

ikona boxu
Podrobnosti pro zájemce: 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:

Cifernik probiha vyuka po poledni.png

Odpolední výuka: Probíhá výuka a zároveň je po poledni.

Cifernik tri ctvrti po poledni.png

Je po poledni a zároveň je tři čtvrti na celou.

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

ikona boxu
Podrobnosti pro zájemce: 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:

Cifernik 14 45.png

Zpráva o přesném čase (14:45) poskytne všechnu chybějící informaci a odstraní veškerou neurčitost.

Cifernik tri ctvrti.png

Tato zpráva vyloučí víc možností, poskytne proto víc informace.

Cifernik po poledni.png

Stejný počet možností vyloučí zpráva „Je po poledni“.

Cifernik suda hodina.png

Zpráva „Je sudá hodina“ vyloučí právě polovinu možností (bílá plocha).
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.
ikona boxu
Další požadavky
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. Podívejme se na dvě nezávislé zprávy, např. „Je tři čtvrti na celou“ a „Je sudá hodina.“

Jak změřit, kolik toho nevíme?

ikona boxu
Měření informace bez logaritmu

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ě.

ikona boxu
Podrobnosti pro zájemce: jak změřit, kolik toho nevíme?
ikona boxu
Úloha: Doplň tabulku

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

Cifernik nevim nic.png

nic
1440 11

Cifernik tri ctvrti.png

Tři čtvrti
24 1416/1440 = 59/60

Cifernik suda hodina.png

Sudá hodina
10

Cifernik nevim nic.png

nic
1440

Cifernik suda hodina.png

Sudá hodina
720 720

Cifernik tri ctvrti.png

Tři čtvrti
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

Cifernik nevim nic.png

nic
1440 11

Cifernik tri ctvrti.png

Tři čtvrti
24 5 1416 1416/1440 = 59/60 6

Cifernik suda hodina.png

Sudá hodina
720 10 12 4 708 708/720 = 59/60 6

Cifernik nevim nic.png

nic
1440 11

Cifernik suda hodina.png

Sudá hodina
720 10 720 720/1440 = 1/2 1

Cifernik tri ctvrti.png

Tři čtvrti
24 5 12 4 12 12/24 = 1/2 1
ikona boxu
Samostatný průzkum
Máme-li čas a šikovné studenty, můžeme samozřejmě nechat i tuto slepou (byť nápomocnou) uličku prozkoumat samotné studenty.

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

Cifernik suda hodina.png

„Je sudá hodina.“

Cifernik tri ctvrti.png

„Je tři čtvrti na celou.“

Cifernik suda tri ctvrti prunik.png

„Je tři čtvrti na nějakou lichou hodinu.“

Cifernik 14 45.png

„Je tři čtvrti na tři.“
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

Měření množství informace počtem ušetřených otázek
Zpráva

Cifernik suda hodina.png

„Je sudá hodina.“

Cifernik tri ctvrti.png

„Je tři čtvrti na celou.“

Cifernik suda tri ctvrti prunik.png

„Je tři čtvrti na nějakou lichou hodinu.“

Cifernik 14 45.png

„Je tři čtvrti na tři.“
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.

ikona boxu
Pamatuj si:

„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.

ikona boxu
Pamatuj si:

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í

ikona boxu
Podrobnosti pro zájemce: 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!


ikona boxu
Úloha:

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.

ikona boxu
Nápověda

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 0,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“

Cifernik tri ctvrti.png

„Je tři čtvrti na celou.“
Zpráva redukuje možnosti na 1/60 původního počtu. Tohle množství v celých bitech vyjádřit nelze. Pomocí šestibitové zprávy(tedy pomocí šesti půlení) bychom totiž měli být schopni zredukovat možnosti na 1/64 původního počtu, a ne jenom na 1/60. Přitom 5 bitů(pět půlení) je málo, pětibitová zpráva zredukuje možnosti jen na 1/32. Skutečné množství informace tedy musí být někde mezi tím, mezi 5 a 6 bity (a zřejmě blíž k 6). Dvojkový logaritmus nám dá přesný výsledek.

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.

ikona boxu
A co sčítání množství informace v nezávislých zprávách?

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!

ikona boxu
Pamatuj si:

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í

ikona boxu

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.