Icon Forklift.svg

Do této učebnice průběžně přibývá obsah. Současný stav je už ale dobře použitelný a byla by škoda čekat, až bude publikace zcela hotová. Pravděpodobně bude pořád co zlepšovat. Na stránce Kontakt nám můžete dát vědět, pokud si všimnete nějakých chyb či jiných nedostatků.

Data a význam

Z Informatika pro každého
Přejít na: navigace, hledání
Měření stromů a informací · Kódování a redundance
ikona boxu
Co se naučíš:
  • Určit počet možností, které lze kódovat slovem dané délky
  • Určit délku slova dané abecedy, které může zakódovat jednu z daného počtu možností
  • Rozlišovat množství dat a množství informace
  • Spočítat minimální délku zprávy pro dané množství informace, resp. maximální množství informace pro danou délku zprávy
  • Jaká je spojitost dvou pohledů na informaci: jako na úbytek možností a jako na zprávu spolu s jejím významem
  • Co je to kódovací strom, jak souvisí se stromem rozhodovacím a používat jej
  • Co a k čemu je datový typ
  • Jak fungují násobné jednotky množství informace a proč
ikona boxu
Obvyklý průběh hodiny

V této hodině se obloukem vracíme k pojetí informace jako datové zprávy spolu s jejím významem. Studentům ukážeme, že jde o různé pohledy na stejnou věc. Jiný pohled ovšem otevře jiné souvislosti. Na příkladech a úlohách se tak studenti blíže seznámí s některými pojmy (kódování datový typ) a v nových souvislostech se objeví pojmy známé (dvojková soustava, násobné předpony jednotek).

Vlastně nic zde není vyloženě nová látka. Počítání délek a kapacit zpráv je kombinatorika, kódovací stromy jsou jen přebarvené rozhodovací a tak dále. Nové pohledy na známé jevy jsou nicméně důležité (např. pojem datového typu, komplikace u předpon).

Spinning Dancer.gif

Význam přijímaným datům přisuzuje příjemce. Otáčí se žena na obrázku doleva, či doprava? Interpretuje někdo pohyb siluety opačně? Kdo má pravdu? Dovedeš se vžít do situace druhého pohyb ženy ve svých očích otočitMůžeš zkusit předem představit, jak vlastně opačný pohyb vypadá, různě rychle mrkat, ženu zakrýt a dívat se jen na odraz nohou dole.?
Řekli jsme si, že informace jsou data spolu s jejich významem, a pak jsme zjistili, že informace je úbytek možností. Znamenají tedy snad interpretovanáPřipomeneme, že interpretace je výklad, tedy přiřazení významu — ať už básni, nebo poslounosti bitů. Slovem „význam“ zde míníme „co to znamená“, nikoliv „jak je to důležité“. data úbytek možností? Inu, ano. Jedno je potřeba k druhému a naopak: bez interpretování dat nemáme jak vyloučit možnosti a interpretace dat je vlastně vyloučení ostatních interpretací. Nemluvě o tom, že bez vyloučení nějakých možností nemá interpretace dat žádný přínos.

Data jsou pouhou posloupností znaků bez významu. Odpovědi „ANO, NE, ANO, ANO“ nám o myšleném zvířeti mnoho neřeknou, pokud nevíme, co znamenají, tedy k jakým se vážou otázkám. Informace tedy zaznamenáváme jako posloupnost znaků. Vždycky. Hudbu zapisujeme do not (nebo nahráváme třeba do formátu MP3), fotografie jsou definovány barvami pixelů, čísla zapisujeme číslicemi. Prozkoumej následující ukázky.

Příklad: Různě zaznamenaná data

Podívej se na jednotlivé obrázky. Poznáš, co na nich je? Jakým způsobem jsou v jednotlivých případech data zaznamenána? Lze je rozdělit na nějaké menší, základní díly, jako třeba písmena nebo jiné znaky? Které ukázky dovedeš interpretovat, které nikoliv? Proč?

