Teoria informacji/TI Ćwiczenia 1

Ćwiczenia

Ćwiczenie 1 [Definicja kodu]

Mamy dane zbiory:

{0,01,11}

{0,11,10}

{00,01,10}

{00,001,100}

{1,010,110,001,000,101}

Określ:

Które z nich są kodami?

Które są bezprefiskowe?

Które są maksymalne bezprefiksowe?

Rozwiązanie

{0,01,11} - Jest kodem, nie jest bezprefiksowy (0 jest prefiksem 01).

{0,11,10} - Jest kodem bezprefiksowym maksymalnym (łatwo rozrysować drzewo).

{00,01,10} - Jest kodem bezprefiksowym, ale nie maksymalnym (można dodać 11).

{00,001,100} - Nie jest kodem (ciąg 00100 można zapisać na dwa sposoby).

{1,010,110,001,000,101} - Nie jest kodem (nie spełnia nawet nierówności Krafta).

Ćwiczenie 2 [Rozpoznawanie kodów]

Czy istnieje algorytm, który dla dowolnego skończonego zbioru X nad alfabetem $\mathrm{\Sigma }$ stwierdza, czy X jest kodem?

Wskazówka 1

Należy sprawdzić, czy jakiś ciąg znaków można uzyskać więcej niż jednym sposobem. Czy można jakoś ograniczyć z góry długość ciągów, jakie wystarczy sprawdzić?

Wskazówka 2

Wygodnym podejściem do problemu jest zbudowanie odpowiedniej struktury danych. Może być nią graf, którego wierzchołkami są sufiksy słow ze zbioru X, a krawędź prowadzi z x do z, jeśli istnieje $y\in X$, takie że $y=xz$. W zbiorze wierzchołków wyróżniamy podzbiór $U=\{z:(\mathrm{\exists }x,y\in X)y=xz\}$. Zbiór X nie jest kodem wtedy i tylko wtedy, gdy istnieje słowo posiadające faktoryzacje startujące z dwóch różnych słów $x,y\in X$. Łatwo sptawdzić, że jest to równoważne istnieniu w opisanym grafie ścieżki z pewnego wierzchołka $z\in U$ do wierzchołka $\epsilon$.

Rozwiązanie

Struktura opisana we Wskazówce 2 prowadzi do poniższego algorytmu. Wykorzystujemy w nim operację odwrotną do konkatenacji słów. Jeśli x i y są słowami takimi, że x jest prefiksem y, to niech $z=x^{-1}y⟺xz=y$.

function Code(X:set of words):boolean;
//Dla danego zbioru X określamy czy jest on kodem
var x,y : word;
   $U,\mathrm{\Delta },\mathrm{\Delta }1$ : set of words;
begin
  $U:=\mathrm{\varnothing }$;
  $\mathrm{\Delta }:=\mathrm{\varnothing }$;
  forall x in X do
    forall y in X do
      if x < y then $\mathrm{\Delta }:=\mathrm{\Delta }\cup \{x^{-1}y\}$;
  
  while  $(\mathrm{\Delta }\ne \mathrm{\varnothing }\wedge \epsilon \in ̸\mathrm{\Delta })$  do 
  begin
     $U:=U\cup \mathrm{\Delta }$;
     $\mathrm{\Delta }1$ := $\mathrm{\varnothing }$;
    forall x in $\mathrm{\Delta }$ do
      forall y in X do
        if x $\le$ y then $\mathrm{\Delta }1$:=$\mathrm{\Delta }1\cup \{x^{-1}y\}$;
        else if y < x then $\mathrm{\Delta }1$:=$\mathrm{\Delta }1\cup \{y^{-1}x\}$;
    $\mathrm{\Delta }:=\mathrm{\Delta }1-U$;
  end;
  if $\epsilon \in \mathrm{\Delta }$ then Code:=0
  else Code:=1;
end;

W pierwszej fazie, algorytm generuje zbiór U opisany we Wskazówce 2. Z kolei, w pętli while, znajduje wszystkie sufiksy osiągalne z tego zbioru. Pętla zatrzymuje się, bo każdy jej obrót powieksza zbiór U. Poprawność algorytmu wynika z uwagi we wskazówce 2.

Ćwiczenie 3 [Nieskończone kody]

Definicja kodu nie zakłada, że zawiera on skończenie wiele słów. Przykładem nieskończonego kodu jest zbiór $\{0^{n}1|n\in \mathbb{\mathbb{N}}\}$.

Udowodnij, że każdy nieskończony kod również spełnia nierówność Krafta.

