ASD Ćwiczenia 9: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
mNie 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"> | |||
'''Rozwiązanie''' | |||
<div class="mw-collapsible-content" style="display:none"> | |||
Indukcja po <math>k</math>. | Indukcja po <math>k</math>. | ||
</div> | |||
</div> | |||
}} | }} | ||
| Linia 13: | Linia 18: | ||
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> | |||
}} | }} | ||
| Linia 27: | Linia 35: | ||
(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. | (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 | <div class="mw-collapsible mw-made=collapsible mw-collapsed"> | ||
'''Rozwiązanie''' | |||
********** rysunek | <div class="mw-collapsible-content" style="display:none"> | ||
**************** rysunek | |||
</div> | |||
</div> | |||
}} | }} | ||
| Linia 36: | Linia 47: | ||
{{cwiczenie|[ | {{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. | ||
Rozwiązanie | <div class="mw-collapsible mw-made=collapsible mw-collapsed"> | ||
'''Rozwiązanie''' | |||
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. | <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. | 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> | |||
}} | }} | ||
| Linia 53: | Linia 67: | ||
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 65: | Linia 83: | ||
Jakie są pesymistyczne (nie zamortyzowane) koszty poszczególnych operacji na kopcach Fibonacciego? | Jakie są pesymistyczne (nie zamortyzowane) koszty poszczególnych operacji na kopcach Fibonacciego? | ||
Rozwiązanie | <div class="mw-collapsible mw-made=collapsible mw-collapsed"> | ||
'''Rozwiązanie''' | |||
<div class="mw-collapsible-content" style="display:none"> | |||
MakePQ: 1 | MakePQ: 1 | ||
| Linia 80: | Linia 100: | ||
Meld 1 | Meld 1 | ||
</div> | |||
</div> | |||
}} | }} | ||
| Linia 89: | Linia 111: | ||
Napisz pseudokod operacji DelMin i DecreaseKey na kopcach Fibonacciego. | Napisz pseudokod operacji DelMin i DecreaseKey na kopcach Fibonacciego. | ||
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. 20.2 i 20.3. | Zobacz [[ASD_Moduł_9#CLRS|[CLRS]]], podrozdz. 20.2 i 20.3. | ||
</div> | |||
</div> | |||
}} | }} | ||
| Linia 100: | Linia 126: | ||
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>? | ||
Rozwiązanie | <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. | Nie. Nietrudno podać przykład ciągu operacji, który prowadzi do powstania drzewa-linii. | ||
</div> | |||
</div> | |||
}} | }} | ||
| Linia 111: | Linia 141: | ||
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>? | ||
Rozwiązanie | <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ż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życ takiej struktury danych do posortowania <math>n</math> elementów w czasie <math>o(n\log n)</math>. | ||
</div> | |||
</div> | |||
}} | }} | ||
Wersja z 15:41, 9 sie 2006
Ćwiczenie [Dowód lematu 1]
{{{3}}}
Ćwiczenie [Kolejka dwumianowa 1]
{{{3}}}
Ćwiczenie [Kolejka dwumianowa 2]
{{{3}}}
Ćwiczenie [Reprezentacja]
{{{3}}}
Ćwiczenie [Meld i DelMin]
{{{3}}}
Ćwiczenie [Koszty operacji]
{{{3}}}
Ćwiczenie [Pseudokod]
{{{3}}}
Ćwiczenie [Wysokość drzewa]
{{{3}}}
Ćwiczenie [Modyfikacja kopca Fibonacciego]
{{{3}}}
