Zaawansowane algorytmy i struktury danych/Ćwiczenia 14
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwaniaZadanie 1
Jaka jest minimalna stała
taka, że dla każdego drzewa rozmiaru co najmniej 2 mamyRozwią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