V ukázkách Vidíš mnoho znaků, tedy dat, ale ne všichni známe jejich význam. Ty znaky, které nedovedeme interpretovat, nám žádnou informaci nedávají. Z našeho pohledu ty texty mohou být doslova o čemkoliv. Informaci z dat získáme teprve jejich interpretací. Význam zprávě tedy přisuzuje příjemce. Význam dění v okolním světě přisuzujeme my sami. Například je na každém z nás, jak se chceme na svět dívat a jaký význam přisoudíme různým událostem ve svém životě.

ikona boxu
Zajímavé důsledky
  1. Nelze uvažovat informaci bez dat. To by nebylo co interpretovat. Myšlenky nedovedeme předávat nějak „přímo“. Vlastně ani není jasné, jestli „samy o sobě“ existují (a jak to případně ověřit). O informaci hovoříme vždy ve spojení s jejím zakódováním, tedy s její reprezentací. Jinak není o čem hovořit. Leckdo si už při zkoušení mohl ověřit: máme-li v hlavě myšlenku, kterou nedovedeme sdělit, je to pro ostatní zcela stejné, jako bychom tu myšlenku neměli.

Možná už jste také ve společenských vědách uvažovali, jestli třeba hrachovku k obědu vidí všichni stejně zelenouCo když ji někdo vidí modře, a modrou naopak zeleně?, nebo jaké to je být netopýremKdyby dejme tomu uměl mluvit, jak by to vysvětlil? Jak vyprávět o létání, spaní hlavou dolů a vnímání světa prostřednictvím echolokace?.

  1. Zároveň data se neobejdou bez fyzického média, „nosiče“. Data musí být vždy hmotná. Neznáme případ, kdy by docházelo k přenosu informace jinak, než prostřednictvím uspořádání nějaké látky (barva na papíře) či pole (radiový signál). Uspořádání může být v prostoru (polohy výstupků a prohlubní v drážce gramofonové desky) i v čase (postupné změny tlaku vzduchu, tvořící zvuk).

Podaří se ti přijít na nějaký druh informace a způsob jejího předávání, který nelze přepsat jako posloupnost znaků?

ikona boxu
Nápověda
Ne každá úloha v téhle učebnici je řešitelná.


V našich předchozích úvahách jsme pokládání otázek (a tím i význam jednotlivých odpovědí) řídili pomocí rozhodovacích stromů. Představme si, že se na používání téhož rozhodovacího stromu (viz následující obrázek) pro komunikaci o číslech všichni shodnou. Když si pak myslím číslo a někdo druhý se ho snaží „uhodnout“, nemusím čekat na jeho otázky. Používáme stejný rozhodovací strom, takže vím předem, které otázky položí a v jakém pořadí. Stačí tedy poslat rovnou odpovědi.

Tentýž strom, ovšem místo odpovědí ANO a NE jsou použity 1 a 0. Čísla jsou pak jednoznačně určena právě posloupností nul a jedniček.

Strom 0 15 otoceny 01.svg

Rozhodovací a zároveň kódovací strom pro celá čísla v rozsahu 0-15. Posloupnost odpovědí jednoznačně určuje konkrétní možnost, např. číslo 11.

Strom 0 15 otoceny.svg

Příklad: Příklad reprezentace čísla odpověďmi na otázky

Předpokládejme použití stromu níže (vpravo) a odpovědi (neboli datovou zprávu) ANO, NE, ANO, ANO. K interpretaci použijeme strom. Od kořene následujeme odpovědi až k příslušnému listu, tedy uvažovanému číslu. Vidíme, že odpovědi se váží postupně k porovnání s 8, 12, 10 a 11 a vedou k číslu 11.

Strom nám tedy umožňuje jednoznačně reprezentovat libovolné číslo v daném rozsahu pomocí posloupnosti odpovědí. Najednou ho používáme jiným způsobem, totiž jako kódovací strom: nikoliv ke zjišťování myšleného čísla postupným dotazováním, ale k jeho zakódování (a následnému dekódování). Větvení už neodpovídá otázkám, ale odlišnostem kódů pro různé kódované možnosti. Znázornění stromu přitom může vypadat úplně stejně.

ikona boxu
Úloha: Kterému číslu odpovídá zpráva ANO, ANO, NE, ANO?


ikona boxu
Nápověda
Postupuj od kořene podle jednotlivých odpovědí ve zprávě.

Řešení

13
ikona boxu
Úloha: Najdi zakódování čísla 3.
Jestli se chceš procvičit víc, zkus si i další čísla, případně jiné stromy (třeba hned ten vedle, s jedničkami a nulami).
ikona boxu
Nápověda
Zde musíš postupovat opačně:
  1. Najdi číslo 3 mezi listy stromu.
  2. Najdi cestu od kořene k danému listu.
  3. Na otočeném stromě teď stačí prostě přečíst odpovědi-kódy, které po cestě ke kódované hodnotě mineš.

Řešení

NE, NE, ANO, ANO

V praxi se samozřejmě častěji uplatní číslice 1 a 0, namísto ANO a NE, tak jako na druhém vyobrazeném stromu. Princip ovšem zůstává stejný. Zároveň je lhostejné, že uvažujeme zrovna čísla. Čísla totiž mohou reprezentovat cokoliv jiného. Všechno, o čem má smysl se přesně dorozumívat, umíme nějak seřadit a očíslovat (a když už číslujeme, můžeme samozřejmě číslovat binárně, tedy pomocí číslic 1 a 0).


Když se na takovém způsobu očíslování dohodneme, stačí se už dál namísto původních objektů bavit už jen o těch číslech. Vzpomeň si v téhle souvislosti na pojem zobrazení z matematikyZobrazení je předpis, který každému prvku definičního oboru přiřazuje právě jeden prvek oboru hodnot. Autům registrační značky, lidem matky a otce, výrokům jejich pravdivost, zápisům konstrukcí jejich výsledky, racionálním číslům jejich převrácené hodnoty atp. - vzpomínáš?. V informatice se využívá velmi často. Zde množině nějakých objektů (studentů školy, bankovních účtů, výrobkům v obchodě, střepům z keltské osady v muzeu...) jednoznačně přiřazujeme hodnoty přirozených čísel, a těmto hodnotám potom binární kódy. Výhodou také je, že pak můžeme použít všechno, co už s čísly umíme — např. metodu půlení intervalů.


ikona boxu
Úloha: Jaký znáš další způsob, který umožňuje zapisovat čísla jen pomocí číslic 1 a 0?
ikona boxu
Poznámky pro učitele

Tady se dá pochopitelně vyřádit. Zde předpokládáme, že dvojkovou soustavu známe klasicky (součty mocnin) a teď se na ni díváme jinýma očima - jako na vedlejší výsledek optimálního hádání čísla (resp. jedné z očíslovaných možností, kde ty možnosti jsou cokoliv).

ikona boxu
0, 1, 2, 3, ...

Na tomto příkladu mimo jiné vidíš jeden z důvodů, proč je příjemné pracovat s rozsahy hodnot, které začínají nulou: Půlení intervalu se nám pěkně shoduje s dvojkovou soustavou. Informatici počítají od nuly často a rádi. Ty taky, jen si to možná neuvědomuješ. Při narození ti není jeden rok, vstup do budovy není v prvním patře — najdeš další podobné příklady? V každém případě: informatik si vždy hlídá, kdy se počítá od nuly a kdy od jedné.

Porovnej jej s naším stromem! V čem se shodují, v čem se liší?

ikona boxu
Hádání čísla po cifrách

Někteří z vás možná při zjišťování myšlených čísel postupovali po jednotlivých cifrách. Nejdřív se doptali (třeba i půlením intervalu) na jednotky, pak na desítky, a tak dále, dokud nezjistili všechny cifry. Tenhle postup je člověku velmi blízký, protože přirozeně rozkládá daný problém na menší části - tedy čísla na jednotlivé cifry. Ze znalosti jednotlivých cifer se pak snadno složí celé hledané číslo.

