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 2 wersji utworzonych przez 2 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">
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Linia 9: Linia 9:
</div>
</div>


}}
 




Linia 17: 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>?
 
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Rozwiązanie'''  
'''Rozwiązanie'''  
Linia 25: Linia 25:
</div>
</div>


}}
 




Linia 31: Linia 31:


{{cwiczenie|[Przykładowy ciąg operacji]|kolejka_dwumianowa2|
{{cwiczenie|[Przykładowy ciąg operacji]|kolejka_dwumianowa2|
Narysuj  
Narysuj <br>
(a) kolejkę dwumianową  
(a) kolejkę dwumianową <br>
(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.
(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">
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Rozwiązanie'''  
'''Rozwiązanie'''  
<div class="mw-collapsible-content" style="display:none">
<div class="mw-collapsible-content" style="display:none">
(a) [[Grafika:Bh_ex.png]]
(a) [[Grafika:Bh_ex.png]]
(b) [[Grafika:Fibh_ex.png]]
</div>
</div>
</div>
</div>


}}
 




Linia 49: Linia 51:
{{cwiczenie|[Reprezentacja]|kolejka_dwumianowa3|
{{cwiczenie|[Reprezentacja]|kolejka_dwumianowa3|
Zaproponuj reprezentację komputerową kolejki dwumianowej i kopca Fibonacciego, która umożliwia realizację 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">
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Rozwiązanie'''  
'''Rozwiązanie'''  
<div class="mw-collapsible-content" style="display:none">
<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.
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.
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 59: Linia 61:
</div>
</div>


}}
 




Linia 66: 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.
 
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Rozwiązanie'''  
'''Rozwiązanie'''  
Linia 75: Linia 77:
</div>
</div>


}}




Linia 82: Linia 83:
{{cwiczenie|[Koszty operacji]|koszty_operacji|
{{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">
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Rozwiązanie'''  
'''Rozwiązanie'''  
Linia 103: Linia 104:
</div>
</div>


}}
 




Linia 110: 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">
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Rozwiązanie'''  
'''Rozwiązanie'''  
Linia 118: Linia 119:
</div>
</div>
</div>
</div>
}}
 




{{cwiczenie|[Zaznaczanie węzłów]|zaznaczanie|
{{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ść?
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">
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Rozwiązanie'''  
'''Rozwiązanie'''  
Linia 130: Linia 131:
</div>
</div>
</div>
</div>
}}
 




Linia 136: 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">
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Rozwiązanie'''  
'''Rozwiązanie'''  
Linia 144: Linia 145:
</div>
</div>
</div>
</div>
}}
 




Linia 151: 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">
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Rozwiązanie'''  
'''Rozwiązanie'''  
<div class="mw-collapsible-content" style="display:none">
<div class="mw-collapsible-content" style="display:none">


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>.
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>
</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”