Zaawansowane algorytmy i struktury danych/Wykład 14: Różnice pomiędzy wersjami

Aktualna wersja na dzień 22:15, 11 wrz 2023

Algorytmy równoległe II

W module tym zajmiemy się obliczaniem wyrażeń arytmetycznych i równoległymi obliczeniami na drzewach związanymi z tzw. kontrakcją drzew. W dużym stopniu w module tym możemy zapomnieć o maszynie PRAM i przyjąć, że naszym modelem obliczeń równoległych jest drzewo (lub graf acykliczny). Czas równoległy to wysokość drzewa, a liczba procesorów to liczba węzłów. Węzły odpowiadają akcjom do wykonania, a drzewo (lub ogólniej graf acykliczny) odpowiada wymuszaniu pewnej kolejności wykonywania akcji. W jednym równoległym kroku możemy wykonać jednocześnie wszystkie te akcje, dla których akcje poprzedzające je w drzewie (grafie) są już wykonane.

Czasami dana akcja nie musi czekac na zakonczenie wszystkich poprzedzających ja akcji, a może wykonywać jakąś pożyteczną pracę wcześniej, jeśli tylko część informacji potrzebnej do wykonania tej akcji jest obliczona. Ta część informacji to na przykład obliczona wartość jednego z poprzedników danego węzła. Pomimo, że drugi poprzednik się jeszcze liczy możemy zacząc liczyć częsciowe wyniki związane z tym węzłem.

Zasadniczy problem to jak przekształcić (spłaszczyć) drzewo chude (o dużej wysokości) w semantycznie równoważne drzewo o małej wysokości nie zmieniając istotnie rzędu liczby węzłów drzewa.

Obliczanie wyrażeń arytmetycznych: algorytm jednoczesnych podstawień

Zakładamy, że wyrażenie zadane jest przez program sekwencyjny (w skrócie PS). Program taki jest "sztywną" sekwencją operacji, bez instrukcji warunkowych. PS jest bardzo prostym modelem obliczeń sekwencyjnych. Bardziej precyzyjnie, definiujemy program sekwencyjny jako ciąg instrukcji przypisań postaci $x_{i} : = W_{i}$ , gdzie $W_{i}$ jest wyrażeniem arytmetycznym zawierającym $O (1)$ operacji. W przypadku gdy operacje są logiczne, PS nazywamy obwodem logicznym (ang. boolean circuit). Ogólnie problem obliczenia wartości obwodu logiczngo jest P-zupełny, podobnie jest dla arytmetycznych programów sekwencyjnych.

Problemy te są się w klasie NC, gdy graf związany z programem sekwencyjnym jest drzewem, a sam program odpowiada obliczaniu wyrażenia arytmetycznego, co będziemy dalej zakładać.

Zmienne w programie sekwencyjnym są ponumerowane. Jeśli po lewej stronie instrukcji przypisania jest zmienna $x_{i}$ a po prawej zmienna $x_{j}$ , to wymagamy, aby $j < i$ . Zakładamy, że struktura obliczeń jest drzewem oraz operacje są ze zbioru ${+, -, *, /}$ .

Obserwacja Program sekwencyjny odpowiada układowi arytmetycznemu w sensie poprzedniego modułu, jednakże motywacją zmiany terminologii ‘’układ arytmetyczny’’ na ‘’PS’’ jest sekwencyjny zapis. . W przypadku układu arytmetycznego, liczba węzłów odpowiada czasowi sekwencyjnemu, a wysokość czasowi równoległemu.

W module tym zajmiemy się, w sensie układu arytmetycznego, transformacją jednego układu na równoważny mu drugi układ, który ma małą (logarytmiczną) wysokość.

Sekwencyjna pojedyncza operacja podstawiania polega na zastąpieniu zmiennej $x_{j}$ w danym wyrażeniu $W_{i}$ , gdzie $i > j$ , przez $W_{j}$ oraz redukcji wyrażenia po podstawieniu. \myskip Mówimy, że zmienna $x_{j}$ jest "bezpieczna", gdy jej prawa strona w programie sekwencyjnym (wyrażenie $W_{j}$ ) zawiera co najwyżej jedną zmienną. W przykładzie poniżej 5 pierwszych zmiennych jest bezpiecznych.

Przykład

Rozważmy następujący program sekwencyjny $P$ :

$x 1 = 1$ , $x 2 = 2$ , $x 3 = 6$ , $x 4 = 4$ , $x 5 = x 3 + 2$ ,

$x 6 = x 2 + x 1$ , $x 7 = 3 * x 6 + 2 * x 5$ , $x 8 = 2 * x 7 + x 4$ .

Przykładowo, po wykonaniu wszystkich bezpiecznych podstawień (w tym wypadku tylko zastąpienie $x 5$ przez $x 3 + 2$ ) do prawej strony dla x7 otrzymujemy

x 7 = 3 * x 6 + 2 * x 3 + 4

.

Operacja Reduce polega na wykonaniu jednocześnie wszystkich bezpiecznych podstawień we wszystkich wyrażeniach $W_{i}$ . W programie rozważamy tylko te zmienne, które są istotne z punktu widzenia liczenia ostatecznego wyniku $x_{n}$ . Zmienne te nazywamy istotnymi. Są one osiągalne ze zmiennej $x_{n}$ w grafie programu. Oznaczmy przez Reduce(P) nowy program sekwencyjny, bez zmiennych nieistotnych.

Algorytm JP

(Algorytm Jednoczesnych-Podstawien)

repeat {Operacja Reduce}

for each $x_{i}$ do in parallel

wykonaj jednoczesnie wszystkie bezpieczne podstawienia w $W_{i}$ .

until $x_{n}$ obliczone;

Historia algorytmu dla przykładowego programu P danego powyżej wygląda następująco, gdzie $P = P_{0}, P_{i + 1} = R e d u c e (P_{i})$ .

$P_{1}$ :
    $x 3 = 6$ ; $x 6 = 3$ ;
    $x 7 = 3 * x 6 + 2 * x 3 + 4$ ;
    $x 8 = 2 * x 7 + 4$ .

$P_{2}$ :
    $x 7 = 25$ , $x 8 = 2 * x 7 + 4$ .

$P_{3}$ :
    $x 8 = 54$ .

Pokażemy, że algorytm wykonuje $O (\log n)$ iteracji. Udowodnimy bardzo precyjne oszacowanie: rozmiar najmniejszego programu sekwencyjnego, który wmaga $k$ iteracji jest równy $k$ -tej liczbie Fibonacciego. Jest to zaskakująco podobne do analogicznego faktu dla drzew AVL, czas równoległy odpowiada tutaj wysokości drzewa.

Równoległa kontrakcja drzew

Grafem obliczeń $T = 𝒢 (𝒫)$ programu sekwencyjnego $P$ jest skierowany graf acykliczny, którego węzły odpowiadają zmiennym biorącym aktualnie udział w obliczeniu $x_{n}$ . Synami węzła $x_{i}$ (zmiennej) są zmienne występujące w danym momencie w $W_{i}$ . Graf $T$ zawiera tylko węzły osiągalne z korzenia $x_{n}$ . Przez rozmiar rozumiemy liczbę węzłów grafu (liczbę zmiennych w przypadku PS).

Zauważmy, że w danej iteracji algorytmu JP rozmiar grafu $T$ może być znacznie mniejszy niż $n$ , ponieważ wiele zmiennych może być nieosiągalnych z korzenia.

Jedna iteracja Reduce ( $P_{i} \to P_{i + 1}$ ) odpowiada następującej operacji $C o n t r a c t (𝒢 (P_{i}))$ , patrz rysunek.

Rysunek 1. Składowe operacje jednej iteracji Contract(T): Compress oraz Rake.

W rzeczywistości możemy zapomnieć o algorytmie JP i maszynie PRAM. Obliczanie na drzewie jest samo w sobie sensownym modelem obliczeń równoległych. Czas równoległy jest liczbą iteracji, która przekształca początkowe drzewo w drzewo jednoelementowe.

