powrót
kopciuszek powróciła
pod miotłę do macocha
użera się z jego ogłuszającymi
od siedmiu boleści muzykantami
pod kiecką rozsypują się
niebieskie majtki
i nucą
jestem pół naukowa
i w pełni kulturalna
buzuje mi w zadku
panuję nad słowami
nikt nie wie że przed laty
tańczyłam z królewiczem na balu
on źle użył swe szelki
a ja zgubiłam pantofelki
wh
2011-02-05
Saturday, February 5, 2011
Thursday, January 27, 2011
Węzły i linki. Cz. 0 (Wstęp)
Wyobraźmy sobie zawieszony w powietrzu (lub pod wodą) elastyczny sznurek, którego końce są szczepione. Sznurek może być niemiłosiernie zaplątany. Gdy wodzimy po nim okiem, to widzimy jeden po drugim zakrzywiony odcinek sznurka, który na moment chowa się pod innym, itd. I te łuki składają się na cały sznurek. Czy da się sznurek tak rozplątać, żeby utworzył na koniec okrąg? Przy rozplątywaniu nie wolno rwać go, można tylko przemieszczać, można rozciągać i kurczyć. Tych łuków w każdym momencie ma być tylko skończona liczba, ale problem i tak jest trudny (ba, jest TRUDNY!!!).
Ogólniej, można wyobrazić sobie dwa takie poplątane kłębki. Czy da się jeden z nich tak przemieścić i zdeformować (znowu nie wolno rozrywać), by na koniec oba wyglądały tak samo, by się różniły tylko o przesunięcie równoległe (gdy jeden ze sznurków usuniemy, a drugim będziemy będziemy manipulować, to na koniec ma zająć miejsce tego usuniętego, ale dokładnie tak jakbyśmy widzieli ten poprzedni).
Sznurek, ze szczepionymi końcami, zafiksowany w przetrzeni, nazywamy węzłem.
Otrzymaliśmy pewną relację równoważności pomiędzy węzłami. Ogólniej, kłębek może zawierać nie jeden sznurek (czyli węzeł), lecz szereg rozłącznych sznurków. Zbiór w przestrzeni euklidesowej, który rozpada się na unię rozłącznych węzłów nazywa się linkiem. Dla linków stawia się pytania podobne jak dla węzłów. I właśnie takimi pytaniami, związanymi z rozplątywaniem linków, zajmuje się Teoria Węzłów i Linków. Na przykład znany jest klasyczny link, złożony z trzech "okręgów", z których żadne dwa nie są zahaczone, ale jednak tych trzech "okręgów" nie da się rozsunąć w przestrzeni tak, by znalazły się wewnątrz trzech, parami rozłącznych kul, każdy w swojej własnej kuli (lub żeby, co na jedno wychodzi, wylądowały na jednej, wspólnej płaszczyźnie, ale dalej te "okręgi" mają być parami rozłączne).
Dla pełniejszego i głębszego zrozumienia węzłów i linków wprowadźmy orientację czyli na każdym sznurku narysujmy strzałkę wzdłuż sznurka - można w jednym z dwóch istniejących kierunków. Narysowanie strzałki w dowolnym miejscu sznurka indukuje zgodną strzałkę w dowolnym jego miejscu (strzałka może wędrować wzdłuż sznurka). To jest właśnie orientacja sznurka. Odtąd możemy klasyfikować węzły i linki subtelniej, żądając zachowania kierunku strzałek.
Z miejsca otrzymujemy dwa rodzaje węzłów. Jedne można tak przekształcać, żeby otrzymać je z powrotem, ale ze strzałką zwróconą w przeciwnym kierunku. Na przykład taki jest okrąg. Możemy go obrócić w przestrzeni wokół jednej z jego średnic o 180 stopni. Wtedy okrąg najdzie na siebie, ale strzałka będzie wskazywać kierunek przeciwny (wzdłuż "sznurka"), a nie oryginalny. W przypadku pewnych innych węzłów jest to niemożliwe.
Pokrewnym pytaniem jest równaważność węzła i jego odbicia lustrzanego (nawet gdy nie obchodzi nas orientacja w sensie strzałki namalowanej na sznurku). Pewne węzły nie dają się przekształcić na swoje odicie lustrzane.
TERMINOLOGIA
Przypominam, że bijekcja jest tym samym, co odwzorowanie wzajemnie jednoznaczne. Bijekcja zbioru skończonego na siebie nazywana jest permutacją.
Bijekcja (na przykład permutacja), która każdemu argumentowi przypisuje jego samego, nazywa się odwzorowaniem tożsamościowym lub po prostu tożsamością. Oznaczamy je [;I_E : E \rightarrow E;], więc [;I_E(x):=x;] dla każdego [;x\in E;].
CYKLE
Parę uporządkowaną [;(E\ \nu);], złożoną z niepustego zbioru skończonego [;E;] i permutacji [;\nu;] będziemy nazywać cyklem. Elementy zbioru [;E;] będziemy nazywać odcinkami. Gdy [;\nu(a)=b;] to odcinek [;b;] nazywamy następnym po [;a;], a odcinek [;a;] poprzednikiem odcinka [;b;].
Najprostszy cykl otrzymujemy, gdy zbiór odcinków [;E;] jest 1-elementowy (wtedy ten jedyny odcinek jest swoim własnym poprzednikiem i następnikiem).
Cykl [;(F\ \mu);] nazywamy podcyklem cyklu [;(E\ \nu);], gdy spełnione są dwa warunki
Cykl [;(E\ \nu);] nazywamy prostym, gdy nie zawiera żadnego podcyklu właściwego (t.j. różnego od siebie samego).
Dwa cykle (lub podcykle) nazywamy rozłącznymi, gdy nie mają wspólnego odcinka. Jest jasnym, że każdy cykl rozpada się jednoznacznie na parami rozłączne podcykle proste - jest to jedna z najwcześniejszych obserwacji (twierdzeń :-) teorii grup permutacji. To, że podstawą linków są permutacje, wskazuje na moźliwy silny związek teorii linków z teorią grup. Teoria linków jest wzbogaconą teorią grup permutacji. Jednak klasyczny, silnie rozwinięty główny głęboki związek teorii węzłów z teorią grup jest zupełnie inny, via grupę fundamentalną dopełnienia węzła w przestrzeni euklidesowej (są też inne).
PRZYKŁAD 0 Cykl [;(E\ I_E);] rozpada się na jednoodcinkowe cykle proste.
Cykl, którego wszystkie podcykle proste składają się z pojedynczego odcinka, nazywa się cyklem zredukowanym.
Izomorfizmem dwóch cykli [;(E\ \nu);] [;(F\ \mu);] nazywamy bijeckcję [;f : E \rightarrow F;] taką, że
[;f(\nu(x)) = \mu(f(x);]
dla każdego odcinka [;x\in E;]. Gdy dla dwóch cykli istnieje izomorfizm, to nazywamy je izomorficznymi. Przy izomorfiźmie podcykl prosty przechodzi na podcykl prosty, o tej samej liczbie odcinków; mówimy, że izomorfizm zachowuje rozkład na podcykle proste. Cykle izomorficzne rozpadają się na tę samą liczbę podcykli prostych (przy czym liczba odcinków w odpowiednich podcyklach jest ta sama).
Niech cykle [;(E\ \nu);] [;(F\ \mu);] oraz odcinek [;a\in E;], taki że [;\nu(a)\ne a;], będą następująco powiązane:
Wtedy mówimy, że cykl [;(F\ \mu);] jest prostą redukcją cyklu [;(E\ \nu);], a ten ostatni prostym rozszerzeniem poprzedniego (o odcinek [;\nu(a);].
Gdy cykl [;(F\ \mu);] można przedstawić jako wynik szeregu prostych redukcji, poczynając od cyklu [;(E\ \nu);], to cykl [;(F\ \mu);] nazywamy redukcją cyklu [;(E\ \nu);], a ten ostatni rozszerzeniem poprzedniego.
Niech podzbiór [;F;] zbioru [;E;] zawiera dokładnie po jednym odcinku z każdego cyklu prostego cyklu [;(E\ \nu;]. Wtedy cykl [;(E\ \nu);] redukuje się do cyklu [;(F\ I_E);] czyli każdy cykl redukuje się do cyklu zredukowanego. Tak więc dwa cykle są izomorficzne [;\Leftrightarrow;] redukują się do cykli zredukowanych, o tej samej liczbie odcinków.
Ogólniej, można wyobrazić sobie dwa takie poplątane kłębki. Czy da się jeden z nich tak przemieścić i zdeformować (znowu nie wolno rozrywać), by na koniec oba wyglądały tak samo, by się różniły tylko o przesunięcie równoległe (gdy jeden ze sznurków usuniemy, a drugim będziemy będziemy manipulować, to na koniec ma zająć miejsce tego usuniętego, ale dokładnie tak jakbyśmy widzieli ten poprzedni).
Sznurek, ze szczepionymi końcami, zafiksowany w przetrzeni, nazywamy węzłem.
Otrzymaliśmy pewną relację równoważności pomiędzy węzłami. Ogólniej, kłębek może zawierać nie jeden sznurek (czyli węzeł), lecz szereg rozłącznych sznurków. Zbiór w przestrzeni euklidesowej, który rozpada się na unię rozłącznych węzłów nazywa się linkiem. Dla linków stawia się pytania podobne jak dla węzłów. I właśnie takimi pytaniami, związanymi z rozplątywaniem linków, zajmuje się Teoria Węzłów i Linków. Na przykład znany jest klasyczny link, złożony z trzech "okręgów", z których żadne dwa nie są zahaczone, ale jednak tych trzech "okręgów" nie da się rozsunąć w przestrzeni tak, by znalazły się wewnątrz trzech, parami rozłącznych kul, każdy w swojej własnej kuli (lub żeby, co na jedno wychodzi, wylądowały na jednej, wspólnej płaszczyźnie, ale dalej te "okręgi" mają być parami rozłączne).
Dla pełniejszego i głębszego zrozumienia węzłów i linków wprowadźmy orientację czyli na każdym sznurku narysujmy strzałkę wzdłuż sznurka - można w jednym z dwóch istniejących kierunków. Narysowanie strzałki w dowolnym miejscu sznurka indukuje zgodną strzałkę w dowolnym jego miejscu (strzałka może wędrować wzdłuż sznurka). To jest właśnie orientacja sznurka. Odtąd możemy klasyfikować węzły i linki subtelniej, żądając zachowania kierunku strzałek.
Z miejsca otrzymujemy dwa rodzaje węzłów. Jedne można tak przekształcać, żeby otrzymać je z powrotem, ale ze strzałką zwróconą w przeciwnym kierunku. Na przykład taki jest okrąg. Możemy go obrócić w przestrzeni wokół jednej z jego średnic o 180 stopni. Wtedy okrąg najdzie na siebie, ale strzałka będzie wskazywać kierunek przeciwny (wzdłuż "sznurka"), a nie oryginalny. W przypadku pewnych innych węzłów jest to niemożliwe.
Pokrewnym pytaniem jest równaważność węzła i jego odbicia lustrzanego (nawet gdy nie obchodzi nas orientacja w sensie strzałki namalowanej na sznurku). Pewne węzły nie dają się przekształcić na swoje odicie lustrzane.
TERMINOLOGIA
Przypominam, że bijekcja jest tym samym, co odwzorowanie wzajemnie jednoznaczne. Bijekcja zbioru skończonego na siebie nazywana jest permutacją.
Bijekcja (na przykład permutacja), która każdemu argumentowi przypisuje jego samego, nazywa się odwzorowaniem tożsamościowym lub po prostu tożsamością. Oznaczamy je [;I_E : E \rightarrow E;], więc [;I_E(x):=x;] dla każdego [;x\in E;].
CYKLE
Parę uporządkowaną [;(E\ \nu);], złożoną z niepustego zbioru skończonego [;E;] i permutacji [;\nu;] będziemy nazywać cyklem. Elementy zbioru [;E;] będziemy nazywać odcinkami. Gdy [;\nu(a)=b;] to odcinek [;b;] nazywamy następnym po [;a;], a odcinek [;a;] poprzednikiem odcinka [;b;].
Najprostszy cykl otrzymujemy, gdy zbiór odcinków [;E;] jest 1-elementowy (wtedy ten jedyny odcinek jest swoim własnym poprzednikiem i następnikiem).
Cykl [;(F\ \mu);] nazywamy podcyklem cyklu [;(E\ \nu);], gdy spełnione są dwa warunki
- [;F\subseteq E;]
- [;\mu = \nu\,|\,F;]
Cykl [;(E\ \nu);] nazywamy prostym, gdy nie zawiera żadnego podcyklu właściwego (t.j. różnego od siebie samego).
Dwa cykle (lub podcykle) nazywamy rozłącznymi, gdy nie mają wspólnego odcinka. Jest jasnym, że każdy cykl rozpada się jednoznacznie na parami rozłączne podcykle proste - jest to jedna z najwcześniejszych obserwacji (twierdzeń :-) teorii grup permutacji. To, że podstawą linków są permutacje, wskazuje na moźliwy silny związek teorii linków z teorią grup. Teoria linków jest wzbogaconą teorią grup permutacji. Jednak klasyczny, silnie rozwinięty główny głęboki związek teorii węzłów z teorią grup jest zupełnie inny, via grupę fundamentalną dopełnienia węzła w przestrzeni euklidesowej (są też inne).
PRZYKŁAD 0 Cykl [;(E\ I_E);] rozpada się na jednoodcinkowe cykle proste.
Cykl, którego wszystkie podcykle proste składają się z pojedynczego odcinka, nazywa się cyklem zredukowanym.
Izomorfizmem dwóch cykli [;(E\ \nu);] [;(F\ \mu);] nazywamy bijeckcję [;f : E \rightarrow F;] taką, że
[;f(\nu(x)) = \mu(f(x);]
dla każdego odcinka [;x\in E;]. Gdy dla dwóch cykli istnieje izomorfizm, to nazywamy je izomorficznymi. Przy izomorfiźmie podcykl prosty przechodzi na podcykl prosty, o tej samej liczbie odcinków; mówimy, że izomorfizm zachowuje rozkład na podcykle proste. Cykle izomorficzne rozpadają się na tę samą liczbę podcykli prostych (przy czym liczba odcinków w odpowiednich podcyklach jest ta sama).
Niech cykle [;(E\ \nu);] [;(F\ \mu);] oraz odcinek [;a\in E;], taki że [;\nu(a)\ne a;], będą następująco powiązane:
- [;F = E\backslash\{\nu(a)\};]
- [;\mu\,|\,G\backslash\{a\} = \nu\,|\,E\backslash\{a\ \nu(a)\} ;]
- [;\mu(a) = \nu(\nu(a));]
Wtedy mówimy, że cykl [;(F\ \mu);] jest prostą redukcją cyklu [;(E\ \nu);], a ten ostatni prostym rozszerzeniem poprzedniego (o odcinek [;\nu(a);].
Gdy cykl [;(F\ \mu);] można przedstawić jako wynik szeregu prostych redukcji, poczynając od cyklu [;(E\ \nu);], to cykl [;(F\ \mu);] nazywamy redukcją cyklu [;(E\ \nu);], a ten ostatni rozszerzeniem poprzedniego.
Niech podzbiór [;F;] zbioru [;E;] zawiera dokładnie po jednym odcinku z każdego cyklu prostego cyklu [;(E\ \nu;]. Wtedy cykl [;(E\ \nu);] redukuje się do cyklu [;(F\ I_E);] czyli każdy cykl redukuje się do cyklu zredukowanego. Tak więc dwa cykle są izomorficzne [;\Leftrightarrow;] redukują się do cykli zredukowanych, o tej samej liczbie odcinków.
Wednesday, January 5, 2011
Wstęp do Teorii Informacji. Cz.5
Swoją metodę kompresji z Części 4' uzupełnię algorytmem pomocniczym, który ulepsza (dalej kompresuje) kodowanie z Części 4'. Cechą charakterystyczną kodowania z Części 4' jest równa długość otrzymanych kodów binarnych, powiedzmy [;n;]. Na ogół nie wykorzystuje się przy tym wszystkich [;2^n;] kodów binarnych długości, co z miejsca daje możliwość dalszej poprawy.
W niniejszej nocie algorytm poprawiający zilustruję jednak na prostszych przykładach, by szybciej pokazać jak działa. Zajmę się raz jeszcze (patrz Część 3) kodowaniem binarnym ternarnych strun losowych, w których każda wartość bitu trójkowego [;0\ 1\ 2;] występuje z tym samym prawdopodobienstwem [;1/3;], na każdej pozycji struny, statystycznie niezależnie od każdej innej pozycji.
Zacznijmy raz jeszcze, jak w Części 3, od najprostszego kodowania:
Używamy aż całe 2 bity binarne dla zakodowania jednego ternarnego, gdy według teorii Shannona powinno w tym celu średnio wystarczyć
[;log_2(3) \approx 1.585;]
bitów binarnych (nawet ciut mniej). Możemy z łatwością ulepszyć powyższe kodowanie następująco:
Ponieważ w oryginalnym kodowaniu nie wykorzystaliśmy binarnego kodu [;11;], to w kodzie [;10;] zero usunęliśmy, i nasze kodowanie dalej daje się wiernie odkodować (jako że żaden z trzech nowych kodów nie jest prefiksem żadnego pozostalego). Tym razem bitów binarnych na wszystkie trzy trójkowe zużyliśmy 2+2+1=5, zamiast 2+2+2=6, jak poprzednio. Zatem tym losowy bit trójkowy kodujemy średnio za pomocą 5/3 bitów binarnych. Z miejsca uzyskaliśmy przyzwoitą średnią liczbę bitów dwójkowych na jeden trójkowy, niewiele gorszą (czyli większą) od idealnego [;log_2(3);].
Korzystając z nierówności [;3^3 < 2^5;], możemy otrzymać następne proste kodowanie bloków ternarnych, tym razem długości 3, przez bloki binarne o długości 5: po prostu kolejnym 27 ternarnym kodom podporządkujemy odpowiednio 27 kolejnych kodów binarnych długości 5:
Kod ten operuje na większych blokach niż poprzedni - ulepszony - algorytm, a mimo to średnia liczba bitów dwójkowych na jeden trójkowy dla obu kodowań jest ta sama, 5/3. Możemy jednak nasz ostatni kod ulepszyć:
Tylko ostatnie trzy wyrazy binarnego kodu zaczynają się na 11. Możemy więc je skrócić, wciąż zachowując warunek: żaden wyraz binarnego kodu nie jest prefiksem żadnego innego. Pozostałe 24 binarne kody pozostawiamy be zmian:
Zamiast 27 bloków binarnych o długości 5, mamy obecnie 24 o długości 5, 2 o długości 4, oraz 1 o długości 3. Zaoszczędziliśmy 4 bity, i jest ich teraz w sumie [;24\cdot 5+2\cdot 4+ 3 = 131;]. Obecnie liczba dwójkowych bitów na jeden trójkowy wynosi
[;131/81 \approx 1.6173;]
Zbliżyliśmy się do idealnego [;\log_2(3);]. Można w tych samych ramach bardziej, bo powyższe ulepszenie było leniwe, takie by jak najmniej pisać, by jak najlepiej wykorzystać trzykropek. Lepsze ulepszenie otrzymuje się, przez równowmierne rozłożenie oszczędności (w poniższej tabeli, w lewej kolumnie mamy kolejne liczby w układzie trójkowym, a koncentrować warto się na kodach po prawej):
Tym razem zaoszczędziliśmy 5 bitów (zamiast jak przedtem 4), używając do kodowania tylko 130 bitów. Obecna liczba dwójkowych bitów na jeden trójkowy wynosi
[;130/81 \approx 1.605;]
(a nawet ciut mniej). Przypominam, że [;\log_2(3)\approx 1.585;] .
REMARK Nie ważne dla kodowania było to, że przedstawialiśmy lewą stronę powyższej tabeli jako trójkowe struny długości 3. Ważne było tylko to, że było ich 27. Chodziło o podanie 27 binarnych kodów, za pomocą których można kodować wiernie. Był to bardzo, ale to bardzo specjalny przypadek problemu, który nieźle rozwiązali Shannon i Fano, a optymalnie - Huffman.
Przy równych prawdopodobieństwach elementów źródłowego alfabetu probabilistycznego, problem zamienia się w kombinatoryczny, o prawdopodobieństwach można nie mówić - po prostu w ostatnim przypadku chcieliśmy kodować 27 symboli tak by otrzymać wierne kodowanie ich strun. Ogólniej, zamiast alfabetu o 3 symbolach, lub 27, lub innej potędze 3, możemy rozpatrywać alfabety o dowolnej liczbie symboli. Ale to już temat dla oddzielnej noty.
W niniejszej nocie algorytm poprawiający zilustruję jednak na prostszych przykładach, by szybciej pokazać jak działa. Zajmę się raz jeszcze (patrz Część 3) kodowaniem binarnym ternarnych strun losowych, w których każda wartość bitu trójkowego [;0\ 1\ 2;] występuje z tym samym prawdopodobienstwem [;1/3;], na każdej pozycji struny, statystycznie niezależnie od każdej innej pozycji.
Zacznijmy raz jeszcze, jak w Części 3, od najprostszego kodowania:
- [;0 \rightarrow 00;]
- [;1 \rightarrow 01;]
- [;2 \rightarrow 10;]
Używamy aż całe 2 bity binarne dla zakodowania jednego ternarnego, gdy według teorii Shannona powinno w tym celu średnio wystarczyć
[;log_2(3) \approx 1.585;]
bitów binarnych (nawet ciut mniej). Możemy z łatwością ulepszyć powyższe kodowanie następująco:
- [;0 \rightarrow 00;]
- [;1 \rightarrow 01;]
- [;2 \rightarrow 1;]
Ponieważ w oryginalnym kodowaniu nie wykorzystaliśmy binarnego kodu [;11;], to w kodzie [;10;] zero usunęliśmy, i nasze kodowanie dalej daje się wiernie odkodować (jako że żaden z trzech nowych kodów nie jest prefiksem żadnego pozostalego). Tym razem bitów binarnych na wszystkie trzy trójkowe zużyliśmy 2+2+1=5, zamiast 2+2+2=6, jak poprzednio. Zatem tym losowy bit trójkowy kodujemy średnio za pomocą 5/3 bitów binarnych. Z miejsca uzyskaliśmy przyzwoitą średnią liczbę bitów dwójkowych na jeden trójkowy, niewiele gorszą (czyli większą) od idealnego [;log_2(3);].
Korzystając z nierówności [;3^3 < 2^5;], możemy otrzymać następne proste kodowanie bloków ternarnych, tym razem długości 3, przez bloki binarne o długości 5: po prostu kolejnym 27 ternarnym kodom podporządkujemy odpowiednio 27 kolejnych kodów binarnych długości 5:
- [;000 \rightarrow 00000;]
- [;001 \rightarrow 00001;]
- [;002 \rightarrow 00010;]
- [;010 \rightarrow 00011;]
- [;\dots\rightarrow\dots;]
- [;\dots\rightarrow\dots;]
- [;221 \rightarrow 11001;]
- [;222 \rightarrow 11010;]
Kod ten operuje na większych blokach niż poprzedni - ulepszony - algorytm, a mimo to średnia liczba bitów dwójkowych na jeden trójkowy dla obu kodowań jest ta sama, 5/3. Możemy jednak nasz ostatni kod ulepszyć:
Tylko ostatnie trzy wyrazy binarnego kodu zaczynają się na 11. Możemy więc je skrócić, wciąż zachowując warunek: żaden wyraz binarnego kodu nie jest prefiksem żadnego innego. Pozostałe 24 binarne kody pozostawiamy be zmian:
- [;000 \rightarrow 00000;]
- [;\dots\rightarrow\dots;]
- [;\dots\rightarrow\dots;]
- [;212 \rightarrow 10111;]
- [;220 \rightarrow 1100;]
- [;221 \rightarrow 1101;]
- [;222 \rightarrow 111;]
Zamiast 27 bloków binarnych o długości 5, mamy obecnie 24 o długości 5, 2 o długości 4, oraz 1 o długości 3. Zaoszczędziliśmy 4 bity, i jest ich teraz w sumie [;24\cdot 5+2\cdot 4+ 3 = 131;]. Obecnie liczba dwójkowych bitów na jeden trójkowy wynosi
[;131/81 \approx 1.6173;]
Zbliżyliśmy się do idealnego [;\log_2(3);]. Można w tych samych ramach bardziej, bo powyższe ulepszenie było leniwe, takie by jak najmniej pisać, by jak najlepiej wykorzystać trzykropek. Lepsze ulepszenie otrzymuje się, przez równowmierne rozłożenie oszczędności (w poniższej tabeli, w lewej kolumnie mamy kolejne liczby w układzie trójkowym, a koncentrować warto się na kodach po prawej):
- [;000 \rightarrow 00000;]
- [;001 \rightarrow 00001;]
- [;002 \rightarrow 00010;]
- [;010 \rightarrow 00011;]
- [;011 \rightarrow 00100;]
- [;012 \rightarrow 00101;]
- [;020 \rightarrow 0011 \quad\quad *;]
- [;021 \rightarrow 01000;]
- [;022 \rightarrow 01001;]
- [;100 \rightarrow 01010;]
- [;101 \rightarrow 01011;]
- [;102 \rightarrow 01100;]
- [;110 \rightarrow 01101;]
- [;111 \rightarrow 0111 \quad\quad *;]
- [;112 \rightarrow 10000;]
- [;120 \rightarrow 10001;]
- [;121 \rightarrow 10010;]
- [;122 \rightarrow 10011;]
- [;200 \rightarrow 10100;]
- [;201 \rightarrow 10101;]
- [;202 \rightarrow 1011 \quad\quad *;]
- [;210 \rightarrow 11000;]
- [;211 \rightarrow 11001;]
- [;212 \rightarrow 1101 \quad\quad *;]
- [;220 \rightarrow 11100;]
- [;221 \rightarrow 11101;]
- [;222 \rightarrow 1111 \quad\quad *;]
Tym razem zaoszczędziliśmy 5 bitów (zamiast jak przedtem 4), używając do kodowania tylko 130 bitów. Obecna liczba dwójkowych bitów na jeden trójkowy wynosi
[;130/81 \approx 1.605;]
(a nawet ciut mniej). Przypominam, że [;\log_2(3)\approx 1.585;] .
REMARK Nie ważne dla kodowania było to, że przedstawialiśmy lewą stronę powyższej tabeli jako trójkowe struny długości 3. Ważne było tylko to, że było ich 27. Chodziło o podanie 27 binarnych kodów, za pomocą których można kodować wiernie. Był to bardzo, ale to bardzo specjalny przypadek problemu, który nieźle rozwiązali Shannon i Fano, a optymalnie - Huffman.
Przy równych prawdopodobieństwach elementów źródłowego alfabetu probabilistycznego, problem zamienia się w kombinatoryczny, o prawdopodobieństwach można nie mówić - po prostu w ostatnim przypadku chcieliśmy kodować 27 symboli tak by otrzymać wierne kodowanie ich strun. Ogólniej, zamiast alfabetu o 3 symbolach, lub 27, lub innej potędze 3, możemy rozpatrywać alfabety o dowolnej liczbie symboli. Ale to już temat dla oddzielnej noty.
Tuesday, January 4, 2011
Teoria Informacji. Luźne uwagi.
Co tam, Epsilon jest blogiem, więc mogę sobie pozwolić na uwagi od Sasa do lasa.
Algorytmy kompresujące dane dzielą się na lossy i lossless, co po polsku znaczy: stratne i bezstratne. Brzydkie nazwy, fuj! Wprowadziłem ładniejsze terminy: kompresja wierna i niewierna.
Po kompresji wiernej oryginalne dane można w pełni odtworzyć. Po niewiernej na ogół nie można. Niewierna ma zachowywać to co ważne z danego punktu widzenia. Różnym punktom widzenia powinny odpowiadać różne kompresje.
Im dłużej przyglądam się swojemu cyklowi "Wstęp do Teorii Informacji. Cz. nn" (tu, w tym blogu, w Epsilonie), tym silniej i ostrzej widzę, jak i czym się różni od podejścia klasycznego. Ale czy i jak nowe jest moje podejście, to nie wiem, powinienem odnowić kontakty i popytać specjalistów lub przynajmniej ludzi o lepszej ode mnie erudycji. Więcej o różnicach poniżej.
Chociaż Claude Shannon stworzył Teorię Informacji sam jeden (chyba w 1948 roku), to pierwszy algorytm, kompresujący teksty wiernie, stworzyli niemal jednocześnie i niezależnie Shannon i Fano. Komputery były jeszcze w powijakach, a oni już stworzyli algorytmy kodujące binarnie. Ciekawe.
Pierwszy etap kodowania, to kodowanie pojedynczych symboli alfabetu probabilistycznego za pomocą skończonych strun binarnych o zmiennej długości. Samo w sobie ma to ograniczony potencjał. Ale niżej zobaczymy, że przy lekkiej interpretacji uzyskuje się jednak bardzo dużo. Ciekawe. Jedna więcej nietrudna idea, a taki zysk!
Ogólna idea polega na krótkim kodowaniu symboli o wysokiej częstotliwości występowania w losowych strunach (o wysokim prawdopodobieństwie), a więc siłą rzeczy symbolom o niskim prawdopodobieństwie trzeba wtedy przypisywać dłuższe kody binarne, by cały kod dał się odkodować. Shannon i Fano postąpili naturalnie - podzielili symbole na dwie grupy tak, by różniły się te dwie totalnym prawdopodobienstwem możliwie mało, czyli sumy prawdopodobienstw w każdej grupie powinny w miarę możliwości przybliżyć 1/2. Wtedy symbolem jeednej grupy przypisujemy jako pierwszy bit 0, a drugiej grupie 1. Potem w ramach każdej grupy operację dzielenia na dwie zbliżone pod względem totalnego prawdopodobienstwa iterujemy, otrzymując dalsze bity. Powstanie drzewo kodujące, które pozwala kodować i jednoznacznie dekodować. Zakłada się, że drzewo kodu Shannona-Fano jest z góry znane dekodującemu.
Ta dziel (w miarę po równo) i panuj popularna metoda jest bardzo naturalna, zwykły rozsądek (zwykły po czasie).
Najlepszym algorytmem kodującym pojedyncze symbole alfabetu probabilistycznego jest praktyczny i bardzo elegancki algorytm Huffmana. Najlepszy w ścisłym sensie minimalizowania współczynnika oszczędności, co Huffman ślicznie udowodnił w wyjątkowo eleganckiej pracy. (Istnieje w matematyce ogromna liczba, zatrzęsienie, wyjątkowo eleganckich prac, wyników, pojęć, ... - już taka matematyka jest, piękna i elegancka). Być może, kto wie, poświęcę algorytmowi Huffmana post lub parę. Warto go stosować jako drugą połowę algorytmu dwuczęściowego, którego pierwszą połową jest mój algorytm, który opisałem w Części 4'. Co prawda Hufmana stosowałoby się do tak specjalnego przypadku, że na pewno prościej i może lepiej zastosować zamiast Huffmana pewien algorytm, specjalny dla powstałych sytuacji, jeszcze pomyślę.
Gdy zastosujemy algorytm Shannona-Fano lub Huffmana na przykład do alfabetu probabilistycznego [;(A\ \pi);], gdzie [;A:={F\ S};] oraz [;\pi(F) := 5/6,\quad \pi(S):=1/6;], to nic ciekawego się nie otrzyma. Dla małych alfabetów algorytmy kodujące pojedyncze symbole wiele nie zdziałają. Nawet ogólniej, kłopot naprawdę polega nie na tym, że alfabet jest mały, lecz na tym, że co najmniej jeden symbol ma spore prawdopodobieństwo, co przy małej liczbie symboli jest koniecznością.
Tak naprawdę, to chodzi o kodowanie bloków (strun) o równej długości [;n;], powiedzmy strun o 8 symbolach. Każdy blok traktujemy wtedy jako jeden symbol nowego rodzaju. Wtedy każdy blok ma relatywnie małe prawdopodobieństwo. Im większa wspólna długość [;n;] tym mniejsze maksymalne prawdopodobieństwo bloku; a przy [;n;] dążącym do zera maksymalne prawdopodobieństwo bloku dąży do zera. W przypadku symboli [;F\ S;], wszystkie bloki długości 8 mają prawdopodobieństwa nie większe niż [;5/6)^8 < 1/4].
Przy długich blokach otrzymuje się lepszą kompresję, ale jest to dogodne tylko do czasu. Powstają wszelakie niewygody, fizyczność świata rzeczywistego wtrąca się do świata matematyki (z czego matematyka korzysta, rozwija się :-).
Dotąd pisałem tylko o kompresji koncepcyjnie najprostszych strun losowych, w których prawdopodobieństwo występowania symboli na różnych pozycjach zależało wyłącznie od rozkładu prawdopodobieństw w alfabecie, i od niczego więcej. W przypadku strun będących polskimi tekstami, prawdopodobieństwo wystąpienia litery lub innego znaku silnie zależy także od tego, co pojawiło się na miejscu poprzednim. Na przykład po kropce lub po przecinku prawie na pewno wystąpi odstęp lub
itd. :-)
Algorytmy kompresujące dane dzielą się na lossy i lossless, co po polsku znaczy: stratne i bezstratne. Brzydkie nazwy, fuj! Wprowadziłem ładniejsze terminy: kompresja wierna i niewierna.
Po kompresji wiernej oryginalne dane można w pełni odtworzyć. Po niewiernej na ogół nie można. Niewierna ma zachowywać to co ważne z danego punktu widzenia. Różnym punktom widzenia powinny odpowiadać różne kompresje.
Im dłużej przyglądam się swojemu cyklowi "Wstęp do Teorii Informacji. Cz. nn" (tu, w tym blogu, w Epsilonie), tym silniej i ostrzej widzę, jak i czym się różni od podejścia klasycznego. Ale czy i jak nowe jest moje podejście, to nie wiem, powinienem odnowić kontakty i popytać specjalistów lub przynajmniej ludzi o lepszej ode mnie erudycji. Więcej o różnicach poniżej.
Chociaż Claude Shannon stworzył Teorię Informacji sam jeden (chyba w 1948 roku), to pierwszy algorytm, kompresujący teksty wiernie, stworzyli niemal jednocześnie i niezależnie Shannon i Fano. Komputery były jeszcze w powijakach, a oni już stworzyli algorytmy kodujące binarnie. Ciekawe.
Pierwszy etap kodowania, to kodowanie pojedynczych symboli alfabetu probabilistycznego za pomocą skończonych strun binarnych o zmiennej długości. Samo w sobie ma to ograniczony potencjał. Ale niżej zobaczymy, że przy lekkiej interpretacji uzyskuje się jednak bardzo dużo. Ciekawe. Jedna więcej nietrudna idea, a taki zysk!
Ogólna idea polega na krótkim kodowaniu symboli o wysokiej częstotliwości występowania w losowych strunach (o wysokim prawdopodobieństwie), a więc siłą rzeczy symbolom o niskim prawdopodobieństwie trzeba wtedy przypisywać dłuższe kody binarne, by cały kod dał się odkodować. Shannon i Fano postąpili naturalnie - podzielili symbole na dwie grupy tak, by różniły się te dwie totalnym prawdopodobienstwem możliwie mało, czyli sumy prawdopodobienstw w każdej grupie powinny w miarę możliwości przybliżyć 1/2. Wtedy symbolem jeednej grupy przypisujemy jako pierwszy bit 0, a drugiej grupie 1. Potem w ramach każdej grupy operację dzielenia na dwie zbliżone pod względem totalnego prawdopodobienstwa iterujemy, otrzymując dalsze bity. Powstanie drzewo kodujące, które pozwala kodować i jednoznacznie dekodować. Zakłada się, że drzewo kodu Shannona-Fano jest z góry znane dekodującemu.
Ta dziel (w miarę po równo) i panuj popularna metoda jest bardzo naturalna, zwykły rozsądek (zwykły po czasie).
Najlepszym algorytmem kodującym pojedyncze symbole alfabetu probabilistycznego jest praktyczny i bardzo elegancki algorytm Huffmana. Najlepszy w ścisłym sensie minimalizowania współczynnika oszczędności, co Huffman ślicznie udowodnił w wyjątkowo eleganckiej pracy. (Istnieje w matematyce ogromna liczba, zatrzęsienie, wyjątkowo eleganckich prac, wyników, pojęć, ... - już taka matematyka jest, piękna i elegancka). Być może, kto wie, poświęcę algorytmowi Huffmana post lub parę. Warto go stosować jako drugą połowę algorytmu dwuczęściowego, którego pierwszą połową jest mój algorytm, który opisałem w Części 4'. Co prawda Hufmana stosowałoby się do tak specjalnego przypadku, że na pewno prościej i może lepiej zastosować zamiast Huffmana pewien algorytm, specjalny dla powstałych sytuacji, jeszcze pomyślę.
Gdy zastosujemy algorytm Shannona-Fano lub Huffmana na przykład do alfabetu probabilistycznego [;(A\ \pi);], gdzie [;A:={F\ S};] oraz [;\pi(F) := 5/6,\quad \pi(S):=1/6;], to nic ciekawego się nie otrzyma. Dla małych alfabetów algorytmy kodujące pojedyncze symbole wiele nie zdziałają. Nawet ogólniej, kłopot naprawdę polega nie na tym, że alfabet jest mały, lecz na tym, że co najmniej jeden symbol ma spore prawdopodobieństwo, co przy małej liczbie symboli jest koniecznością.
Tak naprawdę, to chodzi o kodowanie bloków (strun) o równej długości [;n;], powiedzmy strun o 8 symbolach. Każdy blok traktujemy wtedy jako jeden symbol nowego rodzaju. Wtedy każdy blok ma relatywnie małe prawdopodobieństwo. Im większa wspólna długość [;n;] tym mniejsze maksymalne prawdopodobieństwo bloku; a przy [;n;] dążącym do zera maksymalne prawdopodobieństwo bloku dąży do zera. W przypadku symboli [;F\ S;], wszystkie bloki długości 8 mają prawdopodobieństwa nie większe niż [;5/6)^8 < 1/4].
Przy długich blokach otrzymuje się lepszą kompresję, ale jest to dogodne tylko do czasu. Powstają wszelakie niewygody, fizyczność świata rzeczywistego wtrąca się do świata matematyki (z czego matematyka korzysta, rozwija się :-).
Dotąd pisałem tylko o kompresji koncepcyjnie najprostszych strun losowych, w których prawdopodobieństwo występowania symboli na różnych pozycjach zależało wyłącznie od rozkładu prawdopodobieństw w alfabecie, i od niczego więcej. W przypadku strun będących polskimi tekstami, prawdopodobieństwo wystąpienia litery lub innego znaku silnie zależy także od tego, co pojawiło się na miejscu poprzednim. Na przykład po kropce lub po przecinku prawie na pewno wystąpi odstęp lub
itd. :-)
Monday, January 3, 2011
Wstęp do Teorii Informacji. Cz.4"
W Części 4' podałem połowę podstawowego twierdzenia Shannona o kodowaniu strun losowych, pokazując, że istnieją kodowania, których stopień oszczędności dowolnie blisko przybliża entropię używanego alfabetu losowego. W niniejszej nocie pokaże, że kodowania, średnio, lepszej oszczędności niż danej przez entropię, mieć już nie mogą.
Oprócz Części 4', warto przejrzeć przed czytaniem poniższego tekstu, lub w trakcie, także Część 4. Będę zakładał ich znajomość. Zresztą warto porównać Część 4' i 4", widzieć jak są pokrewne.
Niech [;\mathbf{A} := (A\ \pi);] będzie alfabetem probabilistycznym. Niech [;n>2;] będzie liczbą naturalną (według intencji raczej sporą, choć formalnie tego nie wymagam). [;A;]-strunę [;S := (a_0\ \dots\ a_{n-1});] nazywam [;(\mathbf{A}\ n^+);]-struną lub minimalnie przesyconą lub dla krótkości po prostu przesyconą [;\Leftarrow:\Rightarrow;] spełnione są dwie nierówności:
Zbiór wszystkich takich strun przesyconych oznaczamy symbolicznie [;\Delta(\mathbf{A}\ n);].
UWAGA 0 Zbiory [;\Delta(\mathbf{A}\ n);] oraz [;\nabla(\mathbf{A}\ n);] można słowo w słowo tak samo zdefiniować dla dowolnej liczby dodatniej [;n;] (zamiast wyłącznie dla naturalnych). Zachodzi wtedy równość:
[;\Delta(\mathbf{A}\ n) = \nabla\left(\mathbf{A}\ \,n\!+\!\mu\left(\mathbf{A}\right)\right);]
TWIERDZENIE 0 Żadna z dowolnych dwóch różnych [;(\mathbf{A}\ n^+);]-strun nie jest prefiksem drugiej.
DOWÓD Gdy prefiks właściwy pewnej struny ma informację [;n;] lub większą, to sama struna nie może być minimalnie przesycona. KONIEC DOWODU
TWIERDZENIE 1 Każda A-struna nieskończona jest jednoznacznym, nieskończonym złożeniem strun przesyconych. Każda A-struna skończona jest jednoznaczynym skończonym złożeniem strun, z których wszystkie, poza ewentualnie ostatnią (tę występująca na ostatnim miejscu po prawej), są przesycone.
DOWÓD Zbyt nudny by go prezentować. W każdym razie, jednoznaczność rozkładu wynika z Twierdzenia 0. KONIEC DOWODU
TWIERDZENIE 2 S-kuby dowolnych dwóch różnych, przesyconych A-strun są rozłączne.
DOWÓD Na mocy Twierdzenia 0, żadna z tych dwóch strun nie jest prefiksem pozostałej. Zatem rzeczywiście ich S-kuby są rozłączne. KONIEC DOWODU
TWIERDZENIE 3 Dla dowolnej struny nieskończonej [;(a_0\ a_1\ \cdots)\in A^{\mathbb{Z}_+};] istnieje dokładnie jedno [;m;] takie, że [;(a_0\ \cdots\ a_{m-1})\in\Delta(\mathbf{A}\ n);]. Innymi słowy:
[;\bigcup_{S\in\Delta(\mathbf{A}\ n)}B_S = A^{\mathbb{Z}_+};]
DOWÓD Ponieważ [;A;] jest skończone, to
[;\min_{a\in A}\iota(a) > 0;]
więc
[;\lim_{m\rightarrow \infty} \iota\left((a_0\ \dots\ a_{m-1})\right) = \infty;]
przy czym ciąg informacji prefiksów [;\iota\left((a_0\ \dots\ a_{m-1})\right));] jest rosnący. Zatem istnieje dokładnie jedno naturalne [;m;] takie, że prefiks jest przesycony. KONIEC DOWODU
Przypominam (patrz Część 4', Tw.3), że dla dowolnej A-struny skończonej [;S;] zachodzi nierówność
[;\pi''(B_S) = \pi(S) = \frac{1}{2^{\iota(S)}};]
Wynika z niej, że
[;\pi''(B_S) \le \frac{1}{2^n};]
Stąd
TWIERDZENIE 4
[;|\Delta(\mathbf{A}\ n)| \ge 2^n;]
KONIEC DOWODU
Przypominam (patrz Część 4'), że marginesem [;\mu(\mathbf{A});] alfabetu probabilistycznego [;\mathbf{A};] nazywam maksimum informacji jego symboli. Natychmiast otrzymujemy wynik główny
TWIERDZENIE 5 Niech [;\mathbf{A} := (A\ \pi);] będzie alfabetem probabilistycznym. Rozpatrzmy dowolne wierne kodowanie binarne skończonych [;A;]-strun. Wtedy dla dowolnej liczby naturalnej [;n;] istnieje przesycona A-struna [;S;] (więc spełnia warunek [;\iota(S) < n+\mu(\mathbf{A});] ), której kod ma conajmniej [;n;] bitów dwójkowych.
DOWÓD Wszystkich niepustych ciągów zer i jedynek, o długości mniejszej od [;n;], jest tylko [;2^{n}-2;]. Natomiast strun przesyconych jest co najmniej [;2^n;]. KONIEC DOWODU
Oprócz Części 4', warto przejrzeć przed czytaniem poniższego tekstu, lub w trakcie, także Część 4. Będę zakładał ich znajomość. Zresztą warto porównać Część 4' i 4", widzieć jak są pokrewne.
Niech [;\mathbf{A} := (A\ \pi);] będzie alfabetem probabilistycznym. Niech [;n>2;] będzie liczbą naturalną (według intencji raczej sporą, choć formalnie tego nie wymagam). [;A;]-strunę [;S := (a_0\ \dots\ a_{n-1});] nazywam [;(\mathbf{A}\ n^+);]-struną lub minimalnie przesyconą lub dla krótkości po prostu przesyconą [;\Leftarrow:\Rightarrow;] spełnione są dwie nierówności:
- [;\iota(S) \ge n;]
- [;\iota(S') < n;] dla [;S' := (a_0\ \dots\ a_{n-2});]
Zbiór wszystkich takich strun przesyconych oznaczamy symbolicznie [;\Delta(\mathbf{A}\ n);].
UWAGA 0 Zbiory [;\Delta(\mathbf{A}\ n);] oraz [;\nabla(\mathbf{A}\ n);] można słowo w słowo tak samo zdefiniować dla dowolnej liczby dodatniej [;n;] (zamiast wyłącznie dla naturalnych). Zachodzi wtedy równość:
[;\Delta(\mathbf{A}\ n) = \nabla\left(\mathbf{A}\ \,n\!+\!\mu\left(\mathbf{A}\right)\right);]
TWIERDZENIE 0 Żadna z dowolnych dwóch różnych [;(\mathbf{A}\ n^+);]-strun nie jest prefiksem drugiej.
DOWÓD Gdy prefiks właściwy pewnej struny ma informację [;n;] lub większą, to sama struna nie może być minimalnie przesycona. KONIEC DOWODU
TWIERDZENIE 1 Każda A-struna nieskończona jest jednoznacznym, nieskończonym złożeniem strun przesyconych. Każda A-struna skończona jest jednoznaczynym skończonym złożeniem strun, z których wszystkie, poza ewentualnie ostatnią (tę występująca na ostatnim miejscu po prawej), są przesycone.
DOWÓD Zbyt nudny by go prezentować. W każdym razie, jednoznaczność rozkładu wynika z Twierdzenia 0. KONIEC DOWODU
TWIERDZENIE 2 S-kuby dowolnych dwóch różnych, przesyconych A-strun są rozłączne.
DOWÓD Na mocy Twierdzenia 0, żadna z tych dwóch strun nie jest prefiksem pozostałej. Zatem rzeczywiście ich S-kuby są rozłączne. KONIEC DOWODU
TWIERDZENIE 3 Dla dowolnej struny nieskończonej [;(a_0\ a_1\ \cdots)\in A^{\mathbb{Z}_+};] istnieje dokładnie jedno [;m;] takie, że [;(a_0\ \cdots\ a_{m-1})\in\Delta(\mathbf{A}\ n);]. Innymi słowy:
[;\bigcup_{S\in\Delta(\mathbf{A}\ n)}B_S = A^{\mathbb{Z}_+};]
DOWÓD Ponieważ [;A;] jest skończone, to
[;\min_{a\in A}\iota(a) > 0;]
więc
[;\lim_{m\rightarrow \infty} \iota\left((a_0\ \dots\ a_{m-1})\right) = \infty;]
przy czym ciąg informacji prefiksów [;\iota\left((a_0\ \dots\ a_{m-1})\right));] jest rosnący. Zatem istnieje dokładnie jedno naturalne [;m;] takie, że prefiks jest przesycony. KONIEC DOWODU
Przypominam (patrz Część 4', Tw.3), że dla dowolnej A-struny skończonej [;S;] zachodzi nierówność
[;\pi''(B_S) = \pi(S) = \frac{1}{2^{\iota(S)}};]
Wynika z niej, że
[;\pi''(B_S) \le \frac{1}{2^n};]
Stąd
TWIERDZENIE 4
[;|\Delta(\mathbf{A}\ n)| \ge 2^n;]
KONIEC DOWODU
Przypominam (patrz Część 4'), że marginesem [;\mu(\mathbf{A});] alfabetu probabilistycznego [;\mathbf{A};] nazywam maksimum informacji jego symboli. Natychmiast otrzymujemy wynik główny
TWIERDZENIE 5 Niech [;\mathbf{A} := (A\ \pi);] będzie alfabetem probabilistycznym. Rozpatrzmy dowolne wierne kodowanie binarne skończonych [;A;]-strun. Wtedy dla dowolnej liczby naturalnej [;n;] istnieje przesycona A-struna [;S;] (więc spełnia warunek [;\iota(S) < n+\mu(\mathbf{A});] ), której kod ma conajmniej [;n;] bitów dwójkowych.
DOWÓD Wszystkich niepustych ciągów zer i jedynek, o długości mniejszej od [;n;], jest tylko [;2^{n}-2;]. Natomiast strun przesyconych jest co najmniej [;2^n;]. KONIEC DOWODU
Friday, December 31, 2010
Wstęp do Teorii Informacji. Cz.4'
Poniżej podam dowód pewnego podstawowego wyniku Shannona, o kompresji tekstów (strun). W wersji wyniku, którą podaję, dowód jest krótki i łatwy (i chyba elegancki) - miejsce zajmie tylko przypomnienie wstępnych definicji podstawowych. Przejście do wersji klasycznej jest intuicyjnie oczywiste, a i formalnie jest rutynowe, ale wymaga solidnej znajomości elementarnych podstaw teorii prawdopodobieństwa.
Niniejszy post jest kontynuacją Części 4, w której wprowadziłem klasyczną terminologię:
Prawdopodobieństwo [;\pi''(B);], zbioru [;B;] w przestrzeni [;A^n;] lub [;A^{\mathbb{Z_+}};], można traktować jako objętość tego zbioru; przy czym objętość całej przestrzeni jest równa 1. Myślenie w terminach objętości powinno ułatwić zrozumienie i zapamiętanie wielu rozważań (chyba, że jesteś strasznym oryginałem :-).
Alfabety probabilistyczne rozważamy w kontekście strun losowych, w których symbole na każdym miejscu występują z prawdopodobieństwem danym przez alfabet probabilistyczny, przy czym symbole w różnych miejscach struny występują niezależnie od pozostałych (jak wyniki rzutów kostką lub monetą).
Powszechnym w algebrze nieprzemiennej i w logice matematycznej, a potem podstawowym dla całej informatyki, jest pojęcie złożenia dwóch strun (skończonych):
[;W := S.T;]
Dla strun [;S := (a_0\ \dots\ a_{m-1});] oraz [;T := (b_0\ \dots\ b_{n-1});], ich złożenie [;W;] definiujemy jako strunę o długości [;m+n;]:
Złożenie strun jest działaniem łącznym, dzięki czemu w wyrażeniach [;S.T.U;] [;Q.S.T.U;] itp. nie musimy stosować nawiasów.
Złożenie strun skończonych i skończonej z nieskończoną (w tej kolejności) rozpatruje się także w przestrzeni [;A^{\mathbb{Z}_+};]. W szczególności, dla A-struny skończonej [;S;], S-kub [;B_S;] może być równoważnie i elegancko określony jak następuje:
[;B_S := \left\{ S.T : T\in A^{\mathbb{Z}_+}\right\};]
Dla ustalonego alfabetu [;A;], skończone struny niepuste (o skończonej, dodatniej długości - innych strun dotąd w tej serii not nie rozpatrywałem, z wyjątkiem elementów przestrzeni [;A^{\mathbb{Z}_+};]) tworzą półgrupę (i to półgrupę wolną). Gdy dołączymy strunę pustą [;\emptyset;], to uzyskamy monoid (a nawet monoid wolny), w którym rolę jedności gra właśnie struna pusta.
Niech [;(A\ \pi);] będzie alfabetem probabilistycznym. Jego marginesem [;\mu(A\ \pi);] nazywam maksymalną informację jego symbolu:
[;\mu(A\ \pi) := \max_a\ \iota(a);]
Margines jest więc informacja symbolu o najmniejszym prawdopodobieństwie, więc zawsze jest równy nie mniej niż 1 (nawet jest większy niż 1, poza jedynym wyjątkiem, gdy mamy dokładnie 2 symbole, i każdy ma prawdopodobieństwo równe 1/2).
Niech [;\mathbf{A} := (A\ \pi);] będzie alfabetem probabilistycznym. Niech [;n > \mu(\mathbf{A});] będzie dowolną liczbą naturalną (tak naprawdę, to obchodzą nas przede wszystkim liczby [;n;] sporo większe od marginesu). [;A;]-strunę [;S := (a_0 \dots\ a_{m-1});] nazywam [;(\mathbf{A}\ n);]-struną lub struną nasyconą (względem [;\mathbf{A};] oraz [;n;]) [;\Leftarrow:\Rightarrow;] [;S;] spełnia dwa warunki:
(Prawa nierówność w pierwszym warunku wynika z pozostałych dwóch nierówności). W kontekście jednego twierdzenia, gdy mówimy o strunach nasyconych, to cały czas mamy na myśli ustaloną liczbę naturalną [;n;], oraz ustalony alfabet propbabilistyczny. Udowodnię teraz ciąg łatwych własności strun nasyconych, prowadzący do wyniku głównego.
TWIERDZENIE 0 Żadna [;(\mathbf{A}\ n);]-struna nie jest prefiksem żadnej innej, różnej od niej [;(\mathbf{A}\ n);]-struny.
DOWÓD Prefiks właściwy struny nasyconej nie jest nasycony, gdyż ma informację nieprzekraczającą [;n-\mu(\mathbf{A});]. KONIEC DOWODU
TWIERDZENIE 1 Każda A-struna nieskończona jest jednoznacznym, nieskończonym złożeniem strun nasyconych. Każda A-struna skończona jest jednoznaczynym skończonym złożeniem strun, z których wszystkie, poza ewentualnie ostatnią (tę występująca na ostatnim miejscu po prawej), są nasycone.
DOWÓD Zbyt nudny by go prezentować. W każdym razie, jednoznaczność rozkładu wynika z Twierdzenia 0. KONIEC DOWODU
TWIERDZENIE 2 S-kuby dowolnych dwóch różnych, nasyconych A-strun są rozłączne.
DOWÓD Na mocy Twierdzenia 0, żadna z tych dwóch strun nie jest prefiksem pozostałej. Zatem rzeczywiście ich S-kuby są rozłączne. KONIEC DOWODU
TWIERDZENIE 3 Dla dowolnej A-struny skończonej [;S;] zachodzi równość
[;\pi''(B_S) = \pi(S) = \frac{1}{2^{\iota(S)}};]
DOWÓD Niech [;S := (a_0\ \dots\ a_{n-1});] Należy skorzystać z definicji informacji, i z własności logarytmu:
[;\frac{1}{2^{\iota(S)}} =
\frac{1}{2^{\sum_{k < n}\iota(a_k)}} =
\frac{1}{2^{\sum_{k < n}\log_2\left(\frac{1}{\pi(a_k)}\right)}} ;]
[;= \frac{1}{2^{\log_2\left(
\prod_{k < n}\frac{1}{\pi(a_k)}
\right)}} = \frac{1}{\prod_{k < n}\frac{1}{\pi(a_k)}} = \pi(S);]
KONIEC DOWODU
Niech [;\mathbf{A} := (A\ \pi);] będzie alfabetem probabilistycznym. Niech [;\nabla(\mathbf{A}\ n);] będzie zbiorem wszystkich [;(\mathbf{A}\ n);]-strun (czyli strun nasyconych). Jest ich nie więcej niż [;2^n;], co - w połączeniu z Twierdzeniem 1 jest głównym wynikiem tej noty:
TWIERDZENIE 4
[;|\nabla(\mathbf{A}\ n)| \le 2^n;]
dla każdego naturalnego [;n \ge \mu(\mathbf{A});].
DOWÓD Wiemy z poprzedniego twierdzenia (Tw. 3), że [;\pi''(B_S) \ge 2^{-n};] dla dowolnej struny nasyconej [;S;]. Ponieważ S-kuby są rozłączne, oraz [;\pi''(A^{\mathbb{Z}_+}) = 1;], to takich S-kubów jest nie więcej niż [;2^n;]. KONIEC DOWODU
Widzimy, że struny nasycone [;S;] możemy kodować za pomocą bloków zero-jedynkowych, długości [;n;], czyli - przy [;n;] sporo większym od marginesu [;\mu(\mathbf{A});] - co najwyżej nieznacznie dłuższych od informacji [;\iota(S);]. Niech [;\delta > 0;] będzie dowolną, dodatnią liczbą rzeczywistą (chodzi o dowolnie małe). Gdy ustalimy
[;n > \delta + \mu\cdot(1+\delta);]
to liczba bitów dwójkowych kodu będzie tylko nieznacznie przekraczać liczbę bitów informacji zawartej w źródłowej strunie nasyconej:
[;\frac{n}{\iota(S)} < 1 +\delta;]
Niech [;\delta\ n;] będą jak powyżej. Gdy ustalimy dostatecznie wielką liczbę naturalną [;M;], to A-struny [;T;] długości co najmniej [;M;] będą złożeniem długiego ciągu strun nasyconych, zakończonych ewentualnie struną nienasyconą (a te są relatywnie krótkie, bo marginesowe). Struny nasycone zakodują się za pomocą nie więcej niż [;(1+\delta');] dwójkowego bitu per bit informacji, gdzie [\delta';] jest stałą spełniającą:
[;0 < \delta' < \delta;]
Gdyby nie było nienasyconej końcówki, to cała struna [;T;] zakodowałaby się za pomocą średnio [;1+\delta';] dwójkowego bitu per bit informacji. Ewentualna nienasycona końcówka może to nieco zepsuć, ale dla dostatecznie dużego [;M;] wciąż będzie prawdziwe nieco gorsze oszacowanie [;1+\delta;] dwójkowego bitu per bit informacji.
UWAGA Istnienie [;\delta';] wynika ze skończoności zbioru \nabla(\mathbf{A}\ n) wszystkich strun nasyconych [;S;]. Możemy przyjąć
[;\delta' =
\max_{S\in\nabla(\mathbf{A}\ n)}\ \left(\frac{n}{\iota(S)}\ -\ 1\right);]
Nieco już praktyczniejszą kwestią jest takie dobranie [;\delta';] by [;M;] mogło być jak najmniejsze.
W tym odcinku nie chciałem Was nużyć zbyt pedantycznymi, rutynowymi, epsilon-delta ścisłymi dowodami.
W całej nocie moglibyśmy zastąpić [;2;], w roli podstawy logarytmu i potęgowania, przez dowolną liczbę naturalną [;b > 1;] - Hugo Steinhaus powiedziałby, że 2 jest zmienna :-). Chociaż takie uogólnienie jest automatyczne, to i tak jest bardzo wartościowe. Wynika z niego na przykład to, że przy ustalonej liczbie [;\alpha := |A|;] symboli alfabetu, maksuymalną entropię alfabetu probabilistycznego otrzymuje się przy jednorodnym rozkładzie prawdopodobieństw symboli, gdy
[;\pi(a) = \frac{1}{\alpha};]
dla każdego [;a\in A;]. Pomyślcie o tym :-)
Niniejszy post jest kontynuacją Części 4, w której wprowadziłem klasyczną terminologię:
- alfabet probabilistyczny [;(A\ \pi);] - zawsze zakładamy, że [;|A| > 1;], czyli że istnieją co najmniej 2 różne symbole;
- [;A;]-struna (i [;A;]-blok) ;
- informacja
[;\iota(a) := \log_2\left(\frac{1}{\pi(a)}\right);]
symbolu [;a;] alfabetu [;A;] ; - entropia
[;\epsilon(A\ \pi) := \sum_{a\in A} \pi(a)\cdot\log_2\left(\frac{1}{\pi(a)}\right);]
alfabetu probabilistycznego [;(A\ \pi);] ; - informacja
[;\iota(S) := \sum_{k < n} \log_2\left(\frac{1}{\pi(a_k)}\right);]
[;A;]-struny [;S := (a_0 \dots\ a_{n-1});] ; - przestrzenie skończenie i nieskończenie wymiarowe [;A;]-strun:
[;A^n;] oraz [;A^{\mathbb{Z_+}};]
wraz z funkcją prawdopodobieństwa [;\pi'';] (patrz następne trzy punkty tej listy); - prawdopodobieństwo [;\pi''(B);] dowolnego zbioru [;B\subseteq A^n;], jako suma prawdopodobieństw [;\pi(S);] jego [;A;]-strun:
[;\pi''(B) := \sum_{S\in B} \pi(S);]
dla dowolnego [;n = 1\ 2\ \dots;] - S-kub [;B_S;]:
[;B_S := \left\{(x_0\ x_1\ \dots) : \displaystyle\forall_{k < n}\ x_k = a_k \right\} ;]
dla dowolnej skończonej [;A;]-struny [;S := (a_0 \dots\ a_{n-1});] ; - Prawdopodobieństwo [;\pi'';] w przestrzeni [;A^{\mathbb{Z_+}};]:
[;\pi''(B_S) := \pi(S);]
oraz prawdopodobieństwo [;\pi'';] dowolnego zbioru, będącego unią skóńczonej lub przeliczalnej rodziny parami rozłącznych S-kubów jest sumą prawdopodobieństw [;pi'';] S-kubów, będących składnikami unii.
Prawdopodobieństwo [;\pi''(B);], zbioru [;B;] w przestrzeni [;A^n;] lub [;A^{\mathbb{Z_+}};], można traktować jako objętość tego zbioru; przy czym objętość całej przestrzeni jest równa 1. Myślenie w terminach objętości powinno ułatwić zrozumienie i zapamiętanie wielu rozważań (chyba, że jesteś strasznym oryginałem :-).
Alfabety probabilistyczne rozważamy w kontekście strun losowych, w których symbole na każdym miejscu występują z prawdopodobieństwem danym przez alfabet probabilistyczny, przy czym symbole w różnych miejscach struny występują niezależnie od pozostałych (jak wyniki rzutów kostką lub monetą).
Powszechnym w algebrze nieprzemiennej i w logice matematycznej, a potem podstawowym dla całej informatyki, jest pojęcie złożenia dwóch strun (skończonych):
[;W := S.T;]
Dla strun [;S := (a_0\ \dots\ a_{m-1});] oraz [;T := (b_0\ \dots\ b_{n-1});], ich złożenie [;W;] definiujemy jako strunę o długości [;m+n;]:
- [;W(i) := S(i);] dla [;i=0\ \dots\ m-1;]. oraz
- [;W(i) := T(i-m);] dla [;i=m\ \dots\ n-1;].
Złożenie strun jest działaniem łącznym, dzięki czemu w wyrażeniach [;S.T.U;] [;Q.S.T.U;] itp. nie musimy stosować nawiasów.
Złożenie strun skończonych i skończonej z nieskończoną (w tej kolejności) rozpatruje się także w przestrzeni [;A^{\mathbb{Z}_+};]. W szczególności, dla A-struny skończonej [;S;], S-kub [;B_S;] może być równoważnie i elegancko określony jak następuje:
[;B_S := \left\{ S.T : T\in A^{\mathbb{Z}_+}\right\};]
Dla ustalonego alfabetu [;A;], skończone struny niepuste (o skończonej, dodatniej długości - innych strun dotąd w tej serii not nie rozpatrywałem, z wyjątkiem elementów przestrzeni [;A^{\mathbb{Z}_+};]) tworzą półgrupę (i to półgrupę wolną). Gdy dołączymy strunę pustą [;\emptyset;], to uzyskamy monoid (a nawet monoid wolny), w którym rolę jedności gra właśnie struna pusta.
Niech [;(A\ \pi);] będzie alfabetem probabilistycznym. Jego marginesem [;\mu(A\ \pi);] nazywam maksymalną informację jego symbolu:
[;\mu(A\ \pi) := \max_a\ \iota(a);]
Margines jest więc informacja symbolu o najmniejszym prawdopodobieństwie, więc zawsze jest równy nie mniej niż 1 (nawet jest większy niż 1, poza jedynym wyjątkiem, gdy mamy dokładnie 2 symbole, i każdy ma prawdopodobieństwo równe 1/2).
Niech [;\mathbf{A} := (A\ \pi);] będzie alfabetem probabilistycznym. Niech [;n > \mu(\mathbf{A});] będzie dowolną liczbą naturalną (tak naprawdę, to obchodzą nas przede wszystkim liczby [;n;] sporo większe od marginesu). [;A;]-strunę [;S := (a_0 \dots\ a_{m-1});] nazywam [;(\mathbf{A}\ n);]-struną lub struną nasyconą (względem [;\mathbf{A};] oraz [;n;]) [;\Leftarrow:\Rightarrow;] [;S;] spełnia dwa warunki:
- [;n - \mu(\mathbf{A}) < \iota(S) \le n;]
- [;\iota(S') \le n-\mu(\mathbf{A});], gdzie [;S' := (a_0\ \dots\ a_{m-2});]
(Prawa nierówność w pierwszym warunku wynika z pozostałych dwóch nierówności). W kontekście jednego twierdzenia, gdy mówimy o strunach nasyconych, to cały czas mamy na myśli ustaloną liczbę naturalną [;n;], oraz ustalony alfabet propbabilistyczny. Udowodnię teraz ciąg łatwych własności strun nasyconych, prowadzący do wyniku głównego.
TWIERDZENIE 0 Żadna [;(\mathbf{A}\ n);]-struna nie jest prefiksem żadnej innej, różnej od niej [;(\mathbf{A}\ n);]-struny.
DOWÓD Prefiks właściwy struny nasyconej nie jest nasycony, gdyż ma informację nieprzekraczającą [;n-\mu(\mathbf{A});]. KONIEC DOWODU
TWIERDZENIE 1 Każda A-struna nieskończona jest jednoznacznym, nieskończonym złożeniem strun nasyconych. Każda A-struna skończona jest jednoznaczynym skończonym złożeniem strun, z których wszystkie, poza ewentualnie ostatnią (tę występująca na ostatnim miejscu po prawej), są nasycone.
DOWÓD Zbyt nudny by go prezentować. W każdym razie, jednoznaczność rozkładu wynika z Twierdzenia 0. KONIEC DOWODU
TWIERDZENIE 2 S-kuby dowolnych dwóch różnych, nasyconych A-strun są rozłączne.
DOWÓD Na mocy Twierdzenia 0, żadna z tych dwóch strun nie jest prefiksem pozostałej. Zatem rzeczywiście ich S-kuby są rozłączne. KONIEC DOWODU
TWIERDZENIE 3 Dla dowolnej A-struny skończonej [;S;] zachodzi równość
[;\pi''(B_S) = \pi(S) = \frac{1}{2^{\iota(S)}};]
DOWÓD Niech [;S := (a_0\ \dots\ a_{n-1});] Należy skorzystać z definicji informacji, i z własności logarytmu:
[;\frac{1}{2^{\iota(S)}} =
\frac{1}{2^{\sum_{k < n}\iota(a_k)}} =
\frac{1}{2^{\sum_{k < n}\log_2\left(\frac{1}{\pi(a_k)}\right)}} ;]
[;= \frac{1}{2^{\log_2\left(
\prod_{k < n}\frac{1}{\pi(a_k)}
\right)}} = \frac{1}{\prod_{k < n}\frac{1}{\pi(a_k)}} = \pi(S);]
KONIEC DOWODU
Niech [;\mathbf{A} := (A\ \pi);] będzie alfabetem probabilistycznym. Niech [;\nabla(\mathbf{A}\ n);] będzie zbiorem wszystkich [;(\mathbf{A}\ n);]-strun (czyli strun nasyconych). Jest ich nie więcej niż [;2^n;], co - w połączeniu z Twierdzeniem 1 jest głównym wynikiem tej noty:
TWIERDZENIE 4
[;|\nabla(\mathbf{A}\ n)| \le 2^n;]
dla każdego naturalnego [;n \ge \mu(\mathbf{A});].
DOWÓD Wiemy z poprzedniego twierdzenia (Tw. 3), że [;\pi''(B_S) \ge 2^{-n};] dla dowolnej struny nasyconej [;S;]. Ponieważ S-kuby są rozłączne, oraz [;\pi''(A^{\mathbb{Z}_+}) = 1;], to takich S-kubów jest nie więcej niż [;2^n;]. KONIEC DOWODU
Widzimy, że struny nasycone [;S;] możemy kodować za pomocą bloków zero-jedynkowych, długości [;n;], czyli - przy [;n;] sporo większym od marginesu [;\mu(\mathbf{A});] - co najwyżej nieznacznie dłuższych od informacji [;\iota(S);]. Niech [;\delta > 0;] będzie dowolną, dodatnią liczbą rzeczywistą (chodzi o dowolnie małe). Gdy ustalimy
[;n > \delta + \mu\cdot(1+\delta);]
to liczba bitów dwójkowych kodu będzie tylko nieznacznie przekraczać liczbę bitów informacji zawartej w źródłowej strunie nasyconej:
[;\frac{n}{\iota(S)} < 1 +\delta;]
Niech [;\delta\ n;] będą jak powyżej. Gdy ustalimy dostatecznie wielką liczbę naturalną [;M;], to A-struny [;T;] długości co najmniej [;M;] będą złożeniem długiego ciągu strun nasyconych, zakończonych ewentualnie struną nienasyconą (a te są relatywnie krótkie, bo marginesowe). Struny nasycone zakodują się za pomocą nie więcej niż [;(1+\delta');] dwójkowego bitu per bit informacji, gdzie [\delta';] jest stałą spełniającą:
[;0 < \delta' < \delta;]
Gdyby nie było nienasyconej końcówki, to cała struna [;T;] zakodowałaby się za pomocą średnio [;1+\delta';] dwójkowego bitu per bit informacji. Ewentualna nienasycona końcówka może to nieco zepsuć, ale dla dostatecznie dużego [;M;] wciąż będzie prawdziwe nieco gorsze oszacowanie [;1+\delta;] dwójkowego bitu per bit informacji.
UWAGA Istnienie [;\delta';] wynika ze skończoności zbioru \nabla(\mathbf{A}\ n) wszystkich strun nasyconych [;S;]. Możemy przyjąć
[;\delta' =
\max_{S\in\nabla(\mathbf{A}\ n)}\ \left(\frac{n}{\iota(S)}\ -\ 1\right);]
Nieco już praktyczniejszą kwestią jest takie dobranie [;\delta';] by [;M;] mogło być jak najmniejsze.
W tym odcinku nie chciałem Was nużyć zbyt pedantycznymi, rutynowymi, epsilon-delta ścisłymi dowodami.
W całej nocie moglibyśmy zastąpić [;2;], w roli podstawy logarytmu i potęgowania, przez dowolną liczbę naturalną [;b > 1;] - Hugo Steinhaus powiedziałby, że 2 jest zmienna :-). Chociaż takie uogólnienie jest automatyczne, to i tak jest bardzo wartościowe. Wynika z niego na przykład to, że przy ustalonej liczbie [;\alpha := |A|;] symboli alfabetu, maksuymalną entropię alfabetu probabilistycznego otrzymuje się przy jednorodnym rozkładzie prawdopodobieństw symboli, gdy
[;\pi(a) = \frac{1}{\alpha};]
dla każdego [;a\in A;]. Pomyślcie o tym :-)
Thursday, December 30, 2010
Wstęp do Teorii Informacji. Cz.4
Przedstawię w niniejszej nocie jeden z wyników Clauda Shannona, o tym że można długie teksty kompresować, przybliżając się dowolnie blisko do ograniczenia podanego przez Shannona. Moje podejście będzie niestandardowe, a może nawet oryginalne - mała na to ostatnie szansa, bo literatura jest ogromna, a jej nie znam.
Na ogół definiuje się wyrazy kodu, powiedzmy zero-jedynkowe, o zmiennej długości, dla odcinków (bloków) oryginału o równej długości. Ja natomiast podzielę (w Części 4') teksty oryginalne na odcinki o nierównej długości, ale koduję je za pomocą 0-1 wyrazów o równej długości. To nastepnie bez większego trudu pozwala skonstruować inne, bardziej klasyczne kodowanie A-bloków (to znaczy A-strun - patrz niżej) o równej długości za pomocą bloków zero-jedynkowych, o zmiennej długości.
Gdy matematyk zajmuje się pewnym zastosowaniem, to początkowo szuka odpowiedniej definicji (tj. systemu definicji czyli teorii) - odpowiedniej, czyli spełniającej dwa warunki:
Jak tylko uzyska taką definicje, to krzyczy: niech się dzieje, co się ma dziać, ale odtąd liczy się moja definicja - po czym rozwija teorię. Definicja i rzeczywistość nie są tym samym. Nie istnieje "prawdziwa" definicja, tak jak nie istnieje prawdziwa mapa terenu. Istnieją co najwyżej lepsze i gorsze. Najlepsze są nieporównywalne pod względem matematycznej lepszości, choć mogą oddawać rzeczywistość z różną dokładnością lub w różnym zakresie (mogą zajmować się różnymi obszarami zastosowania) - podobnie nieporównywalne są dobre mapy: są fizyczne, administracyjne, geologiczne, nawigacyjne, ... Używają różnych układów współrzędnych (siatek), różnych skal pomniejszenia, przedstawiają różne tereny. Podobnie jest ze związkiem teorii matematycznych z rzeczywistością.
W niniejszej nocie, śladem Shannona, będzie podana matematyczna definicja informacji i entropii. Będzie zastosowana do teorii kompresji tekstów (strun nad zadanym alfabetem [;A;]). Struny, których wszystkie symbole należą do alfabetu [;A;] nazywamy A-strunami. Informację w niniejszej nocie mierzymy w bitach dwójkowych; stąd we wzorach logarytm o podstawie 2.
Niech [;(0;\infty);] oznacza przedział wszystkich wszystkich dodatnich liczb rzeczywistych. Przez alfabet probabilistyczny rozumiem parę uporządkowaną
[;(A\ \pi);]
gdzie alfabet [;A;] jest dowolnym zbiorem skończonym, oraz [;\pi : A \rightarrow (0;\infty);] spełnia warunek:
[;\sum_{a\in A} \pi(a)=1;]
Alfabet probabilistyczny w zasadzie jest po prostu skończoną przestrzenią probabilistyczną, jako że funkcja [;\pi;] naturalnie indukuje funkcję prawdopodobieństwa [;\pi';], zdefiniowaną dla dowolnego podzbioru [;B;] zbioru [;A;]:
[;\pi'(B) := \sum_{a\in B} \pi(a);]
Ponieważ jesteśmy zainteresowani w strunach, w których symbole występujące na dowolnych dwóch miejscach są niezależne (statystycznie), to definiujemy prawdopodobieństwo [;\pi(S);] dowolnej [;A;]-struny
[;S := (a_0 \dots a_{n-1});]
jako iloczyn prawdopodobieństw poszczególnych znaków:
[;\pi(S) := \prod_{k < n} \pi(a_k);]
Wtedy suma prawdopodobieństw wszystkich [;A;]-strun o ustalonej długości [;n;] jest równa 1, czyli struny o ustalonej długości tworzą przestrzeń probabilistyczną; takich strun o ustalonej długości [;n;] jest wszystkich razem [;|A|^n;].
Niech [;(A\ \pi);] będzie alfabetem probabilistycznym. Informacją zawartą w symbolu [;a\in A;] nazywamy
[;\iota(a) := \log_2\left(\frac{1}{\pi(a)}\right);]
Im symbol ma niższe prawdopodobieństwo (wystąpienia w tekście), tym każde jego wystąpienie niesie więcej informacji. Gdy pewien symbol ma prawdopodobieństwo bliskie 1, to występuje w tekstach prawie na każdym miejscu, i jego występowanie jest spodziewane. Wtedy niesie on niewielką informację (logarytm jest bliski zeru).
Entropią [;\epsilon(A\ \pi);] alfabetu probabilistycznego [;(A\ \pi);] nazywamy wartość oczekiwaną, czyli średnią ważoną informacji zawartych w symbolach alfabetu:
[;\epsilon(A\ \pi) := \sum_{a\in A} \pi(a)\cdot \log_2\left(\frac{1}{\pi(a)}\right);]
Informacją zawartą w strunie [;S := (a_0\dots a_{n-1});] nazywamy sumę informacji jej symboli:
[;\iota(S) := \sum_{k < n} \iota(a_k);]
Informacja per symbol, czyli informacja struny podzielona przez jej długość (przez liczbę jej symboli) jest dla długich, losowych strun na ogół równa w przybliżeniu entropii alfabetu.
Dla elegancji rozpatrzmy także struny nieskończone [;(a_0\ a_1\ \dots);]. Są one punktami czyli tworzą przestrzeń [;A^{\mathbb{Z}_+};], będacą iloczynem kartezjańskim nieskończenie wielu kopii [;A;]. W przestrzeni tej wprowadzamy miarę probabilistyczna, zaczynając od definicji [;\pi''(B_S);] miary S-kubów [;B(S);], gdzie [;S := (a_0\ \dots\ a_{n-1};] jest struną skończoną, oraz
[;B_S := \left\{(x_0\ x_1\ \dots) : \displaystyle\forall_{k < n} x_k = a_k \right\} ;]
oraz S-kub jest zdefiniowany jako podzbiór przestrzeni:
[;\pi''\left(B_S\right) := \pi(S) = \prod_{k < n} \pi(a_k) ;]
Następnie miarę unii skończonej lub przeliczalnej rodziny parami rozłącznych S-kubów definiuje się jako sumę miar wchodzących w tę rodzinę S-kubów. Podstawowa własność S-kubów brzmi następująco:
TWIERDZENIE 0 Niech [;S\ T;] będą dwiema skończonymi A-strunami. Wtedy boksy [;B_S\ B_T;] są rozłączne [;\Leftrightarrow;] żadna ze strun [;S\ T;] nie jest prefiksem (początkowym odcinkiem) drugiej.
Wynika stąd, że dwa S-kuby są albo rozłączne albo jeden z nich jest zawarty w drugim.
Miara całej przestrzeni [;A^{\mathbb{Z}_+};] wynosi dokładnie 1.
cdn. (patrz Cz.4')
Na ogół definiuje się wyrazy kodu, powiedzmy zero-jedynkowe, o zmiennej długości, dla odcinków (bloków) oryginału o równej długości. Ja natomiast podzielę (w Części 4') teksty oryginalne na odcinki o nierównej długości, ale koduję je za pomocą 0-1 wyrazów o równej długości. To nastepnie bez większego trudu pozwala skonstruować inne, bardziej klasyczne kodowanie A-bloków (to znaczy A-strun - patrz niżej) o równej długości za pomocą bloków zero-jedynkowych, o zmiennej długości.
Gdy matematyk zajmuje się pewnym zastosowaniem, to początkowo szuka odpowiedniej definicji (tj. systemu definicji czyli teorii) - odpowiedniej, czyli spełniającej dwa warunki:
- definicja nieźle przybliża ważną (lub pilną) część zastosowania;
- definicja jest na tyle trafna, prosta i elegancka, że prowadzi do harmonijnej, głębokiej teorii.
Jak tylko uzyska taką definicje, to krzyczy: niech się dzieje, co się ma dziać, ale odtąd liczy się moja definicja - po czym rozwija teorię. Definicja i rzeczywistość nie są tym samym. Nie istnieje "prawdziwa" definicja, tak jak nie istnieje prawdziwa mapa terenu. Istnieją co najwyżej lepsze i gorsze. Najlepsze są nieporównywalne pod względem matematycznej lepszości, choć mogą oddawać rzeczywistość z różną dokładnością lub w różnym zakresie (mogą zajmować się różnymi obszarami zastosowania) - podobnie nieporównywalne są dobre mapy: są fizyczne, administracyjne, geologiczne, nawigacyjne, ... Używają różnych układów współrzędnych (siatek), różnych skal pomniejszenia, przedstawiają różne tereny. Podobnie jest ze związkiem teorii matematycznych z rzeczywistością.
W niniejszej nocie, śladem Shannona, będzie podana matematyczna definicja informacji i entropii. Będzie zastosowana do teorii kompresji tekstów (strun nad zadanym alfabetem [;A;]). Struny, których wszystkie symbole należą do alfabetu [;A;] nazywamy A-strunami. Informację w niniejszej nocie mierzymy w bitach dwójkowych; stąd we wzorach logarytm o podstawie 2.
Niech [;(0;\infty);] oznacza przedział wszystkich wszystkich dodatnich liczb rzeczywistych. Przez alfabet probabilistyczny rozumiem parę uporządkowaną
[;(A\ \pi);]
gdzie alfabet [;A;] jest dowolnym zbiorem skończonym, oraz [;\pi : A \rightarrow (0;\infty);] spełnia warunek:
[;\sum_{a\in A} \pi(a)=1;]
Alfabet probabilistyczny w zasadzie jest po prostu skończoną przestrzenią probabilistyczną, jako że funkcja [;\pi;] naturalnie indukuje funkcję prawdopodobieństwa [;\pi';], zdefiniowaną dla dowolnego podzbioru [;B;] zbioru [;A;]:
[;\pi'(B) := \sum_{a\in B} \pi(a);]
Ponieważ jesteśmy zainteresowani w strunach, w których symbole występujące na dowolnych dwóch miejscach są niezależne (statystycznie), to definiujemy prawdopodobieństwo [;\pi(S);] dowolnej [;A;]-struny
[;S := (a_0 \dots a_{n-1});]
jako iloczyn prawdopodobieństw poszczególnych znaków:
[;\pi(S) := \prod_{k < n} \pi(a_k);]
Wtedy suma prawdopodobieństw wszystkich [;A;]-strun o ustalonej długości [;n;] jest równa 1, czyli struny o ustalonej długości tworzą przestrzeń probabilistyczną; takich strun o ustalonej długości [;n;] jest wszystkich razem [;|A|^n;].
Niech [;(A\ \pi);] będzie alfabetem probabilistycznym. Informacją zawartą w symbolu [;a\in A;] nazywamy
[;\iota(a) := \log_2\left(\frac{1}{\pi(a)}\right);]
Im symbol ma niższe prawdopodobieństwo (wystąpienia w tekście), tym każde jego wystąpienie niesie więcej informacji. Gdy pewien symbol ma prawdopodobieństwo bliskie 1, to występuje w tekstach prawie na każdym miejscu, i jego występowanie jest spodziewane. Wtedy niesie on niewielką informację (logarytm jest bliski zeru).
Entropią [;\epsilon(A\ \pi);] alfabetu probabilistycznego [;(A\ \pi);] nazywamy wartość oczekiwaną, czyli średnią ważoną informacji zawartych w symbolach alfabetu:
[;\epsilon(A\ \pi) := \sum_{a\in A} \pi(a)\cdot \log_2\left(\frac{1}{\pi(a)}\right);]
Informacją zawartą w strunie [;S := (a_0\dots a_{n-1});] nazywamy sumę informacji jej symboli:
[;\iota(S) := \sum_{k < n} \iota(a_k);]
Informacja per symbol, czyli informacja struny podzielona przez jej długość (przez liczbę jej symboli) jest dla długich, losowych strun na ogół równa w przybliżeniu entropii alfabetu.
Dla elegancji rozpatrzmy także struny nieskończone [;(a_0\ a_1\ \dots);]. Są one punktami czyli tworzą przestrzeń [;A^{\mathbb{Z}_+};], będacą iloczynem kartezjańskim nieskończenie wielu kopii [;A;]. W przestrzeni tej wprowadzamy miarę probabilistyczna, zaczynając od definicji [;\pi''(B_S);] miary S-kubów [;B(S);], gdzie [;S := (a_0\ \dots\ a_{n-1};] jest struną skończoną, oraz
[;B_S := \left\{(x_0\ x_1\ \dots) : \displaystyle\forall_{k < n} x_k = a_k \right\} ;]
oraz S-kub jest zdefiniowany jako podzbiór przestrzeni:
[;\pi''\left(B_S\right) := \pi(S) = \prod_{k < n} \pi(a_k) ;]
Następnie miarę unii skończonej lub przeliczalnej rodziny parami rozłącznych S-kubów definiuje się jako sumę miar wchodzących w tę rodzinę S-kubów. Podstawowa własność S-kubów brzmi następująco:
TWIERDZENIE 0 Niech [;S\ T;] będą dwiema skończonymi A-strunami. Wtedy boksy [;B_S\ B_T;] są rozłączne [;\Leftrightarrow;] żadna ze strun [;S\ T;] nie jest prefiksem (początkowym odcinkiem) drugiej.
Wynika stąd, że dwa S-kuby są albo rozłączne albo jeden z nich jest zawarty w drugim.
Miara całej przestrzeni [;A^{\mathbb{Z}_+};] wynosi dokładnie 1.
cdn. (patrz Cz.4')
Monday, December 27, 2010
Wstęp do Teorii Informacji. Cz.3
Część 1 sugerowała, z pewnym uzasadnieniem, że losowe struny (teksty), złożone z symboli 0 1, każdy występujący na dowolnym miejscu z prawdopodobieństwem 1/2, niezależnie od pozostałych (jak Orzeł i Reszka przy rzutach monetą), nie dają się kompresować; oznacza to, że nie istnieje algorytm, który by wiernie kodował takie struny, zastępując je przez inne struny 0-1, o mniejszej długości oczekiwanej.
Część 2 poświęcona była strunom losowym, złożonych z symboli F S, w których każde wystąpienie symbolu było niezależne od pozostałych, ale tym razem prawdopodobieńtwa wynosiły 1/6 i 5/6. Takie struny (gdy nie są zbyt krótkie) dają się skompresować średnio lepiej niż 2/3 razy niż w przypadku prawdopodobieństw 1/2:1/2. Czyli jeden symbol takiej informacji jest wart mniej niż 2/3 symbolu 0-1 struny losowej o równych prawdopodobieństwach dla 0 i 1.
Poniżej zajmiemy się łatwiejszym zadaniem. Porównamy kanał ternarny, przesyłający bezbłędnie symbole 0 1 2, z bezbłędnym binarnym, przesyłającym symbole 0 1. Takie porównanie może być ważne dla biznesu. Kanał trójkowy jest droższy, ale efektywniejszy. Co opłaca się lepiej, mieć dwa kanały trójkowe, czy trzy dwójkowe? Odpowiedź może zależeć od wielu czynników, ale między innymi od porównania poniżej.
Powiedzmy, że z ternarnego kanału otrzymujemy ciąg niezależnych symboli 0 1 2, z równymi prawdopodobieństwami 1/3. Mamy go przesłać w świat, a raczej informację, używając kanał binarny. Każdy trójkowy bit możemy zastąpić przez dwa bity dwójkowe jak następuje:
(Gdy wyrazy kodu są jednakowej długości, to oczywiście kod się dekoduje, i to łatwo). Widzimy, że trójkowy bit jest wart nie więcej niż dwa dwójkowe (z pewnością mniej, bo nie wykorzystaliśmy 11, ale o tym później).
I na odwrót, gdy otrzymujemy informację w postaci bitów dwójkowych 0 1, a mamy ją dalej przekazać kanałem trójkowym, to każdy symbol binarny 0 1 zastępujemy tym samym 0 lub 1, ale traktowanym jako bit trójkowy. Zatem bit dwójkowy jest nie więcej wart niż jeden bit trójkowy (zobaczymy, że wyraźnie mniej).
Nie chcę urazić Meksykańczyków, ale mnie goła takila nie smakuje. Drugi i dalsze kieliszki piję już jednak z lodem i czym tak jeszcze - wódce nigdy bym tak nie ubliżył (chyba, że w gościach, to trudno, gdakam w Rzymie jak starożytni). Wszystko jedno takila pomaga mi nie przejmować się zbytnio edytorem, pije się chropowato, ale pisze się gładziej. (Dzieci, nie czytać tego. Banach powiedział, że matematyka nie jest dla dzieci.) Co do jakości mojej noty? Cóż, to się nazywa po angielsku trade-off (coś za coś). W moim subiektywnym odczuciu, moja (c)nota tylko zyskuje.
Wykorzystajmy nierówności typu
[;3^k < 2^n;]
oraz
[;3^k > 2^n;]
dla porównania kanału trójkowego z dwójkowym. Na przykład:
Pierwszą nierówność już wykorzystaliśmy. Powiedziała nam, że trójkowy bit jest wart co najwyżej dwa bity dwójkowe. Następna nierówność mówi nam że co najwyżej 5/3, a ostatnia, że 8/5 lub mniej. Ogólnie nierówność [;3^k < 2^n;] mówi nam, że bit trójkowy jest wart co najwyżej [;n/k;] bitu dwójkowego. Rzeczywiście, każdą z [;3^k;] strun trójkowych, długości [;k;] możemy zastąpić przez dwójkową, o długości [;n;], przy czym różne przez różne.
Podobnie nierówności:
mówią nam kolejno, że bit trójkowy jest wart co najmniej jednego dwójkowego; następna nierówność - że co najmniej półtora czyli 3/2 dwójkowego; a ostatnia, że nawet 19/12 lub więcej. Otrzymaliśmy łącznie nierówność:
(19/12)*info(bit2) < info(bit3) < (8/5)*info(bit2)
Można też porównanie prowadzić w drugą stronę, gdy bity dwójkowe tłumaczymy na trójkowe:
(5/8)*info(bit3) < info(bit2) < (12/19)*info(bit3)
Prosta teoria liczb mówi nam, że istnieją coraz większe wykładniki [;k'\ k''\ n'\ n'';] takie, że:
oraz oba ułamki po bokach następujących (oczywiście prawdziwych) nierówności:
[;\frac{k'}{n'} < \log_2(3) < \frac{k''}{n''};]
przybliżają [;\log_2(3);] z dowolną dokładnością. Ta obserwacja daje dobry powód, żeby uważać trójkowy bit informacji wart [;\log_2(3);] dwójkowego bitu informacji. Dalsze twierdzenia pokażą, że to jest głęboko uzasadniona opinia. (Podobnie można uważać, że jeden bit dwójkowy jest wart [;\log_3(2);] bitu trójkowego; ze szkoły wiecie, że
[;\log_3(2) = \frac{1}{\log_2(3)};]
Wszystko dzieje się harmonijnie.)
Chociaż polskie wychowanie burzy się przed tym co jako naukowiec muszę obiektywnie przyznać, wartość kolejnych kieliszków takili (czy jak tam to się spelluje), po pięciu maleje eksponencjalnie (za to smak się po trochu poprawia). Jednak kończę tę notę, jakże niechętnie, z innego powodu. Muszę wkrótce lecieć (takila itp zmiękcza "muszę", ale obowiązek, to obowiązek). Nie chcę się spieszyć z pisaniem przesadnie, przerwać coś w połowie, lub pisać na siłę, i wszystko zapaprać. Zresztą butelka wyschła. Z lodem i itp, jak wiecie, to nic nie jest. 3/4L. Przysięgam, że nie była pełna. Szkoda, że nie była pełna. Żal. Koniec takilowych zwierzeń.
Część 2 poświęcona była strunom losowym, złożonych z symboli F S, w których każde wystąpienie symbolu było niezależne od pozostałych, ale tym razem prawdopodobieńtwa wynosiły 1/6 i 5/6. Takie struny (gdy nie są zbyt krótkie) dają się skompresować średnio lepiej niż 2/3 razy niż w przypadku prawdopodobieństw 1/2:1/2. Czyli jeden symbol takiej informacji jest wart mniej niż 2/3 symbolu 0-1 struny losowej o równych prawdopodobieństwach dla 0 i 1.
Poniżej zajmiemy się łatwiejszym zadaniem. Porównamy kanał ternarny, przesyłający bezbłędnie symbole 0 1 2, z bezbłędnym binarnym, przesyłającym symbole 0 1. Takie porównanie może być ważne dla biznesu. Kanał trójkowy jest droższy, ale efektywniejszy. Co opłaca się lepiej, mieć dwa kanały trójkowe, czy trzy dwójkowe? Odpowiedź może zależeć od wielu czynników, ale między innymi od porównania poniżej.
Powiedzmy, że z ternarnego kanału otrzymujemy ciąg niezależnych symboli 0 1 2, z równymi prawdopodobieństwami 1/3. Mamy go przesłać w świat, a raczej informację, używając kanał binarny. Każdy trójkowy bit możemy zastąpić przez dwa bity dwójkowe jak następuje:
- 0 ➔ 00
- 1 ➔ 01
- 2 ➔ 10
(Gdy wyrazy kodu są jednakowej długości, to oczywiście kod się dekoduje, i to łatwo). Widzimy, że trójkowy bit jest wart nie więcej niż dwa dwójkowe (z pewnością mniej, bo nie wykorzystaliśmy 11, ale o tym później).
I na odwrót, gdy otrzymujemy informację w postaci bitów dwójkowych 0 1, a mamy ją dalej przekazać kanałem trójkowym, to każdy symbol binarny 0 1 zastępujemy tym samym 0 lub 1, ale traktowanym jako bit trójkowy. Zatem bit dwójkowy jest nie więcej wart niż jeden bit trójkowy (zobaczymy, że wyraźnie mniej).
Nie chcę urazić Meksykańczyków, ale mnie goła takila nie smakuje. Drugi i dalsze kieliszki piję już jednak z lodem i czym tak jeszcze - wódce nigdy bym tak nie ubliżył (chyba, że w gościach, to trudno, gdakam w Rzymie jak starożytni). Wszystko jedno takila pomaga mi nie przejmować się zbytnio edytorem, pije się chropowato, ale pisze się gładziej. (Dzieci, nie czytać tego. Banach powiedział, że matematyka nie jest dla dzieci.) Co do jakości mojej noty? Cóż, to się nazywa po angielsku trade-off (coś za coś). W moim subiektywnym odczuciu, moja (c)nota tylko zyskuje.
Wykorzystajmy nierówności typu
[;3^k < 2^n;]
oraz
[;3^k > 2^n;]
dla porównania kanału trójkowego z dwójkowym. Na przykład:
- [;3 < 2^2;]
- [;3^3 < 2^5;]
- [;3^5 < 2^8;]
Pierwszą nierówność już wykorzystaliśmy. Powiedziała nam, że trójkowy bit jest wart co najwyżej dwa bity dwójkowe. Następna nierówność mówi nam że co najwyżej 5/3, a ostatnia, że 8/5 lub mniej. Ogólnie nierówność [;3^k < 2^n;] mówi nam, że bit trójkowy jest wart co najwyżej [;n/k;] bitu dwójkowego. Rzeczywiście, każdą z [;3^k;] strun trójkowych, długości [;k;] możemy zastąpić przez dwójkową, o długości [;n;], przy czym różne przez różne.
Podobnie nierówności:
- [;3 > 2;]
- [;3^2 > 2^3;]
- [;3^{12} > 2^{19};]
mówią nam kolejno, że bit trójkowy jest wart co najmniej jednego dwójkowego; następna nierówność - że co najmniej półtora czyli 3/2 dwójkowego; a ostatnia, że nawet 19/12 lub więcej. Otrzymaliśmy łącznie nierówność:
(19/12)*info(bit2) < info(bit3) < (8/5)*info(bit2)
Można też porównanie prowadzić w drugą stronę, gdy bity dwójkowe tłumaczymy na trójkowe:
(5/8)*info(bit3) < info(bit2) < (12/19)*info(bit3)
Prosta teoria liczb mówi nam, że istnieją coraz większe wykładniki [;k'\ k''\ n'\ n'';] takie, że:
- [;2^{k'} < 3^{n'};]
- [;2^{k''} > 3^{n''};]
oraz oba ułamki po bokach następujących (oczywiście prawdziwych) nierówności:
[;\frac{k'}{n'} < \log_2(3) < \frac{k''}{n''};]
przybliżają [;\log_2(3);] z dowolną dokładnością. Ta obserwacja daje dobry powód, żeby uważać trójkowy bit informacji wart [;\log_2(3);] dwójkowego bitu informacji. Dalsze twierdzenia pokażą, że to jest głęboko uzasadniona opinia. (Podobnie można uważać, że jeden bit dwójkowy jest wart [;\log_3(2);] bitu trójkowego; ze szkoły wiecie, że
[;\log_3(2) = \frac{1}{\log_2(3)};]
Wszystko dzieje się harmonijnie.)
Chociaż polskie wychowanie burzy się przed tym co jako naukowiec muszę obiektywnie przyznać, wartość kolejnych kieliszków takili (czy jak tam to się spelluje), po pięciu maleje eksponencjalnie (za to smak się po trochu poprawia). Jednak kończę tę notę, jakże niechętnie, z innego powodu. Muszę wkrótce lecieć (takila itp zmiękcza "muszę", ale obowiązek, to obowiązek). Nie chcę się spieszyć z pisaniem przesadnie, przerwać coś w połowie, lub pisać na siłę, i wszystko zapaprać. Zresztą butelka wyschła. Z lodem i itp, jak wiecie, to nic nie jest. 3/4L. Przysięgam, że nie była pełna. Szkoda, że nie była pełna. Żal. Koniec takilowych zwierzeń.
Friday, December 24, 2010
Wstęp do Teorii Informacji. Cz.2
Metauwaga: końcowe uwagi są istotną częścią niniejszej noty. Kto temat poznaje z tej noty, powinien przeczytać także uwagi końcowe.
Jak w poprzedniej Części 1, rozpatruję kanał binarny, czyli przyjmujący i przekazujący na zewnątrz sygnały 0 1. Zakładam, że bezbłędnie co kanał otrzyma to przekaże.
Tym razem chcemy przekazać ciąg wyników rzutów kostką, przy czym obchodzi nas tylko, czy wypadło 6. Oznaczając wynik 6 przez "S" (sukces), a pozostałą możliwość (od 1 do 5) przez F, z każdym ciągiem rzutów kostką możemy związać ciąg liter S i F. Jak przekazać te informację, jak ją kodować?
Mógłby ktoś machnąć ręką na litery, by po prostu przekazywać wyniki rzutów, na przykład
2 6 1 1 4 3 4 3 5 6 3 3 ...
By tak dosłownie postąpić, to potrzebny byłby kanał przekazujący bity szóstkowe 1 2 3 4 5 6. Taki kanał jest bardziej złożony od binarnego. Byłaby w takim postępowaniu marnacja, gdyż interesują nas tylko wygrane:
F S F F F F F F F S F F ...
Więc możemy użyć kanału binarnego, wysyłając tyle samo sygnałów, ale prostszych (0 1), gdzie 0 kodowałoby F, oraz 1 kodowałoby S. Wtedy powyższy ciąg rzutów kostki byłby zakodowany w sposób zredukowany, ale adekwatny dla naszego zadania:
0 1 0 0 0 0 0 0 0 1 0 0 ...
Powiedzmy, że za każdym razem wysyłamy 12 milionów wyników rzutów kostki (może chodzi o zachowanie jakiejś siatki krystalicznej, a nie dosłownie o kostkę do Chińczyka). Czy rzeczywiście musimy wysyłać aż tyle sygnałów? W przypadku rzutów monetą podobna procedura była optymalna. Zachodzi jednak istotna różnica. W przypadku monety, szansa zarówno Orła jak i Reszki była równa 1/2. Tym razem szansa wygranej S jest 1/6, a przegranej F aż 5/6. Nie widać jak z tego skorzystać bezpośrednio, gdy mamy przecież za każdym razem możliwe dwa różne wyniki (F lub S) oraz dwa różne sygnały do dyspozycji (0 oraz 1). Postęp uzyskamy kodując nie pojedyncze znaki F i S, lecz na przykład ich trójki, choćby tak:
Dla ilustracji zapiszmy wcześniejszy ciąg FSFFFFFFFSFF..., grupując symbole po trzy:
FSF FFF FFF SFF ...
Ciąg ten nowa metoda zakoduje tak (dodaję odstępy by było lepiej widać kodowanie):
101 0 0 110 ...
czyli zamiast 12 sygnałów przesyłanych wcześniejszą metodą, obecna przesyła tylko 8. Popatrzmy teraz jak jest ogólnie, to znaczy policzmy oczekiwaną długość przesyłki. Uczyńmy to najpierw dla przesyłki XYZ ciągu trzech symboli F S. Prawdopodobieństwo ciągu XYZ (gdzie każde X Y Z oznacza albo S albo F) dane jest wzorem:
[;p(XY\!Z) := \left(\frac{1}{6}\right)^{3-f}\cdot \left(\frac{5}{6}\right)^f = \frac{5^f}{6^3};]
gdzie [;f;] jest liczbą wystąpień F w ciągu XYZ. Grupując ciągi według [;f;] równego 0 1 2 lub 3, otrzymujemy następujące wyrażenie dla długości oczekiwanej kodu ciągu długości 3:
[;1\cdot 5\cdot\frac{1}{6^3} + 3\cdot 5\cdot\frac{5}{6^3} + 3\cdot 3\cdot\frac{5^2}{6^3} + 1\cdot 1\cdot\frac{5^3}{6^3} = \frac{215}{108};]
Każdy ciąg XYZ trzech liter F S możemy zakodować przez średnio niecałe dwie cyfry 0 1. Zatem ciąg 12 milionów liter F S możemy zakodować przez średnio mniej niż 8 milionów znaków 0 1. Jest tak dlatego, że S występuje średnio 5 razy rzadziej niż F. Możemy odtąd uważać, że informacja zawarta w strunie 12 milionów znaków F S jest średnio warta mniej niż zapis ciągu 8 milionów znaków 0 1.
Lepiej oszczędność kodowania liczyć nie w przeliczeniu na 3 lub 12 milionów znaków tekstu źródłowego, lecz dla jednego znaku. Czyli współczynnik oszczędności (kompresji) naszego kodowania (dla tekstów [;A;], których długość [;|A|;] jest podzielna przez 3) wynosi:
[;\frac{\frac{215}{108}}{3} = \frac{215}{324} < 2/3;]
Współczynnik oszczędności pozwala porównywać wydajność kodowania tekstów o różnej długości - im niższy współczynnik, tym wydajniejsze kodowanie. Zrobiliśmy kolejny krok w kierunku zrozumienia informacji w sensie Shannona.
UWAGA 0 Żaden z powyższych 8 wyrazów kodu:
0 100 101 110 11100 11101 11110 11111
nie jest prefiksem (czyli odcinkiem początkowym) żadnego innego wyrazu.
UWAGA 1 Dzięki własności z Uwagi 0, nasze kodowanie jest wierne, czyli daje się jednoznacznie odkodować - gdy teksty źródłowe [;A\ B;] są różne, to ich zakodowane wersje [;K(A)\ K(B);] też są różne:
[;A\ne B \Rightarrow K(A)\ne K(B);]
W przeciwnym razie, gdy [;K(A) = K(B);], nie moglibyśmy zdecydować, czy tekstem źródłowym było [;A;] czy [;B;], lub może jeszcze co innego.
W praktyce wierność to za mało. Potrzebny jest algorytm (i to wydajny), który potrafi obliczyć [;A;], gdy dane jest [;K(A);]. Właśnie taką pożądaną, wygodną sytuację mamy, gdy żaden wyraz kodu nie jest prefiksem innego wyrazu kodu.
UWAGA 2 Występuje pewna drobna nieregularność przy naszym kodowaniu odcinkami złóżonych z trzech znaków F S. Co będzie, gdy długość tekstu żródłowego (czyli liczba występujących w nim znaków F S) nie jest podzielna przez 3? Powiedzmy, że tekst żródłowy miał 12 milionów i jeden znak. Rozwiązanie jest proste: przedłużamy tekst o znak lub dwa znaki F, tak by jego długość stała się podzielna przez 3. W przypadku 12 milionów i jednego znaku, tekst przedłużymy o strunę FF. Współczynnik oszczędności kodowania
[;\frac{|K(A)|}{|A|};]
dalej w mianowniku ma 12000001, a nie 12000003. Więc przeciętna oszczędność kodowania w przypadku przedłużonych tekstów jest nieco gorsza niż dla tekstów, których długość jest okrągłą wielokrotnością 3. Przy długich tekstach nie ma to większego znaczenia (nadwyżka współczynnika oszczędności dąży do zera, gdy długość źródłowego tekstu dąży do nieskończoności). Tak działa oddech nieskończoności. Pozwala zaniedbywać drobne komplikacje.
Jak w poprzedniej Części 1, rozpatruję kanał binarny, czyli przyjmujący i przekazujący na zewnątrz sygnały 0 1. Zakładam, że bezbłędnie co kanał otrzyma to przekaże.
Tym razem chcemy przekazać ciąg wyników rzutów kostką, przy czym obchodzi nas tylko, czy wypadło 6. Oznaczając wynik 6 przez "S" (sukces), a pozostałą możliwość (od 1 do 5) przez F, z każdym ciągiem rzutów kostką możemy związać ciąg liter S i F. Jak przekazać te informację, jak ją kodować?
Mógłby ktoś machnąć ręką na litery, by po prostu przekazywać wyniki rzutów, na przykład
2 6 1 1 4 3 4 3 5 6 3 3 ...
By tak dosłownie postąpić, to potrzebny byłby kanał przekazujący bity szóstkowe 1 2 3 4 5 6. Taki kanał jest bardziej złożony od binarnego. Byłaby w takim postępowaniu marnacja, gdyż interesują nas tylko wygrane:
F S F F F F F F F S F F ...
Więc możemy użyć kanału binarnego, wysyłając tyle samo sygnałów, ale prostszych (0 1), gdzie 0 kodowałoby F, oraz 1 kodowałoby S. Wtedy powyższy ciąg rzutów kostki byłby zakodowany w sposób zredukowany, ale adekwatny dla naszego zadania:
0 1 0 0 0 0 0 0 0 1 0 0 ...
Powiedzmy, że za każdym razem wysyłamy 12 milionów wyników rzutów kostki (może chodzi o zachowanie jakiejś siatki krystalicznej, a nie dosłownie o kostkę do Chińczyka). Czy rzeczywiście musimy wysyłać aż tyle sygnałów? W przypadku rzutów monetą podobna procedura była optymalna. Zachodzi jednak istotna różnica. W przypadku monety, szansa zarówno Orła jak i Reszki była równa 1/2. Tym razem szansa wygranej S jest 1/6, a przegranej F aż 5/6. Nie widać jak z tego skorzystać bezpośrednio, gdy mamy przecież za każdym razem możliwe dwa różne wyniki (F lub S) oraz dwa różne sygnały do dyspozycji (0 oraz 1). Postęp uzyskamy kodując nie pojedyncze znaki F i S, lecz na przykład ich trójki, choćby tak:
- FFF → 0
- FFS → 100
- FSF → 101
- SFF → 110
- FSS → 11100
- SFS → 11101
- SSF → 11110
- SSS → 11111
Dla ilustracji zapiszmy wcześniejszy ciąg FSFFFFFFFSFF..., grupując symbole po trzy:
FSF FFF FFF SFF ...
Ciąg ten nowa metoda zakoduje tak (dodaję odstępy by było lepiej widać kodowanie):
101 0 0 110 ...
czyli zamiast 12 sygnałów przesyłanych wcześniejszą metodą, obecna przesyła tylko 8. Popatrzmy teraz jak jest ogólnie, to znaczy policzmy oczekiwaną długość przesyłki. Uczyńmy to najpierw dla przesyłki XYZ ciągu trzech symboli F S. Prawdopodobieństwo ciągu XYZ (gdzie każde X Y Z oznacza albo S albo F) dane jest wzorem:
[;p(XY\!Z) := \left(\frac{1}{6}\right)^{3-f}\cdot \left(\frac{5}{6}\right)^f = \frac{5^f}{6^3};]
gdzie [;f;] jest liczbą wystąpień F w ciągu XYZ. Grupując ciągi według [;f;] równego 0 1 2 lub 3, otrzymujemy następujące wyrażenie dla długości oczekiwanej kodu ciągu długości 3:
[;1\cdot 5\cdot\frac{1}{6^3} + 3\cdot 5\cdot\frac{5}{6^3} + 3\cdot 3\cdot\frac{5^2}{6^3} + 1\cdot 1\cdot\frac{5^3}{6^3} = \frac{215}{108};]
Każdy ciąg XYZ trzech liter F S możemy zakodować przez średnio niecałe dwie cyfry 0 1. Zatem ciąg 12 milionów liter F S możemy zakodować przez średnio mniej niż 8 milionów znaków 0 1. Jest tak dlatego, że S występuje średnio 5 razy rzadziej niż F. Możemy odtąd uważać, że informacja zawarta w strunie 12 milionów znaków F S jest średnio warta mniej niż zapis ciągu 8 milionów znaków 0 1.
Lepiej oszczędność kodowania liczyć nie w przeliczeniu na 3 lub 12 milionów znaków tekstu źródłowego, lecz dla jednego znaku. Czyli współczynnik oszczędności (kompresji) naszego kodowania (dla tekstów [;A;], których długość [;|A|;] jest podzielna przez 3) wynosi:
[;\frac{\frac{215}{108}}{3} = \frac{215}{324} < 2/3;]
Współczynnik oszczędności pozwala porównywać wydajność kodowania tekstów o różnej długości - im niższy współczynnik, tym wydajniejsze kodowanie. Zrobiliśmy kolejny krok w kierunku zrozumienia informacji w sensie Shannona.
UWAGA 0 Żaden z powyższych 8 wyrazów kodu:
0 100 101 110 11100 11101 11110 11111
nie jest prefiksem (czyli odcinkiem początkowym) żadnego innego wyrazu.
UWAGA 1 Dzięki własności z Uwagi 0, nasze kodowanie jest wierne, czyli daje się jednoznacznie odkodować - gdy teksty źródłowe [;A\ B;] są różne, to ich zakodowane wersje [;K(A)\ K(B);] też są różne:
[;A\ne B \Rightarrow K(A)\ne K(B);]
W przeciwnym razie, gdy [;K(A) = K(B);], nie moglibyśmy zdecydować, czy tekstem źródłowym było [;A;] czy [;B;], lub może jeszcze co innego.
W praktyce wierność to za mało. Potrzebny jest algorytm (i to wydajny), który potrafi obliczyć [;A;], gdy dane jest [;K(A);]. Właśnie taką pożądaną, wygodną sytuację mamy, gdy żaden wyraz kodu nie jest prefiksem innego wyrazu kodu.
UWAGA 2 Występuje pewna drobna nieregularność przy naszym kodowaniu odcinkami złóżonych z trzech znaków F S. Co będzie, gdy długość tekstu żródłowego (czyli liczba występujących w nim znaków F S) nie jest podzielna przez 3? Powiedzmy, że tekst żródłowy miał 12 milionów i jeden znak. Rozwiązanie jest proste: przedłużamy tekst o znak lub dwa znaki F, tak by jego długość stała się podzielna przez 3. W przypadku 12 milionów i jednego znaku, tekst przedłużymy o strunę FF. Współczynnik oszczędności kodowania
[;\frac{|K(A)|}{|A|};]
dalej w mianowniku ma 12000001, a nie 12000003. Więc przeciętna oszczędność kodowania w przypadku przedłużonych tekstów jest nieco gorsza niż dla tekstów, których długość jest okrągłą wielokrotnością 3. Przy długich tekstach nie ma to większego znaczenia (nadwyżka współczynnika oszczędności dąży do zera, gdy długość źródłowego tekstu dąży do nieskończoności). Tak działa oddech nieskończoności. Pozwala zaniedbywać drobne komplikacje.
Thursday, December 23, 2010
Wstęp do Teorii Informacji. Cz.1
Czysta nauka zajmuje się abstrahowaniem i ekstrahowaniem ze skomplikowanej rzeczywistości prostych modeli. Z czasem, gdy prosty model jest dostatecznie zbadany, a istnieje potrzeba lepszego przybliżenia rzeczywistości, tworzy się modele bardziej zaawansowane. Toczy się nieustanna walka mikrochaosu z porządkiem. Ta walka jest częścią chaosu.
Zastosowania nauki są sztuką, a ten który naukę stosuje powinien być artystą, który w zastanej, niejasnej sytuacji potrafii rozpoznać jej strukturę, potrafi oddzielić mało ważne elementy od ważnych, po czym stosuje właściwy dział teorii, powiedzmy właściwy model. Przeciętny wyrobnik "stosuje" teorię, którą powierzchownie narzuca mu sformułowanie problemu lub szef.
Tak czy inaczej, będę rozpatrywał bardzo proste, aż fikcyjne kanały komunikacyjne. Celem będzie wyczucie (zrozumienie) pojęcia informacji.
Pewien serwer na swojej frontowej stronie internetowej wyświetla każdego dnia jeden z dwóch losowo wybranych obrazów, każdy z nich ma 1000x1000 = milion kropek. Gdy kolegę poinformuję, który z dwóch RGB-obrazów dziś jest wyświetlany, to czy przekazuję mu informację wartą miliona kropek (32 milionów bitów)? Nie - przekazałem informację jednobitową, jak odpowiedź na pytanie "0 czy 1?".
Powyższa fikcyjna anegdotka daje przedsmak znaczenia słowa informacja. Informacja istnieje nie absolutnie, lecz w kontekście. Inżynierzy mawiają nawet: co jest szumem dla jednego, jest informacją dla drugiego.
Rozpatrzmy kanał, który na wejściu i wyjściu przyjmuje i przekazuje tylko dwa sygnały: 0 i 1. Niech to będzie kanał dyskretny także w czasie. Działa wiecznie, zawsze, i co jedną stutysięczną sekundy przekazuje sygnal. Gdy sami nic w tej sprawie nie czynimy, to przekazuje szum, przypadkowe 0 lub 1. Na dodatek niech to będzie kanał idealny: gdy otrzymuje 0 to przekazuje na wyjściu 0, gdy 1, to 1, bez przekłamań.
Niech eksperyment lub pomiar fizyczny daje ciąg losowy dwóch możliwości, jakby Orzeł i Reszka. Prawdopodobienstwo każdej wynosi 1/2. Wiadomo, że chcemy przekazać 10 milionów kolejnych wyników, coś jakby
OOORORRORRRRROOROOO...
Zakładamy, że wiadomo, kiedy zaczynamy nadawanie, ale musimy podać metodę na rozpoznanie końca transmisji (kanał przecież zawsze coś nadaje, nie wyłącza się). Metodę przekazu musimy ustalić zawczasu. Pytanie: jaka jest najszybsza metoda kodowania (przekazująca jak najmniej znaków, które potem trzeba i można jednoznacznie odkodować)?
Co to znaczy najszybsza, gdy dla różnych ciągów wynik może być a priori różny, w zależności od ciągu (i od ustalonej metody)? Szybkość jest odwrotnie proporcjonalna do czasu transmisji, czyli do długości mierzonej liczbą nadanych sygnałów.
Jedna z odpowiedzi może w danym przykładzie brzmieć "długością procedury nazywamy średnią liczbę przekazów sygnałów". Czyli jest to suma liczb sygnałów potrzebnych dla jednorazowego przekazania każdego możliwego ciągu [;c;], podzielona przez liczbę tych ciągów:
[;\frac{\sum_c\,L(c)}{2^{{10}^7}};]
gdzie [;L(c);] jest liczbą sygnałów (bitów 0 1), potrzebną dla przesyłki ciągu [;c;]. W kontekście ogólnym teorii, to samo można ująć jako wartość spodziewaną długości transmisji czyli tak: każdy ciąg Orłów i Reszek, długości [;10^7;], ma prawdopodobieństwo wystąpienia równe
[;p(c) := 1/2^{{10}^7};]
Wtedy wartość oczekiwana jest zdefiniowana za pomocą wzoru:
[;\sum_c\,(L(c)\cdot p(c));]
Widzimy, że w danym przypadku obie definicje dają tę samą długość, więc i szybkość, przekazu, bo prawdopodobieństwa [;p(c);] są wszystkie równe.
UWAGA 0 Na ogół, przy innych zadaniach, prawdopodobieństwa [;p(c);] są różne, zależą od [;c;]. Wtedy teoria na ogół stosuje definicję z prawdopodobieństwami, gdyż właśnie ta ma znaczenie praktyczne. Definicja ze średnią arytmetyczną i tak jest jej specjalnym przypadkiem, gdy prawdopodobieństwa są równe.
Najprostsze kodowanie w powyższym przypadku przesyłania informacji o ciągu 10 milionów Orłów i Reszek wygląda tak: z góry zapowiadamy raz na zawsze, że przesyłka będzie miała 10 milionów sygnałów - dzięki temu wiadomo kiedy transmisja skończy się, przy czym każdego Orła kodujemy jako 0, oraz każdą Reszkę jako 1. Żeby było to jasnym, gdyby chodziło o ciąg dugości 6, jak ROOORR, to przekazalibyśmy 100011. Przy wyjściu, adresat (odbiorca) sam już sobie przetłumaczy (zdekoduje) każde 0 na Orła, i każde 1 na Reszkę. Jest to najprostsza procedura. Mądrość powszechna mówi, że jest to najlepsza procedura, że szybszej już nie ma. Nawiedzeni uważają to za oczywiste. Wcale to nie jest oczywiste! Każde sensowne uściślenie tego "twierdzenia" oznacza prawdziwe twierdzenie, i wtedy mądrość powszechna jest podtrzymana, ze ścisłym omówieniem "nasza procedura jest najszybsza w danym sensie. Zauważmy, że nie mówimy o przesłaniu jednego ciągu, lecz o losowym, czyli o przesyłaniu wszystkich.
Długość transmisji liczona jako wartość oczekiwana liczby sygnałów oczywiście wynosi dokładnie 10 milionów, [;10^7;].
Mądrość ludowa o optymalnośći powyższej najprostszej procedury zostałaby podważona, gdyby nie założenie, że a propos nie wiadomo, kiedy transmisja kończy się (kanał działa wiecznie, nie milknie). W przeciwnym wypadku, gdyby kanał milknął, to nie musielibyśmy wysyłać na przykład ostatniego odcinka zer, co w połowie wypadków dałoby zysk co najmniej jednego sygnału. Wartość oczekiwana długości transmisji zmniejszyłaby się co najmniej o połowę sygnału.
Spróbujmy podważyć mądrość ludową "legalnie". Umówmy się z adresatem, że zero 0 na pierwszym miejscu oznacza koniec transmisji, oraz że cały ciąg składa się wtedy wyłącznie z Orłów (zer). Gdy pierwszym wysłanym sygnałem jest 1, to po nim wysyłamy 10 milionów sygnałów po staremu, jakby się właśnie zaczęła transmisja. Może, bądźmy skąpi, gdy mamy przekazać same Orły czyli zera, a Reszkę czyli 1 jedynie na samym końcu, to sobie ten ostatni sygnał darujmy, czyli w sumie znowu wyślemy tylko 10 milionów sygnałów, zamiast 10 milionów + jeden. Jest to prawidłowa procedura, gdyż adresat za każdym razem jest w stanie rozpoznać koniec naszej transmisji.
Policzmy oczekiwaną szybkość tej procedury. Z jednej strony wspaniale zyskaliśmy przy ciągu zerowym, a z drugiej ponieśliśmy niewielką stratę przy wszystkich pozostałych ciągach poza jednym. Jaki jest bilans? Oczekiwana długość transmisji wynosi
[;1\cdot 1\cdot p + (2^L-2)\cdot (L+1)\cdot p + 1\cdot L\cdot p;]
[;=\ (2^L\cdot L + (1 + 2^L - 2\cdot(L+1) + L)\cdot p;]
[;=\ L\ +\ 1\ -\ (L+1)\cdot p\ \ >\ \ L;]
gdzie [;L := 10^7;] jest długością ciągu Orłów i Reszek, oraz
[;p := \frac{1}{2^L} = \frac{1}{2^{{10}^7}};]
jest prawdopodobieństwem jednego ciągu, dowolnego. Widzimy, że średnia długość transmisji wzrosła prawie o jeden sygnał - niewiele, ale jednak.
Powróćmy do niepoprawnej procedury ucinania ogona zer. Poszło o drobiazg :-). Gdybyśmy mogli zaznaczyć jakoś koniec transmisji, to wszystko byłoby w porządku. Wystarczyłoby na koniec dać sygnał 2. Oznaczałoby to jednak inny, bardziej złożony (droższy) kanał, zdolny do przesyłania trójkowych bitów (0 1 2) zamiast dwójkowych (0 1).
W ramach naszego zwykłego kanału binarnego można próbować zakodować koniec transmisji jako specjalny ciąg kilku 0 i 1. Wtedy jednak płacimy karę, bo na koniec przesyłamy ten dodatkowy kod. Co gorsza, w trakcje transmisji musimy unikać przesłania kodu końca transmisji przedwcześnie, co powoduje dodatkowe wydłużanie kodu. Tymczasem zysk z ucinania ogona, gdy nie martwimy się o zaznaczenie końca transmisji, wynosi dokładnie jeden sygnał minus [;1/2^L;] (przeciętnie). Niełatwo zmieścić kod końca transmisji w ramach jednego sygnału minus [;1/2^L;], a nawet jest to niemożliwe - zresztą próbujcie, bo to może być dobre ćwiczenie.
Zastosowania nauki są sztuką, a ten który naukę stosuje powinien być artystą, który w zastanej, niejasnej sytuacji potrafii rozpoznać jej strukturę, potrafi oddzielić mało ważne elementy od ważnych, po czym stosuje właściwy dział teorii, powiedzmy właściwy model. Przeciętny wyrobnik "stosuje" teorię, którą powierzchownie narzuca mu sformułowanie problemu lub szef.
Tak czy inaczej, będę rozpatrywał bardzo proste, aż fikcyjne kanały komunikacyjne. Celem będzie wyczucie (zrozumienie) pojęcia informacji.
Pewien serwer na swojej frontowej stronie internetowej wyświetla każdego dnia jeden z dwóch losowo wybranych obrazów, każdy z nich ma 1000x1000 = milion kropek. Gdy kolegę poinformuję, który z dwóch RGB-obrazów dziś jest wyświetlany, to czy przekazuję mu informację wartą miliona kropek (32 milionów bitów)? Nie - przekazałem informację jednobitową, jak odpowiedź na pytanie "0 czy 1?".
Powyższa fikcyjna anegdotka daje przedsmak znaczenia słowa informacja. Informacja istnieje nie absolutnie, lecz w kontekście. Inżynierzy mawiają nawet: co jest szumem dla jednego, jest informacją dla drugiego.
Rozpatrzmy kanał, który na wejściu i wyjściu przyjmuje i przekazuje tylko dwa sygnały: 0 i 1. Niech to będzie kanał dyskretny także w czasie. Działa wiecznie, zawsze, i co jedną stutysięczną sekundy przekazuje sygnal. Gdy sami nic w tej sprawie nie czynimy, to przekazuje szum, przypadkowe 0 lub 1. Na dodatek niech to będzie kanał idealny: gdy otrzymuje 0 to przekazuje na wyjściu 0, gdy 1, to 1, bez przekłamań.
Niech eksperyment lub pomiar fizyczny daje ciąg losowy dwóch możliwości, jakby Orzeł i Reszka. Prawdopodobienstwo każdej wynosi 1/2. Wiadomo, że chcemy przekazać 10 milionów kolejnych wyników, coś jakby
OOORORRORRRRROOROOO...
Zakładamy, że wiadomo, kiedy zaczynamy nadawanie, ale musimy podać metodę na rozpoznanie końca transmisji (kanał przecież zawsze coś nadaje, nie wyłącza się). Metodę przekazu musimy ustalić zawczasu. Pytanie: jaka jest najszybsza metoda kodowania (przekazująca jak najmniej znaków, które potem trzeba i można jednoznacznie odkodować)?
Co to znaczy najszybsza, gdy dla różnych ciągów wynik może być a priori różny, w zależności od ciągu (i od ustalonej metody)? Szybkość jest odwrotnie proporcjonalna do czasu transmisji, czyli do długości mierzonej liczbą nadanych sygnałów.
Jedna z odpowiedzi może w danym przykładzie brzmieć "długością procedury nazywamy średnią liczbę przekazów sygnałów". Czyli jest to suma liczb sygnałów potrzebnych dla jednorazowego przekazania każdego możliwego ciągu [;c;], podzielona przez liczbę tych ciągów:
[;\frac{\sum_c\,L(c)}{2^{{10}^7}};]
gdzie [;L(c);] jest liczbą sygnałów (bitów 0 1), potrzebną dla przesyłki ciągu [;c;]. W kontekście ogólnym teorii, to samo można ująć jako wartość spodziewaną długości transmisji czyli tak: każdy ciąg Orłów i Reszek, długości [;10^7;], ma prawdopodobieństwo wystąpienia równe
[;p(c) := 1/2^{{10}^7};]
Wtedy wartość oczekiwana jest zdefiniowana za pomocą wzoru:
[;\sum_c\,(L(c)\cdot p(c));]
Widzimy, że w danym przypadku obie definicje dają tę samą długość, więc i szybkość, przekazu, bo prawdopodobieństwa [;p(c);] są wszystkie równe.
UWAGA 0 Na ogół, przy innych zadaniach, prawdopodobieństwa [;p(c);] są różne, zależą od [;c;]. Wtedy teoria na ogół stosuje definicję z prawdopodobieństwami, gdyż właśnie ta ma znaczenie praktyczne. Definicja ze średnią arytmetyczną i tak jest jej specjalnym przypadkiem, gdy prawdopodobieństwa są równe.
Najprostsze kodowanie w powyższym przypadku przesyłania informacji o ciągu 10 milionów Orłów i Reszek wygląda tak: z góry zapowiadamy raz na zawsze, że przesyłka będzie miała 10 milionów sygnałów - dzięki temu wiadomo kiedy transmisja skończy się, przy czym każdego Orła kodujemy jako 0, oraz każdą Reszkę jako 1. Żeby było to jasnym, gdyby chodziło o ciąg dugości 6, jak ROOORR, to przekazalibyśmy 100011. Przy wyjściu, adresat (odbiorca) sam już sobie przetłumaczy (zdekoduje) każde 0 na Orła, i każde 1 na Reszkę. Jest to najprostsza procedura. Mądrość powszechna mówi, że jest to najlepsza procedura, że szybszej już nie ma. Nawiedzeni uważają to za oczywiste. Wcale to nie jest oczywiste! Każde sensowne uściślenie tego "twierdzenia" oznacza prawdziwe twierdzenie, i wtedy mądrość powszechna jest podtrzymana, ze ścisłym omówieniem "nasza procedura jest najszybsza w danym sensie. Zauważmy, że nie mówimy o przesłaniu jednego ciągu, lecz o losowym, czyli o przesyłaniu wszystkich.
Długość transmisji liczona jako wartość oczekiwana liczby sygnałów oczywiście wynosi dokładnie 10 milionów, [;10^7;].
Mądrość ludowa o optymalnośći powyższej najprostszej procedury zostałaby podważona, gdyby nie założenie, że a propos nie wiadomo, kiedy transmisja kończy się (kanał działa wiecznie, nie milknie). W przeciwnym wypadku, gdyby kanał milknął, to nie musielibyśmy wysyłać na przykład ostatniego odcinka zer, co w połowie wypadków dałoby zysk co najmniej jednego sygnału. Wartość oczekiwana długości transmisji zmniejszyłaby się co najmniej o połowę sygnału.
Spróbujmy podważyć mądrość ludową "legalnie". Umówmy się z adresatem, że zero 0 na pierwszym miejscu oznacza koniec transmisji, oraz że cały ciąg składa się wtedy wyłącznie z Orłów (zer). Gdy pierwszym wysłanym sygnałem jest 1, to po nim wysyłamy 10 milionów sygnałów po staremu, jakby się właśnie zaczęła transmisja. Może, bądźmy skąpi, gdy mamy przekazać same Orły czyli zera, a Reszkę czyli 1 jedynie na samym końcu, to sobie ten ostatni sygnał darujmy, czyli w sumie znowu wyślemy tylko 10 milionów sygnałów, zamiast 10 milionów + jeden. Jest to prawidłowa procedura, gdyż adresat za każdym razem jest w stanie rozpoznać koniec naszej transmisji.
Policzmy oczekiwaną szybkość tej procedury. Z jednej strony wspaniale zyskaliśmy przy ciągu zerowym, a z drugiej ponieśliśmy niewielką stratę przy wszystkich pozostałych ciągach poza jednym. Jaki jest bilans? Oczekiwana długość transmisji wynosi
[;1\cdot 1\cdot p + (2^L-2)\cdot (L+1)\cdot p + 1\cdot L\cdot p;]
[;=\ (2^L\cdot L + (1 + 2^L - 2\cdot(L+1) + L)\cdot p;]
[;=\ L\ +\ 1\ -\ (L+1)\cdot p\ \ >\ \ L;]
gdzie [;L := 10^7;] jest długością ciągu Orłów i Reszek, oraz
[;p := \frac{1}{2^L} = \frac{1}{2^{{10}^7}};]
jest prawdopodobieństwem jednego ciągu, dowolnego. Widzimy, że średnia długość transmisji wzrosła prawie o jeden sygnał - niewiele, ale jednak.
Powróćmy do niepoprawnej procedury ucinania ogona zer. Poszło o drobiazg :-). Gdybyśmy mogli zaznaczyć jakoś koniec transmisji, to wszystko byłoby w porządku. Wystarczyłoby na koniec dać sygnał 2. Oznaczałoby to jednak inny, bardziej złożony (droższy) kanał, zdolny do przesyłania trójkowych bitów (0 1 2) zamiast dwójkowych (0 1).
W ramach naszego zwykłego kanału binarnego można próbować zakodować koniec transmisji jako specjalny ciąg kilku 0 i 1. Wtedy jednak płacimy karę, bo na koniec przesyłamy ten dodatkowy kod. Co gorsza, w trakcje transmisji musimy unikać przesłania kodu końca transmisji przedwcześnie, co powoduje dodatkowe wydłużanie kodu. Tymczasem zysk z ucinania ogona, gdy nie martwimy się o zaznaczenie końca transmisji, wynosi dokładnie jeden sygnał minus [;1/2^L;] (przeciętnie). Niełatwo zmieścić kod końca transmisji w ramach jednego sygnału minus [;1/2^L;], a nawet jest to niemożliwe - zresztą próbujcie, bo to może być dobre ćwiczenie.
Wednesday, December 22, 2010
Wstęp do Teorii Informacji. Cz.0
Wiadomo, że człowiek kulturalny, to taki, który ma solidne wykształcenie humanistyczne. Mało kto uważa, że także matematyczne. Od wynalezienia szpiegostwa, radio, telegrafu, telefonu, tv, lingwistyki, komputerów, plików komputerowych, dysków komputerowych, komunikacji satelitarnej i sond kosmicznych, internetu, baz danych... chyba wypada osobie kulturalnej także wiedzieć czym jest bit informacji, entropia, czym są różne kodowania. Krótko mówiąc, wypada wiedzieć coś niecoś z zakresu Teorii Informacji - uprzedzam, że nie chodzi wyłącznie o służby specjalne, donosicielstwo i lustrację.
Teoria Informacji jest częścią inżynierii i informatyki, ale dla mnie głównie matematyki, po czym stosuje się ją do innych dziedzin. Występuje też w fizyce.
Teoria Informacji jest nowoczesna. Stworzył ją i rozwinął jeden genialny człowiek - Claude Shannon. Sam jeden! - co jest niezwykłe i unikatowe. Wśród pierwszych, którzy docenili Shannona, i zastosowali jego idee twórczo, był wielki A.N.Kołmogorow. Po nich włączyły się setki i tysiące.
Teoria Informacji skupia się na badaniu kanału informacyjnego, a ściślej mówiąc na przygotowaniu informacji przed wejściem do kanału, i na interpretacji tego co z kanału wychodzi. Natomiast inżynierzy i fizycy mogą też zajmować się samym kanałem, badaniem go lub wymyślaniem lepszego. Matematyk zakłada, że własności kanału będą mu podane na talerzu. Co prawda matematyk też może rozwijać teorię badania kanału. Byłyby to badania o naturze statystycznej.
Kanał otrzymuje od świata pewnego rodzaju sygnały u swojego wejścia, przy czym może otrzymywać je z pewną prędkością, i nie szybciej. Podobnie, przekazuje sygnały światu u swojego wyjścia, znowu z pewną ograniczoną szybkością. Na ogół zakłada się, że rodzaj sygnałów i szybkość jest ta sama na obu końcach. Dodatkowo kanał może charakteryzować swoisty szum, który powoduje stratę lub deformację części sygnałów. Celem Teorii Informacji jest uzyskanie takich metod kodowania informacji przed wejściem do kanału, i dekodowania sygnałów po opuszczeniu kanału, by w miarę szybko, prosto i pełnie przekaz informacji był jak najwierniejszy - chcemy odzyskać informację, która została nadana u wejścia. Stąd potrzeba kodów, które wykrywają i poprawiają błędy. Wymagają one kodowania i dekodowania.
Ponieważ używanie kanału może być drogie, to często staramy się informację skondensować, by nasza przesyłka wykorzystywała jak najmniejszą część zdolności kanału (by inni mogli z niego korzystać jednocześnie), i by trwała jak najkrócej.
Ponieważ źli ludzie podsłuchują dobrych, to istnieje potrzeba enkrypcji i dekrypcji, czyli sekretnego kodowania i dekodowania - ta część Teorii Informacji nazywa się kryptografią. Połowę tej teorii, czyli sztukę niezrozumiałego wyrażania się, opanowali politycy.
Trzy cele Teorii Informacji: niezawodność, szybkość (w tym skrótowość), i sekretność przesyłki stwarzają napięcie, gdyż przeczą sobie nawzajem. Potrzeba specjalisty i naukowca, żeby je godził możliwie harmonijnie. Zresztą każdy z tych trzech kierunków teorii zasługuje także i przede wszystkim na odrębne badania, i tak się czyni. Mamy więc trzy powiązane teorie:
przy czym za każdym razem występuje kodowanie i dekodowanie.
Teoria Informacji jest częścią inżynierii i informatyki, ale dla mnie głównie matematyki, po czym stosuje się ją do innych dziedzin. Występuje też w fizyce.
Teoria Informacji jest nowoczesna. Stworzył ją i rozwinął jeden genialny człowiek - Claude Shannon. Sam jeden! - co jest niezwykłe i unikatowe. Wśród pierwszych, którzy docenili Shannona, i zastosowali jego idee twórczo, był wielki A.N.Kołmogorow. Po nich włączyły się setki i tysiące.
Teoria Informacji skupia się na badaniu kanału informacyjnego, a ściślej mówiąc na przygotowaniu informacji przed wejściem do kanału, i na interpretacji tego co z kanału wychodzi. Natomiast inżynierzy i fizycy mogą też zajmować się samym kanałem, badaniem go lub wymyślaniem lepszego. Matematyk zakłada, że własności kanału będą mu podane na talerzu. Co prawda matematyk też może rozwijać teorię badania kanału. Byłyby to badania o naturze statystycznej.
Kanał otrzymuje od świata pewnego rodzaju sygnały u swojego wejścia, przy czym może otrzymywać je z pewną prędkością, i nie szybciej. Podobnie, przekazuje sygnały światu u swojego wyjścia, znowu z pewną ograniczoną szybkością. Na ogół zakłada się, że rodzaj sygnałów i szybkość jest ta sama na obu końcach. Dodatkowo kanał może charakteryzować swoisty szum, który powoduje stratę lub deformację części sygnałów. Celem Teorii Informacji jest uzyskanie takich metod kodowania informacji przed wejściem do kanału, i dekodowania sygnałów po opuszczeniu kanału, by w miarę szybko, prosto i pełnie przekaz informacji był jak najwierniejszy - chcemy odzyskać informację, która została nadana u wejścia. Stąd potrzeba kodów, które wykrywają i poprawiają błędy. Wymagają one kodowania i dekodowania.
Ponieważ używanie kanału może być drogie, to często staramy się informację skondensować, by nasza przesyłka wykorzystywała jak najmniejszą część zdolności kanału (by inni mogli z niego korzystać jednocześnie), i by trwała jak najkrócej.
Ponieważ źli ludzie podsłuchują dobrych, to istnieje potrzeba enkrypcji i dekrypcji, czyli sekretnego kodowania i dekodowania - ta część Teorii Informacji nazywa się kryptografią. Połowę tej teorii, czyli sztukę niezrozumiałego wyrażania się, opanowali politycy.
Trzy cele Teorii Informacji: niezawodność, szybkość (w tym skrótowość), i sekretność przesyłki stwarzają napięcie, gdyż przeczą sobie nawzajem. Potrzeba specjalisty i naukowca, żeby je godził możliwie harmonijnie. Zresztą każdy z tych trzech kierunków teorii zasługuje także i przede wszystkim na odrębne badania, i tak się czyni. Mamy więc trzy powiązane teorie:
- kody wykrywające i poprawiające błędy;
- kompresja danych;
- enkrypcja
przy czym za każdym razem występuje kodowanie i dekodowanie.
Monday, December 20, 2010
prawa poezji sikają na kiepskie wiersze
poetry laws piss on poor poems
(Long live alliterations! :-)
do laws of physics constrain physics?
without laws there would be no physics and no physicists
(the same holds for poetry and poets)
wh,
2010-12-19
Przetłumaczę:
czy prawa fizyki ograniczają fizykę?
bez praw fizyki nie byłoby ani fizyki ani fizyków
(podobnie z poezją i poetami)
wh,
2010-12-19
(Long live alliterations! :-)
do laws of physics constrain physics?
without laws there would be no physics and no physicists
(the same holds for poetry and poets)
wh,
2010-12-19
Przetłumaczę:
czy prawa fizyki ograniczają fizykę?
bez praw fizyki nie byłoby ani fizyki ani fizyków
(podobnie z poezją i poetami)
wh,
2010-12-19
Saturday, November 20, 2010
Nieskończoność w topologii ogólnej
Przestrzenie topologiczne i T1-przestrzenie
Rodzinę [;\mathbf F;] podzbiorów zbioru [;X;] nazywam fermologią, gdy spełnia następujące warunki:
- Jeżeli [;\emptyset \ne \mathbf{H}\subseteq \mathbf{F};], to [;\cap \mathbf{H}\in\mathbf{F};].
- [;\forall_{\,A\,B\,\in\,\mathbf{F}}\ A\cup B\,\in\,\mathbf{F};]
- [;\emptyset\ X\,\in \mathbf{F};]
Parę [;(X\ \mathbf{F});], gdzie [;\mathbf{F};] jest fermologią w [;X;], nazywamy przestrzenią topologiczną. Zbiory należące do [;\mathbf{F};] nazywamy domkniętymi. Jeżeli w przestrzeni topologicznej [;(X\ \mathbf{F});] każdy jednoelementowy podzbiór zbioru [;X;] jest domknięty to taką przestrzeń nazywamy T1-przestrzenią, a jej fermologię T1-fermologią.
Dowolną przestrzeń topologiczną [;(X\ \mathbf{F});] nazywamy dyskretną, a jej fermologię też dyskretną, gdy [;\mathbf{F};] jest rodziną wszystkich podzbiorów zbioru [;X;]. Jest tak [;\Leftarrow:\Rightarrow\quad\forall_{\,x\in X}\, X\backslash\{x\}\in\mathbf{F};]. Gdy przestrzeń lub fermologia nie jest dyskretna, to mówimy, że jest niedyskretna.
TWIERDZENIE 0 Zbiór X jest nieskończony [;\Leftarrow:\Rightarrow;] istnieje w X T1-fermologia niedyskretna.
Zauważmy jeszcze, że przecięcie wszystkich T1-fermologii w zbiorze X jest T1-fermologią w X. Taka fermologia nazywana jest najsłabszą T1-fermologią w X. Jeżeli w X istnieje niedyskretna T1-fermologia, to będzie nią także ta najsłabsza.
Zbiory gęste
Zbiór [;A\subseteq X;] nazywamy gęstym w przestrzeni topologicznej [;\Leftarrow:\Rightarrow\quad X;] jest jedynym zbiorem domkniętym, zawierającym [;A;].
TWIERDZENIE 1 Zbiór X jest nieskończony [;\Leftarrow:\Rightarrow;] istnieje w X taka T1-fermologia, że w powstalej przestrzeni topologicznej istnieje podzbiór gęsty, różny od X.
Powyższe twierdzenie brzmi różnie od poprzedniego, ale gdy mu się przyjrzeć, to różnicy istotnej nie ma. Chodzi o to, że w zakresie T1-fermologii, niedyskretne pokrywają się z tym, które dopuszczają podzbiór gęsty, różny od całego zbioru X.
Przestrzenie spójne
Przestrzeń topologiczną [;(X\ \mathbf{F});] nazywamy spójną [;\Leftarrow:\Rightarrow;] dopełnienie [;X\backslash A;] dowolnego niepustego zbioru domkniętego [;A;], różnego od [;X;], nie jest domknięte.TWIERDZENIE 2 Zbiór [;X;] jest nieskończony [;\Leftarrow:\Rightarrow\quad X;] ma co najmniej dwa różne elementy oraz istnieje w [;X;] taka T1-fermologia, że powstała przestrzeń topologiczna jest spójna.
Tym razem dla nieskończonego [;X;] rodzina T1-fermologii dających przestrzeń spójną różni się od rodziny wszystkich niedyskretnych (jest mniejsza). Wciąż jednak wystarczy sprawdzić T1-fermologię najsłabszą.
Uwaga końcowa
Powyższe wyniki są rozbrajająco proste i naiwne. Celem tej notki było przede wszystkim wzbudzenie zainteresowania topologia, i dania powodu przynajmniej do zapamiętania pojęć jak zbiory domknięte, gęste, oraz spójność. Ta ostatnia ma już charakter geometryczny.Wednesday, November 17, 2010
Nieskończoność w teorii mnogości
Wstęp
Definicje nieskończoności są w teorii mnogości przede wszystkim dwóch rodzajów: albo wprowadzają uporządkowanie, względem którego nie ma elementu naj (największego lub najmniejszego), albo w duchu Cantora mówią nam, że całość może być równoważna swojej części.
Pojawia się też nieskończoność świeżo w ogólnej topologii, ale to już jednak jest materiał na następny post.
NOTACJA i TERMINOLOGIA
Przyda nam się niewielki słowniczek pojęć:
- Iniekcja - jest to funkcja [;f : X \rightarrow Y;], która każde dwa różne argumenty odwzorowuje w różne wartości, czyli spełnia warunek:
[;*\quad\quad\forall_{\,x'\,x''\in X}\ \left(f(x')=f(x'')\ \Rightarrow\ x'=x''\right);]
(można skracać przez [;f;]). - Surjekcja - jest to funkcja [;f : X \rightarrow Y;], która odwzorowuje [;X;] na całe [;Y;], czyli spełnia warunek:
[;*\quad\quad\forall_{\,y\in Y}\,\exists_{\,x\in X}\ f(x) = y;] - Bijekcja - jest to funkcja [;f : X \rightarrow Y;], która jednocześnie jest iniekcją i surjekcją.
- Relacja - w niniejszej nocie relacją w zbiorze [;X;] nazywamy dowolny podzbiór [;M\subseteq X^2;] kwadratu kartezjańskiego [;X^2 := X\times X;]. Dla relacji często zamiast
[;*\quad\quad (x\ y)\ \in\ M;]
piszemy
[;*\quad\quad x\,M\,y;] - Element prawy - Elementem prawym relacji [;M;] w [;X;] nazywamy każdy element [;x\in X;], dla którego nie istnieje [;y\in X;], spełniające:
[;*\quad\quad x\,M\,y;] - Element lewy - Elementem prawym relacji [;M;] w [;X;] nazywamy każdy element [;x\in X;], dla którego nie istnieje [;y\in X;], spełniające:
[;*\quad\quad y\,M\,x;] - Relacja przechodnia - relację [;M;] w [;X;] nazywamy przechodnią [;\Leftarrow:\Rightarrow;]
[;*\quad\quad \forall_{x\,y\,z\,\in X}\ \left(\left(x\,M\,y\quad\&\quad y\,M\,z\right)\quad\Rightarrow \quad x\,M\,z\right);]
W przypadku relacji przechodniej elementy prawe nazywamy często maksymalnymi, a elementy lewe - minimalnymi. Relacje przechodnie oznaczamy często symbolami typu [;<;] lub [;\le;]. W przypadku symboli typu odwróconego, jak [;>;], umawiamy się na opak, że prawe elementy są minimalne, a lewe - maksymalne (zwłaszcza, gdy relacja [;>;] jest odwrotnością relacji [;<;]). - Relacja antysymetryczna - relację [;M;] w [;X;] nazywamy antysymetryczną [;\Leftarrow:\Rightarrow;] nie istnieje żadna para elementów [;x\,y\in M;], spełniająca oba warunki: [;x\,M\,y\quad\&\quad y\,M\,x;].
- Porządek ostry - relację [;M;] w [;X;] nazywamy (częściowym) porządkiem ostrym [;\Leftarrow:\Rightarrow;] [;M;] jest przechodnie i antysymetryczne.
Mnogościowa charakteryzacja nieskończoności
Następujące własności zbioru X są równoważne. Zbiór X, z definicji, jest nieskończony [;\Leftarrow:\Rightarrow;] X posiada dowolną (a więc wszystkie) z następujących równoważnych własności:
- Istnieje niepusta rodzina S podzbiorów zbioru X, taka że dla każdego zbioru A, należącego do S, istnieje zbiór B, należący do S\{A}, taki że B zawiera A - takie S nie ma elementu maksymalnego.
- Istnieje niepusta rodzina S podzbiorów zbioru X, taka że dla każdego zbioru A. należącego do S, istnieje zbiór B, należący do S\{A}, taki że A zawiera B - takie S nie ma elementu minimalnego.
- Istnieje iniekcja [;f : X\rightarrow X;], które nie jest surjekcją.
- Istnieje surjekcja [;f : X \rightarrow Y;], która nie jest iniekcją.
- Istnieje niepusty porządek ostry [;M;] w [;X;], nieposiadająca elementu prawego (tj. maksymalnego).
- Istnieje niepusty porządek ostry [;M;] w [;X;], nieposiadający elementu lewego (tj. minimalnego).
- Istnieje niepusta rodzina S niepustych podzbiorów zbioru X, taka że z jednej strony jej przecięcie jest puste, a z drugiej przecięcie dowolnych dwóch jej elementów zawiera inny element tejże rodziny S.
- Istnieje rodzina S podzbiorów zbioru X, różnych od X, i taka że z jednej strony jej unia jest całym X, a z drugiej unia dowolnych dwóch jej elementów jest zawarta w innym elemencie tejże rodziny S.
Warunki dotyczące rodziny podzbiorów S są pokrewne warunkom dotyczących ostrego porządku. Gdy się chwilę zastanowić, to także warunek dotyczący iniekcji jest im pokrewny. Warunek dotyczący surjekcji jest równoważny warunkowi dotyczącemu iniekcji ze względu na aksjomat wyboru.
We własnościach, w których występuje istnienie ostrego porządku, można było żądać, żeby taka relacja istniała w podzbiorze. Wtedy podzbiór byłby nieskończony, a więc także cały zbiór (takie oczywiste "a więc" należy w matematyce uzasadniać). Równoważność takich wariacji z podanymi warunkami wymaga umiejętności przedłużania porządku z podzbioru na całość, co czyni się z pomocą aksjomatu wyboru (lub przynajmmniej pewnej jego osłabionej wersji).
Analogi warunków w terminach iniekcji i surjekcji można z łatwością sformułować w dowolnej kategorii - wystarczy te terminy zastąpić przez monomorfizm i epimorfizm. Daje to atrakcyjne podejście do nieskończoności w dowolnych kategoriach. Podobnie można postąpić w przypadku rodziny podzbiorów S - w kategoriach ogólnych można mówić o rodinie podobiektów. Trudniej o przeniesienie na kategorie ogólne relacji ostrego porządku.
Nieskończoność w logice matematycznej
Nieskończoność (potencjalna) metateorii jest w swojej naturze czymś fizycznym. Jest to część świata materialnego, przynajmniej według naszej interpretacji.
W samej logice, nieskończoności większość autorów nie wprowadza, dopiero czyni to przy okazji matematyki: arytmetyki lub - najczęściej - teorii mnogości. Ale na przykład logik Stephen Cole Kleene wolał z miejsca zanurzyć teorię liczb naturalnych, a więc także nieskończoność, w logice. Czyni się to następująco:
Predykat Nat(x) oznacza, że x jest liczbą naturalna (co może być prawdą lub fałszem, w zależności od tego co za x podstawimy). Wprowadza się do teorii stałą 1 oraz konstrukcję syntaktyczną Nxt(x) - to nie jest predykat, lecz w wyniku aksjomatów to będzie funkcja następnika x+1 liczby naturalnej x. Następnie do logiki wklucza się kilka dodatkowych, specjalnych aksjomatów, w tym aksjomaty Peano (wyrażenie =' oznacza "nierówne"):
(i) Nat(1)
(ii) Nat(x) to Nat(Nxt(x))
(iii) x=y to Nxt(x) = Nxt(y)
(iv) Nxt(x) = Nxt(y) to x=y
(v) Nat(x) to Nxt(x) =' 1
(vi) x =' 1 to EXISTS y ( Nxt(y) = x)
(VII) Dla każdego predykatu T(x) zachodzi następujący aksjomat viiT (zapisany dla przejrzystości w trzech linijkach):
(T(1) AND FORALL x ((Nat(x) AND T(x)) to T(Nxt(x))))
to
FORALL x (T(x))
Tak więc mamy nieskończenie wiele aksjomatów viiT , które łącznie dają schemat aksjomatyczny zwany aksjomatem indukcji matematycznej. Zdaje się, że chociaż sama nieskończoność niby nie wymaga nieskończonego schematu aksjomatów, to wymaga go teoria, w której ta nieskończoność żyje i ma sens. Tak jest w przypadku teorii liczb naturalnych, i tak jest także z teorią mnogości. Bez nieskończonych schematów teorie, mimo dopuszczenia nieskończoności, byłyby dosyć płytkie i ograniczone (pustawe).
Znaczenie powyższych aksjomatów jest następujące: operacja Nxt pozwala nam w nieskończoność iść do przodu. Aksjomat (v) mówi, że nie kręcimy się w kółko (co mogłoby sytuację uczynić skończoną). Indukcja (VII) mówi, że zbiór wszystkich liczb naturalnych tworzy (spójną jakby) ścieżkę, zaczynająca się od 1, krok po kroku zawierającą wszystkie liczby naturalne:
1 Nxt(1) Nxt(Nxt(1)) Nxt(Nxt(Nxt(1))) ...
Innych liczb naturalnych, według aksjomatu indukcji, nie ma. Czyli, dla uzyskania nieskończoności, aksjomatu indukcji nie potrzebujemy. Potrzebujemy go dla rozwinięcia teorii głębokiej.
Co prawda sytuacja jest subtelna. W sensie metateoretycznym możemy twierdzić, że uzyskaliśmy konstrukcję nieskonczona. Jest to oczywiste. Ale bez indukcji nie możemy dowieść, że tak naprawdę jest, bowiem nie możemy pokazać, że z czasem, poczynająć od 1, nie zaczneimy się kręcić w kółko - należy dowieść, że x jest różne na przykład od Nxt(Nxt(Nxt(x))). Jest to "materialnie" oczywiste dla nieskończonego podzbioru "liczb naturalnych" (bezindukcyjnych), ale nie mamy tego jak pokazać bez indukcji matematycznej (lub podobnego schematu), bo nawet Nxt(x) = x dla pewnych x może zachodzić, gdy indukcji się nie założy.
UWAGA: W metamatematyce, nawet bez indukcji matematycznej, i tak stosuje się to, co Profesor Andrzej Mostowski nazywał przesłanką indukcyjną. Chodzi o to, że predykaty i inne wyrażenia buduje się rekursyjnie (indukcyjnie). Kończy się konstrukcje takich wyrażeń aksjomatem: innych wyrażeń naszego (właśnie definiowanego) typu, poza wyżej podanymi, nie ma. To właśnie pozwala na dowody indukcukcyjne, tak powszechne także w informatyce.
W samej logice, nieskończoności większość autorów nie wprowadza, dopiero czyni to przy okazji matematyki: arytmetyki lub - najczęściej - teorii mnogości. Ale na przykład logik Stephen Cole Kleene wolał z miejsca zanurzyć teorię liczb naturalnych, a więc także nieskończoność, w logice. Czyni się to następująco:
Predykat Nat(x) oznacza, że x jest liczbą naturalna (co może być prawdą lub fałszem, w zależności od tego co za x podstawimy). Wprowadza się do teorii stałą 1 oraz konstrukcję syntaktyczną Nxt(x) - to nie jest predykat, lecz w wyniku aksjomatów to będzie funkcja następnika x+1 liczby naturalnej x. Następnie do logiki wklucza się kilka dodatkowych, specjalnych aksjomatów, w tym aksjomaty Peano (wyrażenie =' oznacza "nierówne"):
(i) Nat(1)
(ii) Nat(x) to Nat(Nxt(x))
(iii) x=y to Nxt(x) = Nxt(y)
(iv) Nxt(x) = Nxt(y) to x=y
(v) Nat(x) to Nxt(x) =' 1
(vi) x =' 1 to EXISTS y ( Nxt(y) = x)
(VII) Dla każdego predykatu T(x) zachodzi następujący aksjomat viiT (zapisany dla przejrzystości w trzech linijkach):
(T(1) AND FORALL x ((Nat(x) AND T(x)) to T(Nxt(x))))
to
FORALL x (T(x))
Tak więc mamy nieskończenie wiele aksjomatów viiT , które łącznie dają schemat aksjomatyczny zwany aksjomatem indukcji matematycznej. Zdaje się, że chociaż sama nieskończoność niby nie wymaga nieskończonego schematu aksjomatów, to wymaga go teoria, w której ta nieskończoność żyje i ma sens. Tak jest w przypadku teorii liczb naturalnych, i tak jest także z teorią mnogości. Bez nieskończonych schematów teorie, mimo dopuszczenia nieskończoności, byłyby dosyć płytkie i ograniczone (pustawe).
Znaczenie powyższych aksjomatów jest następujące: operacja Nxt pozwala nam w nieskończoność iść do przodu. Aksjomat (v) mówi, że nie kręcimy się w kółko (co mogłoby sytuację uczynić skończoną). Indukcja (VII) mówi, że zbiór wszystkich liczb naturalnych tworzy (spójną jakby) ścieżkę, zaczynająca się od 1, krok po kroku zawierającą wszystkie liczby naturalne:
1 Nxt(1) Nxt(Nxt(1)) Nxt(Nxt(Nxt(1))) ...
Innych liczb naturalnych, według aksjomatu indukcji, nie ma. Czyli, dla uzyskania nieskończoności, aksjomatu indukcji nie potrzebujemy. Potrzebujemy go dla rozwinięcia teorii głębokiej.
Co prawda sytuacja jest subtelna. W sensie metateoretycznym możemy twierdzić, że uzyskaliśmy konstrukcję nieskonczona. Jest to oczywiste. Ale bez indukcji nie możemy dowieść, że tak naprawdę jest, bowiem nie możemy pokazać, że z czasem, poczynająć od 1, nie zaczneimy się kręcić w kółko - należy dowieść, że x jest różne na przykład od Nxt(Nxt(Nxt(x))). Jest to "materialnie" oczywiste dla nieskończonego podzbioru "liczb naturalnych" (bezindukcyjnych), ale nie mamy tego jak pokazać bez indukcji matematycznej (lub podobnego schematu), bo nawet Nxt(x) = x dla pewnych x może zachodzić, gdy indukcji się nie założy.
UWAGA: W metamatematyce, nawet bez indukcji matematycznej, i tak stosuje się to, co Profesor Andrzej Mostowski nazywał przesłanką indukcyjną. Chodzi o to, że predykaty i inne wyrażenia buduje się rekursyjnie (indukcyjnie). Kończy się konstrukcje takich wyrażeń aksjomatem: innych wyrażeń naszego (właśnie definiowanego) typu, poza wyżej podanymi, nie ma. To właśnie pozwala na dowody indukcukcyjne, tak powszechne także w informatyce.
Pierwszy kontakt z nieskończonością
Przede wszystkim nieskończoność występuje w metamatematyce. Po prostu mamy potencjalnie nieskończenie wiele różnych zapisów, w szczególności predykatów, gdzie predykat rozumiem w sensie logiki matematycznej. Poświęcę temu kilka słów.
Niektórzy autorzy, definiując teorię matematyczną, zaczynają od tego, że ma nieskończony alfabet, po czym dają przykład:
x x' x'' x''' ...
Wolałbym, żeby zbioru tak złożonych wyrażeń, jak x'''', nie nazywali alfabetem. Prawdziwa teoria powinna zaczynać od skończonego zbioru znaków, przy tym niewielkiego, łatwego do ogarnięcia wzrokiem, tak by każde dwa różne znaki można było z łatwościę odróżnić. Można na przykład, przynajmniej celem ścisłego wprowadzenia danej teorii, do zbioru znaków wyjściowych zaliczyć 26 liter małych i 26 dużych alfabetu angielskiego, cyfry dziesiętne 0 ... 9, nawiasy ( ), prim ', oraz ' + - * =. Razem powiedzmy 60 znaków (teoretycznie dwa wystarczyłyby). Dopiero na następnym etapie buduje się wyrażenia oznaczające na przykład zmienne, jak wymienione wyrażenia: x x' x'' x''' ... (które kolejno składają się z 1 2 3 ... znaków - nie są pojedynczymi znakami). Można mieć też konstrukcje definiujące nowe pojęcia, jak powiedzmy SUMA, których syntaks znowu używa podane wyjściowe znaki (tu: A M S U).
UWAGA 0: Odstęp " " należy do metateorii (nie jest znakiem teorii). W każdym razie możemy tak się rozsądnie umówić.
UWAGA 1: Można teorię stworzyć dla komputera, żeby komputer ją uprawiał. Znowu wyjściowych "znaków" powinno być skończenie wiele, i powinny być łatwo przez komputer rozróżniane. Z tego powodu stosuje się tylko dwa znaki wewnątrz komputera, o których ludzie na ogół mówią 0 oraz 1. Próbowano więcej "znaków", ale z powodów technologicznych wtedy kłopoty z błędami tak wzrastały, że w zasadzie z tych prób zrezygnowano, prawie.
Kilka słów o predykatach: są to ciągi znaków (struny czyli po angielsku strings), w których jednoznacznie można wyróżnić zmienne (jeżeli występują). Gdy za zmienne podstawimy konkretne wartości stałe, to powinniśmy otrzymać zdanie (w sensie formalnej definicji danej teorii), czyli coś, co jest albo prawdziwe albo fałszywe. Czyli predykat jest funkcją logiczną, której wartościami są Prawda i Fałsz. Na przykład słynny jest predykat Fermata, z jego tak zwanego Ostatniego Twierdzenia:
EXP(x n) + EXP(y n) = EXP(z n)
gdzie EXP(a b) oznacza [;a^b;], ale dla ilustracji chciałem się ograniczyć do wcześniej wspomnianych 60 znaków. Fermat wyraził przypuszczenie, że ten predykat jest zawsze fałszywy, gdy x y z n są liczbami naturalnymi 1 2 ..., takimi że n > 2. Dowód zajął ponad trzysta lat.
Niektórzy autorzy, definiując teorię matematyczną, zaczynają od tego, że ma nieskończony alfabet, po czym dają przykład:
x x' x'' x''' ...
Wolałbym, żeby zbioru tak złożonych wyrażeń, jak x'''', nie nazywali alfabetem. Prawdziwa teoria powinna zaczynać od skończonego zbioru znaków, przy tym niewielkiego, łatwego do ogarnięcia wzrokiem, tak by każde dwa różne znaki można było z łatwościę odróżnić. Można na przykład, przynajmniej celem ścisłego wprowadzenia danej teorii, do zbioru znaków wyjściowych zaliczyć 26 liter małych i 26 dużych alfabetu angielskiego, cyfry dziesiętne 0 ... 9, nawiasy ( ), prim ', oraz ' + - * =. Razem powiedzmy 60 znaków (teoretycznie dwa wystarczyłyby). Dopiero na następnym etapie buduje się wyrażenia oznaczające na przykład zmienne, jak wymienione wyrażenia: x x' x'' x''' ... (które kolejno składają się z 1 2 3 ... znaków - nie są pojedynczymi znakami). Można mieć też konstrukcje definiujące nowe pojęcia, jak powiedzmy SUMA, których syntaks znowu używa podane wyjściowe znaki (tu: A M S U).
UWAGA 0: Odstęp " " należy do metateorii (nie jest znakiem teorii). W każdym razie możemy tak się rozsądnie umówić.
UWAGA 1: Można teorię stworzyć dla komputera, żeby komputer ją uprawiał. Znowu wyjściowych "znaków" powinno być skończenie wiele, i powinny być łatwo przez komputer rozróżniane. Z tego powodu stosuje się tylko dwa znaki wewnątrz komputera, o których ludzie na ogół mówią 0 oraz 1. Próbowano więcej "znaków", ale z powodów technologicznych wtedy kłopoty z błędami tak wzrastały, że w zasadzie z tych prób zrezygnowano, prawie.
Kilka słów o predykatach: są to ciągi znaków (struny czyli po angielsku strings), w których jednoznacznie można wyróżnić zmienne (jeżeli występują). Gdy za zmienne podstawimy konkretne wartości stałe, to powinniśmy otrzymać zdanie (w sensie formalnej definicji danej teorii), czyli coś, co jest albo prawdziwe albo fałszywe. Czyli predykat jest funkcją logiczną, której wartościami są Prawda i Fałsz. Na przykład słynny jest predykat Fermata, z jego tak zwanego Ostatniego Twierdzenia:
EXP(x n) + EXP(y n) = EXP(z n)
gdzie EXP(a b) oznacza [;a^b;], ale dla ilustracji chciałem się ograniczyć do wcześniej wspomnianych 60 znaków. Fermat wyraził przypuszczenie, że ten predykat jest zawsze fałszywy, gdy x y z n są liczbami naturalnymi 1 2 ..., takimi że n > 2. Dowód zajął ponad trzysta lat.
Sunday, October 10, 2010
Pokój z lampą. Ćwiczenie na przekazywanie informacji. Cz. 0
W naqnaq, w grupie "Zagadki", niejaki Witzar podał szereg świetnych zadań kombinatoryczno-informatycznych, które nazwał logicznymi. Jego scenariusz więzienny zastąpię szkolnym, żeby zadanie brzmiało mniej ponuro.
ZADANIE [;n;] zdolnych uczniów zebrano razem, żeby ustalili optymalną strategię prowadzenia wspólnej gry. Każdy uczeń za ten honor i możliwość wpłacił 300zł na pewne konto. Do wygrania mają wspólną podróż dookoła świata i stypendium dla każdego z nich do końca studiów. Po zebraniu, już do końca gry, nie wolno się im komunikować. Otóż po zebraniu, każdego dnia losowo wybrany uczeń uda się do pewnego pokoiku, w którym lampa będzie zapalona lub zgaszona. Po sobie zostawi lampę zgaszoną lub zapaloną według swojego życzenia (według wspólnie ustalonej strategii). Może też oświadczyć, że wraz z nim każdy student już w tym pokoiku był co najmniej jeden raz. Jeżeli pomyli się, to wpłaty uczniów przepadną, oraz będą nici z podróży i stypendium. Jeżeli oświadczenie będzie poprawne, to wszyscy uczniowie wygrają, zgodnie z obietnicą.
Podpowiedz uczniom jak najlepszą strategię.
Dla n=1, przy jednym uczniu, uczeń wchodzi do pokoiku i woła wygrałem! - i rzeczywiście wygrał. Koniec.
Przy n=2 uczniowie mogą się umówić, że
Jest to absolutnie najlepsza strategia. Szybciej wygrać jest niemożliwym.
Przy n=3 następująca umowa jest optymalna (lepszej nie ma):
Znowu opisana strategia jest optymalna. Za każdym razem wygrywa jak tylko najszybciej można. Już dla n=4 tak dobrej strategii nie ma, co wykażę w następnej nocie. Teraz podam jeszcze definicje kilku pojęć, by dało się rozmawiać o zadaniu ściśle. W szczegółności ściśle zdefiniuję strategię.
Uczniów numerujemy: [;0\ \ldots\ n-1;]. Podobnie numerujemy od zera, ale w nieskończoność, dni w pokoiku: [;0\ 1\ 2\ \ldots;].
Przebiegiem (losowania) nazywamy dowolny ciąg
[;\bullet\quad\quad w : \{0\ 1\ \ldots\} \rightarrow \{\0\ \ldots\ n-1\};]
UWAGA Chociaż gra, aż po okrzyk "zwycięstwo!" może trwać skończoną liczbę dni, to teoretycznie wygodnie jest zakładać, że losowanie uczniów powtarza się każdego dnia w nieskończoność (po zakończeniu gry nikogo to już nie obchodzi, nikomu to nie przeszkadza).
Poniższe funkcje za swój argument mają także przebieg, co będziemy często pomijać, żeby za bardzo nie piętrzyć notacji.
Zapisem ucznia [;u;] w dniu gry [;d;] nazywamy strukturę
[;\bullet\quad\quad \ker_{u\ d} := (v_{u\ d}\ \ \delta_{u\ d}\ \ b_{u\ d});]
następujących danych:
Strategią nazywamy dowolną funkcję [;S;] która każdemu a priori możliwemu zapisowi [;\ker;] przypisuje wartość [;S(\ker);], będącą równą 0 (lampę przed opuszczeniem pokoju gasimy lub pozostawiamy zgaszoną) albo 1 (lampę przed opuszczeniem pokoju zapalamy lub zostawiamy zapaloną) albo 2 (wołamy wtedy: zwycięstwo!).
W praktyce, pełna definicja uczniowskiej strategi powinna dać się opisać w notesiku, który uczeń będzie miał przy sobie - strategia powinna dać się opisać jako skonczony algorytm. Teoretycznie prościej jest mówić o strategiach będących dowolnymi funkcjami, jak wyżej.
Uczeń po wejściu do pokoiku uaktualnia swój zapis [;\ker;], po czym stosuje do niego funkcję strategiczną, [;S(\ker);].
Dla liczby uczniów n=1 lub 2 lub 3 podane wyżej strategie dają najszybszą wygraną - nawet granie na szczęście, bez żadnej strategii, też nigdy nie da szybszej wygranej. Takie strategie nazwijmy natychmiastowymi. Zdefiniuję je teraz ściśle, a nawet całe spektrum różnych klas strategii.
Najpierw z każdym przebiegiem
[;\bullet\quad\quad w : \{0\ 1\ \ldots\} \rightarrow \{\0\ \ldots\ n-1\};]
zwiążmy jego stopień zaawansowania [;\deg_w;] :
[;\bullet\quad\quad \deg_w(d)\ :=\ \min_{u=0\ \ldots\ n-1}\ v_{u\ d};]
Ponadto zdefiniujmy końce cykli, [;C_w(q);], jako numer pierwszego dnia, w którym każdy uczeń wszedł do pokoiku minimum [;q;] razy:
[;\bullet\quad\quad C_w(q) := min_{\deg_w(d) = q}\ d;]
a gdy takiego dnia nie ma (gdy pewien uczeń nigdy nie był wylosowany aż [;q;] razy), to przyjmujemy [;C(q) := \infty;].
Gdy dla pewnego [;q;] strategia [;S;] zapewnia zwycięstwo nie później niż w dniu [;C_w(q);], to powiemy, że jest opieszała rzędu [;q;].
Strategie opieszałę rzędu 1 są absolutnie najlepsze, są natychmiastowe. Istnieją jednak tylko dla liczby uczniów n=1 2 3. Już dla n=4, i dla wszystkich większych n, strategia natychmiastowa nie istnieje.
Prawdopodobnie uzyskanie strategii, której opieszałość jest rzędu [;\sqrt{n};] (gdzie n jest liczbą uczniów), jest całkiem dobrym wynikiem.
ZADANIE [;n;] zdolnych uczniów zebrano razem, żeby ustalili optymalną strategię prowadzenia wspólnej gry. Każdy uczeń za ten honor i możliwość wpłacił 300zł na pewne konto. Do wygrania mają wspólną podróż dookoła świata i stypendium dla każdego z nich do końca studiów. Po zebraniu, już do końca gry, nie wolno się im komunikować. Otóż po zebraniu, każdego dnia losowo wybrany uczeń uda się do pewnego pokoiku, w którym lampa będzie zapalona lub zgaszona. Po sobie zostawi lampę zgaszoną lub zapaloną według swojego życzenia (według wspólnie ustalonej strategii). Może też oświadczyć, że wraz z nim każdy student już w tym pokoiku był co najmniej jeden raz. Jeżeli pomyli się, to wpłaty uczniów przepadną, oraz będą nici z podróży i stypendium. Jeżeli oświadczenie będzie poprawne, to wszyscy uczniowie wygrają, zgodnie z obietnicą.
Podpowiedz uczniom jak najlepszą strategię.
Dla n=1, przy jednym uczniu, uczeń wchodzi do pokoiku i woła wygrałem! - i rzeczywiście wygrał. Koniec.
Przy n=2 uczniowie mogą się umówić, że
- będą zapalać lampkę albo nie, byle jak;
- początkowego dnia uczeń w pokoiku będzie cicho (nie zawoła, że wygrał);
- każdego następnego dnia, jeżeli uczeń w pokoiku nie był w nim poprzedniego dnia, to zawoła "wygraliśmy!".
Jest to absolutnie najlepsza strategia. Szybciej wygrać jest niemożliwym.
Przy n=3 następująca umowa jest optymalna (lepszej nie ma):
- uczeń, który do danego dnia włącznie, od początkowego, był w pokoiku za każdym razem, pozostawia za sobą światło zgaszone;
- gdy dzień nie jest początkowy, a w czasie przynajmniej jednego z poprzednich dni był w pokoiku inny uczeń od danego, to:
- zastawszy światło zgaszone, uczeń pozostawia po sobie światło zapalone;
- jeżeli uczeń był w pokoiku także poprzedniego dnia, i pozostawił światło zapalone, to znowu zostawia po sobie światło zapalone;
- jeżeli poprzedniego dnia był inny uczeń od danego, i pozostawił światło zapalone, to obecny uczeń woła "wygraliśmy!".
Znowu opisana strategia jest optymalna. Za każdym razem wygrywa jak tylko najszybciej można. Już dla n=4 tak dobrej strategii nie ma, co wykażę w następnej nocie. Teraz podam jeszcze definicje kilku pojęć, by dało się rozmawiać o zadaniu ściśle. W szczegółności ściśle zdefiniuję strategię.
Uczniów numerujemy: [;0\ \ldots\ n-1;]. Podobnie numerujemy od zera, ale w nieskończoność, dni w pokoiku: [;0\ 1\ 2\ \ldots;].
Przebiegiem (losowania) nazywamy dowolny ciąg
[;\bullet\quad\quad w : \{0\ 1\ \ldots\} \rightarrow \{\0\ \ldots\ n-1\};]
UWAGA Chociaż gra, aż po okrzyk "zwycięstwo!" może trwać skończoną liczbę dni, to teoretycznie wygodnie jest zakładać, że losowanie uczniów powtarza się każdego dnia w nieskończoność (po zakończeniu gry nikogo to już nie obchodzi, nikomu to nie przeszkadza).
Poniższe funkcje za swój argument mają także przebieg, co będziemy często pomijać, żeby za bardzo nie piętrzyć notacji.
Zapisem ucznia [;u;] w dniu gry [;d;] nazywamy strukturę
[;\bullet\quad\quad \ker_{u\ d} := (v_{u\ d}\ \ \delta_{u\ d}\ \ b_{u\ d});]
następujących danych:
- [;v_{u\ d};] jest liczbą wizyt ucznia [;u;] w pokoiku, w czasie dni [;0\ \ldots\ d;];
- [;\delta_{u\ d} : \{0\ \ldots\ v_{u\ d}-1\} \rightarrow \{0\ 1\ \ldots\};] jest funkcją, która informuje nas o dniach wizyt [;\delta_{u\ d}(0)\ \ldots\ \delta_{u\ d}(v-1);], ucznia [;u;];
- [;b_{u\ d} : \{0\ \ldots\ v_{u\ d}-1\} \rightarrow \{0\ 1\};] jest funkcją, która informuje nas o zastanym stanie lampy, [;b_{u\ d}(t);] na początku wizyty w dniu [;\delta_{u\ d}(t);]; gdy uczeń zastał ciemność, to zapisze wartość funkcji [;b;] jako [;0;]. a jeżeli lampa świeciła się, to zapisze [;1;]; dla ustalenia uwagi (to zupełnie nieważne) zakładamy, że na samym początku dnia [;0;] lampa była zgaszona .
Strategią nazywamy dowolną funkcję [;S;] która każdemu a priori możliwemu zapisowi [;\ker;] przypisuje wartość [;S(\ker);], będącą równą 0 (lampę przed opuszczeniem pokoju gasimy lub pozostawiamy zgaszoną) albo 1 (lampę przed opuszczeniem pokoju zapalamy lub zostawiamy zapaloną) albo 2 (wołamy wtedy: zwycięstwo!).
W praktyce, pełna definicja uczniowskiej strategi powinna dać się opisać w notesiku, który uczeń będzie miał przy sobie - strategia powinna dać się opisać jako skonczony algorytm. Teoretycznie prościej jest mówić o strategiach będących dowolnymi funkcjami, jak wyżej.
Uczeń po wejściu do pokoiku uaktualnia swój zapis [;\ker;], po czym stosuje do niego funkcję strategiczną, [;S(\ker);].
Dla liczby uczniów n=1 lub 2 lub 3 podane wyżej strategie dają najszybszą wygraną - nawet granie na szczęście, bez żadnej strategii, też nigdy nie da szybszej wygranej. Takie strategie nazwijmy natychmiastowymi. Zdefiniuję je teraz ściśle, a nawet całe spektrum różnych klas strategii.
Najpierw z każdym przebiegiem
[;\bullet\quad\quad w : \{0\ 1\ \ldots\} \rightarrow \{\0\ \ldots\ n-1\};]
zwiążmy jego stopień zaawansowania [;\deg_w;] :
[;\bullet\quad\quad \deg_w(d)\ :=\ \min_{u=0\ \ldots\ n-1}\ v_{u\ d};]
Ponadto zdefiniujmy końce cykli, [;C_w(q);], jako numer pierwszego dnia, w którym każdy uczeń wszedł do pokoiku minimum [;q;] razy:
[;\bullet\quad\quad C_w(q) := min_{\deg_w(d) = q}\ d;]
a gdy takiego dnia nie ma (gdy pewien uczeń nigdy nie był wylosowany aż [;q;] razy), to przyjmujemy [;C(q) := \infty;].
Gdy dla pewnego [;q;] strategia [;S;] zapewnia zwycięstwo nie później niż w dniu [;C_w(q);], to powiemy, że jest opieszała rzędu [;q;].
Strategie opieszałę rzędu 1 są absolutnie najlepsze, są natychmiastowe. Istnieją jednak tylko dla liczby uczniów n=1 2 3. Już dla n=4, i dla wszystkich większych n, strategia natychmiastowa nie istnieje.
Prawdopodobnie uzyskanie strategii, której opieszałość jest rzędu [;\sqrt{n};] (gdzie n jest liczbą uczniów), jest całkiem dobrym wynikiem.
Subscribe to:
Posts (Atom)