Zaawansowane algorytmy i struktury danych/Ćwiczenia 2

From Studia Informatyczne

Spis treści

Zadanie 1

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

Rozwiązanie

.

Zanalizuj zachowanie się sumy i+j, suma ta wynosi co najwyżej 2n.

Zadanie 2

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

Rozwiązanie

.

Postępujemy zachłannie, tak jak w przypadku binarnym, za każdym razem sklejamy

k aktualnie najmnieszych elementów. W pierwszym kroku być może mniej niż k, tak aby w następnych zawsze było k.

Zadanie 3

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

Rozwiązanie

.

Programowanie dynamiczne.

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

.

Skonstruuj jak najbardziej pełne, regularne drzewo.

Zadanie 5

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

Rozwiązanie

.

Skorzystaj z technik używanych w string-matchingu ze stałą pamięcią.