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

{{{3}}}

Ć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?

Wskazowka 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ć?

Wskazowka 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\}$;
    $\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

{{{3}}}

Ć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$)?

Wskazowka

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óre są prefiksami innych (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

{{{3}}}