Zaawansowane algorytmy i struktury danych/Ćwiczenia 14

From Studia Informatyczne

Spis treści

Zadanie 1

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

|Contract(T)| \le c\cdot |T|

Rozwiązanie

c=2/3.


Zadanie 2

Uzasadnij, dlaczego |T_k|=Fib_k<math> oraz <math> Contract(T_k)=T_{k-1}.

Rozwiazanie

Wynika to z rekurencji definiującej drzewa T_k

Zadanie 3

Udowodnij, że TIME'(Fib_k+1)>k.


Rozwiązanie

.

Weź statyczny liść v, dodatkowo korzeń r i zbuduj drzewo, którego korzeniem jest r, następnikiem r jest korzeń T_p,

oraz dodatkowo korzeń T_p ma syna v.


Zadanie 4

Udowodnij indukcyjnie punkt (b) wzmocnionego lematu o kontrakcji.

Rozwiązanie

Niech x będzie pierwszym węzłem na ścieżce ze statycznego węzła do korzenia takim, że |T_x|\ge FIB_{k-1}.

Ponadto niech T1, T2 oraz T3 będą drzewami zdefiniowanymi następująco:

T1 jest równy T z węzłem x jako statyczny liść (z obciętymi poddrzewami o korzeniach p,q, T2 = T_p\otimes x, oraz T3= T_q. Wtedy |T1|, |T2| \le FIB_{k-1} oraz |T3| < FIB_{k-1}.

Po (k-1)-szej redukcji drzewa T1 oraz T są

zredukowane do jednego węzła z jednym statycznym liściem dzięki założeniu indukcyjnemu (b) . Wszystkie węzły T3 stają się liśćmi po (k-2)-giej redukcji dzięki założeniu indukcyjnemu (b).

W konsekwencji, po redukcji k-1 korzeń całego drzewa T ma jedynego następnika x' takiego, że x'=x lub

x'\in T_p. Następnie w k-tej redukcji korzeń ma jedyne dowiązanie do węzła statycznego v. Kończy to dowód indukcyjny punktu (b).


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 O(\log n).

Rozwiązanie

.

Liczba zmodyfikowanych kontrakcji jest nie mniejsza niż liczba kontrakcji, które opisujemy w module, a więc w dlaszym ciągu logarytmiczna.