Zaawansowane algorytmy i struktury danych/Ćwiczenia 14: Różnice pomiędzy wersjami

Wersja z 10:48, 11 wrz 2006

Zadanie 1

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

| C o n t r a c t (T) | \leq c \cdot | T |

Rozwi?zanie

Zadanie 2

Uzasadnij dlaczego $| T_{k} | = F i b_{k} < m a t h > o r a z < m a t h > C o n t r a c t (T_{k}) = T_{k - 1}$ .

Rozwi?zanie

Wynika to z rekurencji definiuj?cej drzewa $T_{k}$

Zadanie 3

Udowdnij, ?e $T I M E^{'} (F i b_{k} + 1) > k$ .

Rozwi?zanie

.

Wez statyczny li?? v, dodatkowt 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} | \geq F I B_{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, $T 2 = T_{p} \otimes x$ , oraz $T 3 = T_{q}$ . Wtedy $| T 1 |, | T 2 | \leq F I B_{k - 1}$ oraz $| T 3 | < F I B_{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"n 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"od indukcyjny punktu (b).

Zadanie 5

Przypu??my, ?e zmieniamy definicje kontrakcji. Najpierw wykonujemy Rake, a potem (po zako?czeniu Rake) wykonujemy Compress. Udowodnij, ?e liczb? kontrakcji jest w dalszym ci?gu $O (\log n)$ .

Rozwi?zanie

@@ Linia 1: / Linia 1: @@
-Zadanie.
-Jaka jest minimalna stała c taka, że dla każdego drzewa rozmiaru co najmniej 2 mamy
+== Zadanie 1 ==
+Jaka jest minimalna sta?a c taka, ?e dla ka?dego drzewa rozmiaru co najmniej 2 mamy
 <center><math> |Contract(T)| \le c\cdot |T| </math> </center>
-Rozwiązanie
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwi?zanie'''  <div class="mw-collapsible-content" style="display:none">
 c=2/3.
+</div>
+</div>
-Zadanie.
+== Zadanie 2 ==
 Uzasadnij dlaczego <math>|T_k|=Fib_k<math> oraz <math> Contract(T_k)=T_{k-1}</math>.
-Rozwiazanie.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwi?zanie'''  <div class="mw-collapsible-content" style="display:none">
-Wynika to z rekurencji definiującej drzewa <math> T_k </math>
+Wynika to z rekurencji definiuj?cej drzewa <math> T_k </math>
+</div>
+</div>
-Zadanie.
+== Zadanie 3 ==
-Udowdnij, że <math> TIME'(Fib_k+1)>k</math>.
+Udowdnij, ?e <math> TIME'(Fib_k+1)>k</math>.
-Rozwiązanie.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwi?zanie'''  <div class="mw-collapsible-content" style="display:none">.
-Wez statyczny liść v, dodatkowt korzeń r i zbuduj drzewo którego korzeniem jest r, następnikiem r jest korzeń <math> T_p</math>, oraz dodatkowo korzeń <math> T_p </math>
+Wez statyczny li?? v, dodatkowt korze? r i zbuduj drzewo kt?rego korzeniem jest r, nast?pnikiem r jest korze? <math> T_p</math>, oraz dodatkowo korze? <math> T_p </math>
 ma syna v.
+</div>
+</div>
-Zadanie.
+== Zadanie 4 ==
 Udowodnij indukcyjnie punkt (b) wzmocnionego lematu o kontrakcji.
-Rozwiazanie.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwi?zanie'''  <div class="mw-collapsible-content" style="display:none">
-Niech  x będzie  pierwszym węzłem na ścieżce ze statycznego węzła do korzenia takim, że <math> |T_x|\ge
+Niech  x b?dzie  pierwszym w?z?em na ?cie?ce ze statycznego w?z?a do korzenia takim, ?e <math> |T_x|\ge
 FIB_{k-1}</math>.
-Ponadto niech  T1, T2 oraz T3 będą drzewami zdefiniowanymi następująco.
+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,
+T1 jest r?wny T z w?z?em x jako statyczny li?? (z obci?tymi poddrzewami o korzeniach p,q,
 <math> T2 = T_p\otimes x</math>, oraz <math> T3= T_q </math>.
 Wtedy  <math>|T1|, |T2| \le FIB_{k-1}</math>  oraz <math> |T3| < FIB_{k-1}</math>.
-Po  (k-1)-szej redukcji drzewa  T1 oraz  T są
+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
+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?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"n całego drzewa T ma jedynego następnika x' takiego, że x'=x lub
+W konsekwencji po redukcji  k-1 korze"n ca?ego drzewa T ma jedynego nast?pnika x' takiego, ?e x'=x lub
-<math> x'\in T_p</math>. Następnie w  k-tej redukcji  korzeń ma jedyne dowiązanie do węzła statycznego v. Kończy to
+<math> x'\in T_p</math>. Nast?pnie w  k-tej redukcji  korze? ma jedyne dowi?zanie do w?z?a statycznego v. Ko?czy to
 dow"od indukcyjny punktu (b).
+</div>
+</div>
-Zadanie.
+== Zadanie 5 ==
-Przypuśćmy, że zmieniamy definicje kontrakcji. Najpierw wykonujemy Rake, a potem (po zakończeniu Rake) wykonujemy Compress.
+Przypu??my, ?e zmieniamy definicje kontrakcji. Najpierw wykonujemy Rake, a potem (po zako?czeniu Rake) wykonujemy Compress.
-Udowodnij, że liczbą kontrakcji jest w dalszym ciągu <math> O(\log n)</math>.
+Udowodnij, ?e liczb? kontrakcji jest w dalszym ci?gu <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">.
-Liczba zmodyfikowanych  kontrakcji jest nie mniejsza niż liczba kontrakcji które opisujemy w module, a więc w dlaszym ciągu logarytmiczna.
+Liczba zmodyfikowanych  kontrakcji jest nie mniejsza ni? liczba kontrakcji kt?re opisujemy w module, a wi?c w dlaszym ci?gu logarytmiczna.
+</div>
+</div>

Zaawansowane algorytmy i struktury danych/Ćwiczenia 14: Różnice pomiędzy wersjami

Wersja z 10:48, 11 wrz 2006

Spis treści

Zadanie 1

Zadanie 2

Zadanie 3

Zadanie 4

Zadanie 5

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia