If you're seeing this message, it means we're having trouble loading external resources on our website.

Pokud používáš webový filtr, ujisti se, že domény: *.kastatic.org and *.kasandbox.org jsou vyloučeny z filtrování.

Hlavní obsah

Matematická teorie komunikace

Claude Shannon ukázal, jak lze generovat "anglicky vypadající" text pomocí Markovovských řetězců. Tvůrce: Brit Cruise.

Chceš se zapojit do diskuze?

Zatím žádné příspěvky.
Umíš anglicky? Kliknutím zobrazíš diskuzi anglické verze Khan Academy.

Transkript

Shannon právě skončil vývoj teorií vztahujících se k šifrování a proto si byl dobře vědom, že lidská komunikace je směsí náhodnosti a statistických závislostí. Písmena v naších zprávách byla zjevně do určité míry závislá na předchozích písmenech. V roce 1949 publikoval přelomový článek "A Mathematical Theory of Communication". Využívá v něm Markovovy modely jako nástroj k pochopení komunikace. Začíná s ukázkovým příkladem. Představte si, že se setkáte s textem napsaným v abecedě písmen "A" "B" a "C". O tomto jazyce nic nevíte. Ale všimnete si, že se "áčka" drží spolu zatímco "béčka" a "céčka" ne. Pak ukázal, že můžete navrhnout stroj pro generování podobně vypadajícího textu použítím Markovova řetězce. Začal aproximací nultého řádu, kde jsme jen nezávisle vybrali každý symbol (A, B nebo C) náhodně a vytvořili řetězec. Tento řetězec ale nevypadá jako ten původní. Shannon ukázal, že lepší je aproximace 1. řádu, kde jsou písmena vybrána nezávisle, ale podle pravděpodobnosti s jakou se daná písmena v řetězci objevují. Tohle už je trochu lepší, protože "áčka" se objevují více, ale stále to nezachycuje strukturu. Další krok je klíčový. Aproximace druhého řádu, bere v potaz každý pár symbolů. V tomto případě máme 3 stavy. První stav představuje všechny páry začínající na "A", druhý páry začínající na "B" a třetí páry začínající na "C". Všimněte si, že kelímek s "A" má mnoho párů "AA", protože podmíněná pravděpodobnost "A" po "A" je v naší původní zprávě větší. Teď můžeme vytvářet sekvence pomocí modelu 2. řádu takto: Začneme kdekoli, vybereme kostičku a napíšeme první písmeno a posuneme se ke kelímku podle druhého písmena. Pak vybereme novou kostičku a tento proces opakujeme donekonečna. Tato posloupnost již začíná vypadat jako naše původní zpráva, protože tento model zahrnuje podmíněné závislosti mezi písmeny. Dalšího zlepšení dosáhneme pomocí aproximace 3. řádu, která zahrnuje skupiny 3 písmen - triagramy. V tomto případě potřebujeme 9 stavů. Shannon poté použil stejný postup na reálný anglický text a použil statistiku, která byla známa pro písmena, páry, triagramy atd. Ukázal to samé zlepšení pro přechody od aproximací 0. řádu, 1. řádu, 2. řádu a 3. řádu. Poté zkusil to samé pomocí slov místo písmen. Napsal: "Podobnost s běžným anglickým textem..." ...se velmi zvyšuje s každým řádem." A opravdu, tyto stroje produkovaly sice bezobsažný text, ale obsahovaly podobnou statistickou strukturu, kterou je možno vidět v angličtině. Shannon poté definoval kvantitativní míru informace, když si uvědomil, že množství informace ve zprávě musí souviset s návrhem stroje, který by mohl být použit ke generování podobných sekvencí. To nás přivádí ke konceptu entropie.