Teď už dovedeš vysvětlitZkus to!, proč takové strategie nejsou optimálníNedělí totiž počet zbývajících možnosti na poloviny. Dělení na poloviny po desítkových cifrách nejde: deset můžu rozpůlit jen jednou, podruhé už poloviny nebudou stejné. A tahle neobratnost se nasčítá u každé cifry.

Jak ale teď vidíme, myšlenka hádání po cifrách by použít šla. Jen je třeba zvolit vhodnou soustavu. Takovou, která umožní zjistit hodnotu na daném místě půlením — takže např.Jaké jsou další možnosti? Používají se v informatice? soustavu dvojkovou. Na rozhodovacím stromě ale můžete vidět, že hádání po dvojkových cifrách „shodou okolností“ vede na v podstatě stejnou strategii, jako půlení intervalů. Je to další ukázka toho, že na dvojkovou soustavu v informatice narazíte na každém rohu.

Datový typ

ikona boxu
Přípona vs. typ

Zamysli se: je přípona definována typem souboru? Je typ souboru definován příponou? Co je asi v e-mailové příloze s názvem takhle-vypadam-v-plavkach.jpg.exe? Dovedeš změnit příponu názvu souboru? Dovedeš změnit typ souboru?

V počítačích jsou ovšem jako nuly a jedničky ukládána všechna data. Jak počítač rozezná, co zrovna ta která skupina bitů reprezentuje, neboli jaké bylo použito kódování? V případě souborů řešení znáš. Konvence velí označovat typ souboru pomocí přípony. Název spustitelného souboru bude končit .exe, textový dokument třeba .odt, komprimovaná fotografie nejspíš .jpg.

ikona boxu
Datový typ je datový typ

Samozřejmě, i informace o datovém typu musí být v počítači nějak uložena a reprezentována. Takže existuje i datový typ datový typ.

Podobnou situaci a její řešení znáš z práce v tabulkovém procesoru. Data v buňce mohou být stále stejná, třeba 0,35 (s odpovídající binární reprezentací uvnitř počítače). Mohou ale mít různý význam, a proto může být vhodné je zobrazit různým způsobem - jako procenta, peníze, s různým počtem desetinných míst atd., a různým způsobem s nimi pracovat. „Typu čísla“ odpovídá v informatice pojem datový typ. Ten udává, jak se na danou skupinu bitů dívat a jak s ní zacházet. Je to kladné celé číslo, nebo může být i záporné, nebo nemusí být ani celé? Je to znak? Je to něco ještě komplexnějšího, jako třeba seznam čísel, URL adresa, barvy pixelů v obrázku? Má smysl daná data porovnávat, sčítat, řadit? Datový typ tedy určuje, jak interpretovat jednotlivé jedničky a nuly.


Velikosti pamětí a násobné jednotky informace

Kromě datového typu musí počítač také vědět, kde jsou data v paměti uložená. To je informace, uložená jak jinak, než binárně. Z toho plyne drobná komplikace. Základní jednotka je bit, o něco praktičtěji použitelný je bajt. Podle SI bychom pak měli tisíc bajtů v kilobajtu, milion bajtů v megabajtu atd. V takové situaci by ovšem skoro nic (třeba paměťové karty) nemělo velikost v celých kilobajtech či megabajtech.

Značka Předpona Význam ve světě lidí Význam ve světě informatiků
k kilo 103 210 = 1 024
M mega 106 220 = 1 048 576
G giga 109 230 = 1 073 741 824
T tera 1012 240 = 1 099 511 627 776

Když si na přesné určení místa v paměti, kam uložíme nějaká data, vyhradíme 1 bajt, rozlišíme jím 28=256 různých míst. Když má každé takové místo kapacitu třeba čtyř bajtůObvykle se totiž vyplatí pracovat rovnou s většími kusy dat než s jednotlivými bajty, natož bity., jsme schopni pracovat celkem s 256⋅4=1024 bajty paměti. Ale říkat kvůli tomu každou chvíli „1,024 kilobajtů“ je otravné. A na druhou stranu, kdyby se vyráběly paměti s přesně 1000 bajty, tak zbytečně mrháme s 24 nepoužitými adresami. To se dnes může jevit jako drobnost, ale byly doby, kdy informatici šetřili doslova každý bit. A dnes, kdy je paměť lehce dostupná, by ztráty způsobené rozdílem přirozeně adresovatelných velikostí (tedy mocnin 2) a standardních SI předpon (tedy mocnin 10) byly ještě větší. Příklad s adresováním čtyřbajtových kousků jedním bajtem je jen příklad, ale i jinak zvolené hodnotyNapř. víc bajtů pro určení jednotlivých míst v paměti. povedou k výsledkům ve tvaru mocniny dvou.

