Teoria informacji/TI Wykład 1: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
 
(Nie pokazano 39 wersji utworzonych przez 4 użytkowników)
Linia 1: Linia 1:
 +
[[Image:pascal_mini.jpg||thumb|right|200px|Blaise Pascal (1623–1662)]]
 
''Je n’ai fait celle-ci plus longue que parce que je n’ai pas eu le loisir de la faire plus courte. ''
 
''Je n’ai fait celle-ci plus longue que parce que je n’ai pas eu le loisir de la faire plus courte. ''
  
(Napisałem ten list trochę dłuższy, gdyż nie miałem czasu napisać go krócej).
+
(Napisałem ten [list] trochę dłuższy, gdyż nie miałem czasu napisać go krócej).
  
 
Blaise Pascal, ''Lettres provinciales'', 1657
 
Blaise Pascal, ''Lettres provinciales'', 1657
 +
  
 
=== ''Notacja'', co to takiego? ===
 
=== ''Notacja'', co to takiego? ===
  
Zaczynamy od prostego eksperymentu: Odgadnij ''słowo'' o którym ktoś myśli – na przykład zgadując literę po literze. Czy będzie to równie łatwe w przypadku odgadywania ''liczby''?
+
Na początek prosty eksperyment: Ktoś wymyśla ''słowo'', a kto inny ma za zadanie
Zauważmy że w przeciwieństwie do słów w języku naturalnym, liczby całkowite w systemie dziesiętnym są „ciasno upakowane”. Dowolny ciąg znaków ze zbioru {0, 1, …, 9} jest jakąś liczbą (o ile nie zaczyna się od zera), ale bardzo niewiele ciągów z liter {a, b, …, z} jest sensownymi słowami. Możliwym wyjaśnieniem tego jest fakt że nasze „algorytmy” do komunikacji za pomocą słów wymagają znacznie więcej redundancji niż te do operowania liczbami.
+
je odgadnąć, zgadując literę po literze.  
 +
Zwykle udaje się to znacznie szybciej niż by to wynikało z pesymistycznego oszacowania.
 +
Czy jednak będzie to równie łatwe w przypadku odgadywania ''liczby''?
 +
Zauważmy, że w przeciwieństwie do słów w języku naturalnym, liczby całkowite w systemie dziesiętnym  
 +
(czy ogólnie k-arnym, dla k > 1)
 +
są „ciasno upakowane”. Mianowicie dowolny ciąg znaków ze zbioru {0, 1, …, 9} przedstawia jakąś liczbę
 +
(jeśli zignorujemy początkowe zera),  
 +
podczas gdy bardzo niewiele ciągów utworzonych
 +
z liter {a, b, …, z} to sensowne słowa. Wynika to między innymi z tego, że nasze „algorytmy” do komunikacji za pomocą słów wymagają znacznie więcej redundancji niż te do operowania liczbami. Tę redundancję szczególnie widać, gdy jest ona wprowadzana celowo.
 +
 
 +
Przykład: Wypełniając czek wpisujemy kwotę zarówno przy pomocy liczb, jak i słownie. Zajmuje to oczywiście znacznie więcej miejsca, ale dzięki temu nie musimy obawiać się, że jakaś literówka zmieni wartość wpisanej kwoty.
 +
Podobnie postępujemy, gdy przekazując przez telefon na przykład
 +
nazwę stolicy Gruzji, mówimy: T jak Teresa, B jak Barbara, I jak Iwona, L jak Lucyna,
 +
I jak Iwona, S jak Stanisław, I jak Iwona. Radiowcy mają zresztą na tę okoliczność międzynarodowy standard,
 +
tzw.
 +
alfabet fonetyczny: ''Alpha Bravo Charlie Delta... Yankee Zulu''.
 +
 
 +
'''Teoria informacji''' charakteryzuje w sposób matematyczny  zapis, przesyłanie i odtwarzanie informacji.
 +
Dąży przy tym do pogodzenia
 +
dwóch przeciwstawnych celów:
 +
* zapisywania wiadomości jak najzwięźlej
 +
* chronienia wiadomości przed przekłamaniami podczas transmisji.
 +
 
 +
 
 +
[[Image:rusell.jpg||thumb|right|200px|Bertrand Russell (1872–1970)]]
 +
Zacznijmy od prostego pytania. Czy istnieją wiadomości, których nie da się zapisać zwięźlej?
 +
Przypuśćmy, że wiadomość jest liczbą naturalną. Liczby naturalne można na wiele sposobów zapisać
 +
w języku polskim,
 +
na przykład sto dwadzieścia pięć, najmniejsza liczba doskonała, rok bitwy pod Grunwaldem itp.
 +
Jeśli jednak spróbujemy objąć wszystkie te sposoby  „w ogólności”, natrafimy na
 +
słynny '''paradoks Berry'ego''' (podany przez B.Russela):
 +
 
 +
''Niech ''n'' będzie najmniejszą liczbą naturalną której nie da się zdefiniować w języku polskim za pomocą mniej niż dwudziestu pięciu słów.''
 +
 
 +
Ale przecież właśnie zdefiniowaliśmy tę liczbę - za pomocą powyższego zdania!
 +
 
 +
Istotne jest zatem ścisłe rozumienie pojęcia definiowania. Aby uniknąć paradoksów takich jak wyżej, definicja nie może być częścią opisywanego obiektu. Krokiem w tym kierunku jest ścisłe określenie pojęcia notacji.
 +