Z każdą krawędzią $e = (x_{i}, x_{j})$ grafu $𝒢 (𝒫)$ jest związana pewna funkcja $f_{e} (x)$ postaci:

f_{e} (x) = \frac{a x + b}{c x + d}

gdzie $a, b, c, d$ są pewnymi stałymi.

Początkowo funkcja ta jest identycznościowa. Jeśli w danym momencie następnikami węzła $x_{i}$ są $x_{j}, x_{k}$ oraz $e 1 = (x_{i}, x_{j}), e 2 = (x_{i}, x_{k})$ , to wartością zmiennej $x_{i}$ jest: $f_{e 1} (x_{j}) \otimes f_{e 2} (x_{k})$ , gdzie $\otimes$ jest operacją arytmetyczną odpowiadającą węzłowi $x_{i}$ .

Podstawianie wyrażeń za zmienne odbywa się na funkcjach związanych z krawędziami. Jeśli wartości $x_{j}, x_{k}$ są obliczone (zmienne te odpowiadają aktualnie liściom), to wartość $f_{e 1} (x_{j}) \otimes f_{e 2} (x_{k})$ jest konkretną końcową wartością zmiennej $x_{i}$ .

Rozważamy też "spłaszczoną" wersję $T^{'} = s q u a s h (T)$ drzewa T, odpowiadającą algorytmowi kontrakcji. W drzewie $T^{'}$ wewnętrzne węzły odpowiadają zmiennym programu sekwencyjnego lub krawędziom między zmiennymi. Wartością krawędzi $e$ jest funkcja $f_{e}$ , reprezentowana przez cztery stałe $a, b, c, d$ . Jeśli krawędź $e 1 = (x, z)$ jest kompozycją dwóch krawędzi $e 1 = (x, y), e 2 = (y, z)$ , to wartością $f_{e}$ jest kompozycja funkcji $f_{e 1}, f_{e 2}$ . Kompozycja ta polega na wykonaniu operacji na czterch stałych odpowiadających funkcjom. Jeśli zależność jest tylko od jednej krawędzi, to automatycznie rozumiemy, że funkcja odpowiadająca pominiętej krawędzi jest identycznościowa (a takie są początkowo wszystkie funkcje w początkowym grafie $𝒢 (𝒫)$ ). Na następującym przykładzie pokażemy, jak działa operacja Contract i w jaki sposób związana jest ona z algorytmem JP.

Rysunek 2. Przykładowe drzewo

T

wyrażenia. Początkowe wartości w liściach są podane w kwadracikach, numery węzłów są w podane w nawiasach.

Rysunek 3. Drzewo

T_{1} = C o n t r a c t (T)

razem z dodatkowymi funkcjami na krawędziach. Brak funkcji oznacza funkcję identycznościową.

Rysunek 4. Kolejne drzewa

T_{3}, T_{4}, T_{5}

. Algorytm wykonuje 4 kontrakcje.

Rysunek 5. "Spłaszczone" drzewo

