Zaawansowane algorytmy i struktury danych/Ćwiczenia 14

Z Studia Informatyczne
< Zaawansowane algorytmy i struktury danych
Wersja z dnia 19:12, 25 wrz 2006 autorstwa Dorota (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zadanie 1

Jaka jest minimalna stała taka, że dla każdego drzewa rozmiaru co najmniej 2 mamy

Rozwiązanie


Zadanie 2

Uzasadnij, dlaczego .

Rozwiazanie

Zadanie 3

Udowodnij, że .


Rozwiązanie


Zadanie 4

Udowodnij indukcyjnie punkt (b) wzmocnionego lematu o kontrakcji.

Rozwiązanie


Zadanie 5

Przypuśćmy, że zmieniamy definicje kontrakcji. Najpierw wykonujemy Rake, a potem (po zakończeniu Rake) wykonujemy Compress. Udowodnij, że liczba kontrakcji jest w dalszym ciągu .

Rozwiązanie