Intuicyjnie, jesy ona nadana przez zewnętrznego obserwatora w celu rozróżniania pomiędzy obiektami.
 +
 
 +
 
 +
{{definicja|[Notacja]|Notacja| '''Notacją''' dla ''S'' nazywamy dowolną różnowartościową funkcję <math>\alpha:S \to \Sigma^*</math> gdzie <math>\Sigma</math> jest skończonym alfabetem.
 +
}}
 +
 
 +
 
 +
{{fakt||fakt_notacji| Jeśli <math> |S| = m \ge 1</math> i <math>|\Sigma|=r\ge2</math> to dla pewnego <math>s \in S</math> zachodzi:
 +
<center><math>|\alpha(s)|\ge \lfloor log_r m \rfloor</math></center>
 +
}}
 +
 
 +
{{dowod|||Ciągów znaków z <math>\Sigma</math> o długości mniejszej niż ''k'' jest:
 +
 
 +
<center><math>1 + r + r^2 + \ldots + r^{k-1}=\frac{r^k-1}{r-1}<r^k </math></center>
 +
 
 +
Podstawiając <math>k=\lfloor log_r m \rfloor </math>, stwierdzamy, że nie ma wystarczająco wiele ciągów krótszych niż ''k'' do oznaczenia wszystkich elementów ''S''.}}
 +
 
 +
 
 +
{{wniosek||wniosek_notacji| Jeśli <math>\alpha: N\to \Sigma^*</math> jest dowolną notacją dla liczb naturalnych, to dla nieskończenie wielu ''n'' musi zajść: <math>\alpha(n)> \lfloor log_r n \rfloor </math>.
 +
}}
 +
 
 +
{{dowod||| Oczywiście obcięcie <math>\alpha </math> do <math>\{0, 1, \ldots, n-1\}</math> jest także notacją. Zatem z powyższego Faktu, dla każdego <math> n > 0</math> możemy wskazać <math> m_n \in \{0, 1, \ldots, n-1\} </math>, takie że <math> \alpha (m_n ) \ge \lfloor log_r n \rfloor > \lfloor log_r m_n \rfloor </math> (przyjmijmy, że <math> log_r 0 = - \infty </math>). Pozostaje zauważyć, że zbiór wszystkich takich <math> m_n </math> jest nieskończony. W przeciwnym razie, dla pewnego <math> m</math>  w tym zbiorze, mielibyśmy <math> m = m_n</math> i w konsekwencji <math> \alpha (m) \ge \lfloor log_r n \rfloor </math> dla nieskończenie wielu <math>n</math>, co jest oczywiście niemożliwe.}}
 +
 
 +
 
 +
Jako zastosowanie, możemy podać teorioinformacyjny dowód znanego faktu:
 +
 
 +