T^{'} = s q u a s h (T)

liczące to samo, co drzewo T, ale mające mniejszą wysokość (ogólnie logarytmiczną). Drzewo to można jeszcze bardziej spłaszczyć, kompresując łańcuchy dwukrawędziowe (eliminując węzły wewnętrzne mające dokładnie jednego syna.

Oszacowanie liczby kontrakcji

Załóżmy, że graf $𝒢 (𝒫)$ programu sekwencyjnego P jest drzewem T. Wtedy liczba iteracji algorytmu JP jest równa liczbie kontrakcji drzewa T, po której korzeń T staje się liściem. Przez $T I M E (n)$ oznaczmy maksymalną liczbę kontrakcji potrzebnych do zredukowania do jednego węzła drzewa o $n$ węzłach. Niech $F i b_{n}$ będziem $n$ -tą liczbą Fibonacciego, gdzie $F i b_{0} = 1, F i b_{1} = 2$ . Udowodnimy:

Twierdzenie

(a) $T I M E (F i b_{n}) = n$ .

(b) $F i b_{k} \leq n < F i b_{k + 1^{‴} \Rightarrow T I M E (n) = k}$ .

Jako bezpośredni wniosek otrzymujemy:

\log_{ϕ} + c \leq T I M E (n) \leq \log_{ϕ} + c, dla pewnej stałej c

gdzie $Φ = \frac{1 + \sqrt{5}}{2}$ jest liczbą tzw. złotego podziału (w przybliżeniu $Φ \approx 1.6$ ).

Udowodnimy najpierw, że $T I M E (F i b_{k}) \geq k$ . Niech $T_{k}$ będzie $k$ -tym drzewem Fibonacciego, zdefiniowanym na rysunku. Drzewo $T_{k + 2}$ powstaje przez utożsamienie korzeni dwóch początkowo rozłącznych wierzchołkowo drzew $T_{k}$ i $T_{k + 1}$ oraz dodanie nowego korzenia.

Rysunek 6. Drzewa Fibonacciego.

Pozostawiamy jako ćwiczenie uzasadnienie tego, że $| T_{k} | = F i b_{k}$ oraz $C o n t r a c t (T_{k}) = T_{k - 1}$ .

Wynika stąd, że $T I M E (F i b_{k}) \geq k$ .

Przejdziemy teraz do dowodu następującego faktu.

Lemat o kontrakcji

$n \leq F i b_{k} \Rightarrow T I M E (n) \leq k$ .

Wprowadzamy pojęcie statycznego węzła jako liścia, który nigdy nie może być "odcięty", nie możemy usunąć krawędzi prowadzącej do niego. Poza tym operacja kontrakcji działa tak jak poprzednio. Na rysunkach statyczny węzeł jest zaznaczony jako kwadracik. Jeśli drzewo ma dokładnie jeden statyczny węzeł, to po pewnej liczbie kontrakcji otrzymujemy drzewo składające się tylko z korzenia i tego węzła. Oznaczmy przez $T I M E^{'} (n)$ maksymalną liczbę kontrakcji dla drzewa mającego n węzłów, które doprowadzają do takiej sytuacji. W liczbę n nie wliczamy węzła statycznego.

Pozostawiamy jako ćwiczenie dowód tego, że $T I M E^{'} (F i b_{k} + 1) > k$ .

Następujący dosyć oczywisty fakt jest użyteczny w dalszym dowodzie lematu o kontrakcji.

Fakt. Niech $x \in T$ oraz $T^{'}, T_{x}$ będą takie, jak pokazane na Rysunku 7. Jeśli $t$ kontrakcji redukuje $T^{'}$ do drzewa rozmiaru jeden (nie licząc węzła statycznego), to po $t$ kontrakcjach drzewo $T$ redukuje się do pojedyńczego węzła staje się drzewem złożonym tylko z korzenia, którego jedynem następnikiem jest liść lub element drzewa $T_{x}$ .

Rysunek 7. Graficzna definicja drzew

T^{'}

,

T_{x}

.

Udowodnimy lemat, który będzie rozszerzeniem lematu o kontrakcji. Celowo wzmacniamy tezę, aby ułatwić dowód przez indukcję.

Lemat Wzmocniony lemat o kontrakcji

(a) $n < F I B_{k} \Rightarrow T I M E (n) < k - 1$ ;

(b) $n \leq F I B_{k} \Rightarrow T I M E^{'} (n) < k$ .

Dowód przeprowadzamy przez indukcję ze względu na $k$ . Dla $k = 1$ , $k = 2$ łatwo sprawdzić, że teza zachodzi. Załóżmy teraz, że teza zachodzi dla wszystich $k^{'}$ mniejszych niż dane $k > 2$ .

Dowód punktu (a)

Rozważmy drzewo $T$ takie, że $| T | < F I B_{k}$ . Niech $x$ będzie najniższym (o najmniejszej wysokości) węzłem, takim że $| T_{x} | \geq F I B_{k - 1}$ . Niech $p$ , $q$ będą następnikami $x$ , patrz Rysunek 8. (Jeśli $x$ ma tylko jednego następnika, nazwijmy go $p$ ). Zatem

| T_{p} |, | T_{q} | < F I B_{k - 1}

Udowodnimy, że po $k - 1$ -szej kontrakcji korzeń $T$ staje się liściem. Możliwe są dwa przypadki:

Przypadek I: Po kontrakcji $(k - 2)$ -giej węzeł $x$ jest liściem.
Z założenia indukcyjnego wynika, że drzewo $T 1$ jest zredukowane do korzenia z jednym następnikiem, który jest wewnątrz $T_{x}$ . Ponieważ wszystkie węzły w $T_{x}$ stały się liśćmi (gdyż korzeń $T_{x}$ stał się liściem), to w następnej kontrakcji wykonujemy operację Rake i korzeń całego drzewa staje się liściem.

Rysunek 8. Drzewo

T

i jego dekompozycja:

| T | < F I B_{k}

,

| T 1 | \leq F I B_{k - 2}

,

| T_{x} | \geq F I B_{k - 1}

,

| T_{p} | < F I B_{k - 1}

.

Przypadek II: Korzeń drzewa $T_{x}$ wymaga co najmniej $k - 1$ kontrakcji by stał się liściem.
Dla drzewa $T$ niech $v \notin R$ będzie dodatkowym węzłem, a $R \otimes v$ będzie nowym drzewem o korzeniu $v$ mającym jednego następnika - korzeń R. Łatwo zauważyć, że co najmniej jedno z drzew $T_{p} \otimes x$ lub $T_{q} \otimes x$ wymaga co najmniej $k - 1$ kontrakcji, aby korzeń stał się liściem. Przyjmijmy, bez straty ogólności, że jest to pierwsze z nich.

Z założenia indukcyjnego wynika, że $| T_{p} \otimes x | \geq F I B_{k - 1}$ (zatem $| T_{p} | = F I B_{k - 1} - 1)$ . Wynika stąd, że drzewo $T 2$ z węzłem statycznym (patrz Rysunek 8) jest "małe": $| T 2 | \leq F I B_{k - 2}$ .

W tej sytuacji z założenia indukcyjnego (b) wynika, że drzewo $T 2$ jest zredukowane do korzenia z jednym liściem po $k - 2$ kontrakcjach. Wszystkie węzły $T_{p}$ stają się liścmi po $k - 2$ kontrakcjach na mocy założenia indukcyjnego (a). Zatem podobnie jak w przypadku I, korzeń całego drzewa staje się liściem po $k - 1$ kontrakcjach.

Dowód punktu (b)

Przypadek ten rozpatruje się podobnie jak punkt (a), stosując odpowiednią dekompozycję drzewa $T$ . Dowód ten pozostawiamy jako ćwiczenie.

Obserwacja.Możliwe są różne inne definicje kontrakcji drzew. Na przykład moglibyśmy rozważać, że w jednej iteracji kontrakcji najpierw wykonujemy Rake (usuń liście), a dopiero potem Compress. My wykonywaliśmy to w jednym kroku równocześnie, co wydaje się bardziej naturalne.

@@ Linia 3: / Linia 3: @@
 __TOC__
-W module tym  zajmiemy się  obliczaniem wyrażeń arytmetycznych i równoległymi obliczeniami na drzewach związanmi  z tzw. ''kontrakcją drzew''
+W module tym zajmiemy się obliczaniem wyrażeń arytmetycznych i równoległymi obliczeniami na drzewach związanymi z tzw. ''kontrakcją drzew''.
+W dużym stopniu w module tym możemy zapomnieć o maszynie PRAM i przyjąć, że naszym modelem obliczeń równoległych jest drzewo (lub graf acykliczny).
+Czas równoległy to wysokość drzewa, a liczba procesorów to liczba węzłów. Węzły odpowiadają akcjom do wykonania, a drzewo (lub ogólniej graf acykliczny) odpowiada wymuszaniu pewnej kolejności wykonywania akcji.  W jednym równoległym kroku możemy wykonać jednocześnie wszystkie te akcje, dla
+których akcje poprzedzające je w drzewie (grafie) są już wykonane.
+Czasami dana akcja nie musi czekac na zakonczenie wszystkich poprzedzających ja akcji, a może wykonywać jakąś pożyteczną pracę wcześniej, jeśli tylko część informacji potrzebnej do wykonania tej akcji jest obliczona.
+Ta część informacji to na przykład obliczona wartość jednego z poprzedników danego węzła. Pomimo, że drugi poprzednik się jeszcze liczy możemy zacząc liczyć częsciowe wyniki związane z tym węzłem.
+Zasadniczy problem to jak przekształcić (''spłaszczyć'')
+drzewo ''chude''
+(o dużej wysokości) w semantycznie równoważne drzewo o małej wysokości nie zmieniając istotnie rzędu liczby węzłów drzewa.
 ==Obliczanie wyrażeń arytmetycznych: algorytm jednoczesnych podstawień ==
-Zakładamy, że wyrażenie zadane jest przez ''program sekwencyjny'' (w skrócie ''PS''). Program taki jest ''sztywną'' sekwencją operacji, bez instrukcji warunkowych. PS jest bardzo prostym modelem obliczeńsekwencyjnych. Bardziej precyzyjnie, definiujemy program sekwencyjny jako  ciąg instrukcji przypisań postaci<math>x_i := W_i</math>, gdzie <math>W_i</math> jest wyrażeniem arytmetycznym zawierającym <math>O(1)</math> operacji. W przypadku gdy operacjesą logiczne PS nazywamy obwodem logicznym (ang. boolean circuit). Ogólnie problem obliczenia wartości obwodulogiczngo jest P-zupełny, podobnie jest dla arytmetycznych programów sekwecyjnych. Problemy te są w klasie NC gdy graf związany z programem sekwencyjnym jest drzewem, a sam program odpowiada obliczaniu wyrażeniaarytmetycznego, co będziemy dalej zakładać.
+Zakładamy, że wyrażenie zadane jest przez ''program sekwencyjny'' (w skrócie ''PS''). Program taki jest "sztywną" sekwencją operacji, bez instrukcji warunkowych. PS jest bardzo prostym modelem obliczeń sekwencyjnych. Bardziej precyzyjnie, definiujemy program sekwencyjny jako ciąg instrukcji przypisań postaci <math>x_i := W_i</math>, gdzie <math>W_i</math> jest wyrażeniem arytmetycznym zawierającym <math>O(1)</math> operacji. W przypadku gdy operacje są logiczne, PS nazywamy obwodem logicznym (ang. boolean circuit). Ogólnie problem obliczenia wartości obwodu logiczngo jest P-zupełny, podobnie jest dla arytmetycznych programów sekwencyjnych.
+Problemy te są się w klasie NC, gdy graf związany z programem sekwencyjnym jest drzewem, a sam program odpowiada obliczaniu wyrażenia  arytmetycznego, co będziemy dalej zakładać.
+Zmienne w programie sekwencyjnym  są ponumerowane. Jeśli po lewej stronie instrukcji przypisania jest zmienna <math>x_i</math> a po prawej zmienna <math>x_j</math>, to wymagamy, aby <math>j<i</math>. Zakładamy, że struktura obliczeń jest drzewem oraz operacje  są ze zbioru <math>\{+,-,*,/\}</math>.
+'''Obserwacja''' Program sekwencyjny odpowiada układowi arytmetycznemu w sensie poprzedniego modułu, jednakże motywacją zmiany terminologii ‘’układ arytmetyczny’’ na ‘’PS’’ jest sekwencyjny zapis. . W przypadku układu arytmetycznego, liczba węzłów odpowiada czasowi sekwencyjnemu, a wysokość czasowi równoległemu.
+W module tym zajmiemy się, w sensie układu arytmetycznego, transformacją jednego układu  na równoważny mu drugi układ,
+który ma małą (logarytmiczną) wysokość.<br>
-Zmienne w programie sekwencyjnym  są ponumerowane. Jeśli po lewej stronie instrukcji przypisaniajest zmienna <math>x_i</math> a po prawej zmienna <math>x_j</math> to wymagamy aby <math>j<i</math>. Zakładamy, że struktura obliczeń jest drzewem oraz operacje  są ze zbioru <math>\{+,-,*,/\}</math>.
-Sekwencyjna pojedyńcza operacja podstawiania polega na zastąpieniu zmiennej <math>x_j</math> w danym wyrażeniu <math>W_i</math>,gdzie <math>i>j</math> przez <math>W_j</math> oraz redukcji wyrażenia po podstawieniu. \myskip Mówimy, że zmienna <math>x_j</math> jest ''bezpieczna'' gdy jej prawa strona w programie sekwencyjnym (wyrażenie <math>W_j</math>) zawiera co najwyżej jednązmienną. W przykładzie poniżej pierwsze 5 zmiennych są  bezpieczne.
+Sekwencyjna pojedyncza operacja podstawiania polega na zastąpieniu zmiennej <math>x_j</math> w danym wyrażeniu <math>W_i</math>, gdzie <math>i>j</math>, przez <math>W_j</math> oraz redukcji wyrażenia po podstawieniu. \myskip Mówimy, że zmienna <math>x_j</math> jest "bezpieczna", gdy jej prawa strona w programie sekwencyjnym (wyrażenie <math>W_j</math>) zawiera co najwyżej jedną zmienną. W przykładzie poniżej 5 pierwszych zmiennych jest bezpiecznych.
 {{przyklad|||
 Rozważmy następujący program sekwencyjny <math>P</math>:
-<math>x1 = 1</math>, <math>x2 = 2</math>, <math> x3  = 6</math>, <math>x4 = 4</math>, <math>x5 = x3 + 2</math>,
+<math>x1 = 1</math>, <math>x2 = 2</math>, <math>x3  = 6</math>, <math>x4 = 4</math>, <math>x5 = x3 + 2</math>,
 <math>x6 = x2 + x1</math>, <math>x7 = 3*x6 + 2*x5</math>, <math>x8 = 2*x7 + x4</math>.
 }}
-Na przykład po wykonaniu wszystkich bezpiecznych podstawień (w tym wypadku tylko zastąpienie <math>x5</math> przez <math>x3+2</math>) do prawej strony dla x7 otrzymujemy
+Przykładowo, po wykonaniu wszystkich bezpiecznych podstawień (w tym wypadku tylko zastąpienie <math>x5</math> przez <math>x3+2</math>) do prawej strony dla x7 otrzymujemy
 <center><math>x7 = 3*x6 + 2*x3 + 4</math>. </center>
-Operacja ''Reduce'' polega na wykonaniu jednocześnie wszystkich bezpiecznych podstawień we wszystkich wyrażeniach <math>W_i</math>. W programie rozważamy tylko te zmienne, które są istotne z punktu widzenia liczenia ostatecznego wyniku <math>x_n</math>. Zmienne te nazywamy istotnymi, są one osiągalne ze zmiennej <math>x_n</math> w grafie programu. Oznaczmy przez ''Reduce(P)'' nowy program sekwencyjny, bez zmiennych nieistotnych.
+Operacja ''Reduce'' polega na wykonaniu jednocześnie wszystkich bezpiecznych podstawień we wszystkich wyrażeniach <math>W_i</math>. W programie rozważamy tylko te zmienne, które są istotne z punktu widzenia liczenia ostatecznego wyniku <math>x_n</math>. Zmienne te nazywamy istotnymi. Są one osiągalne ze zmiennej <math>x_n</math> w grafie programu. Oznaczmy przez ''Reduce(P)'' nowy program sekwencyjny, bez zmiennych nieistotnych.
 {{algorytm|JP||
@@ Linia 38: / Linia 57: @@
 }}
-Historia algorytmu dla przykładowego programu P danego powyżej wygląda następująco, gdzie <math>P=P_0, P_{i+1}= \textsl{Reduce}(P_i)</math>.
+Historia algorytmu dla przykładowego programu P danego powyżej wygląda następująco, gdzie <math>P=P_0, P_{i+1}= \mathit{Reduce}(P_i)</math>.
 <math>P_1</math>: <br>
@@ Linia 51: / Linia 70: @@
 &nbsp;&nbsp;&nbsp;<math>x8 =54</math>.<br>
-Pokażemy, że algorytm wykonuje <math>O(\log n)</math> iteracji. Udwodnimy bardzo precyjne oszacowanie: rozmiar najmnieszego programu sekwencyjnego, który wmaga <math>k</math> iteracji jest równy <math>k</math>-tej liczbie Fibonacciego. Jest to zaskakująco podobne do analogicznego faktu dla drzew AVL, czas równoległy odpowiada wysokości drzewa.
+Pokażemy, że algorytm wykonuje <math>O(\log n)</math> iteracji. Udowodnimy bardzo precyjne oszacowanie: rozmiar najmniejszego programu sekwencyjnego, który wmaga <math>k</math> iteracji jest równy <math>k</math>-tej liczbie Fibonacciego.
+Jest to zaskakująco podobne do analogicznego faktu dla drzew AVL, czas równoległy odpowiada tutaj wysokości drzewa.
-==Kontrakcja drzew==
+==Równoległa kontrakcja drzew==
-Grafem obliczeń  <math>T=\cal{G}(P)</math> programu sekwencyjnego <math>P</math> jest skierowany graf acykliczny którego węzły odpowiadają zmiennych biorącym aktualnie udział w obliczeniu <math>x_n</math>. Synami węzła <math>x_i</math> (zmiennej) są zmiennewystępujące w danym momencie w <math>W_i</math>.  Graf <math>T</math> zawiera tylko węzły osiągalne z korzenia <math>x_n</math>. Przezrozmiar rozumiemy liczbę węzłów grafu  (liczbę zmiennych w przypadku PS).
+Grafem obliczeń  <math>T=\cal{G}(P)</math> programu sekwencyjnego <math>P</math> jest skierowany graf acykliczny, którego węzły odpowiadają zmiennym biorącym aktualnie udział w obliczeniu <math>x_n</math>. Synami węzła <math>x_i</math> (zmiennej) są zmienne występujące w danym momencie w <math>W_i</math>.  Graf <math>T</math> zawiera tylko węzły osiągalne z korzenia <math>x_n</math>. Przez rozmiar rozumiemy liczbę węzłów grafu  (liczbę zmiennych w przypadku PS).
-Zauważmy, że w danej iteracji algorytmu JP rozmiar grafu <math>T</math> może być znacznie mniejszy niż <math>n</math>, ponieważ wiele zmiennych możebyć nieosiągalnych z  korzenia.
+Zauważmy, że w danej iteracji algorytmu JP rozmiar grafu <math>T</math> może być znacznie mniejszy niż <math>n</math>, ponieważ wiele zmiennych może być nieosiągalnych z  korzenia.
-Jedna iteracja ''Reduce'' (<math>P_{i}\rightarrow P_{i+1}</math>) odpowiada następującej operacji <math>Contract({\cal{G}}(P_i))</math>,\   patrz rysunek.
+Jedna iteracja ''Reduce'' (<math>P_{i}\rightarrow P_{i+1}</math>) odpowiada następującej operacji <math>Contract({\cal{G}}(P_i))</math>, patrz rysunek.
 <center>[[Grafika:Parallel2-1.png]]<br> Rysunek 1. Składowe operacje jednej iteracji  Contract(T): ''Compress'' oraz   ''Rake''. </center>
-W rzeczywistości możemy  zapomnieć o  algorytmie  JP i maszynie PRAM. Obliczanie na drzewie jestsamo w sobie sensownym modelem obliczeń równoległych. Czas równoległy jest liczbą iteracji, któraprzekształca początkowe drzewo w drzewo jednoelementowe. Z każdą krawędzią <math>e=(x_i,x_j)</math> grafu <math>\cal{G}(P)</math> jest związana pewna funkcja <math>f_e(x)</math> postaci:
+W rzeczywistości możemy zapomnieć o algorytmie JP i maszynie PRAM. Obliczanie na drzewie jest samo w sobie sensownym modelem obliczeń równoległych. Czas równoległy jest liczbą iteracji, która przekształca początkowe drzewo w drzewo jednoelementowe.
+Z każdą krawędzią <math>e=(x_i,x_j)</math> grafu <math>\cal{G}(P)</math> jest związana pewna funkcja <math>f_e(x)</math> postaci:
+<center><math>f_e(x)= \frac{ax+b}{cx+d}</math></center>
+gdzie <math>a,b,c,d</math> są pewnymi stałymi.
-<center><math> f_e(x)\ =\ \frac{ax+b}{cx+d},</math></center>
+Początkowo funkcja ta jest identycznościowa. Jeśli w danym momencie następnikami węzła <math>x_i</math> są <math>x_j,\ x_k</math> oraz <math>e1=(x_i,x_j), e2=(x_i,x_k)</math>, to wartością zmiennej <math>x_i</math> jest: <math>f_{e1}(x_j) \otimes f_{e2}(x_k)</math>, gdzie <math>\otimes</math> jest operacją arytmetyczną odpowiadającą węzłowi <math>x_i</math>.
-gdzie <math>a,b,c,d</math> są pewnymi stałymi. Początkowo funkcja ta jest identycznościowa. Jeśli w danym momencie następnikami węzła <math>x_i</math> są<math>x_j,\ x_k</math>, oraz <math>e1=(x_i,x_j), e2=(x_i,x_k)</math> to wartością zmiennej <math>x_i</math> jest: <math>f_{e1}(x_j) \otimes f_{e2}(x_k)</math>, gdzie <math>\otimes</math> jest operacją arytmetyczną odpowiadającą węzłowi <math>x_i</math>, w grafie obliczeń operacja ta jest niezmienna, podstawianie wyrażeń za zmienne odbywa się na  funkcjeach na krawędziach. Jeśli wartości <math>x_j,x_k</math> są obliczone (zmienne te odpowiadają aktualnie liściom) to wartość <math>f_{e1}(x_j) \otimesf_{e2}(x_k)</math> jest konkretną końcową wartością zmiennej <math>x_i</math>.
+Podstawianie wyrażeń za zmienne odbywa się na  funkcjach związanych z krawędziami. Jeśli wartości <math>x_j,x_k</math> są obliczone (zmienne te odpowiadają aktualnie liściom), to wartość <math>f_{e1}(x_j) \otimes f_{e2}(x_k)</math> jest konkretną końcową wartością zmiennej <math>x_i</math>.
-Rozważamy  też ''spłaszczoną'' wersję <math>T'=squash(T)</math>  drzewa T, odpowiadającą algorytmowi kontrakcji. W drzewie T' wewnętrzne węzły odpowiadają zmiennych programu sekwencyjnego lub krawędziom między zmiennymi, wartością krawędzi<math>e</math> jest funkcja <math>f_e</math> reprezentowana przez cztery stałe <math>a,b,c,d</math>. Jeśli krawędź <math>e1=(x,z)</math> jest kompozycją dwóch krawędzi <math>e1=(x,y), e2=(y,z)</math> to wartością <math>f_e</math> jest kompozycja funkcji <math>f_{e1},  f_{e2}</math>. Kompozycja ta polega na wykonaniu operacji na czterch stałych odpowiadających funkcjom. Jeśli zależność jest tylko odjednej krawędzi to automatycznie rozumiemy że funkcja odpowiadająca pominiętej krawędzi jest identycznościowa (a takie są początkowo wszystkie funkcje w początkowym grafie <math>\cal{G}(P)</math>). Na następującym przykładzie pokażemy jak działa operacja Contract i w jaki sposób związana jest ona zalgorytmem JP.
+Rozważamy też "spłaszczoną" wersję <math>T'=squash(T)</math> drzewa T, odpowiadającą algorytmowi kontrakcji. W drzewie <math>T'</math> wewnętrzne węzły odpowiadają zmiennym programu sekwencyjnego lub krawędziom między zmiennymi. Wartością krawędzi<math>e</math> jest funkcja <math>f_e</math>, reprezentowana przez cztery stałe <math>a,b,c,d</math>. Jeśli krawędź <math>e1=(x,z)</math> jest kompozycją dwóch krawędzi <math>e1=(x,y), e2=(y,z)</math>, to wartością <math>f_e</math> jest kompozycja funkcji <math>f_{e1},  f_{e2}</math>. Kompozycja ta polega na wykonaniu operacji na czterch stałych odpowiadających funkcjom. Jeśli zależność jest tylko od jednej krawędzi, to automatycznie rozumiemy, że funkcja odpowiadająca pominiętej krawędzi jest identycznościowa (a takie są początkowo wszystkie funkcje w początkowym grafie <math>\cal{G}(P)</math>). Na następującym przykładzie pokażemy, jak działa operacja Contract i w jaki sposób związana jest ona z algorytmem JP.
-<center>[[Grafika:Parallel2-2.png]]<br> Rysunek 2. Przykładowe drzewo <math>T</math> wyrażenia, początkowe wartości w liściach są podane w kwadracikach, numery węzłów  są w podane w nawiasach.<center>
+<center>[[Grafika:Parallel2-2.png]]<br> Rysunek 2. Przykładowe drzewo <math>T</math> wyrażenia. Początkowe wartości w liściach są podane w kwadracikach, numery węzłów  są w podane w nawiasach. <center>
@@ Linia 82: / Linia 108: @@
-<center>[[Grafika:Parallel2-5.png]]<br> Rysunek 5. ''Spłaszczone'' drzewo <math>T'=squash(T)</math>  liczące to samo co drzewo T, ale mające mniejszą wysokość(ogólnie logarytmiczną). Drzewo to można jeszcze bardzij spłaszczyć kompresując łańcuchy dwukrawędziowe(eliminując węzły wewnętrzne  mające dokładnie  jednego syna. </center>
+<center>[[Grafika:Parallel2-5.png]]<br> Rysunek 5. "Spłaszczone" drzewo <math>T'=squash(T)</math>  liczące to samo, co drzewo T, ale mające mniejszą wysokość (ogólnie logarytmiczną). Drzewo to można jeszcze bardziej spłaszczyć, kompresując łańcuchy dwukrawędziowe (eliminując węzły wewnętrzne  mające dokładnie  jednego syna. </center>
-== Oszacowanie liczby iteracji algorytmu JP ==
+== Oszacowanie liczby kontrakcji==
-Załóżmy, że graf <math>\cal{G}(P)</math> programu sekwenycjnego P jest drzewem T. Wtedy liczba iteracji algorytmu JP jest równa liczbie kontrakcji drzewa T, po której korzeń T staje się liściem. Przez  <math>TIME(n)</math> oznaczmy  maksymalną liczbę kontrakcji potrzebnych do zredukowania  do jednego węzła drzewa o <math>n</math> węzłach. Niech <math>Fib_n</math> będziem <math>n</math>-tą liczbą Fibonacciego,gdzie <math>Fib_0=1, Fib_1=2</math>.Udowodnimy:
+Załóżmy, że graf <math>\cal{G}(P)</math> programu sekwencyjnego P jest drzewem T. Wtedy liczba iteracji algorytmu JP jest równa liczbie kontrakcji drzewa T, po której korzeń T staje się liściem. Przez  <math>TIME(n)</math> oznaczmy  maksymalną liczbę kontrakcji potrzebnych do zredukowania do jednego węzła drzewa o <math>n</math> węzłach. Niech <math>Fib_n</math> będziem <math>n</math>-tą liczbą Fibonacciego, gdzie <math>Fib_0=1, Fib_1=2</math>. Udowodnimy:
 {{twierdzenie|||
 '''(a)''' <math>TIME(Fib_n)=n</math>.
-'''(b)''' <math>Fib_k \le n < Fib_{k+1'''\ \Rightarrow \ TIME(n)=k</math>.
+'''(b)''' <math>Fib_k \le n < Fib_{k+1'''\ \Rightarrow \ TIME(n)=k}</math>.
 }}
 Jako bezpośredni wniosek otrzymujemy:
-<center><math> \log_{\phi}+c \le TIME(n) \le \log_{\phi}+c,\ \textrm{dla pewnej stałej c},</math></center>
+<center><math>\log_{\phi}+c \le TIME(n) \le \log_{\phi}+c,\ \text{dla pewnej stałej c}</math></center>
-gdzie <math>\Phi\ =\ \frac{1+\sqrt{5}}{2}</math> jest liczbą tzw. złotego podziału (w przybliżeniu <math>\Phi \approx 1.6</math>).
+gdzie <math>\Phi= \frac{1+\sqrt{5}}{2}</math> jest liczbą tzw. złotego podziału (w przybliżeniu <math>\Phi \approx 1.6</math>).
-Udowodnimy najpierw, że <math>TIME(Fib_k)\ge k</math>. Niech <math>T_k</math> będzie <math>k</math>-tym drzewem Fibonacciego, zdefiniowanym na rysunku. Drzewo <math>T_{k+2}</math> powstaje przez utożsamienie korzeni dwóch początkowo rozłącznych wierzchołkowo drzew <math>T_k</math> i <math>T_{k+1}</math>, oraz dodanie nowego korzenia.
+Udowodnimy najpierw, że <math>TIME(Fib_k)\ge k</math>. Niech <math>T_k</math> będzie <math>k</math>-tym drzewem Fibonacciego, zdefiniowanym na rysunku. Drzewo <math>T_{k+2}</math> powstaje przez utożsamienie korzeni dwóch początkowo rozłącznych wierzchołkowo drzew <math>T_k</math> i <math>T_{k+1}</math> oraz dodanie nowego korzenia.
 <center>[[Grafika:Parallel2-6.png]]<br> Rysunek 6. Drzewa Fibonacciego. </center>
@@ Linia 115: / Linia 141: @@
 }}
-Wprowadzamy pojęcie ''statycznego węzła'', jako liścia, który nigdy nie może być ''odcięty'',nie możemy usunąć krawędzi prowadzącej do niego. Poza tym operacja kontrakcji działa tak jak poprzednio. Narysunkach statyczny węzeł jest zaznaczony jako kwadracik. Jeśli drzewo ma dokładnie jeden statyczny węzeł,to po pewnej liczbie kontrakcji otrzymujemy drzewo składające się tylko z korzenia i tego węzła. Oznaczmy przez <math>TIME'(n)</math> maksymalną liczbę kontrakcji dla drzewa mającego n węzłów, które doprowadzają do takiej sytuacji. W liczbę n nie wliczamy węzła statycznego.
+Wprowadzamy pojęcie ''statycznego węzła'' jako liścia, który nigdy nie może być "odcięty", nie możemy usunąć krawędzi prowadzącej do niego. Poza tym operacja kontrakcji działa tak jak poprzednio. Na rysunkach statyczny węzeł jest zaznaczony jako kwadracik. Jeśli drzewo ma dokładnie jeden statyczny węzeł, to po pewnej liczbie kontrakcji otrzymujemy drzewo składające się tylko z korzenia i tego węzła. Oznaczmy przez <math>TIME'(n)</math> maksymalną liczbę kontrakcji dla drzewa mającego n węzłów, które doprowadzają do takiej sytuacji. W liczbę n nie wliczamy węzła statycznego.
 Pozostawiamy jako ćwiczenie dowód tego, że <math>TIME'(Fib_k+1)>k</math>.
-Następujący dosyć oczywisty fakt jest użyteczny w dalszym dowodzie Lematu o Kontrakcji.
+Następujący dosyć oczywisty fakt jest użyteczny w dalszym dowodzie lematu o kontrakcji.
-'''Fakt.''' Niech <math>x\in T</math>, oraz <math>T',\ T_x</math> będą takie jak pokazane na Rysunku 7. Jeśli <math>t</math> kontrakcji redukuje< math>T'</math> do drzewa rozmiaru jeden (nie licząc węzła statycznego), to po <math>t</math> kontrakcjach drzewo <math>T</math>  redukuje się do pojedyńczego węzła staje się drzewem złożonym tylko z korzenia któreggo jedynem następnikiem jest liść lub element drzewa <math>T_x</math>.
+'''Fakt.''' Niech <math>x\in T</math> oraz <math>T',\ T_x</math> będą takie, jak pokazane na Rysunku 7. Jeśli <math>t</math> kontrakcji redukuje <math>T'</math> do drzewa rozmiaru jeden (nie licząc węzła statycznego), to po <math>t</math> kontrakcjach drzewo <math>T</math>  redukuje się do pojedyńczego węzła staje się drzewem złożonym tylko z korzenia, którego jedynem następnikiem jest liść lub element drzewa <math>T_x</math>.
 <center>[[Grafika:Parallel2-7.png]]<br> Rysunek 7. Graficzna definicja drzew  <math>T'</math>, <math>T_x</math>.</center>
-Udowodnimy lemat, który będzie rozszerzeniem Lematu o kontrakcji. Celowo wzmacniamy tezę aby ułatwićdowód przez indukcję.<!--%------------------------------------------------------------------------->\myskip '''Wzmocniony Lemat o kontrakcji.'''<!--%------------------------------------------------------------------------->
+Udowodnimy lemat, który będzie rozszerzeniem lematu o kontrakcji. Celowo wzmacniamy tezę, aby ułatwić dowód przez indukcję.
+{{lemat| Wzmocniony lemat o kontrakcji||
+'''(a)''' <math>n < FIB_k\ \Rightarrow\ TIME(n) < k-1</math>;
+'''(b)'''<math>n \le FIB_k\ \Rightarrow\  TIME'(n) <k</math>.
+}}
+Dowód przeprowadzamy przez indukcję ze względu na <math>k</math>. Dla <math>k=1</math>, <math>k=2</math> łatwo sprawdzić, że teza zachodzi.  Załóżmy teraz, że teza zachodzi dla wszystich <math>k'</math> mniejszych niż dane<math>k > 2</math>.
+'''Dowód punktu (a)'''
+Rozważmy drzewo <math>T</math> takie, że <math>|T| < FIB_k</math>. Niech <math>x</math> będzie najniższym (o najmniejszej wysokości) węzłem, takim że <math>|T_x| \ge FIB_{k-1}</math>. Niech  <math>p</math>, <math>q</math> będą następnikami <math>x</math>, patrz Rysunek 8. (Jeśli<math>x</math>  ma tylko jednego następnika, nazwijmy go <math>p</math>). Zatem
+<center><math>|T_ p|, |T_q| < FIB_{k-1}</math></center>
+Udowodnimy, że po <math>k-1</math>-szej kontrakcji korzeń <math>T</math> staje się liściem.  Możliwe są dwa przypadki:
+'''Przypadek I''':  Po kontrakcji <math>(k-2)</math>-giej węzeł <math>x</math> jest liściem. <br>Z założenia indukcyjnego wynika, że drzewo <math>T1</math> jest zredukowane do korzenia z jednym następnikiem, który jest wewnątrz <math>T_x</math>. Ponieważ wszystkie węzły w <math>T_x</math> stały się liśćmi (gdyż korzeń <math>T_x</math> stał się liściem), to w następnej kontrakcji wykonujemy operację Rake i korzeń całego drzewa staje się liściem.
+<center> [[Grafika:Parallel2-8.png]]<br> Rysunek 8. Drzewo <math>T</math> i jego dekompozycja:  <math>|T|<FIB_k</math>,<math>|T1|\le FIB_{k-2}</math>, <math>|T_x|\ge FIB_{k-1}</math>, <math>|T_p|<FIB_{k-1}</math>.</center>
+'''Przypadek II''':  Korzeń drzewa <math>T_x</math> wymaga co najmniej <math>k-1</math> kontrakcji by stał się liściem. <br> Dla drzewa <math>T</math> niech <math>v\notin R</math> będzie dodatkowym węzłem, a <math>R \otimes v</math> będzie nowym drzewem o korzeniu <math>v</math> mającym jednego następnika - korzeń R. Łatwo zauważyć, że co najmniej jedno z drzew <math>T_p\otimes x</math> lub <math>T_q\otimes x</math> wymaga co najmniej <math>k-1</math> kontrakcji, aby korzeń stał się liściem.  Przyjmijmy, bez straty ogólności, że jest to pierwsze z nich.
-\begin{tabbing}{lll}firstleve\=secon\= \kill\>'''(a)'''  \>  <math>n < FIB_k\ \Rightarrow\ TIME(n) < k-1</math>; \\\>'''(b)''' \><math>n \le FIB_k\ \Rightarrow\  TIME'(n) < k</math>.\\\end{tabbing}<!--%------------------------------------------------------------------------->\myskip Dowód przeprowadzamy przez indukcję ze względu na <math>k</math>. Dla <math>k=1</math>, <math>k=2</math> łatwo sprawdzić, że tezazachodzi. \noindent Załóżmy teraz, że teza zachodzi dla wszystich <math>k'</math> mniejszych niż dane<math>k > 2</math>.\myskip '''Dowód punktu (a)'''
+Z założenia indukcyjnego wynika, że <math>|T_p\otimes x| \ge FIB_{k-1}</math> (zatem <math>|T_p|=FIB_{k-1}-1)</math>. Wynika stąd, że drzewo <math>T2</math>  z  węzłem statycznym (patrz Rysunek 8) jest "małe":  <math>|T2| \le  FIB_{k-2}</math>.
-Rozważmy drzewo <math>T</math> takie, że <math>|T| < FIB_k</math>. Niech <math>x</math> będzie najniższym (o najmnieszej wysokości) węzłem,takim że <math>|T_x| \ge FIB_{k-1}</math>. Niech  <math>p</math>, <math>q</math> będą następnikami <math>x</math>, patrz Rysunek&nbsp;[[#fig13]]. (Jeśli<math>x</math>  ma tylko jednego następnika to nazwijmy go <math>p</math>). Zatem<center><math>|T_ p|, |T_q| < FIB_{k-1}</math></center>  Udwodnimy, że po <math>k-1</math>-szej kontrakcjikorzeń <math>T</math> staje się liściem.  Możliwe są dwa przypadki: \myskip '''Przypadek I''':  Po kontrakcji<math>(k-2)</math>-giej węzeł <math>x</math> jest liściem. \vskip 0.2cm Z założenia indukcyjnego wynika, że drzewo <math>T1</math> jestzredukowane do korzenia z jednym następnikiem, który jest wewnątrz <math>T_x</math>. ponieważ wszystkie węzły w <math>T_x</math>stały się liśćmi (gdyż korzeń <math>T_x</math> stał się liściem) to w następnej kontrakcji wykonujemy operacjęRake i korzeń całego drzewa staje się liściem.
+W tej sytuacji z założenia indukcyjnego (b) wynika, że drzewo <math>T2</math> jest zredukowane do korzenia z jednym liściem po <math>k-2</math>  kontrakcjach.  Wszystkie węzły <math>T_p</math>  stają się liścmi po <math>k-2</math> kontrakcjach na mocy założenia  indukcyjnego (a). Zatem podobnie jak w przypadku I, korzeń całego drzewa staje się liściem po <math>k-1</math> kontrakcjach.
-\begin{figure}\unitlength=1.00mm \special{em:linewidth 0.4pt} \linethickness{0.4pt}\begin{picture}(116.33,32.00)\put(21.33,24.00){\line(3,4){6.00}} \put(27.33,31.56){\line(3,-4){6.00}} \put(33.33,23.56){\line(-1,0){5.00}}\put(21.33,23.56){\line(1,0){5.33}} \put(27.67,23.56){\circle{0.89}} \put(27.00,22.22){\line(-3,-4){4.00}}\put(28.67,22.22){\line(3,-4){4.00}} \put(22.33,15.56){\circle{0.89}} \put(33.67,15.56){\circle{0.89}}\put(22.33,14.22){\line(-3,-4){4.33}} \put(22.67,13.78){\line(3,-4){4.00}} \put(26.67,8.44){\line(-1,0){8.67}}\put(33.33,13.78){\line(-3,-4){4.00}} \put(34.00,13.78){\line(3,-4){4.00}} \put(38.00,8.44){\line(-1,0){8.33}}\put(27.67,26.22){\makebox(0,0)[cc]{x}} \put(36.67,15.56){\makebox(0,0)[cc]{q}}\put(19.67,15.56){\makebox(0,0)[cc]{p}} \put(64.00,18.67){\line(-3,-4){4.00}}\put(65.67,18.67){\line(3,-4){4.00}} \put(59.33,12.00){\circle{0.89}} \put(70.67,12.00){\circle{0.89}}\put(59.33,10.67){\line(-3,-4){4.33}} \put(59.67,10.22){\line(3,-4){4.00}} \put(63.67,4.89){\line(-1,0){8.67}}\put(70.33,10.22){\line(-3,-4){4.00}} \put(71.00,10.22){\line(3,-4){4.00}} \put(75.00,4.89){\line(-1,0){8.33}}\put(73.67,12.00){\makebox(0,0)[cc]{q}} \put(56.67,12.00){\makebox(0,0)[cc]{p}}\put(56.00,24.00){\line(3,4){6.00}} \put(62.00,31.56){\line(3,-4){6.00}} \put(68.00,23.56){\line(-1,0){5.00}}\put(56.00,23.56){\line(1,0){5.33}} \put(62.33,23.56){\circle{0.89}} \put(62.33,26.22){\makebox(0,0)[cc]{x}}\put(64.67,19.11){\circle{0.89}} \put(68.33,18.67){\makebox(0,0)[cc]{x}} \put(54.34,27.56){\makebox(0,0)[cc]{T1}}\put(49.33,11.11){\makebox(0,0)[cc]{T<math>_x</math>}} \put(13.33,21.78){\makebox(0,0)[cc]{T}}\put(64.56,1.33){\makebox(0,0)[cc]{case (I)}} \put(96.00,24.00){\line(3,4){6.00}}\put(102.00,31.56){\line(3,-4){6.00}} \put(108.00,23.56){\line(-1,0){5.00}} \put(96.00,23.56){\line(1,0){5.33}}\put(102.33,23.56){\circle{0.89}} \put(101.67,22.22){\line(-3,-4){4.00}} \put(103.33,22.22){\line(3,-4){4.00}}\put(108.33,15.56){\circle{0.89}} \put(108.00,13.78){\line(-3,-4){4.00}} \put(108.67,13.78){\line(3,-4){4.00}}\put(112.67,8.44){\line(-1,0){8.33}} \put(102.33,26.22){\makebox(0,0)[cc]{x}}\put(111.33,15.56){\makebox(0,0)[cc]{q}} \put(94.00,11.56){\circle{0.89}} \put(94.00,10.22){\line(-3,-4){4.33}}\put(94.33,9.78){\line(3,-4){4.00}} \put(98.33,4.44){\line(-1,0){8.67}} \put(91.33,11.56){\makebox(0,0)[cc]{p}}\put(96.00,14.22){\rule{1.67\unitlength}{2.22\unitlength}} \put(100.33,16.00){\makebox(0,0)[cc]{p}}\put(87.00,7.56){\makebox(0,0)[cc]{T<math>_p</math>}} \put(116.33,24.00){\makebox(0,0)[cc]{T2}}\put(100.34,1.31){\makebox(0,0)[cc]{case(II)}}\end{picture}<!--%--><!--%\input{fig13.pic}-->\caption{Drzewo   <math>T</math>  i jego dekompozycja:  <math>|T|<FIB_k</math>,<math>|T1|\le FIB_{k-2}</math>, <math>|T_x|\ge FIB_{k-1}</math>, <math>|T_p|<FIB_{k-1}</math>.} <span id="fig13" \> \end{figure}\myskip '''Przypadek II''':\  Korzeń drzewa <math>T_x</math> wymaga co najmniej <math>k-1</math> kontrakcji by stał się liściem.\vskip 0.2cm Dla drzewa <math>T</math> niech <math>v\notin R</math> będzie dodatkowym węzłem, a <math>R \otimes v</math> będzie nowym drzewemo korzeniu </math>v<math> mającym jednego następnka - korzeń R. łatwo widać, że co najmniej jedno z  drzew </math>T_p\otimesx</math> lub  <math>T_q\otimes  x</math> wymaga co najmniej <math>k-1</math> kontrakcji aby korzeń stał się liściem.  Przyjmijmy, bezstarty ogólności że jest to pierwsze z nich.
+'''Dowód punktu (b)'''
-Z założenia indukcyjnego wynika, że <math>|T_p\otimes x| \ge FIB_{k-1}</math> (zatem <math>|T_p|=FIB_{k-1}-1)</math>. Wynika stąd,że drzewo <math>T2</math>  z  węzłem statycznym, patrz Rysunek&nbsp;[[#fig13}, jest {\em małe}:\  <math>|T2| \le  FIB_{k-2]]</math>.
+Przypadek ten rozpatruje się podobnie jak punkt (a), stosując odpowiednią dekompozycję drzewa <math>T</math>. Dowód ten pozostawiamy jako ćwiczenie.
-W tej sytuacji z założenia indukcyjnego (b) wynika, że drzewo   <math>T2</math> jest zredukowane do korzenia z jednymliściem po <math>k-2</math>  kontrakcjach.  Wszystkie węzły <math>T_p</math>  stają się liścmi po<math>k-2</math> kontrakcjach na mocy założenia  indukcyjnego (a).Zatem, podobnie jak w przypadku I korzeń całego drzewa staje się liściem po k-1 kontrakcjach.<!--%-->\myskip '''Dowód punktu (b)'''.\myskip Przypadek ten rozpatruje się podobnie jak punkt (a), stosującodpowiednią dekompozycję drzewa <math>T</math>.Dowód ten pozostawiamy jako ćwiczenie.<!--%Rozważmy drzewo <math>T</math> z jednym statycznym węzłem <math>v</math>. Niech--><!--%       </math>|T|  \le--><!--%FIB_k<math>. Nie3ch  </math>x<math> 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  <math>T1</math>, <math>T2</math> oraz <math>T3</math> będą drzewami takimi jak na Rysunku&nbsp;[[#fig14]].--><!--%--><!--%Wtedy  <math>|T1|</math>, <math>|T2| \le FIB_{k-1}</math> oraz <math>|T3| < FIB_{k-1}</math>. Po  <math>(k-1)</math>-szej redukcji drzewa  <math>T1</math> and <math>T2</math> są--><!--%zredukowane do jednego węzła z jednym statycznym liściem , dzięki założeniu indukcyjnemu (b) . Wszystekie--><!--%węzły  <math>T3</math> stają się liśćmi po <math>(k-2)</math>=giej redukcji dzięki założeniu indukcyjnemu (b).--><!--%--><!--%W konsekwencji po redukcji  <math>k-1</math> korzeń całego drzewa T ma jedynego następnika <math>x'</math> takiego, że <math>x'=x</math> lub--><!--%<math>x'\in T_p</math>. Następnie w  <math>k</math>-ej redukcji  korzeń ma jedyne dowiązanie do węzła statycznego <math>v</math>. Kończy to--><!--%dowód indukcyjny punktu (b).--><!--%--><!--%\begin{figure}--><!--%\unitlength=1.00mm \special{em:linewidth 0.4pt} \linethickness{0.4pt}--><!--%\begin{picture}(106.33,34.22)--><!--%\put(13.33,24.00){\line(3,4){6.00}} \put(19.33,31.56){\line(3,-4){6.00}} \put(25.33,23.56){\line(-1,0){5.00}}--><!--%\put(13.33,23.56){\line(1,0){5.33}} \put(19.67,23.56){\circle{0.89}} \put(19.00,22.22){\line(-3,-4){4.00}}--><!--%\put(20.67,22.22){\line(3,-4){4.00}} \put(14.33,15.56){\circle{0.89}} \put(25.67,15.56){\circle{0.89}}--><!--%\put(14.33,14.22){\line(-3,-4){4.33}} \put(14.67,13.78){\line(3,-4){4.00}} \put(25.33,13.78){\line(-3,-4){4.00}}--><!--%\put(26.00,13.78){\line(3,-4){4.00}} \put(30.00,8.44){\line(-1,0){8.33}} \put(19.67,26.22){\makebox(0,0)[cc]{x}}--><!--%\put(28.67,15.56){\makebox(0,0)[cc]{q}} \put(11.67,15.56){\makebox(0,0)[cc]{p}}--><!--%\put(5.33,21.78){\makebox(0,0)[cc]{T}} \put(10.33,8.44){\line(1,0){3.33}} \put(18.33,8.44){\line(-1,0){2.67}}--><!--%\put(13.67,7.11){\rule{1.67\unitlength}{2.22\unitlength}} \put(12.33,4.89){\makebox(0,0)[cc]{v}}--><!--%\put(46.66,24.00){\line(3,4){6.00}} \put(52.66,31.56){\line(3,-4){6.00}} \put(58.66,23.56){\line(-1,0){5.00}}--><!--%\put(46.66,23.56){\line(1,0){5.33}} \put(53.00,26.22){\makebox(0,0)[cc]{x}} \put(84.01,31.56){\circle{0.89}}--><!--%\put(83.34,30.22){\line(-3,-4){4.00}} \put(78.67,23.56){\circle{0.89}} \put(78.67,22.22){\line(-3,-4){4.33}}--><!--%\put(79.01,21.78){\line(3,-4){4.00}} \put(84.01,34.22){\makebox(0,0)[cc]{x}}--><!--%\put(76.01,23.56){\makebox(0,0)[cc]{p}} \put(74.67,16.44){\line(1,0){3.33}} \put(82.67,16.44){\line(-1,0){2.67}}--><!--%\put(78.00,15.11){\rule{1.67\unitlength}{2.22\unitlength}} \put(76.67,12.89){\makebox(0,0)[cc]{v}}--><!--%\put(102.00,32.00){\circle{0.89}} \put(101.66,30.22){\line(-3,-4){4.00}} \put(102.33,30.22){\line(3,-4){4.00}}--><!--%\put(106.33,24.88){\line(-1,0){8.33}} \put(105.00,32.00){\makebox(0,0)[cc]{q}}--><!--%\put(52.00,22.22){\rule{1.67\unitlength}{1.78\unitlength}} \put(43.67,27.11){\makebox(0,0)[cc]{T1}}--><!--%\put(71.34,27.11){\makebox(0,0)[cc]{T2}} \put(95.33,28.00){\makebox(0,0)[cc]{T3}}--><!--%\put(52.67,19.11){\makebox(0,0)[cc]{</math>|<math>T1</math>|\le FIB_{k-1}<math>}} \put(79.34,8.89){\makebox(0,0)[cc]{</math>|<math>T2</math>|\le--><!--%FIB_{k-1}</math>}} \put(102.00,22.22){\makebox(0,0)[cc]{<math>|</math>T3<math>|<FIB_{k-1}</math>}}--><!--%\end{picture}--><!--%--><!--%\input{fig14.pic}--><!--%\caption{ Dekompozycja drzewa <math>T</math> z jdnym statycznym węzłem <math>v</math>.}  <span id="fig14" \> --><!--%\end{figure}-->\vskip 0.3cm\noindent'''Obserwacja.'''\Możliwe są różne inne definicje kontrakcji drzew. Na  przykład moglibyśmy rozważać że w jednej iteracji kontrakcji napierw wykonujemy Rake (usuń liście) a dopiero potem Compress. My wykonywaliśmy to w jednym kroku równocześnie, co wydaje się bardzoej naturalne.\end{document}
+'''Obserwacja.'''Możliwe są różne inne definicje kontrakcji drzew. Na przykład moglibyśmy rozważać, że w jednej iteracji kontrakcji najpierw wykonujemy Rake (usuń liście), a dopiero potem Compress. My wykonywaliśmy to w jednym kroku równocześnie, co wydaje się bardziej naturalne.

Zaawansowane algorytmy i struktury danych/Wykład 14: Różnice pomiędzy wersjami

Aktualna wersja na dzień 22:15, 11 wrz 2023

Spis treści

Obliczanie wyrażeń arytmetycznych: algorytm jednoczesnych podstawień

Równoległa kontrakcja drzew

Oszacowanie liczby kontrakcji

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia