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

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

Rozwiązanie

Algorytm taki istnieje. Przyda się do niego operacja odwrotna 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;
    U1,U2: set of words;
begin
  U1:=$\mathrm{\varnothing }$;
  forall x in X do
    forall y in X do
      if x < y then U1:=$U1\cup \{x^{-1}y\}$;
  U2:=U1;
  while U2=U1 do begin
    U1=U2;
    forall x in U1 do
      forall y in X do
        if x $\le$ y then U2:=$U2\cup \{x^{-1}y\}$;
  end;
  if $\epsilon \in U2$ then Code:=0; 
  else Code:=1;
end;

Powyższy algorytm generuje wszystkie krótkie sufiksy ciągów możliwych do uzyskania przy pomocy słów ze zbioru X. Jeśli w którymś momencie trafi na słowo puste, oznacza to że zbiór X nie jest kodem.

Ć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, to 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 której szalki 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}}}