[[Image:euklides.jpg||thumb|right|80px|Euklides (ok. 365p.n.e.-ok. 300p.n.e)]]
 +
{{fakt|(Euklides)|euklides|Istnieje nieskończenie wiele liczb pierwszych.}}
 +
 
 +
{{dowod||do_euklides|Załóżmy przeciwnie, że istnieje tylko ''M'' liczb pierwszych: <math>p_1, p_2, \ldots , p_M</math>. Wprowadzamy notację <math>\alpha: \mathbb{N} \to \{0,1,\#\}^* </math> w następujący sposób: Dla <math>n = p_1^{\beta_1}p_2^{\beta _2}\ldots p_M^{\beta _M}</math> niech
 +
 
 +
<center><math>\alpha(n) = bin(\beta _1)\#bin(\beta _2)\# \ldots \#bin(\beta _M)</math></center>
 +
 
 +
gdzie <math>bin(\beta) </math> jest zwykłym zapisem binarnym liczby <math>\beta</math> (a więc <math>|bin(\beta)|\le 1+\log_2 \beta</math>).
 +
 
 +
Ponieważ <math>2^{\beta _i}\le p_i^{\beta _i}\le n</math>, mamy <math>\beta _i \le log_2 n</math>, dla wszystkich ''i''. A zatem
 +
<center><math>|\alpha(n)|\le M(1+\log_2 \log_2 n) </math></center>
 +
dla wszystkich ''n'', co oczywiście przeczy twierdzeniu, że <math>|a(n)|\ge \log_3 n</math>, dla nieskończenie wielu ''n''.}}
 +
 
 +
=== Kody ===
 +
 
 +
Niektóre własności notacji mają szczególne znaczenie dla ich praktycznego zastosowania.
 +
Przyjrzyjmy się na przykład temu co się dzieje, jeśli w naturalny sposób rozszerzymy notację
 +
<math> \varphi : S \to \Sigma^*</math> do morfizmu <math> \hat\varphi: S^* \to \Sigma^*</math>:
 +
<center><math> \hat\varphi (s_1 \ldots s_i)= \varphi(s_1) \varphi(s_2) \ldots \varphi(s_i)</math></center>
 +
 
 +
Mając dany wynikowy ciąg znaków, kluczowe znaczenie ma to, czy potrafimy odtworzyć jednoznacznie ciąg argumentów.
 +
 
 +
 
 +
{{definicja|[Kod]|kod| Odwzorowanie <math> \varphi : S \to \Sigma^*</math> dla skończonego niepustego zbioru ''S'' jest '''kodem''', jeśli jego naturalne rozszerzenie do morfizmu <math> \hat\varphi</math> jest różnowartościowe. Mówimy, że kod jest '''bezprefiksowy''', jeśli dodatkowo <math> \hat\varphi(s) \not\leq \hat\varphi(s') </math> dla <math>s \neq s'</math>.
 +
}}
 +
 
 +
Nietrudno jest zauważyć, że własność bycia kodem lub bycia kodem bezprefiksowym zależy wyłącznie od postaci zbioru wartości funkcji <math>\varphi</math>, <math>\varphi(S)</math>.
 +
Ponadto, dla każdego kodu, <math>\varepsilon \not\in \varphi (S)</math>.
 +
 
 +
Łatwo też zauważyć, że każdy zbiór bezprefiksowy jest kodem. Istnieją oczywiście kody, które nie są bezprefiksowe (np. dla <math>\varphi(S)=\{aa, baa, ba\}</math>), i notacje, które nie są kodami (np. dla <math>\varphi(S)=\{a, ab, ba\}</math>).
 +
 
 +
W dalszej części będziemy omijać daszek i utożsamiać <math>\hat\varphi</math> z <math>\varphi</math>.
 +
 
 +
Aby kodować zbiór ''S'' o ''m'' elementach za pomocą alfabetu <math>\Sigma</math> o ''r'' elementach (dla <math>m,r \ge 2</math>), wystarczy oczywiście używać ciągów długości <math>\lceil \log_r m \rceil</math>. Wtedy, dla dowolnego <math>w \in S^*</math>, <math>|\varphi(w)|\le|w|\cdot \lceil \log_r m \rceil</math>.
 +
 
 +
Czasem możemy jednak wymyślić bardziej ekonomiczne kodowanie. Jeśli wiemy, że jakieś obiekty z ''S'' pojawiają się częściej niż inne, możemy przyporządkować im krótsze ciągi znaków. W ten sposób średnio możemy uzyskać mniejsze <math>|\varphi(w)| </math>.
 +
 
 +
Bliską analogią jest tu ''Gra w 20 pytań''. W tej grze jedna osoba wymyśla obiekt x (w domyśle z jakiegoś dużego zbioru możliwości ''S''), a druga osoba stara się go odgadnąć przez zadawanie pytań (co najwyżej 20), na które odpowiedzią może być tylko ''tak'' lub ''nie''. Ściśle biorąc, pytania są postaci:
 +
czy <math>x \in S' </math>?, gdzie <math>S' \subseteq S</math>.
 +
 
 +
 
 +
Łatwo zauważyć, że <math>\lceil \log_2 |S| \rceil</math> pytań wystarczy do zidentyfikowania dowolnego obiektu w ''S''. Czy da się to zrobić lepiej?
 +
W ogólności oczywiście nie. Dowolną strategię zadawania pytań możemy sobie wyobrazić jako drzewo binarne, z pytaniem w każdym wierzchołku i rozwiązaniami w liściach. Jeśli liści jest <math>2^k</math>, to drzewo musi oczywiście mieć głębokość co najmniej ''k''. Jednak jeśli niektóre rozwiązania są bardziej ''prawdopodobne'' niż inne, możemy zmniejszyć ''oczekiwaną'' liczbę pytań. (Faktycznie dopiero taka wersja tej gry jest interesująca.)
 +
 
 +
 
 +
Jak działa to w praktyce, możemy prześledzić na przykładzie prostej gry umieszczonej poniżej. Zadaniem czytelnika jest tu odgadnięcie wylosowanej przez komputer planety poprzez zadanie komputerowi jak najmniejszej liczby pytań. Pytania są zawsze postaci: "Czy wylosowana planeta jest w zbiorze ...?" (zbiór jest definiowany przez zaznaczenie odpowiednich checkboxów). Komputer odpowiada tylko '''T''' lub '''N'''. Zachęcamy do zastanowienia się nad optymalną strategią dla każdego z podanych rozkładów prawdopodobieństwa i do porównania ile pytań potrzeba średnio do znalezienia rozwiązania dla każdego z nich. Po rozegraniu sześciu gier na danym rozkładzie, komputer wyświetli ile pytań potrzeba przy optymalnej strategii (którą poznamy na następnych wykładach).
  
Przykład zastosowania: Wypełniając czek wpisujemy kwotę zarówno przy pomocy liczb, jak i słownie. Dzięki temu małe przekłamanie nie zmienia wpisanej kwoty.
+
<applet code="ZgadujZgadula" archive="images/3/3b/Gra.jar" width="750" height="550">
 +
</applet>
  
  
'''Teoria informacji''' usiłuje pogodzić dwa przeciwstawne cele:
+
Dla jakiego rozkładu prawdopodobieństwa odgadnięcie rozwiązania wymaga największej liczby pytań?
* zapisywania wiadomości jak najzwięźlej
+
 
* chronienia wiadomości przed przekłamaniami podczas transmisji
+
=== Kody bezprefiksowe jako drzewa ===
 +
 
 +
{{kotwica|prefiks-drzewo|}}
 +
''Drzewem nad zbiorem X'' (lub krócej X-drzewem) będziemy nazywać dowolny niepusty zbiór <math>T \subseteq X^*</math> zamknięty na operację brania prefiksu. Relację bycia prefiksem będziemy oznaczać przez <math>\le</math>. W X-drzewie dowolny element ''w'' jest ''węzłem'' rzędu |''w''|, <math>\varepsilon</math> jest ''korzeniem'', <math>\le</math>-maksymalne węzły są ''liśćmi''.
 +
 
 +
Dodatkowo będziemy posługiwać się następującymi pojęciami: dla dowolnego <math>w \in T</math>, <math>x \in X</math> i <math>v \in X^*</math>:
 +
* ''wx'' jest ''bezpośrednim następnikiem'' (lub ''dzieckiem'') ''w''
 +
* ''wv'' jest ''poniżej w''
 +
* zbiór <math>T_w=\{v: wv \in T\}</math> nazywamy ''poddrzewem indukowanym przez w''.
 +
 
 +
 
 +
Opierając się na powyższych definicjach, możemy zauważyć, że dowolny bezprefiksowy kod <math>\varphi:S\to \Sigma^*</math> indukuje drzewo nad <math>\Sigma</math>: <math>T_\varphi = \{w: \exists s: w \le \varphi(s)\}</math>.
 +
Na odwrót, dowolne drzewo <math>T \subset \Sigma^*</math> z |S| liśćmi indukuje bezprefiksowy kod nad ''S'' (z dokładnością do permutacji elementów zbioru ''S''). Wartościami tego kodu są właśnie liście drzewa ''T''.
 +
 
 +
W szczególności strategie w opisanej wyżej grze zgadywania elementów zbioru ''S'' indukują kody dla tego zbioru nad alfabetem, powiedzmy, <math> \{ T, N \} </math> (co odpowiada dwóm możliwym odpowiedziom: tak i nie). Przy ustalonej strategii pytającego, kodem elementu <math> s \in  S </math> jest właśnie ciąg odpowiedzi, jaki prowadzi do tego elementu. 
 +
 
 +
{{przyklad||mala gra|
 +
Niech <math> S = \{ s_1, s_2, s_3, s_4 \} </math>, przy czym <math> p(s_1) = \frac{1}{2},
 +
p(s_2) = \frac{1}{4}, p(s_3) = p(s_4) = \frac{1}{8}</math>. Rozważmy strategię, składającą się
 +
z (maksymalnie) trzech pytań: <math> x = s_1 ? </math>, jeśli '''N''', to  <math> x = s_2 ? </math>, jeśli '''N''', to  <math> x = s_3 ? </math>  Wtedy otrzymany kod jest <math> s_1 \mapsto T </math>, <math> s_2  \mapsto N T </math>, <math> s_3  \mapsto N N T </math>, <math> s_4 \mapsto N N N</math>.}}
 +
 
  
  
Czy istnieją wiadomości których nie da się skrócić? Zanim odpowiemy na to pytanie rozważmy paradoks Berrego:
+
Intuicyjnie, widzimy, że strategie minimalizujące średnią liczbę pytań minimalizują zarazem średnią długość kodu. 
  
''Niech n będzie najmniejszą liczbą naturalną której nie da się zdefiniować za pomocą mniej niż 1000 słów.''
+
Zanim jednak zajmiemy się optymalizacją średniej długości kodu, zrobimy dwie podstawowe obserwacje na temat arytmetycznych własności długości dowolnych kodów.
  
(To zdanie definiuje konkretną liczbę, stąd paradoks).  
+
Dla danego kodu <math>\varphi:S\to \Sigma^*</math>, niech <math>|\varphi|:S \to \mathbb{N}</math> określa ''funkcję długości'', zdefiniowaną jako <math>|\varphi|(s)= |\varphi(s)|</math>.
  
Istotne jest zatem prawidłowe definiowanie notacji. Notacja nie jest częścią badanego obiektu. Jest czymś zewnętrznym, nadanym w celu rozróżniania pomiędzy obiektami.
 
  
'''Definicja:'''
+
{{twierdzenie|[Nierówność Krafta]|kraft| Niech <math>2 \le |S| < \infty </math> i niech <math>|\Sigma|=r</math>. Funkcja <math>\ell:S \to \mathbb{N}</math> jest funkcją długości (<math>\ell = |\varphi|</math>) dla pewnego bezprefiksowego kodu <math>\varphi:S\to \Sigma^*</math> wtedy i tylko wtedy, gdy:
''Notacją'' dla S nazywamy dowolną różnowartościową funkcję <math>\alpha:S \to \Sigma^*</math> gdzie <math>\Sigma</math> jest skończonym alfabetem.
+
<center><math>\sum_{s \in S} \frac{1}{r^{\ell (s)}} \leq 1</math></center>}}
  
 +
{{dowod||do_kraft|
 +
<math>\Rightarrow</math>
 +
Jeśli wszystkie słowa <math>\varphi(S)</math> mają tą samą długość ''k'', to uwzględniając różnowartościowość <math>\varphi</math>, dostajemy
 +
<math>\sum_{s \in S} \frac{1}{r^{|\varphi (s)|}} \leq \frac{r^k}{r^k} = 1.</math>
  
'''Fakt: ''' Jeśli <math> |S| = m \ge 1</math> i <math>|\Sigma|=r\ge2</math> to dla pewnego <math>s \in S</math>.
+
Jeśli teraz mamy słowa różnej długości, to oznaczmy przez ''k'' maksymalną długość <math>\varphi(s)</math>. Następnie dla każdego ''s'' mierzymy długość jego kodu <math>|\varphi (s)| = i</math> i definiujemy
 +
<center><math>P_s = \{ \varphi (s) v : v \in \Sigma^{k-i} \}</math></center>
  
:<math>|\alpha(s)|\ge \lfloor log_r m \rfloor</math>
+
(czyli zbiór wszystkich liści na poziomie ''k'' poniżej <math>\varphi(s)</math> w pełnym <math>\Sigma</math>-drzewie). Łatwo teraz zauważyć, że podmienienie <math>\varphi(s)</math> na cały zbiór <math>P_s</math> nie zmieni wartości sumy:
 +
<center><math>\sum_{w \in P_s} \frac{1}{r^{|w|}} = \frac{r^{k-i}}{r^{k}} = \frac{1}{r^i}</math></center>
  
'''Dowód: '''
+
a zbiory <math>P_s</math> i <math>P_{s'}</math> są parami rozłączne, dla różnych <math>s, s'</math>. Tym samym
Ciągów długości mniejszej niż <math>k</math> jest:
 
  
:<math>1 + r + r^2 + \ldots + r^{k-1}=\frac{r^k-1}{r-1}<r^k </math>
+
<center><math>\sum_{s \in S} \frac{1}{r^{|\varphi (s)|}} = \sum_{s \in S} \sum_{w \in P_s}  \frac{1}{r^{|w|}} \leq \frac{r^k}{r^k} = 1</math></center>
  
Podstawiając <math>k=\lfloor log_r m \rfloor </math> stwierdzamy że nie ma wystarczająco wiele słów krótszych niż k do oznaczenia wszystkich elementów S.  
+
<math>\Leftarrow</math>
QED.
+
Posortujmy elementy zbioru S względem rosnącej długości ich kodów <math>\ell (s)</math>, tak że <math>\ell (s_1 ) \leq \ldots \leq \ell (s_m )</math>. Indukcyjnie dla <math>i = 0,1, \ldots ,m-1</math> będziemy definiować <math> \varphi (s_{i+1})</math> jako ''leksykograficznie'' pierwsze słowo długości <math>\ell(s_{i+1})</math> które nie jest porównywalne z żadnym ze słów <math>\varphi (s_1), \ldots , \varphi (s_i)</math> (względem porządku prefiksowego). Jedyne co musimy pokazać, to że takie słowo zawsze istnieje. Tak jak w poprzednim przypadku, oznaczmy przez <math>P_{s_j}</math> zbiór wszystkich węzłów rzędu <math>\ell(s_{i+1})</math> poniżej <math>\varphi(s_j)</math>. Łatwo sprawdzić, że <math>|P_{s_j}| = r^{\ell (i+1)-\ell (j)}</math>. Warunkiem koniecznym i wystarczającym do istnienia szukanego wierzchołka jest
 +
<center><math> r^{\ell (i+1)-\ell (1)} +  r^{\ell (i+1)-\ell (2)}+ \ldots + r^{\ell (i+1)-\ell (i)} < r^{\ell (i+1)}</math></center>
  
 +
co można zapisać jako
 +
<center><math> \frac{1}{r^{\ell (1)}} +  \frac{1}{r^{\ell (2)}}+ \ldots + \frac{1}{r^{\ell (i)}} < 1</math></center>
  
'''Wniosek: ''' Jeśli <math>\alpha: N-> \Sigma*</math> jest dowolną notacją dla liczb naturalnych, to dla nieskończenie wielu n: <math>\alpha(n)> \lfloor log_r n \rfloor </math>
+
To z kolei jest spełnione na mocy założenia dla każdego <math>i<m</math>.}}
  
'''Dowód: ''' Wybierzmy m takie że <math>\lfloor log_r m \rfloor > |\alpha(0)| </math>. Z powyższego Faktu, dla pewnego <math>i_0 \in \{0, 1, \ldots, m-1\}</math> mamy <math>|\alpha(i_0)|\ge \lfloor log_r m \rfloor>\lfloor log_r i_0 \rfloor </math>. Z tego wynika również że <math>i_0>0</math>.
 
  
Wybierzmy teraz m’ takie że <math>\lfloor log_r m' \rfloor > |a(i_0)| </math>. Znów musi istnieć <math>i_1 \in \{0, 1, \ldots, m'-1\}</math> takie że <math>|a(i_1)|\ge \lfloor log_r m' \rfloor>\lfloor log_r i_i \rfloor</math>. Analogicznie <math>i_1>i_0</math>. I tak dalej. QED.
+
Jeśli kod nie jest bezprefiksowy, nierówność Krafta wciąż jest spełniona, co można pokazać za pomocą sprytnej techniki z elementarnej analizy matematycznej.
  
  
Jako zastosowanie, możemy podać teorioinformacyjny dowód znanego faktu:
+
{{twierdzenie|(Mcmillan)|McMillan| Dla dowolnego kodu <math>\varphi : S \to  \Sigma^*</math> istnieje bezprefiksowy kod <math>\varphi'</math> dla którego <math>|\varphi | = |\varphi'|</math>
 +
}}
  
'''Fakt (Euklides): ''' Istnieje nieskończenie wiele liczb pierwszych.
+
{{dowod||do_McMillan|Przypadek <math>|S| = 1</math> jest trywialny. Dla <math>|S|\ge 2</math> musi zachodzić również <math>r=|\Sigma| \ge 2</math>. Wystarczy wtedy pokazać że funkcja <math>| \varphi |</math> spełnia nierówność Krafta. Wprowadźmy oznaczenie <math> K = \sum_{s \in S} \frac{1}{r^{|\varphi (s)|}}</math> i załóżmy że ta nierówność nie jest spełniona, czyli <math>K>1</math>. Niech <math>\mathit{Min} = \min \{ |\varphi (s)| : s \in S \}</math>, <math>\mathit{Max} = \max \{ |\varphi (s)| : s \in S \}</math>. Rozważmy teraz
 +
<center><math>K^n = \left( \sum_{s \in S} \frac{1}{r^{|\varphi (s)|}} \right)^n = \sum_{i = \mathit{Min} \cdot n}^{\mathit{Max}\cdot n} \frac{N_{n,i}}{r^i}</math></center>
  
'''Dowód: ''' Załóżmy przeciwnie, że istnieje tylko M liczb pierwszych: <math>p_1, p_2, \ldots , p_M</math>. Wprowadzamy notację <math>\alpha: N \to \{0,1,\#\}^* </math> w następujący sposób: Dla <math>n = p_1^{\beta_1}p_2^{\beta _2}\ldots p_M^{\beta _M}</math> niech
+
Gdzie <math>N_{n,i}</math> jest liczbą sekwencji <math>q_1, \ldots ,q_n \in S^n</math> takich że <math>i = |\varphi (q_1)| + \ldots + |\varphi (q_n)| =| \varphi (q_1 \ldots q_n)|</math>. Z warunku, że <math>\varphi</math> jest kodem wynika, że każdej takiej sekwencji odpowiada inne słowo nad <math> \Sigma </math>  długości <math>i</math>, a więc takich sekwencji jest nie więcej niż słów:
:<math>\alpha(n) = bin(\beta _1)\#bin(\beta _2)\# \ldots \#bin(\beta _M)</math>
+
<center><math>\frac{N_{n,i}}{r^i} \leq 1</math></center>
  
gdzie <math>bin(\beta) </math> jest zwykłym zapisem binarnym liczby <math>\beta</math> (<math>|bin(\beta)|\le 1+\log_2 \beta</math>).
+
Stąd otrzymujemy
 +
<center><math>K^n \leq (\mathit{Max} - \mathit{Min}) \cdot n +1</math></center>
  
Ponieważ <math>2^{\beta _i}\le p_i^{\beta _i}\le n</math>, mamy <math>\beta _i \le log_2 n</math>, dla wszystkich i. A zatem
+
co dla wystarczająco dużego n musi być fałszem, ponieważ funkcja wykładnicza rośnie szybciej niż liniowa. W konsekwencji <math>K \leq 1</math>}}
:<math>|\alpha(n)|\le M(1+\log_2 \log_2 n) </math>  
 
dla wszystkich n, co oczywiście przeczy twierdzeniu że dla nieskończenie wielu n <math>|a(n)|\ge \log_3 n</math>. QED
 

Aktualna wersja na dzień 11:15, 21 sty 2007

Blaise Pascal (1623–1662)

Je n’ai fait celle-ci plus longue que parce que je n’ai pas eu le loisir de la faire plus courte.

(Napisałem ten [list] trochę dłuższy, gdyż nie miałem czasu napisać go krócej).

Blaise Pascal, Lettres provinciales, 1657


Notacja, co to takiego?

Na początek prosty eksperyment: Ktoś wymyśla słowo, a kto inny ma za zadanie je odgadnąć, zgadując literę po literze. Zwykle udaje się to znacznie szybciej niż by to wynikało z pesymistycznego oszacowania. Czy jednak będzie to równie łatwe w przypadku odgadywania liczby? Zauważmy, że w przeciwieństwie do słów w języku naturalnym, liczby całkowite w systemie dziesiętnym (czy ogólnie k-arnym, dla k > 1) są „ciasno upakowane”. Mianowicie dowolny ciąg znaków ze zbioru {0, 1, …, 9} przedstawia jakąś liczbę (jeśli zignorujemy początkowe zera), podczas gdy bardzo niewiele ciągów utworzonych z liter {a, b, …, z} to sensowne słowa. Wynika to między innymi z tego, że nasze „algorytmy” do komunikacji za pomocą słów wymagają znacznie więcej redundancji niż te do operowania liczbami. Tę redundancję szczególnie widać, gdy jest ona wprowadzana celowo.

Przykład: Wypełniając czek wpisujemy kwotę zarówno przy pomocy liczb, jak i słownie. Zajmuje to oczywiście znacznie więcej miejsca, ale dzięki temu nie musimy obawiać się, że jakaś literówka zmieni wartość wpisanej kwoty. Podobnie postępujemy, gdy przekazując przez telefon na przykład nazwę stolicy Gruzji, mówimy: T jak Teresa, B jak Barbara, I jak Iwona, L jak Lucyna, I jak Iwona, S jak Stanisław, I jak Iwona. Radiowcy mają zresztą na tę okoliczność międzynarodowy standard, tzw. alfabet fonetyczny: Alpha Bravo Charlie Delta... Yankee Zulu.

Teoria informacji charakteryzuje w sposób matematyczny zapis, przesyłanie i odtwarzanie informacji. Dąży przy tym do pogodzenia dwóch przeciwstawnych celów:

  • zapisywania wiadomości jak najzwięźlej
  • chronienia wiadomości przed przekłamaniami podczas transmisji.


Bertrand Russell (1872–1970)

Zacznijmy od prostego pytania. Czy istnieją wiadomości, których nie da się zapisać zwięźlej? Przypuśćmy, że wiadomość jest liczbą naturalną. Liczby naturalne można na wiele sposobów zapisać w języku polskim, na przykład sto dwadzieścia pięć, najmniejsza liczba doskonała, rok bitwy pod Grunwaldem itp. Jeśli jednak spróbujemy objąć wszystkie te sposoby „w ogólności”, natrafimy na słynny paradoks Berry'ego (podany przez B.Russela):

Niech n będzie najmniejszą liczbą naturalną której nie da się zdefiniować w języku polskim za pomocą mniej niż dwudziestu pięciu słów.

Ale przecież właśnie zdefiniowaliśmy tę liczbę - za pomocą powyższego zdania!

Istotne jest zatem ścisłe rozumienie pojęcia definiowania. Aby uniknąć paradoksów takich jak wyżej, definicja nie może być częścią opisywanego obiektu. Krokiem w tym kierunku jest ścisłe określenie pojęcia notacji. Intuicyjnie, jesy ona nadana przez zewnętrznego obserwatora w celu rozróżniania pomiędzy obiektami.


Definicja [Notacja]

Notacją dla S nazywamy dowolną różnowartościową funkcję gdzie jest skończonym alfabetem.


Fakt

Jeśli i to dla pewnego zachodzi:

Dowód

Ciągów znaków z o długości mniejszej niż k jest:
Podstawiając , stwierdzamy, że nie ma wystarczająco wiele ciągów krótszych niż k do oznaczenia wszystkich elementów S. End of proof.gif


Wniosek

Jeśli jest dowolną notacją dla liczb naturalnych, to dla nieskończenie wielu n musi zajść: .

Dowód

Oczywiście obcięcie do jest także notacją. Zatem z powyższego Faktu, dla każdego możemy wskazać , takie że (przyjmijmy, że ). Pozostaje zauważyć, że zbiór wszystkich takich jest nieskończony. W przeciwnym razie, dla pewnego w tym zbiorze, mielibyśmy i w konsekwencji dla nieskończenie wielu , co jest oczywiście niemożliwe. End of proof.gif


Jako zastosowanie, możemy podać teorioinformacyjny dowód znanego faktu:

Euklides (ok. 365p.n.e.-ok. 300p.n.e)

Fakt (Euklides)

Istnieje nieskończenie wiele liczb pierwszych.

Dowód

Załóżmy przeciwnie, że istnieje tylko M liczb pierwszych: . Wprowadzamy notację w następujący sposób: Dla niech

gdzie jest zwykłym zapisem binarnym liczby (a więc ).

Ponieważ , mamy , dla wszystkich i. A zatem

dla wszystkich n, co oczywiście przeczy twierdzeniu, że , dla nieskończenie wielu n. End of proof.gif

Kody

Niektóre własności notacji mają szczególne znaczenie dla ich praktycznego zastosowania. Przyjrzyjmy się na przykład temu co się dzieje, jeśli w naturalny sposób rozszerzymy notację do morfizmu :

Mając dany wynikowy ciąg znaków, kluczowe znaczenie ma to, czy potrafimy odtworzyć jednoznacznie ciąg argumentów.


Definicja [Kod]

Odwzorowanie dla skończonego niepustego zbioru S jest kodem, jeśli jego naturalne rozszerzenie do morfizmu jest różnowartościowe. Mówimy, że kod jest bezprefiksowy, jeśli dodatkowo dla .

Nietrudno jest zauważyć, że własność bycia kodem lub bycia kodem bezprefiksowym zależy wyłącznie od postaci zbioru wartości funkcji , . Ponadto, dla każdego kodu, .

Łatwo też zauważyć, że każdy zbiór bezprefiksowy jest kodem. Istnieją oczywiście kody, które nie są bezprefiksowe (np. dla ), i notacje, które nie są kodami (np. dla ).

W dalszej części będziemy omijać daszek i utożsamiać z .

Aby kodować zbiór S o m elementach za pomocą alfabetu o r elementach (dla ), wystarczy oczywiście używać ciągów długości . Wtedy, dla dowolnego , .

Czasem możemy jednak wymyślić bardziej ekonomiczne kodowanie. Jeśli wiemy, że jakieś obiekty z S pojawiają się częściej niż inne, możemy przyporządkować im krótsze ciągi znaków. W ten sposób średnio możemy uzyskać mniejsze .

Bliską analogią jest tu Gra w 20 pytań. W tej grze jedna osoba wymyśla obiekt x (w domyśle z jakiegoś dużego zbioru możliwości S), a druga osoba stara się go odgadnąć przez zadawanie pytań (co najwyżej 20), na które odpowiedzią może być tylko tak lub nie. Ściśle biorąc, pytania są postaci: czy ?, gdzie .


Łatwo zauważyć, że pytań wystarczy do zidentyfikowania dowolnego obiektu w S. Czy da się to zrobić lepiej? W ogólności oczywiście nie. Dowolną strategię zadawania pytań możemy sobie wyobrazić jako drzewo binarne, z pytaniem w każdym wierzchołku i rozwiązaniami w liściach. Jeśli liści jest , to drzewo musi oczywiście mieć głębokość co najmniej k. Jednak jeśli niektóre rozwiązania są bardziej prawdopodobne niż inne, możemy zmniejszyć oczekiwaną liczbę pytań. (Faktycznie dopiero taka wersja tej gry jest interesująca.)


Jak działa to w praktyce, możemy prześledzić na przykładzie prostej gry umieszczonej poniżej. Zadaniem czytelnika jest tu odgadnięcie wylosowanej przez komputer planety poprzez zadanie komputerowi jak najmniejszej liczby pytań. Pytania są zawsze postaci: "Czy wylosowana planeta jest w zbiorze ...?" (zbiór jest definiowany przez zaznaczenie odpowiednich checkboxów). Komputer odpowiada tylko T lub N. Zachęcamy do zastanowienia się nad optymalną strategią dla każdego z podanych rozkładów prawdopodobieństwa i do porównania ile pytań potrzeba średnio do znalezienia rozwiązania dla każdego z nich. Po rozegraniu sześciu gier na danym rozkładzie, komputer wyświetli ile pytań potrzeba przy optymalnej strategii (którą poznamy na następnych wykładach).

<applet code="ZgadujZgadula" archive="images/3/3b/Gra.jar" width="750" height="550"> </applet>


Dla jakiego rozkładu prawdopodobieństwa odgadnięcie rozwiązania wymaga największej liczby pytań?

Kody bezprefiksowe jako drzewa

Drzewem nad zbiorem X (lub krócej X-drzewem) będziemy nazywać dowolny niepusty zbiór zamknięty na operację brania prefiksu. Relację bycia prefiksem będziemy oznaczać przez . W X-drzewie dowolny element w jest węzłem rzędu |w|, jest korzeniem, -maksymalne węzły są liśćmi.

Dodatkowo będziemy posługiwać się następującymi pojęciami: dla dowolnego , i :

  • wx jest bezpośrednim następnikiem (lub dzieckiem) w
  • wv jest poniżej w
  • zbiór nazywamy poddrzewem indukowanym przez w.


Opierając się na powyższych definicjach, możemy zauważyć, że dowolny bezprefiksowy kod indukuje drzewo nad : . Na odwrót, dowolne drzewo z |S| liśćmi indukuje bezprefiksowy kod nad S (z dokładnością do permutacji elementów zbioru S). Wartościami tego kodu są właśnie liście drzewa T.

W szczególności strategie w opisanej wyżej grze zgadywania elementów zbioru S indukują kody dla tego zbioru nad alfabetem, powiedzmy, (co odpowiada dwóm możliwym odpowiedziom: tak i nie). Przy ustalonej strategii pytającego, kodem elementu jest właśnie ciąg odpowiedzi, jaki prowadzi do tego elementu.

Przykład

Niech , przy czym . Rozważmy strategię, składającą się

z (maksymalnie) trzech pytań: , jeśli N, to , jeśli N, to Wtedy otrzymany kod jest , , , .


Intuicyjnie, widzimy, że strategie minimalizujące średnią liczbę pytań minimalizują zarazem średnią długość kodu.

Zanim jednak zajmiemy się optymalizacją średniej długości kodu, zrobimy dwie podstawowe obserwacje na temat arytmetycznych własności długości dowolnych kodów.

Dla danego kodu , niech określa funkcję długości, zdefiniowaną jako .


Twierdzenie [Nierówność Krafta]

Niech i niech . Funkcja jest funkcją długości () dla pewnego bezprefiksowego kodu wtedy i tylko wtedy, gdy:

Dowód

Jeśli wszystkie słowa mają tą samą długość k, to uwzględniając różnowartościowość , dostajemy

Jeśli teraz mamy słowa różnej długości, to oznaczmy przez k maksymalną długość . Następnie dla każdego s mierzymy długość jego kodu i definiujemy

(czyli zbiór wszystkich liści na poziomie k poniżej w pełnym -drzewie). Łatwo teraz zauważyć, że podmienienie na cały zbiór nie zmieni wartości sumy:

a zbiory i są parami rozłączne, dla różnych . Tym samym

Posortujmy elementy zbioru S względem rosnącej długości ich kodów , tak że . Indukcyjnie dla będziemy definiować jako leksykograficznie pierwsze słowo długości które nie jest porównywalne z żadnym ze słów (względem porządku prefiksowego). Jedyne co musimy pokazać, to że takie słowo zawsze istnieje. Tak jak w poprzednim przypadku, oznaczmy przez zbiór wszystkich węzłów rzędu poniżej . Łatwo sprawdzić, że . Warunkiem koniecznym i wystarczającym do istnienia szukanego wierzchołka jest

co można zapisać jako

To z kolei jest spełnione na mocy założenia dla każdego . End of proof.gif


Jeśli kod nie jest bezprefiksowy, nierówność Krafta wciąż jest spełniona, co można pokazać za pomocą sprytnej techniki z elementarnej analizy matematycznej.


Twierdzenie (Mcmillan)

Dla dowolnego kodu istnieje bezprefiksowy kod dla którego

Dowód

Przypadek jest trywialny. Dla musi zachodzić również . Wystarczy wtedy pokazać że funkcja spełnia nierówność Krafta. Wprowadźmy oznaczenie i załóżmy że ta nierówność nie jest spełniona, czyli . Niech , . Rozważmy teraz

Gdzie jest liczbą sekwencji takich że . Z warunku, że jest kodem wynika, że każdej takiej sekwencji odpowiada inne słowo nad długości , a więc takich sekwencji jest nie więcej niż słów:

Stąd otrzymujemy

co dla wystarczająco dużego n musi być fałszem, ponieważ funkcja wykładnicza rośnie szybciej niż liniowa. W konsekwencji End of proof.gif