Zaawansowane algorytmy i struktury danych/Ćwiczenia 2: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 11: | Linia 11: | ||
==Zadanie 2== | ==Zadanie 2== | ||
Zmodyfiku algorytm Huffmana dla przypadku niebinarnego alfabetu | Zmodyfiku 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. | gdy kodujemy w alfabecie k-arnym, mamy teraz symbole | ||
<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">. | ||
Wersja z 12:08, 12 wrz 2006
Zadanie 1
Pokazać, że algorytm Maksymalny-Sufiks wykonuje co najwyżej 2.|x| porównań symboli.
Rozwiązanie
Zadanie 2
Zmodyfiku algorytm Huffmana dla przypadku niebinarnego alfabetu gdy kodujemy w alfabecie k-arnym, mamy teraz symbole . W algorytmie jednorazowo możemy sklejać więcej niż dwa elementy.
Rozwiązanie
Zadanie 3
Znajdz wielomianowy algorytm dla kodowanie prefiksowego z symbolami kodowymi nierównej długości dla małych c (c=2 lub c=3).
Rozwiązanie
Zadanie 4
Znajdz wielomianowy algorytm dla kodowanie prefiskowego 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
