Teoria informacji/TI Wykład 1

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?

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? 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. 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 wykorzystywana 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 małe przekłamanie nie zmienia wpisanej kwoty.

Teoria informacji charakteryzuje w sposób matematyczny sposoby zapisywania, transmitowana i odtwarzania informacji. W szczególności zajmuje się godzeniem dwóch przeciwstawnych celów:

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

Zacznijmy od podstaw. Czy istnieją wiadomości których nie da się zapisać zwięźlej? Dowolną wiadomość możemy traktować jako ciąg bitów, czyli po prostu liczbę naturalną. Istnieje wiele sposobów zapisu liczb, i zajmowanie się wszystkimi naraz prowadzi do paradoksów. Rozważmy przykładowe zdanie (paradoks Berrego):

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

Dwadzieścia słów można dobrać tylko na skończenie wiele sposobów. Nawet gdyby każdy sposób definiował inną liczbę, pozostaje nieskończenie wiele liczb których zdefiniować tak się nie daje. Wśród nich któraś jest najmniejsza, i właśnie ją zdefiniowaliśmy za pomocą mniej niż dwudziestu słów – sprzeczność.

Istotne jest zatem prawidłowe zdefiniowanie notacji, która służy nam do definiowania liczb. Notacja nie może być częścią badanego obiektu. Musi być czymś zewnętrznym, nadanym w celu rozróżniania pomiędzy obiektami.

Definicja: Notacją dla S nazywamy dowolną różnowartościową funkcję $\alpha :S\to {\mathrm{\Sigma }}^{*}$ gdzie $\mathrm{\Sigma }$ jest skończonym alfabetem.

Fakt: Jeśli $|S|=m\ge 1$ i $|\mathrm{\Sigma }|=r\ge 2$ to dla pewnego $s\in S$ zachodzi:

$|\alpha (s)|\ge \lfloor lo{g}_{r}m\rfloor$

Dowód: Ciągów znaków z $\mathrm{\Sigma }$ o długości mniejszej niż k jest:

$1+r+r^2+\dots +r^{k-1}=\frac{r^k-1}{r-1}<r^k$

Podstawiając $k=\lfloor lo{g}_{r}m\rfloor$ stwierdzamy że nie ma wystarczająco wiele ciągów krótszych niż k do oznaczenia wszystkich elementów S. QED.

Wniosek: Jeśli $\alpha :N\to {\mathrm{\Sigma }}^{*}$ jest dowolną notacją dla liczb naturalnych, to dla nieskończenie wielu n musi zajść: $\alpha (n)>\lfloor lo{g}_{r}n\rfloor$

Dowód: Wybierzmy m takie że $\lfloor lo{g}_{r}m\rfloor >|\alpha (0)|$. Z powyższego Faktu, dla pewnego $i_0\in \{0,1,\dots ,m-1\}$ mamy $|\alpha (i_0)|\ge \lfloor lo{g}_{r}m\rfloor >\lfloor lo{g}_r{i}_0\rfloor$. Z tego wynika również że $i_0>0$.

Wybierzmy teraz m’ takie że $\lfloor lo{g}_r{m}^{\prime }\rfloor >|a(i_0)|$. Znów musi istnieć $i_1\in \{0,1,\dots ,m^{\prime }-1\}$ takie że $|a(i_1)|\ge \lfloor lo{g}_r{m}^{\prime }\rfloor >\lfloor lo{g}_r{i}_1\rfloor$. Analogicznie $i_1>i_0$. I tak dalej. QED.

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

Fakt (Euklides): Istnieje nieskończenie wiele liczb pierwszych.

