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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Tprybick (dyskusja | edycje)
718 edycji
Nie podano opisu zmian
mNie podano opisu zmian
 
(Nie pokazano 9 wersji utworzonych przez 3 użytkowników)
Linia 1: Linia 1:
{{cwiczenie|[Dowód lematu 1]|dowod_lematu1|Udowodnij lemat 1
{{cwiczenie|[Dowód lematu 1]|dowod_lematu1|Udowodnij lemat 1
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Rozwiązanie'''
<div class="mw-collapsible-content" style="display:none">
Indukcja po <math>k</math>.
</div>
</div>


Rozwiązanie


Indukcja po <math>k</math>.
}}




Linia 12: Linia 17:


Do początkowo pustej kolejki dwumianowej wstawiamy klucze 1, 2, ..., 1000. Czy teraz w jej skład wchodzi drzewo <math>B_5</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ązanie  
<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>.
Tak, bo <math>1000 = 2^9+2^8+2^7+2^6+\mathbf{2^5}+2^3</math>.
</div>
</div>


}}








{{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
{{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>


********** rysunek


}}








{{cwiczenie|[Kolejka dwumianowa 3]|kolejka_dwumianowa3|
{{cwiczenie|[Reprezentacja]|kolejka_dwumianowa3|
Zaproponuj reprezentację komputerową kolejki dwumianowej i kopca Fibonacciego, która umożliwiarealizację wszystkich operacji z podanymi kosztami.
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.


Rozwiązanie
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>


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.
}}




Linia 52: Linia 68:
{{cwiczenie|[Meld i DelMin]|meld_delmin|
{{cwiczenie|[Meld i DelMin]|meld_delmin|
Napisz pseudokod operacji Meld i DelMin na kolejkach dwumianowych.
Napisz pseudokod operacji Meld i DelMin na kolejkach dwumianowych.
 
}}
Rozwiązanie
<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).
Zobacz [[ASD_Moduł_9#CLRS|[CLRS]]], podrozdz. 19.2 (konieczne są drobne modyfikacje).
</div>
</div>


}}




Linia 63: Linia 82:


{{cwiczenie|[Koszty operacji]|koszty_operacji|
{{cwiczenie|[Koszty operacji]|koszty_operacji|
Jakie są pesymistyczne (nie zamortyzowane) koszty poszczególnych operacji nakopcach 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>


}}




Linia 82: Linia 111:
{{cwiczenie|[Pseudokod]|pseudokod|
{{cwiczenie|[Pseudokod]|pseudokod|
Napisz pseudokod operacji DelMin i DecreaseKey na kopcach Fibonacciego.
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">


Rozwiązanie
Zobacz [[ASD_Moduł_9#CLRS|[CLRS]]], podrozdz. 20.2 i 20.3.
</div>
</div>


Zobacz [[ASD_Moduł_9#CLRS|[CLRS]]], podrozdz. 20.2 i 20.3.
 
 
{{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>




Linia 93: Linia 137:
{{cwiczenie|[Wysokość drzewa]|wysokosc_drzewa|
{{cwiczenie|[Wysokość drzewa]|wysokosc_drzewa|
Czy wysokość drzewa w <math>n</math>-wierzchołkowym kopcu Fibonacciego jest <math>O(\lg n)</math>?
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">


Rozwiązanie
Nie. Nietrudno podać przykład ciągu operacji, który prowadzi do powstania drzewa-linii.
</div>
</div>


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




Linia 104: Linia 152:
{{cwiczenie|[Modyfikacja kopca Fibonacciego]|modyfikacja_kopca|
{{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>?
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">


Rozwiązanie
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>.
Nie, 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>
 
</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”