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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Dorota (dyskusja | edycje)
376 edycji
Nie podano opisu zmian
mNie podano opisu zmian
 
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 35: Linia 35:
(b) kopiec Fibonacciego <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.
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'''  
Linia 44: Linia 44:
</div>
</div>


}}
 




Linia 51: 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'''  
Linia 61: Linia 61:
</div>
</div>


}}
 




Linia 68: 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 77: Linia 77:
</div>
</div>


}}




Linia 84: 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 105: Linia 104:
</div>
</div>


}}
 




Linia 112: 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 120: 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 132: Linia 131:
</div>
</div>
</div>
</div>
}}
 




Linia 138: 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 146: Linia 145:
</div>
</div>
</div>
</div>
}}
 




Linia 153: 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'''  
Linia 161: Linia 160:
</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”