Zaawansowane algorytmy i struktury danych/Ćwiczenia 2: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
|||
| Linia 1: | Linia 1: | ||
== Zadanie 1 == | == Zadanie 1 == | ||
Pokazaż, że algorytm Maksymalny-Sufiks wykonuje co najwyżej 2.|x| porównań symboli. | |||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie''' <div class="mw-collapsible-content" style="display:none">. | <div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie''' <div class="mw-collapsible-content" style="display:none">. | ||
Zanalizuj zachowanie się sumy i+j, suma ta wynosi co najwyżej 2n. | |||
</div> | </div> | ||
</div> | </div> | ||
==Zadanie 2== | ==Zadanie 2== | ||
Zmodyfikuj algorytm Huffmana dla przypadku niebinarnego alfabetu, | |||
gdy kodujemy w alfabecie k-arnym | gdy kodujemy w alfabecie <math>k</math>-arnym. Mamy teraz symbole | ||
<math>0,1,\ldots, k-1 </math>. W algorytmie jednorazowo możemy sklejać więcej niż dwa elementy. | <math>0,1,\ldots, k-1 </math>. W algorytmie jednorazowo możemy sklejać więcej niż dwa elementy. | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie''' <div class="mw-collapsible-content" style="display:none">. | <div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie''' <div class="mw-collapsible-content" style="display:none">. | ||
Postępujemy zachłannie tak jak w przypadku binarnym, za każdym razem sklejamy | Postępujemy zachłannie, tak jak w przypadku binarnym, za każdym razem sklejamy | ||
k | <math>k</math> aktualnie najmnieszych elementów. W pierwszym kroku być może mniej niż <math>k</math>, tak | ||
aby w następnych zawsze było k. | aby w następnych zawsze było <math>k</math>. | ||
</div> | </div> | ||
</div> | </div> | ||
| Linia 23: | Linia 23: | ||
== Zadanie 3 == | == 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). | dla małych <math>c</math> (<math>c=2</math> lub <math>c=3</math>). | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie''' <div class="mw-collapsible-content" style="display:none">. | <div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie''' <div class="mw-collapsible-content" style="display:none">. | ||
| Linia 34: | Linia 34: | ||
== Zadanie 4 == | == 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. | dla przypadku, gdy wagi wszystkich liści drzewa są takie same. | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie''' <div class="mw-collapsible-content" style="display:none">. | <div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie''' <div class="mw-collapsible-content" style="display:none">. | ||
Skonstruuj jak najbardziej pełne regularne drzewo. | Skonstruuj jak najbardziej pełne, regularne drzewo. | ||
</div> | </div> | ||
</div> | </div> | ||
Wersja z 13:02, 25 wrz 2006
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