Rozwiązanie

Załóżmy przeciwnie, że dla pewnego nieskończonego kodu X mamy $\sum _{s\in S}\frac{1}{r^{\ell (s)}}=1+\epsilon$. Rozważmy kolejne podzbiory $X_1,X_2\dots$ zbioru X zawierające słowa długości co najwyżej 1, 2, itd. Odpowiadający im ciąg sum Krafta $K_1,K_2,\dots$ jest zdefiniowany przez $K_i=\sum _{s\in S\ell (s)\le i}\frac{1}{r^{\ell (s)}}$. Z założenia $\underset{n\to \mathrm{\infty }}{\lim }{K}_n=1+\epsilon$, a więc dla pewnego n mamy $K_n\ge 1+\frac{\epsilon }{2}$. Skończony zbiór $X_n$ nie spełnia zatem nierówności Krafta, czyli nie jest kodem. Kodem nie może być więc żaden jego nadzbiór.

Ćwiczenie 4 [Maksymalne kody]

Załóżmy, że X jest maksymalnym zbiorem bezprefiksowym nad alfabetem $\mathrm{\Sigma }$ (żaden jego nadzbiór nie jest bezprefiskowy). Czy w takim przypadku nierówność Krafta zamienia się w równość (tzn. $\sum _{s\in X}\frac{1}{r^{\ell (s)}}=1$)?

Wskazówka

Czy odpowiedź zależy od tego czy X jest skończony?

Rozwiązanie

W przypadku skończonego X rzeczywiście tak jest. Niech $\ell$ będzie maksymalną długością słowa w X. Wtedy, jeśli nierówność Krafta jest ścisła, któreś słowo długości $\ell$ nie posiada żadnego prefiksu w X - czyli można X rozszerzyć o to słowo.

Inna sytuacja ma miejsce, gdy X jest nieskończony. Wtedy nawet dla niewielkiej sumy Krafta możemy zapewnić, żeby każde słowo było prefiksem jakiegoś słowa w X. Przykładowo, dla alfabetu binarnego weźmy zbiór słów $W3=\{www:w\in {\mathrm{\Sigma }}^{+}\}$ i usuńmy z niego wszystkie słowa, których pewien właściwy prefiks należy do W3 (zauważmy, że ta operacja nie usunie wszystkich słów). Tak uzyskany zbiór jest maksymalny bezprefiksowy, a suma Krafta dla niego jest nie większa niż suma Krafta dla W3, wynosząca $\sum _{s\in W3}\frac{1}{2^{\ell (s)}}=\sum _{i=1}^{\mathrm{\infty }}\frac{2^i}{2^{3i}}=\sum _{i=1}^{\mathrm{\infty }}{4}^{-i}=\frac{1}{3}$.

Zadania domowe

Zadanie 1 - Kody wyczerpujące alfabet

Mówimy że kod wyczerpuje alfabet, jeśli dowolny wystarczająco długi ciąg liter alfabetu zawsze rozpoczyna się od słowa kodowego (innymi słowy dowolny nieskończony ciąg liter da się rozłożyć na słowa kodowe). Pokaż, że dla dowolnego skończonego kodu $X$ dowolne dwa z poniższych warunków implikują trzeci:

• $X$ jest bezprefiksowy
• $X$ wyczerpuje alfabet
• $\sum _{s\in X}\frac{1}{r^{\ell (s)}}=1$

Pokaż, że żaden z tych warunków nie implikuje pozostałych dwóch. Czy założenie o skończoności kodu jest konieczne?

Zadanie 2 - Ważenie monet

Załóżmy, że mamy $n\ge 3$ monet, z których jedna jest fałszywa i różni się ciężarem od pozostałych (może być lżejsza lub cięższa). Naszym zadaniem jest znalezienie fałszywej monety i określenie czy jest cięższa, czy lżejsza. Do dyspozycji mamy jedynie wagę szalkową, na szalki której możemy kłaść monety. Waga wskazuje zawsze jedną z trzech możliwości: lewa szalka cięższa, prawa szalka cięższa lub równowaga.

• Jakie jest górne ograniczenie na liczbę monet $n$, przy których może się nam to udać przy użyciu $k$ ważeń?
• Opracuj strategię pozwalającą rozwiązać zadanie dla trzech ważeń i dwunastu monet.

Wskazówka

Ponumeruj monety i spróbuj porównać ważenie do „Gry w 20 pytań”, pamiętając że tym razem na każde pytanie są trzy możliwe odpowiedzi.