Teoria informacji/TI Ćwiczenia 1

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ć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


Ćwiczenie 2 [Rozpoznawanie kodów]

Czy istnieje algorytm, który dla dowolnego skończonego zbioru X nad alfabetem stwierdza, czy X jest kodem?

Wskazówka 1

Wskazówka 2

Rozwiązanie


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

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

Rozwiązanie


Ćwiczenie 4 [Maksymalne kody]

Załóżmy, że X jest maksymalnym zbiorem bezprefiksowym nad alfabetem (żaden jego nadzbiór nie jest bezprefiskowy). Czy w takim przypadku nierówność Krafta zamienia się w równość (tzn. )?

Wskazówka

Rozwiązanie

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 dowolne dwa z poniższych warunków implikują trzeci:

  • jest bezprefiksowy
  • wyczerpuje alfabet

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 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 , przy których może się nam to udać przy użyciu ważeń?
  • Opracuj strategię pozwalającą rozwiązać zadanie dla trzech ważeń i dwunastu monet.

Wskazówka