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ć więcej niż jednym sposobem. 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 }$;
  U2:=$\mathrm{\varnothing }$;
  forall x in X do
    forall y in X do
      if x < y then U1:=$U1\cup \{x^{-1}y\}$;
  
  while U2 $\ne$ 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, 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}}}