Zaawansowane algorytmy i struktury danych/Ćwiczenia 2

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zadanie 1

Pokazaż, że algorytm Maksymalny-Sufiks wykonuje co najwyżej 2.|x| porównań symboli.

Rozwiązanie

Zadanie 2

Zmodyfikuj algorytm Huffmana dla przypadku niebinarnego alfabetu, gdy kodujemy w alfabecie -arnym. Mamy teraz symbole . W algorytmie jednorazowo możemy sklejać więcej niż dwa elementy.

Rozwiązanie

Zadanie 3

Znajdź wielomianowy algorytm dla kodowanie prefiksowego z symbolami kodowymi nierównej długości dla małych ( lub ).

Rozwiązanie

Zadanie 4

Znajdź wielomianowy algorytm dla kodowania prefiksowego z symbolami kodowymi nierównej długości dla przypadku, gdy wagi wszystkich liści drzewa są takie same.

Rozwiązanie

Zadanie 5

Oblicz minimalny okres słowa w czasie liniowym i pamięci stałej.

Rozwiązanie