Načítám

Transkript

Přemýšlejte o tomto: Alice a Bob přišli na to jak si předávat zprávy mezi svými "domky" ve stromech Zpočátku používali v noci oheň a okenice během dne. Pak využili drát zapojený různými způsoby. Nakonec po drátu vysílali elektrické impulsy, a teď pracují na experimentální bezdrátové metodě. Problém je, že aby mohli zaplatit za vybavení, potřebovali peníze. Tak se rozhodli nabídnout své služby – za poplatek ostatním. První den měla Alice tři nové zákazníky, kteří chtěli vysílat zprávy svým kamarádům do Bobova domku ve stromu. První zákazník chtěl poslat seznam 10 dopadů minci. Druhý zákazník chtěl poslat slovo obsahující 6 písmen. A třetí zákazník chtěl poslat seznam karet, které mu byly rozdány v pokru. Otázkou teď je, jak by měla Alice stanovit cenu. No, cena zprávy by měla záviset na tom, jak dlouho trvá její přenos. Ale jak změřit délku různých typů zpráv pomocí společné jednotky? Abychom to zjistili, zahrajeme si hru. Představte si, že teď jste Bob. A víte, že Alice vám chce poslat tyto zprávy. Ale vše, co můžete udělat je, dostat odpovědi ano / ne na otázky, které jste předem připravili. Alice odpoví odesláním sekvence nul a jedniček, využije metodu variace. Připomeňme si, že všechny jejich metody přenosu zahrnují výměnu rozdílů. Takže 1 může být znázorněna otevřeným oheň, nebo otevřenou okenicí, nebo elektrický impulsem. Bez ohledu na to jak jedničky a nuly znázorňujeme, můžeme tomu říkat "binární čísla" – protože binární číslo může mít pouze jednu ze dvou hodnot-0 nebo 1. Dejme tomu, že 0 představuje "Ne," a 1 představuje "Ano." Váš úkol, je se vždy zeptat na minimální počet otázek, aby bylo možné určit přesně zprávu. Nejprve si promyslíme seznam výsledků 10 dopadů mince. Na každý dopad může odesílatel (tedy Alice) pomýšlet jako na výběr ze dvou různých stran mince (symbolů) panna nebo orel. Kolik otázek se musíte zeptat, abyste zjistili, co padlo? Jedna otázka - např. Je to panna? - bude stačit. Jaký je minimální počet otázek pro zjištění 10 dopadů mince? 10krát jsme vyhodili minci do vzduchu. 1 otázka na jeden dopad. To je 10 otázek -- nebo deset binárních čísel, které musíme odvysílat, abychom předali tuto zprávu. Teď se zamyslíme nad písmeny. Alice jako odesílatel si může představit písmena jako výběr jednoho z 26 symbolů. (Bereme zde v úvahu anglickou abecedu, která má 26 písmen). Začněme s nejjednodušší zprávou -- to je zpráva s jedním písmenem. Kolik potřebuji otázek? Je to A? Je to B? Je to C? Je to D? A tak dále. Ale to není minimální počet otázek. Nejlepší bude klást otázky, které vyloučí polovinu možností. Například polovina abecedy je mezi písmeny M a N. Jako první otázku bychom se mohli zeptat, "je to méně než N?" Pokud je odpověď 1 – ano – vyřadíme polovinu možností – [takže máme] těchto 13 směrem doleva. A protože nemůžeme rozdělit písmeno v polovině, dělíme možná písmena do skupin po 6 a 7. A je to méně než G? Dostáváme odpověď 1, tedy "ano". A nyní zbývá 6 možných písmen. A můžeme je rozdělit na polovinu a zeptat se, "Je to menší než D?" Dostáváme odpověď 0, tedy "ne". Zůstala nám 3 možná písmena. A teď si můžeme vybrat stranu a zeptat se, "Je to D?" Dostáváme odpověď 0, tedy "ne". A konečně nám zbývají jen dvě možnosti. Ptáme se "Je to E?" Dostáváme odpověď "ne". A po pěti otázkách máme správně určené písmeno: F. Uvědomte si, že nebudeme nikdy potřebovat více než pět otázek. Takže nutný počet otázek bude nejméně 4 a nejvíce 5. A obecně, počet otázek na druhou se rovná počtu možných zpráv – který jsme dříve definovali jako "message space." Jak můžeme vypočítat přesný průměr – nebo očekávaný počet otázek, vzhledem k 26? Zeptáme se opačně Dvojka umocněná nějakým číslem se rovná 26. A pro odpověď na tento typ otázek přirozeně využijeme logaritmickou funkci, o základu 2– protože logaritmus o základu 2, dvaceti šesti nám dá exponent kterým musí být dvojka umocněna abychom dostali 26. Což je přibližně 4,7. Takže v průměru přibližně 4,7 otázky bude potřeba na jedno písmeno. Minimálně. A vzhledem k tomu, že chce předat slovo s 6 písmeny, Bob může očekávat, že se zeptá minimálně na 28,2 otázek – Což znamená, že Alice bude muset poslat maximálně 29 binárních čísel. A konečně použijeme tento vzorec pro novou zprávu - rozdané karty na poker. No na každý symbol odesílatel, tedy Alice, může pomýšlet jako na výběr 1 z 52 různých symbolů. A v tomto případě počet otázek je stejný jako počet opakování musíme rozdělit balíček karet a zeptat Alice, ve které hromádce je – dokud nám nezůstane jen jediná karta – a zjistíme, že obvykle potřebujeme karty takto rozdělit šestkrát – nebo, že potřebujeme 6 otázek – a někdy 5. Ale můžeme ušetřit čas a jen použít naši rovnici. Logaritmus (o základu 2) 52 je přibližně 5,7, Protože 2 na 5,7 je přibližně 52, tak minimální počet otázek, v průměru je 5,7 na jednu kartu. Hráč pokeru má v ruce obvykle pět karet. Vyslat zprávu o tom, jaké má karty vyžaduje průměrně 28,5 otázek. Jsme hotovi. Teď máme naši jednotku. Je založena na minimálním počtu otázek pro definici zprávy – nebo 'výšku' rozhodovacího stromu. A vzhledem k tomu, že tyto informace vysílá Alice jako binární čísla můžeme zkrátit tento [výraz], a naší jednotka nazvat "bit" -- místo "binární číslice." Takže máme 10 hodů mincí, to vyžaduje 10 bitů. Slovo se 6 písmeny potřebuje 28,2 bitů. rozdané poker karty pro jednoho hráče 28,5 bitů. Alice, pak rozhodne že bude požadovat jednu korunu za bit, a začne vybírat poplatky. Teď tato myšlenka se objevila v roce 1920. Byl to jeden z abstraktních problémů, o kterých technici v komunikacích přemýšleli. Ralph Hartley byl plodný elektronik a výzkumník, který vycházel z myšlenek Harryho Nyquista – oba pracovali v Bellových laboratořích po první světové válce. A v roce 1928, Hartley publikoval důležitý článek s názvem "Přenos informací." A v něm definoval slovo "informace" za použití symbolu h takto: h = n × logaritmus s, kde h je naše informace, n je počet symbolů – ať už jsou to noty, písmena, čísla, atd. – a s je počet různých symbolů, které jsou k dispozici v daném výběru. A to lze také zapsat jako h = logaritmus s ^ n. A Hartley píše, "Co jsme udělali pak je, že jsme vzali naše praktické měření informace, logaritmus počtu možných symbolů posloupnosti. Takže informace je logaritmus "message space". Ale uvědomme si, že v tomto videu jsme předpokládali, že výběr symbolů je náhodný -- pohodlné zjednodušení. Ale v reálném světě víme, že většina komunikace - jako řeč -- není vždy náhodná. Je to rafinovaná směs předvídaného a překvapení. Neházíme kostkou, když píšeme písmena. A je to právě tato předvídatelnost, která ústí ve významnou úsporu délky vysílání. Protože když předpovídáme, nemělo by být nutné se ptát na tolik ANO / NE otázek, abychom to dokázali definovat. Ale jak bychom mohli formálně modelovat tento rafinovaný rozdíl? Ta otázka nás přivádí ke klíčovému porozumění v rámci našeho příběhu. Napadá vás, co to může být?