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

Aktualna wersja na dzień 10:08, 6 paź 2020

Ć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 [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

Ćwiczenie [Reprezentacja]

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

Rozwiązanie

Ćwiczenie [Meld i DelMin]

Napisz pseudokod operacji Meld i DelMin na kolejkach dwumianowych.

Rozwiązanie

Ćwiczenie [Koszty operacji]

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

Rozwiązanie

Ćwiczenie [Pseudokod]

Napisz pseudokod operacji DelMin i DecreaseKey na kopcach Fibonacciego.

Rozwiązanie

Ćwiczenie [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

Ćwiczenie [Wysokość drzewa]

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

Rozwiązanie

Ćwiczenie [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)$ .

@@ 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ązanieTak, bo <math>1000 = 2^9+2^8+2^7+2^6+\mathbf{2^5}+2^3</math>.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">
-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.
+'''Rozwiązanie'''
-Rozwiązanie********** rysunek ***************
+<div class="mw-collapsible-content" style="display:none">
-ZadanieZaproponuj reprezentację komputerową kolejki dwumianowej i kopca Fibonacciego, która umożliwiarealizację wszystkich operacji z podanymi kosztami.
+Indukcja po <math>k</math>.
-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.
+</div>
-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.
+</div>
-ZadanieNapisz pseudokod operacji Meld i DelMin na kolejkach dwumianowych.
-RozwiązanieZobacz [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 <math>n</math>-wierzchołkowym kopcu Fibonacciego jest <math>O(\lg n)</math>?
+{{cwiczenie|[Kolejka dwumianowa 1]|kolejka_dwumianowa1|
-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 <math>o(\log n)</math>?
+Do początkowo pustej kolejki dwumianowej wstawiamy klucze 1, 2, ..., 1000. Czy teraz w jej skład wchodzi drzewo <math>B_5</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>.
+}}
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">
+'''Rozwiązanie'''
+<div class="mw-collapsible-content" style="display:none">
+Tak, bo <math>1000 = 2^9+2^8+2^7+2^6+\mathbf{2^5}+2^3</math>.
+</div>
+</div>
+{{cwiczenie|[Przykładowy ciąg operacji]|kolejka_dwumianowa2|
+Narysuj <br>
+(a) kolejkę dwumianową <br>
+(b) kopiec Fibonacciego <br>
+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.
+}}
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">
+'''Rozwiązanie'''
+<div class="mw-collapsible-content" style="display:none">
+(a) [[Grafika:Bh_ex.png]]
+(b) [[Grafika:Fibh_ex.png]]
+</div>
+</div>
+{{cwiczenie|[Reprezentacja]|kolejka_dwumianowa3|
+Zaproponuj reprezentację komputerową kolejki dwumianowej i kopca Fibonacciego, która umożliwia realizację wszystkich operacji z podanymi kosztami.
+}}
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">
+'''Rozwiązanie'''
+<div class="mw-collapsible-content" style="display:none">
+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.
+</div>
+</div>
+{{cwiczenie|[Meld i DelMin]|meld_delmin|
+Napisz pseudokod operacji Meld i DelMin na kolejkach dwumianowych.
+}}
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">
+'''Rozwiązanie'''
+<div class="mw-collapsible-content" style="display:none">
+Zobacz [[ASD_Moduł_9#CLRS|[CLRS]]], podrozdz. 19.2 (konieczne są drobne modyfikacje).
+</div>
+</div>
+{{cwiczenie|[Koszty operacji]|koszty_operacji|
+Jakie są pesymistyczne (nie zamortyzowane) koszty poszczególnych operacji na kopcach Fibonacciego?
+}}
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">
+'''Rozwiązanie'''
+<div class="mw-collapsible-content" style="display:none">
+MakePQ: 1
+Insert: 1
+FindMin: 1
+DelMin n
+DecreaseKey n
+Delete n
+Meld 1
+</div>
+</div>
+{{cwiczenie|[Pseudokod]|pseudokod|
+Napisz pseudokod operacji DelMin i DecreaseKey na kopcach Fibonacciego.
+}}
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">
+'''Rozwiązanie'''
+<div class="mw-collapsible-content" style="display:none">
+Zobacz [[ASD_Moduł_9#CLRS|[CLRS]]], podrozdz. 20.2 i 20.3.
+</div>
+</div>
+{{cwiczenie|[Zaznaczanie węzłów]|zaznaczanie|
+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ść?
+}}
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">
+'''Rozwiązanie'''
+<div class="mw-collapsible-content" style="display:none">
+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.
+</div>
+</div>
+{{cwiczenie|[Wysokość drzewa]|wysokosc_drzewa|
+Czy wysokość drzewa w <math>n</math>-wierzchołkowym kopcu Fibonacciego jest <math>O(\lg n)</math>?
+}}
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">
+'''Rozwiązanie'''
+<div class="mw-collapsible-content" style="display:none">
+Nie. Nietrudno podać przykład ciągu operacji, który prowadzi do powstania drzewa-linii.
+</div>
+</div>
+{{cwiczenie|[Modyfikacja kopca Fibonacciego]|modyfikacja_kopca|
+Czy możliwa jest taka modyfikacja kopca Fibonacciego, żeby zarówno operacja Insert, jak i DelMin miały koszt zamortyzowany <math>o(\log n)</math>?
+}}
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">
+'''Rozwiązanie'''
+<div class="mw-collapsible-content" style="display:none">
+Nie, bo wtedy można by użyć takiej struktury danych do posortowania <math>n</math> elementów w czasie <math>o(n\log n)</math>.
+</div>
+</div>

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

Aktualna wersja na dzień 10:08, 6 paź 2020

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia