ASD Ćwiczenia 9: Różnice pomiędzy wersjami

Wersja z 08:10, 3 sie 2006

Ćwiczenie [Dowód lematu 1]

Udowodnij lemat 1

Rozwiązanie

Indukcja po $k$ .

Ćwiczenie [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} + 𝟐^{𝟓} + 2^{3}$ .

Ćwiczenie [Kolejka dwumianowa 2]

Narysuj (a) kolejkę dwumianową (b) kopiec Fibonacciego otrzymane w wyniku wstawienia do początkowo pustej struktury kolejno kluczy 3, 1, 4, 15, 9, 2, 6, wykonaniu Delmin, zmniejszeniu klucza 15 do wartości 5 i usunięciu klucza 4.

Rozwiązanie

- - - - rysunek

Ćwiczenie [Kolejka dwumianowa 3]

Zaproponuj reprezentację komputerową kolejki dwumianowej i kopca Fibonacciego, która umożliwiarealizację 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.

Ćwiczenie [Meld i DelMin]

Napisz pseudokod operacji Meld i DelMin na kolejkach dwumianowych.

Rozwiązanie

Zobacz [CLRS], podrozdz. 19.2 (konieczne są drobne modyfikacje). Zadanie Jakie są pesymistyczne (nie zamortyzowane) koszty poszczególnych operacji nakopcach Fibonacciego? Rozwiązanie MakePQ: 1 Insert: 1 FindMin: 1 DelMin n DecreaseKey n Delete n Meld 1 ZadanieNapisz pseudokod operacji DelMin i DecreaseKey na kopcach Fibonacciego. RozwiązanieZobacz [CLRS], podrozdz. 20.2 i 20.3. ZadanieCzy wysokość drzewa w $n$ -wierzchołkowym kopcu Fibonacciego jest $O (\lg n)$ ? RozwiązanieNie. Nietrudno podać przykład ciągu operacji, który prowadzi do powstania drzewa-linii. ZadanieCzy możliwa jest taka modyfikacja kopca Fibonacciego, żeby zarówno operacja Insert, jak i DelMin miały koszt zamortyzowany $o (\log n)$ ? RozwiązanieNie, bo wtedy można by użyc takiej struktury danych do posortowania $n$ elementów w czasie $o (n \log n)$ .

@@ Linia 1: / Linia 1: @@
-ZadanieUdowodnij Lemat 1.
+{{cwiczenie|[Dowód lematu 1]|dowod_lematu1|Udowodnij lemat 1
-RozwiązanieIndukcja po <math>k</math>.
-ZadanieDo początkowo pustej kolejki dwumianowej wstawiamy klucze 1, 2, ..., 1000.Czy teraz w jej skład wchodzi drzewo <math>B_5</math>?
+Rozwiązanie
-RozwiązanieTak, bo <math>1000 = 2^9+2^8+2^7+2^6+\mathbf{2^5}+2^3</math>.
-ZadanieNarysuj (a) kolejkę dwumianową (b) kopiec Fibonacciego otrzymane w wyniku wstawienia do początkowo pustej struktury kolejno kluczy 3, 1, 4, 15, 9, 2, 6, wykonaniu Delmin, zmniejszeniu klucza 15 do wartości 5 i usunięciu klucza 4.
+Indukcja po <math>k</math>.
-Rozwiązanie********** rysunek ***************
+}}
-ZadanieZaproponuj reprezentację komputerową kolejki dwumianowej i kopca Fibonacciego, która umożliwiarealizację wszystkich operacji z podanymi kosztami.
-RozwiązanieKolejka 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.
+{{cwiczenie|[Kolejka dwumianowa 1]|kolejka_dwumianowa1|
+Do początkowo pustej kolejki dwumianowej wstawiamy klucze 1, 2, ..., 1000. Czy teraz w jej skład wchodzi drzewo <math>B_5</math>?
+Rozwiązanie
+Tak, bo <math>1000 = 2^9+2^8+2^7+2^6+\mathbf{2^5}+2^3</math>.
+}}
+{{cwiczenie|[Kolejka dwumianowa 2]|kolejka_dwumianowa2|
+Narysuj
+(a) kolejkę dwumianową
+(b) kopiec Fibonacciego otrzymane w wyniku wstawienia do początkowo pustej struktury kolejno kluczy 3, 1, 4, 15, 9, 2, 6, wykonaniu Delmin, zmniejszeniu klucza 15 do wartości 5 i usunięciu klucza 4.
+Rozwiązanie
+********** rysunek
+}}
+{{cwiczenie|[Kolejka dwumianowa 3]|kolejka_dwumianowa3|
+Zaproponuj reprezentację komputerową kolejki dwumianowej i kopca Fibonacciego, która umożliwiarealizację 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.
-ZadanieNapisz pseudokod operacji Meld i DelMin na kolejkach dwumianowych.
-RozwiązanieZobacz [CLRS], podrozdz. 19.2 (konieczne są drobne modyfikacje).
+}}
+{{cwiczenie|[Meld i DelMin]|meld_delmin|
+Napisz pseudokod operacji Meld i DelMin na kolejkach dwumianowych.
+Rozwiązanie
+Zobacz [CLRS], podrozdz. 19.2 (konieczne są drobne modyfikacje).
 Zadanie Jakie są pesymistyczne (nie zamortyzowane) koszty poszczególnych operacji nakopcach Fibonacciego?
 Rozwiązanie MakePQ: 1 Insert: 1 FindMin: 1 DelMin n DecreaseKey n Delete n Meld 1
@@ Linia 18: / Linia 52: @@
 ZadanieCzy możliwa jest taka modyfikacja kopca Fibonacciego, żeby zarówno operacja Insert, jak i DelMin miały koszt zamortyzowany <math>o(\log n)</math>?
 RozwiązanieNie, bo wtedy można by użyc takiej struktury danych do posortowania <math>n</math> elementów w czasie <math>o(n\log n)</math>.
+}}

ASD Ćwiczenia 9: Różnice pomiędzy wersjami

Wersja z 08:10, 3 sie 2006

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia