Ćwiczenia | Informatyka MIMUW

Zadanie 1

[Dowód lematu 1]
Udowodnij lemat 1

Rozwiązanie

Indukcja po \( k \). <

Zadanie 2

[Kolejka dwumianowa 1]
Do początkowo pustej kolejki dwumianowej wstawiamy klucze 1, 2, ..., 1000. Czy teraz w jej skład wchodzi drzewo \( B_5 \)?

Rozwiązanie

Tak, bo \( 1000 = 2^9+2^8+2^7+2^6+\mathbf{2^5}+2^3 \).

Zadanie 3

[Przykładowy ciąg operacji]
Narysuj
(a) kolejkę dwumianową
(b) kopiec Fibonacciego
otrzymane w wyniku wstawienia do początkowo pustej struktury kolejno kluczy 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, wykonaniu Delmin, zmniejszeniu klucza 7 do wartości 1 i usunięciu klucza 8.

Rozwiązanie

Zadanie 4

[Reprezentacja]
Zaproponuj reprezentację komputerową kolejki dwumianowej i kopca Fibonacciego, która umożliwia realizację wszystkich operacji z podanymi kosztami.

Rozwiązanie

Kolejka dwumianowa: W każdym węźle pola: klucz, ojciec, lewy syn, prawy brat; wskaźniki do brata w korzeniach wykorzystywane do utrzymywania listy drzew; listy braci (i korzeni) cykliczne.
Kopiec Fibonacciego: Podobnie, ale listy braci dwukierunkowe oraz dodatkowe pole z flagą logiczną, mówiącą czy węzeł stracił syna od czasu ostatniego odcięcia. Dostęp do listy drzew przez wskaźnik do korzenia z najmniejszym kluczem.

Zadanie 5

[Meld i DelMin]
Napisz pseudokod operacji Meld i DelMin na kolejkach dwumianowych.

Rozwiązanie

Zobacz podrozdz. 19.2 (konieczne są drobne modyfikacje).

Zadanie 6

[Koszty operacji]
Jakie są pesymistyczne (nie zamortyzowane) koszty poszczególnych operacji na kopcach Fibonacciego?

Rozwiązanie

MakePQ: 1
Insert: 1
FindMin: 1
DelMin n
DecreaseKey n
Delete n
Meld 1

Zadanie 7

[Pseudokod]

Napisz pseudokod operacji DelMin i DecreaseKey na kopcach Fibonacciego.

Rozwiązanie

Zobacz [CLRS], podrozdz. 20.2 i 20.3.

Zadanie 8

[Zaznaczanie węzłów]
Węzeł 7 nie został zaznaczony w ostatniej fazie operacji DecreaseKey w animacji z wykładu, pomimo że właśnie stracił jednego syna. Powodem jest to, że podczas wykonywania DecreaseKey nie ma potrzeby zaznaczać korzeni (zastanów się, dlaczego!). Jednak jego sąsiad 18 jest zaznaczony. Jak mogło do tego dojść?

Rozwiązanie

Węzeł 18 został zaznaczony, kiedy jeszcze nie był korzeniem, podczas wcześniejszej operacji DecreaseKey lub Delete, a potem stał sie korzeniem w wyniku operacji DelMin.

Zadanie 9

[Wysokość drzewa]
Czy wysokość drzewa w \( n \)-wierzchołkowym kopcu Fibonacciego jest \( O(\lg n) \)?

Rozwiązanie

Nie. Nietrudno podać przykład ciągu operacji, który prowadzi do powstania drzewa-linii.

Zadanie 10

[Modyfikacja kopca Fibonacciego]

Czy możliwa jest taka modyfikacja kopca Fibonacciego, żeby zarówno operacja Insert, jak i DelMin miały koszt zamortyzowany \( o(\log n) \)?

Rozwiązanie

Nie, bo wtedy można by użyć takiej struktury danych do posortowania \( n \) elementów w czasie \( o(n\log n) \).