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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Amal (dyskusja | edycje)
125 edycji
mNie podano opisu zmian
mNie podano opisu zmian
 
(Nie pokazano 19 wersji utworzonych przez 3 użytkowników)
Linia 1: Linia 1:
Zadanie
{{cwiczenie|[Dowód lematu 1]|dowod_lematu1|Udowodnij lemat 1
Udowodnij Lemat 1.
}}


Rozwiązanie
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Indukcja po $k$.
'''Rozwiązanie'''
<div class="mw-collapsible-content" style="display:none">
Indukcja po <math>k</math>.
</div>
</div>


Zadanie
 
 
 
 
 
{{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>?
}}
<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?
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">


Rozwiązanie
MakePQ: 1  
MakePQ: 1  
Insert: 1  
Insert: 1  
FindMin: 1  
FindMin: 1  
DelMin n  
DelMin n  
DecreaseKey n  
DecreaseKey n  
Delete n  
Delete n  
Meld 1
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>

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

Ćwiczenie [Dowód lematu 1]

Udowodnij lemat 1

Rozwiązanie




Ćwiczenie [Kolejka dwumianowa 1]

Do początkowo pustej kolejki dwumianowej wstawiamy klucze 1, 2, ..., 1000. Czy teraz w jej skład wchodzi drzewo B5?

Rozwiązanie




Ć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

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=ASD_Ćwiczenia_9&oldid=78071”