Zaawansowane algorytmy i struktury danych/Ćwiczenia 2: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
m Zastępowanie tekstu – „ </math>” na „</math>” |
||
| Linia 12: | Linia 12: | ||
Zmodyfikuj algorytm Huffmana dla przypadku niebinarnego alfabetu, | Zmodyfikuj algorytm Huffmana dla przypadku niebinarnego alfabetu, | ||
gdy kodujemy w alfabecie <math>k</math>-arnym. Mamy teraz symbole | 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">. | ||
Aktualna wersja na dzień 11:01, 5 wrz 2023
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
