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