Zaawansowane algorytmy i struktury danych/Ćwiczenia 14: Różnice pomiędzy wersjami
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 8: | Linia 8: | ||
c=2/3. | c=2/3. | ||
Zadanie. | Zadanie. | ||
| Linia 14: | Linia 17: | ||
Rozwiazanie. | Rozwiazanie. | ||
Niech x będzie pierwszym w"ez"lem na "scie"rce ze statycznego w"ez"la do korzenia takim, "re <math> |T_x|\ge | |||
FIB_{k-1}</math>. Ponadto niech $T1$, $T2$ oraz $T3$ b"ed"a drzewami odpowiednio: T z węzłem x jako stayczny liść (z obciętymi poddrzewami o korzeniach p,q, | FIB_{k-1}</math>. Ponadto niech $T1$, $T2$ oraz $T3$ b"ed"a drzewami odpowiednio: T z węzłem x jako stayczny liść (z obciętymi poddrzewami o korzeniach p,q, | ||
<math> T_p\otimes x</math>, oraz <math> T_q </math>. | <math> T_p\otimes x</math>, oraz <math> T_q </math>. | ||
Wersja z 11:40, 6 wrz 2006
Zadanie.
Jaka jest minimalna stała c taka, że dla każdego drzewa rozmiaru co najmniej 2 mamy
Rozwiązanie
c=2/3.
Zadanie.
Udowodnij indukcyjnie punkt (b) wzmocnionego lematu o kontrakcji.
Rozwiazanie.
Niech x będzie pierwszym w"ez"lem na "scie"rce ze statycznego w"ez"la do korzenia takim, "re . Ponadto niech $T1$, $T2$ oraz $T3$ b"ed"a drzewami odpowiednio: T z węzłem x jako stayczny liść (z obciętymi poddrzewami o korzeniach p,q,
, oraz .
Wtedy oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle |T3| < FIB_{k-1}M/math>. Po (k-1)-szej redukcji drzewa T1$ oraz T2 sa zredukowane do jednego w"ez"la z jednym statycznym li"sciem , dzi"eki za"lo"reniu indukcyjnemu (b) . Wszystkie w"ez"ly T3 staj"a si"e li"s"cmi po (k-2)-giej redukcji dzi"eki za"lo"reniu indukcyjnemu (b). W konsekwencji po redukcji k-1 korze"n ca"lego drzewa T ma jedynego nast"epnika x' takiego, "re x'=x lub <math> x'\in T_p} . Nast"epnie w k-tej redukcji korze"n ma jedyne dowi"azanie do w"ez"la statycznego v. Ko"nczy to dow"od indukcyjny punktu (b).