Výsledkem je, že informatici předpony kilo, mega, giga atd. nepoužívají jako ostatní, tedy jako 103, 106, 109 atd. Místo toho pracují s nejbližší mocninou dvou. Například 210=1024, což je „skoro přesně tisíc“, každý informatik ví z hlavy, a taky ví, že kilobajt je 1024 bajtů, megabajt je 1024 kilobajtů atd. Megabajt je 1024⋅1024 (čili 220) bajtů, tam už si přesnou hodnotu pamatovat netřeba, nevyskytuje se zase tak často.

Většina lidí ovšem nejsou informatici, a někteří informatici se jim snaží vyjít vstříc, a proto je třeba jistá opatrnost. Snadno se stane, že se dvoumegový soubor nevejde na dvoumegové místo na úložišti, protože ten soubor má 2048 kB, kdežto volného místa je jen 2000 kB. Pokud tedy záleží na přesnosti nebo jsme na hraně možností, je třeba sledovat, s jakými jednotkami opravdu pracujeme (a co přesně nám ukazuje který program). Opatrnost ušetří nejeden zádrhel či zklamání po nákupu komponenty, která je nečekaně malá.


Maximální množství informace v datové zprávě

Víme tedy, že data jsou sledem znaků z předem dané abecedy. Tohle pozorování nám umožní spočítat, kolik nanejvýš informace mohou data nést. Abychom si rozuměli, smí mít každá zpráva pro příjemce nanejvýš jeden význam. Takže kolik různých možných zpráv, tolik nanejvýšNěkolik různých zpráv může nést stejný význam, nějaké zprávy nemusí nést význam žádný. různých významů. Z počtu těchto možností už pak můžeme vyvodit, kolik se do zprávy dané délky přinejlepším vměstná informace.

ikona boxu
Úloha: Které je nejdelší české slovo?

Jak lze takovou informaci zjistit? Jak ji lze co nejspolehlivěji ověřit?

Slov není nekonečně mnoho, takže jistě existuje nějaká nejvyšší délka slova. Mají-li tedy slova omezenou délku, můžeme spočítat, kolik jich lze nanejvýš sestavit. Tento počet pak odpovídá nejvyššímu možnému počtu jejich různých významů. Další významy umožníme prodlužováním zprávy, v našem případě kladením slov za sebe, nebo rozšířením abecedy o nové znaky. Ve skutečnosti pro nás ovšem většina myslitelná slov (shluků písmen) žádný význam nemá.

Jak tedy spočítat, kolik nanejvýš různých významů může nést daná zpráva, a kolik tedy může nést informace? Postupujme od jednoduchých případů. Jednobitová zpráva je prostě buď číslice 0, nebo číslice 1. Jsou tedy celkem dvě možnosti. Použijeme-li bity dva, dostaneme možnosti 4: 00, 01, 10 a 11. Přidání jednoho bitu umožnilo oba předchozí případy (0 a 1) rozštěpit na dva další. Kolik možností může nanejvýš rozlišit tříbitová zpráva? Kolik čtyřbitová? Kdo si není jistý, vypíše všechny možnosti do tabulky.


ikona boxu
Pamatuj si:

Počet slov délky d sestavených ze znaků abecedy o a znacích je ad.

ikona boxu
Úloha: Jak spočíst potřebnou délku slova, nebo potřebnou velikost abecedy?



ikona boxu
Nápověda
Využij vztah mezi danými veličinami, který už znáš.
ikona boxu
Pamatuj si:

