Teoria informacji/TI Ćwiczenia 1

Ćwiczenia dotyczące kodów.

Ćwiczenie Ćwiczenie 1

{{{3}}}

Rozwiązanie

{{{3}}}

{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 Ćwiczenie 2

{{{3}}}

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

{{{3}}}

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 ciągiem.

Ćwiczenie Ćwiczenie 3

{{{3}}}

Wskazowka

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

Rozwiązanie

{{{3}}}

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}$.