Dowód: Załóżmy przeciwnie, że istnieje tylko M liczb pierwszych: $p_1,p_2,\dots ,p_M$. Wprowadzamy notację $\alpha :N\to \{0,1,\mathrm{\#}{\}}^{*}$ w następujący sposób: Dla $n=p_1^{{\beta }_1}{p}_2^{{\beta }_2}\dots p_M^{{\beta }_M}$ niech

$\alpha (n)=bin({\beta }_1)\mathrm{\#}bin({\beta }_2)\mathrm{\#}\dots \mathrm{\#}bin({\beta }_M)$

gdzie $bin(\beta )$ jest zwykłym zapisem binarnym liczby $\beta$ (a więc $|bin(\beta )|\le 1+{\log }_2\beta$).

Ponieważ $2^{{\beta }_i}\le p_i^{{\beta }_i}\le n$, mamy ${\beta }_i\le lo{g}_{2}n$, dla wszystkich i. A zatem

$|\alpha (n)|\le M(1+{\log }_2{\log }_{2}n)$

dla wszystkich n, co oczywiście przeczy twierdzeniu że dla nieskończenie wielu n $|a(n)|\ge {\log }_{3}n$. QED

Kody

Niektóre własności notacji mają szczególne znaczenie dla ich praktycznego zastosowania. Przyjrzyjmy się na przykład co się dzieje jeśli w naturalny sposób rozszerzymy notację $\phi :S\to {\mathrm{\Sigma }}^{*}$ do morfizmu $\hat{\phi }:S^{*}\to {\mathrm{\Sigma }}^{*}$:

$\hat{\phi }(s_1\dots s_i)=\phi (s_1)\phi (s_2)\dots \phi (s_i)$

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

Definicja: Odwzorowanie $\phi :S\to {\mathrm{\Sigma }}^{*}$ dla skończonego niepustego zbioru S jest kodem, jeśli jego naturalne rozszerzenie do morfizmu $\hat{\phi }$ jest różnowartościowe. Mówimy że kod jest bezprefiksowy jeśli dodatkowo $\hat{\phi }(s)\le ̸\hat{\phi }(s^{\prime })$ dla $s\ne s^{\prime }$.

Jak widać własność bezprefiksowości zależy wyłącznie od postaci zbioru $\phi (S)$. Ponadto dla każdego kodu $\epsilon \in ̸\phi (S)$.

Łatwo zauważyć że każdy zbiór bezprefiksowy jest kodem. Istnieją oczywiście kody które nie są bezprefiksowe (np. dla $\phi (S)=\{aa,baa,ba\}$), a nie każda notacja jest kodem (np. dla $\phi (S)=\{a,ab,ba\}$).

W dalszej części będziemy omijać daszek i utożsamiać $\hat{\phi }$ z $\phi$.

Aby kodować zbiór S o m elementach za pomocą alfabetu $\mathrm{\Sigma }$ o r elementach (dla $m,r\ge 2$), wystarczy oczywiście używać ciągów długości $\lceil {\log }_{r}m\rceil$. Wtedy $|\phi (w)|\le |w|\cdot \lceil {\log }_{r}m\rceil$, dla dowolnego $w\in S^{*}$.

Czasem możemy jednak wymyśleć bardziej efektywne kodowanie. Jeśli wiemy że jakieś obiekty z S pojawiają się częściej, możemy im przyporządkować krótsze ciągi znaków. W ten sposób średnio możemy uzyskać mniejsze $|\phi (w)|$.

Bliską analogią jest tu Gra w 20 pytań. W tej grze jedna osoba wymyśla obiekt o (w domyśle z jakiegoś dużego zbioru możliwości S), a druga osoba stara się zgadnąć jaki to obiekt przez zadawanie pytań (np. co najwyżej 20), na które odpowiedzą może być tylko tak lub nie. Tym samym pytania są tak naprawdę postaci $o\in S^{\prime }$?, gdzie $S^{\prime }\subseteq S$.

Łatwo zauważyć że $\lceil {\log }_2|S|\rceil$ 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 $2^k$, 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.)

- przykład

Zapiszmy to formalnie. Drzewem nad zbiorem X, (albo krócej 'X-drzewem'), będziemy nazywać dowolny niepusty zbiór $T\subseteq X^{*}$ zamknięty na operację brania prefiksu. Relację bycia prefiksem będziemy oznaczać przez $\le$. W X-drzewie dowolny element w jest węzłem rzędu |w|, $\epsilon$ jest korzeniem, $\le$-maksymalne węzły są liśćmi. Dodatkowo będziemy posługiwać się następującymi pojęciami: dla dowolnego $w\in T$, $x\in X$ i $v\in X^{*}$:

• wx jest bezpośrednim następnikiem (lub dzieckiem) w
• wv jest poniżej w
• zbiór $T_w=\{v:wv\in T\}$ nazywamy poddrzewem indukowanym przez w

Korzystając z tych definicji, możemy powiedzieć że dowolny bezprefiksowy kod $\phi :S\to {\mathrm{\Sigma }}^{*}$ indukuje drzewo nad $\mathrm{\Sigma }$: :$T_{\phi }=\{w:\mathrm{\exists }s:w\le \phi (s)\}$. W drugą stronę, dowolne drzewo $T\subset {\mathrm{\Sigma }}^{*}$ z |S| liśćmi indukuje bezprefiksowy kod nad S (z dokładnością do permutacji elementów zbioru S).