K rozlišení n možností pomocí (stejně dlouhých) slov z abecedy o a znacích jsou třeba slova délky aspoňSamozřejmě lze vzít i slova delší; neceločíselný výsledek je třeba zaokrouhlit nahoru. loga n znaků.

K rozlišení n možností pomocí slov délky d je třeba abeceda o přinejmenšímSamozřejmě lze použít abecedu i větší; opět, neceločíselný výsledek odmocnění je nutno zaokrouhlit nahoru. znacích.

Připomeň si z předchozích let, kolik různých hodnot se vejde do bajtu, neboli osmice bitů: Je to 28, tedy 256. Počet geneticky různých lidí můžeme velmi hrubě odhadnout jako 43 000 000 000, protože lidská DNA je z informatického hlediska slovo dlouhé asi 3 miliardy znaků, a ty znaky jsou celkem 4.

Teď už nás asi nepřekvapí následující „shoda okolností“. Máme-li k dispozici např. 1024 bitů, sestavíme z nich nanejvýš 21024 různých zpráv, využitelných k jednoznačnému určení 21024 možností. Z předchozí kapitoly víme, kolik informace nese zpráva, umožňující rozlišit daný počet možností. Je třeba spočítat dvojkový logaritmus z počtu rozlišených možností, neboli zjistit, kolikrát musíme možnosti rozdělit na poloviny, dokud nezbyde jediná. Spočtěme tedy log2(21024). Mělo by ti být jasné, že na tom není co počítat: výsledek je 1024. Vidíme, že zpráva dlouhá 1024 bitů může obsahovat nanejvýš také právě 1024 bitů informace. Dává to smysl: O jeden bit delší zpráva může znamenat nanejvýš o jeden bit více informace.

ikona boxu
Pamatuj si:

Délka zprávy v bitech odpovídá její informační kapacitě. Zpráva nikdy nemůže nést víc informace, než jak je dlouhá.

Na tuto nerovnost se lze samozřejmě podívat i z druhé strany:

ikona boxu
Pamatuj si:
Množství informace je dolním limitem délky zprávy potřebné na její zakódování.
ikona boxu
A co komprese?
Možná tě napadlo: ale data přece můžu zkomprimovat! Ano, ale komprese má svou mez. A tou je právě množství informace v datech. Někdy se toho dokonce využívá pro definici množství informace: Množství informace odpovídá právě délce jejího nejkratšího možného zakódování. Komprese prostě odstraňuje buď jen nadbytečná (např. opakující se) data, nebo i data, která nadbytečná nejsou - s nimi ovšem nenávratně mizí i obsažené informace.

Že se komprese vždycky nakonec zastaví si uvědomíš také díky oblíbenému informatickému triku: Zkoumaný jev neomezeně opakovat, nebo dokonce aplikovat na sebe sama. Mám-li zázračný kompresní program, který každý soubor zmenší o 10%, co se stane, když ho použiji na už jednou zkomprimovaný soubor? A pak znovu? A znovu? Aha!



Shrnutí

ikona boxu

Vyjádření „Informace jsou data spolu s jejich významem“ a „Informace je úbytek možností“ jsou jiným úhlem pohledu na tutéž skutečnost.

Data jsou jen posloupností znaků, sama o sobě žádný význam nenesou. Ten jim přiřadí až příjemce informace jejich interpretací. Ke kódování a dekódování lze použít kódovací stromy, které jsou obdobou stromů rozhodovacích.

Co má smysl kódovat (zaznamenávat jako data), lze kódovat jako čísla, a čísla lze výhodně kódovat pomocí dvojkové soustavy.

Druh dat (a tím i způsob jejich interpretace) určuje datový typ.

Násobné jednotky množství informace postupují zpravidla po 210 místo obvyklého kroku 103. Kilobajt je tak 1024 bajtů, nikoliv 1000 bajtů, obdobně se liší i další jednotky.

Počet různých slov délky d sestavených ze znaků abecedy o a znacích je da. Délka zprávy v bitech odpovídá její informační kapacitě. Zpráva nikdy nemůže nést víc informace, než jak je dlouhá.