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

Wersja z 11:34, 1 wrz 2006

Algorytmy równoległe I

W module tym zajmiemy się przyspieszaniem obliczeń za pomocą korzystania z wielu procesrów (maszyn) działających równolegle. Niestety nie ma ogólnie przyjętego modelu obliczeń równoległych, rozważymy w tym module dwa modele: maszynę PRAM i układy arytmetyczne (logiczne). O ile maszyna PRAM jest modelem wysoko-poziomowym, to układy arytmetyczne są modelem niskopoziomowym, ale niewątpliwie bardzo istotnym niskopoziomowym, ale niewątpliwie bardzo istotnym.

Model równoległej abstrakcyjnej Maszyny PRAM

Na początku rozważymy wyidealizowany model obleczeń równoległych zwany Równoległą Maszyną ze Swobodnym Dostępem do Pamięci, w skrócie PRAM (od ang. {\em Parallel Random Access Machine}, wymawiany {\em piram}).

\begin{figure}[bhtp] \begin{center} \mbox{\ } \includegraphics[width=10.5cm]{parallel_fig1.eps} \caption{Struktura koncepycyjna PRAMu }

\end{center} \end{figure}

\noindent Maszyna PRAM {\em składa się} z wielu procesorów pracujących synchronicznie, korzystących ze wspólnej pamięci (która oprócz przechowywania danych służy do komunikacji między procesorami). Każdy procesor jest standardowym komputerm typu RAM (ang. {\em Random Access Machine}). Zakładamy, że procesory są ponumerowane liczbami naturalnymi. Procesory wykonują jeden wspólny program, ale wykonanie poszczególnych instrukcji zależy od indeksu procesora. W jednym kroku procesor pobiera dane z pamięci, potem wykonuje operację, którą może być wpisanie pewnych danych. Wszystkie procesory wykonują jeden krok jednocześnie. Rówoległość jest wyrażona poprzez następującą instrukcję: \myskip \begin{center} \textbf{for all} $i \in X$ \textbf{do in parallel}\ akcja $(i)$ . \end{center} \myskip \noindent Wykonanie tej instrukcji polega na wykonaniu dwóch równoległych operacji:

przydzielenie procesora do każdego elementu ze zbioru $X$ ,
jednoczesne wykonanie przez każdy procesor operacji akcja $(i)$ .

Przeważnie zapis `` $i \in X$ jest w rodzaju\ `` $1 \leq i \leq n$ jeśli $X$ jest zbiorem liczb naturalnych. Litera C (od ang. concurrent) oznacza możliwość jednoczesnego wykonania operacji przez wiele procesorów, E (od ang. exclusive) wyklucza taką możliwość. Operacjami są R (czytanie, od ang. read) oraz W (zapis, od ang. write) w tej samej komórce przez wiele procesorów w tym samym momencie. Mamy zatem EREW PRAM, CREW PRAM, CRCW PRAM (modelu ERCW nie rozważamy jako zupełnie sztuczny).

Podstawowym naszym mdoelem PRAMu będzie CREW PRAM: wiele procesrów może jednocześnie czytać z tej samej komórki, ale tylko jeden może zapisywać. \myskip Prostym przykładem obliczenia na CREW jest liczenie kolejnych wierszy trójkąta Pasacala. Początkowo zakładamy, że $A = [0, 0, 0, 0, 0, 1]$ . Wykonujemy: \vskip 0.2cm \begin{center} \begin{minipage}{10cm} repeat 6 times

for each $1 \leq i \leq 5$ do in parallel \\ \hspace*{1cm} $A [i] : = A [i] + A [i + 1]$ \end{minipage} \end{center} \vskip 0.2cm \noindent Kolejnymi wartościami tablicy A są wektory: \vskip 0.2cm \begin{center} \noindent 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 1

\noindent 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 1

\noindent 0\ \ 0\ \ 0\ \ 0\ \ 1\ \ 1

\noindent 0\ \ 0\ \ 0\ \ 1\ \ 2\ \ 1

\noindent 0\ \ 0\ \ 1\ \ 3\ \ 3\ \ 1

\noindent 0\ \ 1\ \ 4\ \ 6 \ \ 4\ \ 1

\noindent 1\ \ 5\ 10 \ 10\ \ 5\ \ 1 \end{center}

Najważniejszą klasą problemów algorytmicznych stanowią problemy które można obliczyć w czasie wielomianowo-logarytmicznym używając wielomianowej liczby procesorów. Klasę tę oznaczamy przez NC, odpowiadające algorytmy nazywamy algorytmami typu NC.

Niech $𝒫$ oznacza klasę problemów wykonywanych w deterministycznym czasie wielomianowym na maszynie sekwencyjnej. Podstawowym problemem teoretycznym algorytmiki równoległej jest pytanie:

\centerline{ $𝒫 = 𝒩 𝒞$ ?} \myskip Podobnie jak problemy NP-zupełne można zdefiniować probly P-zupełne. Są to te problemy $X \in 𝒫$ , takie że dla każdego innego problemu $Y \in 𝒫$ istnieje NC-redukcja Y do X. Inaczej mówiąc

\centerline{ $𝒫 = 𝒩 𝒞$ wtedy i tylko wtedy gdy \ $X \in N C$ } \myskip Przykłady problemów P-zupełnych:\ programowanie liniowe, maksymalny przepływ w grafie, konstrukcja drzewa DFS, obliczanie wartości układów logicznych, sprawdzanie czy gramatyka bezkontekstowa generuje język pusty. \myskip Przez pracę algorytmu równoległego rozumiemy liczbę procesorów pomnożoną orzez czas. Algorytm jest optymalny gdy jego praca jest tego samego rzędu co czas najlepszego znanego algorytmu sekwencyjnego dla danego problemu.

W szczególności interesują nas algorytmy, które są jednocześnie optymalne i są typu NC. Z praktycznego punku widzenia czynnik $l o g n$ przy liczbie procesorów i przy pracy algorytmu nie jest zbyt istotny. Natomiast czynnik logarytmiczny jest istotny jeśli chodzi o równoległy czas. W tym przypadku potęga logarytmu odgrywa podobną rolę co potęga wielomianu opisującego czas obliczenia sekwencyjnego. Różnica między CRCW i CREW PRAMem w aspekcie klasy NC polega przeważnie na dodaniu jednego czynnika logarytmicznego w funkcji równoległego czasu obliczenia. W przypadku CRCW PRAM założymy, że procesory, jeśli wpisują jednocześnie do tej samej komórki pamięci, to wpisują to samo. Na przykład jeśli początkowo $o u t p u t = 0$ wówczas następujący algorytm obliczy logiczną alternatywę w czasie stałym na CRCW PRAM. \myskip for each $1 \leq i \leq n$ do in parallel \\ \hspace*{1cm} if $A [i] = 1$ then output=1; \vskip 0.6cm Na CREW potrzebujemy logarytmicznego czasu równoległego aby to zrobić. Pokażemy jeszcze dwa proste problemy, które można na CRCW PRAM wykonać w czasei stałym. Następujący algorytm liczy pierwszą pozycję minimalnego elementu w tablicy C[1 . . n] w czasie O(1). \vskip 0.4cm for each $1 \leq i \leq n$ do in parallel $M [i]$ := 0;

for each $1 \leq i, j \leq n$ do in parallel \\ \hspace*{1cm} if $i \neq j$ and $C [i] \leq C [j]$ then $M [i]$ :=1;

for each $1 \leq i \leq n$ do in parallel \\ \hspace*{1cm} if $M [i]$ = 0 then output :=i ; \myskip Oznaczmy ten algorytm przez $A_{1}$ . Algorytm korzysta z $n^{2}$ procesorów. Spróbujemy zmniejszyć tę liczbę do $O (n^{1 + ϵ})$ zachowując czas $O (1)$ , dla dowolnie małego $ϵ > 0$ .

\noindent Niech

\centerline{ $P_{k} (n) = n^{1 + ϵ_{k}}$ , gdzie $ϵ_{k} = \frac{1}{2^{k} - 1}$ .} \myskip \noindent Przypuśćmy, że mamy algorytm $A_{k}$ liczenia minimum w czasie $O (1)$ z $O (P_{k} (n))$ procesorami. Skonstruujemy algorytm $A_{k + 1}$ który działa w czasie stałym i używa tylko $O (P_{k + 1} (n))$ procesorów. \vskip 0.5cm \noindent Algorytm}\ Parser nie mógł rozpoznać (błąd składni): {\displaystyle A_{k+1'''} :

niech $α = \frac{1}{2^{k} + 1}$ ;

podziel tablicę C na rozłączne bloki rozmiaru $n^{α}$ każdy;

równolegle zastosuj algorytm $A_{k}$ do każdego z tych bloków;

zastosuj algorytm $A_{k}$ do tablicy C' składającej się z $\frac{n}{n^{α}}$ minimów w blokach. \vskip 0.5cm \noindent Algorithm $A_{k + 1}$ działa w czasie $O (1)$ korzystając z $P_{k + 1} (n))$ procesorów. Uzasadnienie pozostawiamy jako ćwiczenie. \vskip 0.3cm \noindent Algorytmy $A_{2}, A_{3}, A_{4}, \dots$ używają odpowiednio następującą (asymptotycznie) liczbę procesorów

$n^{1 + \frac{1}{3}}, n^{1 + \frac{1}{15}}, n^{1 + \frac{1}{255}}, n^{1 + \frac{1}{65535}} . .$ . \myskip Rozważmy jeszcze na CRCW PRAM następujący problem pierwszej jedynki: \ dana tablica zerojedynkowa, znaleźć pozycję pierwszej jedynki (od lewej). \myskip Następujący algorytm rozwiązuje problem w czasie stałym z kwadratową liczbą procesorów. Zakładamy na razie, że w ciągu jest jakaąs jedynka. \vskip 0.3cm Algorytm Pierwsza-Jedynka-1;

for each $1 \leq i < j \leq n$ do in parallel

\hspace*{0.6cm} if A[i]=1] and A[j]=1 then A[j]:= 0;

for each $1 \leq i \leq n$ do in parallel

\hspace*{0.6cm} if A[i]=1 then FirstOne :=i. \vskip 0.3cm \noindent Możemy podobnie łatwo sprawdzić czy w ogóle jest jedynka. \vskip 0.3cm Algorytm CzyJestJedynka;

jest-jedynka := 0;

for each $1 \leq i \leq n$ do in parallel

\hspace*{0.6cm} if A[i]=1 then jest-jedynka := 1;

\vskip 0.2cm \noindent Oba powyższe algorytmy korzystają z $O (n^{2})$ procesorów. Możemy łatwo tę liczbę zmniejszyć do liniowej. \myskip Algorytm Pierwsza-Jedynka; \vskip 0.1cm (1)\ Podziel tablicę A na segmenty długośći $\sqrt{n}$ ;

(2)\ W każdym segmencie zastosuj algorytm CzyJestJedynka;

(3)\ } Otrzymujemy ciąg zerojedynkowy $C$ długości Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sqrt{n'''} jako wynik kroku (2);

(4)\ znajdź pierwszą jedynkę w ciągu C za pomocą algorytmu Pierwsza-Jedynka-1;;

(5)\ Zastosuj algorytm Pierwsza-Jedynka-1 do segmentu odpowiadającego \\ \hspace*{1.4cm} pierwszej jedynce w C; \myskip W ten sposób stosujemy trzy razy algorytm o pracy kwadratowej do segmentu długości $\sqrt{n}$ , otrzymujemy złożoność $O ({\sqrt{n}}^{2}) = O (n)$ . Czas jest $O (1)$ . Do szybkich obliczeń równoległych najbardziej nadają się problemy związane z drzewami, chociaż czasami w tych problemach nie widać od razu struktury drzewiastej. Struktura taka odpowiada również drzewu rekursji. Jako przykład rozważmy problem obliczenia sumy $A [1] + A [2] + \dots A [n]$ . Dla uproszczenia załóżmy, że n jest potęgą dwójki.

\begin{figure}[htbp] \begin{center} \mbox{\ } \includegraphics[width=10.cm]{parallel_fig2.eps} \caption{ Metoda pełnego zrównoważonego drzewa binarnego:\ układ arytmetyczny obliczania sumy. Maksymalny poziom $m = \log n$ .}

\end{center} \end{figure}

\noindent Wysokością węzła jest jego maksymalna odległość od liścia, wysokość liścia wynosi 0. Przez $p$ -ty poziom rozumiemy zbiór węzłów o wysokości $p$ . Załóżmy, że elementy $A [1], A [2], . . A [n]$ są umieszczone w liściach pełnego zrównoważonego drrzewa binarnego, następnie wykonujemy (patrz rysunek): \vskip 0.4cm for $p : = 1$ to $\log n$ do

\hspace*{0.5cm} oblicz jedmocześnie wartości węzłów na poziomie $p$ -tym; \myskip Drzewo jest strukturą koncepcyjną, każdemu węzłowi możemy przypisać miejsce w pamięci. W naszym przypadku węzły na poziomie $p$ -tym mogą odpowiadać elementom \\ \centerline{ $A [2^{p}], A [2 * 2^{p}], . . A [3 * 2^{p}] \dots$ . } Poprzedni algorytm można zapisać w formie: \vskip 0.4cm \noindent for $p : = 1$ to $\log n$ do\\ \hspace*{0.5cm} $Δ = 2^{p}$ ; \\ \hspace*{0.5cm} for each $1 \leq i \leq n / Δ$ do in parallel \\ \hspace*{0.9cm} $A [i * Δ] : = A [i * Δ] - Δ / 2] + A [i * Δ]$ ; \\ wynik := $A [n]$ ; \myskip \begin{figure}[hbtp] \begin{center} \mbox{\ } \includegraphics[width=9.cm]{parallel_fig3.eps} \caption{Koncepcyjna struktura równoległej wersji metody {\em dziel i zwycieżaj}. }

\end{center} \end{figure}

Drzewa odpowiadają w pewnym sensie rekursji. Wysokość drzew odpowiada czasowi równoległemu. Podobnie głębokość rekursji odpowiada też czasowi równoległemu. Równoległa wersja tzw. metody dziel i zwyciężaj polega na tym że wywołania rekurencyjne wykonujemy jednocześnie (patrz rysunek). Oczywiście może się zdarzyć, że jedno z nich zakończy się wcześniej. Tym niemniej algorytm czeka na zakończenie obu wywołań.

Pokażemy dwa przykłady zastosowania metody dziel i zwyciężaj w wersji równoległej. Zaczniemy od sumy elementów tablicy $A [1 . . n]$ . Wynik obliczamy jako $S U M A (1, n)$ . Zakładamy znowu, że $n$ jest potęgą dwójki. \myskip \begin{center} \begin{minipage}{12cm} \vskip0.3cm \hspace*{0.6cm}\textbf{funkcja} $S U M A (i, j)$ ; \\ \hspace*{1.2cm}\textbf{if} $j = i$ \textbf{then return} $A [i]$ \textbf{else }\\ \hspace*{1.8cm}{do in parallel} \\ \hspace*{2.5cm} wynik1 := $S U M A (i, ⌊ (i + j) / 2 ⌋$ ;\\ \hspace*{2.5cm} wynik2 := $S U M A (⌈ (i + j) / 2 ⌉, j)$ ;\\ \hspace*{1.8cm}\textbf{return} wynik1 + wynik2; \vskip0.4cm \end{minipage} \end{center} \myskip \noindent Podobny jest schemat sortowania na PRAMie. Niech $P a r a l l e l M e r g e (x)$ będzie algorytmem który, otrzymawszy tablicę $x$ z posortowanymi lewą i prawą połową da wyniku tablicę $x$ posortowaną. łatwo to zrobić w czasie $O (\log n)$ z $n$ procesorami. Dla $i > n / 2$ -ty procesor znajduje w pierwszej połówce sekwencyjnie metodą {\em binary search} najmniejszy element większy od $x [i]$ . Wymaga to czasu $O (\log n)$ . Potem każdy procesor{\em wie} gdzie wstawić {\em swój} element. W sumie otrzymujemy algorytm sortowania w czasie $O (\log^{2})$ z $n$ procesorami. \begin{center} \begin{minipage}{12cm} \vskip0.3cm \hspace*{0.6cm}\textbf{funkcja} $P a r a l l e l S o r t (x)$ ; \\ \hspace*{1.2cm} $n : = s i z e (x)$ ;\\ \hspace*{1.2cm}\textbf{if} $n > 1$ \textbf{then } \\ \hspace*{1.8cm}\textbf{do in parallel}\\ \hspace*{2.5cm} $P a r a l l e l S o r t (F i r s t H a l f (x))$ ;\\ \hspace*{2.5cm} $P a r a l l e l S o r t (S e c o n d H a l f (x))$ ;\\ \hspace*{1.8cm} $P a r a l l e l M e r g e (x)$ \vskip0.4cm \end{minipage} \end{center} \myskip Liczbę procesorów można zmniejszyc do $n / (\log n))$ . Natomiast nietrywialnym jest zmniejszenie czasu na CREW PRAM. Zostało to zrobione przez Richarda Cole'a, który skonstruował algorytm działający w czaie $O (\log n)$ z $O (n)$ procesorami maszyny EREW PRAM. Algorytm ten jest bardzo interesujący ale skomplikowany. \newpage Być może najbardziej podstawowym modelem obliczeń równoległych są układy arytmetyczne (lub logiczne): acyckliczne grafy z przypisaniem pewnych operacji węzłom wewnętrznym. Każdy węzeł liczy pewną wartość w momencie gdy wartości jego poprzedników są policzone. Podobnie jak w drzewie możemy zdefinować pojęcie liścia: węzeł bez poprzedników. Natomiast graf nie musi mieć jednego korzenia, zamiast korzenia w grafie wyróżniamy węzły wynikowe (na rysunku te z których wychodzi strzałka {\em do nikąd}).

Równoległy czas obliczenia odpowiada maksymalej wysokości węzła. Poziomy definiujemy podobnie jak dla drzewa. Algorytm równoległy w jednym równoległym kroku oblicza kolejny poziom. Liczba procesorów odpowiada z reguły maksymalnemu roziarowi poziomu, chociaż możemy inaczej rozplanować obliczenie gdy jedne poziomy są duże, a drugie małe (ale możemy wtedy zmienić strukturę grafu tak aby temu odpowiadała).

Przykładem układu arytmetycznego jest drzewo z rysunku powyżej, które opisuje sumowanie n elementów. Zajmiemy się teraz pewnym rozszerzeniem problemu sumowania. Niech $\oplus$ będzie pewną łączną operacją arytmetyczną (np. suma, mnożenie, maksimum, minimum, pozycja pierwszej jedynki z lewej strony, podobnie z prawej strony).

\noindentProblem sum p[refiksowych.\ dany wektor $x$ rozmiaru $n$ , obliczyć ciąg $y$ taki, gdzie \myskip \begin{center} $y [1] = x [1]$ , $y [2] = x [1] \oplus x [2]$ , $y [3] = x [1] \oplus x [2] \oplus x [3]$ , \ldots \end{center} gdzie \myskip Opiszemy dwa rekurencyjne algorytmy dla tego problemu. Niech $F i r s t H a l f$ , $S e c o n d H a l f$ oznaczją lewą i prawą (odpowiednio) połówkę ciągu. Zakładamy, że n jest potęgą dwójki. \myskip \begin{center} \begin{minipage}{12cm} \vskip0.3cm \hspace*{0.6cm}\textbf{Algorytm} $P r e f S u m s 1 (x)$ ; \\ \hspace*{1.2cm} $n : = s i z e (x)$ ;\\ \hspace*{1.2cm}\textbf{if} $n > 1$ \textbf{then } \\ \hspace*{1.8cm}\textbf{do in parallel}\\ \hspace*{2.5cm} $P r e f S u m s 1 (F i r s t H a l f (x))$ ;\\ \hspace*{2.5cm} $P r e f S u m s 1 (S e c o n d H a l f (x))$ ;\\ \hspace*{1.8cm}\textbf{for each } $n / 2 < j \leq n$ , \textbf{do in parallel} \\ \hspace*{2.4cm} $x [j] : = x [n / 2] \oplus x [j]$ ;\\ \vskip0.4cm \end{minipage} \end{center} \myskip

Układ arytmetyczny odpowiadający algorytmowi PrefSums1 jest przedstawiony na Rysunku #parallel_fig5 dla $n = 4$ i $n = 8$ . Zauważmy, że zasadniczą częśCią układu dla $n = 8$ są dwie kopie układu dla $n = 4$ . Dodatkowo dodajemy węzły odpowiadającej ostatniej instrukcji w algorytmie PrefSums1.

\begin{figure}[bhtp] \begin{center} \mbox{\ } \includegraphics[width=11.5cm]{parallel_fig5.eps} \caption{Układ arytmetyczny odpowiadający algorytmowi PrefSums1. Kolejne grafy powstają jako podwójne kopie porzednich grafów (dla $n / 2$ elementów) z dodanymi elementami odpowiadającymi operacji $x [j] : = x [n / 2] \oplus x [j]$ . }

\end{center} \end{figure}

\noindent Opiszemy teraz inny algorytm rekurencyjny, w którym mamy tylko jedno wywołanie rekurecyjne (w jednej instancji rekursji).

\myskip \begin{center} \begin{minipage}{12cm} \vskip0.3cm \hspace*{0.6cm}\textbf{Algorytm} $P r e f S u m s 2 (x)$ ; \\ \hspace*{1.2cm} $n : = s i z e (x)$ ;\\ \hspace*{1.2cm}\textbf{if} $n > 1$ \textbf{then } \\ \hspace*{1.8cm} utwórz nową tablicę y;\\ \hspace*{1.8cm} for each } $1 \leq i \leq n / 2$ \textbf{do in parallel\\ \hspace*{2.5cm} $y [i] : = x [2 i - 1] \oplus x [2 i]$ ;\\ \hspace*{1.8cm} $P r e f S u m s 2 (y)$ ;\\ \hspace*{1.8cm} for each } $1 \leq i \leq n / 2$ \textbf{do in parallel\\ \hspace*{2.4cm} $x [2 i] : = y [i]$ ;\\ \hspace*{2.4cm} if $i > 1$ then \ $x [2 i - 1] : = y [i - 1] \oplus x [2 i - 1]$ ;\\ \vskip0.4cm \end{minipage} \end{center} \myskip Układ arytmetyczny odpowiadający algorytmowi jest pokazany na rysunku #parallel_fig4. \begin{figure}[bhtp] \begin{center} \mbox{\ } \includegraphics[width=7.2cm]{parallel_fig4.eps} \caption{Układ arytmetyczny odpowiadający PrefSums2. Kolejny graf składa się z pojedyńczej kopii poprzedniego grafu (dla $n / 2$ ), oraz $n / 2 - 1$ dodatkowych operacji. }

\end{center} \end{figure}

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

Wersja z 11:34, 1 wrz 2006

Spis treści

Model równoległej abstrakcyjnej Maszyny PRAM

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 1: / Linia 1: @@
-\noindent '''\Large Moduł ZASD:\ Algorytmy równoległe I''' \myskip
+<font size="6"> Algorytmy równoległe I </font>
-<!--%--------+---------+---------+---------+---------+---------+---------+---------+
--->W module tym  zajmiemy się  przyspieszaniem obliczeń za pomocš korzystania
+__TOC__
-z wielu procesrów (maszyn) działajšcych równolegle.
-Niestety nie ma ogólnie przyjętego modelu obliczeń równoległych, rozważymy w tym module dwa modele:
-maszynę PRAM i układy arytmetyczne (logiczne). O ile maszyna PRAM jest modelem wysoko-poziomowym, to
+W module tym  zajmiemy się  przyspieszaniem obliczeń za pomocą korzystania z wielu procesrów (maszyn) działających równolegle. Niestety nie ma ogólnie przyjętego modelu obliczeń równoległych, rozważymy w tym module dwa modele: maszynę PRAM i układy arytmetyczne (logiczne). O ile maszyna PRAM jest modelem wysoko-poziomowym, to układy arytmetyczne są modelem niskopoziomowym, ale niewątpliwie bardzo istotnym niskopoziomowym, ale
-układy arytmetyczne sš modelem niskopoziomowym, ale niewštpliwie bardzo istotnym niskopoziomowym, ale
+niewątpliwie bardzo istotnym.
-niewštpliwie bardzo istotnym.
-Na poczštku rozważymy wyidealizowany model obleczeń równoległych
+== Model równoległej abstrakcyjnej Maszyny PRAM ==
-zwany Równoległš Maszynš ze Swobodnym Dostępem do Pamięci, w skrócie
+Na początku rozważymy wyidealizowany model obleczeń równoległych zwany Równoległą Maszyną ze Swobodnym Dostępem do Pamięci, w skrócie
 PRAM (od ang. {\em Parallel Random Access Machine}, wymawiany {\em piram}).
@@ Linia 22: / Linia 22: @@
 -->
-\noindent Maszyna    PRAM {\em składa się} z wielu procesorów pracujšcych synchronicznie,
+\noindent Maszyna    PRAM {\em składa się} z wielu procesorów pracujących synchronicznie,
-korzystšcych ze wspólnej pamięci (która oprócz przechowywania danych służy do
+korzystących ze wspólnej pamięci (która oprócz przechowywania danych służy do
 komunikacji między procesorami). Każdy procesor jest standardowym komputerm typu RAM
-(ang. {\em Random Access Machine}). Zakładamy, że procesory sš ponumerowane
+(ang. {\em Random Access Machine}). Zakładamy, że procesory są ponumerowane
 liczbami naturalnymi.
-Procesory wykonujš jeden wspólny program, ale wykonanie poszczególnych instrukcji
+Procesory wykonują jeden wspólny program, ale wykonanie poszczególnych instrukcji
 zależy od indeksu procesora.
-W jednym kroku procesor pobiera dane z pamięci, potem wykonuje operację, którš może być
+W jednym kroku procesor pobiera dane z pamięci, potem wykonuje operację, którą może być
-wpisanie pewnych danych. Wszystkie procesory wykonujš jeden krok jednocze�nie.
+wpisanie pewnych danych. Wszystkie procesory wykonują jeden krok jednocześnie.
-Rówoległo�ć jest wyrażona poprzez następujšcš instrukcję:
+Rówoległość jest wyrażona poprzez następującą instrukcję:
 \myskip
 \begin{center}
@@ Linia 41: / Linia 41: @@
 *przydzielenie procesora do każdego elementu ze zbioru <math>X</math>,
 *jednoczesne wykonanie przez każdy procesor operacji akcja<math>(i)</math>.
-Przeważnie zapis  ``<math>i \in X</math>'' jest w rodzaju\  ``<math>1\leq i\leq n</math>'' je�li  <math>X</math> jest zbiorem liczb naturalnych.
+Przeważnie zapis  ``<math>i \in X</math>'' jest w rodzaju\  ``<math>1\leq i\leq n</math>'' jeśli  <math>X</math> jest zbiorem liczb naturalnych.
 <!--%%
--->Litera C (od ang. concurrent) oznacza możliwo�ć jednoczesnego wykonania operacji przez wiele procesorów,
+-->Litera C (od ang. concurrent) oznacza możliwość jednoczesnego wykonania operacji przez wiele procesorów,
-E (od ang. exclusive) wyklucza takš możliwo�ć.  Operacjami sš R (czytanie, od ang. read) oraz W (zapis, od ang. write)
+E (od ang. exclusive) wyklucza taką możliwość.  Operacjami są R (czytanie, od ang. read) oraz W (zapis, od ang. write)
 w tej samej komórce przez wiele procesorów w tym samym momencie.
 Mamy zatem EREW PRAM, CREW PRAM, CRCW PRAM (modelu ERCW nie rozważamy jako zupełnie sztuczny).
 Podstawowym naszym mdoelem PRAMu będzie CREW PRAM: wiele
-procesrów może jednocze�nie czytać z tej samej komórki, ale tylko jeden może zapisywać.
+procesrów może jednocześnie czytać z tej samej komórki, ale tylko jeden może zapisywać.
 \myskip
 Prostym przykładem
-obliczenia na CREW jest liczenie kolejnych wierszy trójkšta Pasacala. Poczštkowo zakładamy, że
+obliczenia na CREW jest liczenie kolejnych wierszy trójkąta Pasacala. Początkowo zakładamy, że
 <math>A = [0,0,0,0,0,1]</math>. Wykonujemy:
 \vskip 0.2cm
@@ Linia 64: / Linia 64: @@
 \end{center}
 \vskip 0.2cm \noindent
-Kolejnymi warto�ciami tablicy A sš wektory:
+Kolejnymi wartościami tablicy A są wektory:
 \vskip 0.2cm
 \begin{center}
@@ Linia 83: / Linia 83: @@
 \end{center}
-Najważniejszš klasš problemów algorytmicznych stanowiš problemy które można obliczyć w czasie
+Najważniejszą klasą problemów algorytmicznych stanowią problemy które można obliczyć w czasie
-wielomianowo-logarytmicznym używajšc wielomianowej liczby procesorów. Klasę tę oznaczamy przez NC, odpowiadajšce
+wielomianowo-logarytmicznym używając wielomianowej liczby procesorów. Klasę tę oznaczamy przez NC, odpowiadające
 algorytmy nazywamy algorytmami typu NC.
@@ Linia 92: / Linia 92: @@
 \centerline{<math> \cal{P}\ = \ NC \ </math>?}
 \myskip
-Podobnie jak problemy NP-zupełne można zdefiniować probly P-zupełne. Sš to te problemy <math>X \in \cal{P}</math>, takie
+Podobnie jak problemy NP-zupełne można zdefiniować probly P-zupełne. Są to te problemy <math>X \in \cal{P}</math>, takie
 że dla każdego innego problemu <math>Y \in \cal{P}</math> istnieje NC-redukcja Y do X.
-Inaczej mówišc
+Inaczej mówiąc
 \centerline{<math> \cal{P} =  NC \ </math> wtedy i tylko wtedy gdy \ <math>X \in NC</math>}
 \myskip
 '''Przykłady problemów P-zupełnych:\ '''
-programowanie liniowe, maksymalny przepływ w grafie, konstrukcja drzewa DFS, obliczanie warto�ci układów logicznych,
+programowanie liniowe, maksymalny przepływ w grafie, konstrukcja drzewa DFS, obliczanie wartości układów logicznych,
 sprawdzanie czy gramatyka bezkontekstowa generuje język pusty.
 \myskip
-Przez pracę algorytmu równoległego rozumiemy liczbę procesorów pomnożonš orzez czas.
+Przez pracę algorytmu równoległego rozumiemy liczbę procesorów pomnożoną orzez czas.
 Algorytm jest optymalny gdy jego praca jest tego samego rzędu co czas najlepszego znanego algorytmu sekwencyjnego dla
 danego problemu.
-W szczególno�ci interesujš nas algorytmy, które sš jednocze�nie optymalne i sš typu NC.
+W szczególności interesują nas algorytmy, które są jednocześnie optymalne i są typu NC.
 Z praktycznego punku widzenia czynnik <math>log n</math> przy liczbie procesorów i przy pracy algorytmu
-nie jest zbyt istotny. Natomiast czynnik logarytmiczny jest istotny je�li chodzi o równoległy czas. W tym przypadku
+nie jest zbyt istotny. Natomiast czynnik logarytmiczny jest istotny jeśli chodzi o równoległy czas. W tym przypadku
-potęga logarytmu odgrywa podobnš rolę co potęga wielomianu opisujšcego czas obliczenia sekwencyjnego.
+potęga logarytmu odgrywa podobną rolę co potęga wielomianu opisującego czas obliczenia sekwencyjnego.
 Różnica między CRCW i CREW PRAMem w aspekcie klasy NC polega przeważnie na dodaniu jednego czynnika logarytmicznego
 w funkcji równoległego czasu obliczenia.
@@ Linia 116: / Linia 116: @@
 --><!--%
 --><!--%
--->W przypadku CRCW PRAM założymy, że procesory, je�li wpisujš jednocze�nie do tej samej komórki pamięci, to
+-->W przypadku CRCW PRAM założymy, że procesory, jeśli wpisują jednocześnie do tej samej komórki pamięci, to
-wpisujš to samo. Na przykład je�li poczštkowo <math>output=0</math> wówczas następujšcy algorytm obliczy logicznš
+wpisują to samo. Na przykład jeśli początkowo <math>output=0</math> wówczas następujący algorytm obliczy logiczną
 alternatywę w czasie stałym na CRCW PRAM.
 \myskip
@@ Linia 123: / Linia 123: @@
 \hspace*{1cm} if <math>A[i] =1</math> then output=1; \vskip 0.6cm Na CREW potrzebujemy logarytmicznego czasu równoległego
 aby to zrobić. Pokażemy jeszcze dwa proste problemy, które można na CRCW PRAM wykonać w czasei stałym.
-Następujšcy algorytm liczy pierwszš  pozycję minimalnego elementu w  tablicy  C[1 . . n] w czasie  O(1). \vskip 0.4cm
+Następujący algorytm liczy pierwszą  pozycję minimalnego elementu w  tablicy  C[1 . . n] w czasie  O(1). \vskip 0.4cm
 '''for each''' <math>1 \le i\le n</math> '''do in parallel'''  <math>M[i]</math> := 0;
@@ Linia 133: / Linia 133: @@
 \\ \hspace*{1cm} if <math>M[i]</math> = 0 then output :=i ;
 \myskip Oznaczmy ten algorytm przez <math>A_1</math>. Algorytm korzysta z <math>n^2</math> procesorów. Spróbujemy zmniejszyć tę
-liczbę do <math>O(n^{1+\epsilon})</math> zachowujšc czas <math>O(1)</math>, dla dowolnie małego <math>\epsilon >0</math>.
+liczbę do <math>O(n^{1+\epsilon})</math> zachowując czas <math>O(1)</math>, dla dowolnie małego <math>\epsilon >0</math>.
 \noindent Niech
@@ Linia 139: / Linia 139: @@
 \centerline{<math>P_k(n)= n^{1+\epsilon_k}</math>, gdzie <math>\epsilon_k\ =\ \frac{1}{2^{k}-1}</math>.}
 \myskip
-\noindent Przypu�ćmy, że mamy algorytm <math>A_k</math> liczenia minimum w czasie <math>O(1)</math> z <math>O(P_k(n))</math> procesorami.
+\noindent Przypuśćmy, że mamy algorytm <math>A_k</math> liczenia minimum w czasie <math>O(1)</math> z <math>O(P_k(n))</math> procesorami.
 Skonstruujemy algorytm <math>A_{k+1}</math> który działa w czasie stałym i używa tylko  <math>O(P_{k+1}(n)) </math> procesorów.
 \vskip 0.5cm \noindent '''Algorytm}\ <math>A_{k+1'''</math>:
@@ Linia 145: / Linia 145: @@
 niech <math>\alpha=\frac{1}{2^{k}+1}</math>;
-podziel tablicę C na rozłšczne bloki rozmiaru <math>n^{\alpha}</math> każdy;
+podziel tablicę C na rozłączne bloki rozmiaru <math>n^{\alpha}</math> każdy;
 równolegle zastosuj algorytm  <math>A_k</math> do każdego z tych bloków;
-zastosuj algorytm  <math>A_k</math> do tablicy C' składajšcej się z  <math>\frac{n}{n^{\alpha}}</math> minimów w blokach. \vskip
+zastosuj algorytm  <math>A_k</math> do tablicy C' składającej się z  <math>\frac{n}{n^{\alpha}}</math> minimów w blokach. \vskip
-.5cm \noindent Algorithm <math>A_{k+1}</math> działa w czasie <math>O(1)</math> korzystajšc z  <math>P_{k+1}(n))</math> procesorów.
+.5cm \noindent Algorithm <math>A_{k+1}</math> działa w czasie <math>O(1)</math> korzystając z  <math>P_{k+1}(n))</math> procesorów.
-Uzasadnienie pozostawiamy jako ćwiczenie. \vskip 0.3cm \noindent Algorytmy  <math>A_2,\ A_3,\  A_4, \ldots</math> używajš
+Uzasadnienie pozostawiamy jako ćwiczenie. \vskip 0.3cm \noindent Algorytmy  <math>A_2,\ A_3,\  A_4, \ldots</math> używają
-odpowiednio następujšcš (asymptotycznie) liczbę procesorów
+odpowiednio następującą (asymptotycznie) liczbę procesorów
 <math>n^{1+\frac{1}{3}},\ \ n^{1+\frac{1}{15}},\  \ n^{1+\frac{1}{255}},  \ \ n^{1+\frac{1}{65535}} ..</math>. \myskip
-Rozważmy jeszcze   na CRCW PRAM następujšcy '''problem pierwszej jedynki''':
+Rozważmy jeszcze   na CRCW PRAM następujący '''problem pierwszej jedynki''':
 \
-dana tablica zerojedynkowa, znale�ć pozycję pierwszej jedynki (od lewej). \myskip Następujšcy algorytm
+dana tablica zerojedynkowa, znaleźć pozycję pierwszej jedynki (od lewej). \myskip Następujący algorytm
-rozwišzuje problem w czasie stałym z kwadratowš liczbš procesorów. Zakładamy na razie, że w cišgu jest jakašs jedynka.
+rozwiązuje problem w czasie stałym z kwadratową liczbą procesorów. Zakładamy na razie, że w ciągu jest jakaąs jedynka.
 \vskip 0.3cm '''Algorytm'''
 Pierwsza-Jedynka-1;
@@ Linia 177: / Linia 177: @@
 \hspace*{0.6cm} if A[i]=1 then jest-jedynka := 1;
-\vskip 0.2cm \noindent Oba powyższe algorytmy korzystajš z <math>O(n^2)</math> procesorów. Możemy łatwo tę liczbę
+\vskip 0.2cm \noindent Oba powyższe algorytmy korzystają z <math>O(n^2)</math> procesorów. Możemy łatwo tę liczbę
 zmniejszyć do liniowej. \myskip '''Algorytm''' Pierwsza-Jedynka; \vskip 0.1cm '''(1)\ ''' Podziel tablicę A na
-segmenty długo�ći <math>\sqrt{n}</math>;
+segmenty długośći <math>\sqrt{n}</math>;
 '''(2)\ ''' W każdym segmencie zastosuj algorytm CzyJestJedynka;
-'''(3)\ } Otrzymujemy cišg zerojedynkowy <math>C</math> długo�ci  <math>\sqrt{n'''</math> jako wynik kroku (2);
+'''(3)\ } Otrzymujemy ciąg zerojedynkowy <math>C</math> długości  <math>\sqrt{n'''</math> jako wynik kroku (2);
-'''(4)\ ''' znajd� pierwszš jedynkę w cišgu C za pomocš algorytmu Pierwsza-Jedynka-1;;
+'''(4)\ ''' znajdź pierwszą jedynkę w ciągu C za pomocą algorytmu Pierwsza-Jedynka-1;;
-'''(5)\ ''' Zastosuj algorytm Pierwsza-Jedynka-1 do segmentu odpowiadajšcego
+'''(5)\ ''' Zastosuj algorytm Pierwsza-Jedynka-1 do segmentu odpowiadającego
 \\ \hspace*{1.4cm}
 pierwszej jedynce w C;
-\myskip W ten sposób stosujemy trzy  razy algorytm o pracy kwadratowej do segmentu długo�ci <math>\sqrt{n}</math>,
+\myskip W ten sposób stosujemy trzy  razy algorytm o pracy kwadratowej do segmentu długości <math>\sqrt{n}</math>,
-otrzymujemy złożono�ć <math>O(\sqrt{n}^2) = O(n)</math>. Czas jest <math>O(1)</math>.
+otrzymujemy złożoność <math>O(\sqrt{n}^2) = O(n)</math>. Czas jest <math>O(1)</math>.
 <!--%
--->Do szybkich obliczeń równoległych najbardziej nadajš się problemy zwišzane z drzewami, chociaż czasami w tych
+-->Do szybkich obliczeń równoległych najbardziej nadają się problemy związane z drzewami, chociaż czasami w tych
 problemach nie widać od razu struktury drzewiastej. Struktura taka odpowiada również drzewu rekursji.
 Jako przykład rozważmy problem obliczenia sumy <math>A[1]+A[2]+\ldots A[n]</math>. Dla uproszczenia
-załóżmy, że n jest potęgš dwójki.
+załóżmy, że n jest potęgą dwójki.
 <!--%
 --><!--%
@@ Linia 214: / Linia 214: @@
 -->
-\noindent Wysoko�ciš węzła jest jego maksymalna odległo�ć od li�cia, wysoko�ć li�cia wynosi 0.
+\noindent Wysokością węzła jest jego maksymalna odległość od liścia, wysokość liścia wynosi 0.
-Przez <math>p</math>-ty poziom rozumiemy zbiór węzłów o wysoko�ci <math>p</math>.
+Przez <math>p</math>-ty poziom rozumiemy zbiór węzłów o wysokości <math>p</math>.
-Załóżmy, że elementy <math>A[1], A[2], ..A[n]</math> sš umieszczone w li�ciach pełnego
+Załóżmy, że elementy <math>A[1], A[2], ..A[n]</math> są umieszczone w liściach pełnego
 zrównoważonego drrzewa binarnego, następnie wykonujemy (patrz rysunek):
 \vskip 0.4cm
 '''for''' <math>p:=1</math> '''to''' <math>\log n</math> '''do'''
-\hspace*{0.5cm} oblicz jedmocze�nie warto�ci węzłów na poziomie <math>p</math>-tym;
+\hspace*{0.5cm} oblicz jedmocześnie wartości węzłów na poziomie <math>p</math>-tym;
 \myskip
 <!--%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%              %%
--->Drzewo  jest strukturš koncepcyjnš, każdemu węzłowi możemy przypisać miejsce w pamięci. W naszym przypadku
+-->Drzewo  jest strukturą koncepcyjną, każdemu węzłowi możemy przypisać miejsce w pamięci. W naszym przypadku
-węzły na poziomie <math>p</math>-tym mogš odpowiadać elementom
+węzły na poziomie <math>p</math>-tym mogą odpowiadać elementom
 \\
 \centerline{<math>A[2^p],\ A[2*2^p], .. A[3*2^p]\ldots</math>. }
@@ Linia 250: / Linia 250: @@
 -->
-Drzewa odpowiadajš w pewnym sensie rekursji. Wysoko�ć drzew odpowiada czasowi równoległemu. Podobnie
+Drzewa odpowiadają w pewnym sensie rekursji. Wysokość drzew odpowiada czasowi równoległemu. Podobnie
-głęboko�ć rekursji odpowiada też czasowi równoległemu.
+głębokość rekursji odpowiada też czasowi równoległemu.
 Równoległa wersja tzw. metody dziel i zwyciężaj polega na tym że wywołania rekurencyjne
-wykonujemy jednocze�nie (patrz rysunek). Oczywi�cie może się zdarzyć, że jedno z nich zakończy się wcze�niej.
+wykonujemy jednocześnie (patrz rysunek). Oczywiście może się zdarzyć, że jedno z nich zakończy się wcześniej.
 Tym niemniej algorytm czeka na zakończenie obu wywołań.
 Pokażemy dwa przykłady zastosowania metody dziel i zwyciężaj w wersji równoległej.
 Zaczniemy od sumy elementów tablicy <math>A[1..n]</math>.
-Wynik obliczamy jako <math>SUMA(1,n)</math>. Zakładamy znowu, że <math>n</math> jest potęgš dwójki.
+Wynik obliczamy jako <math>SUMA(1,n)</math>. Zakładamy znowu, że <math>n</math> jest potęgą dwójki.
 \myskip
 <!--%-----------------------------------------------------------------
@@ Linia 275: / Linia 275: @@
 \myskip
 \noindent Podobny jest schemat sortowania na PRAMie.
-Niech <math>ParallelMerge(x)</math> będzie algorytmem który, otrzymawszy tablicę <math>x</math> z posortowanymi lewš
+Niech <math>ParallelMerge(x)</math> będzie algorytmem który, otrzymawszy tablicę <math>x</math> z posortowanymi lewą
-i prawš połowš da wyniku tablicę <math>x</math> posortowanš. łatwo to zrobić w czasie <math>O(\log n)</math> z <math>n</math>
+i prawą połową da wyniku tablicę <math>x</math> posortowaną. łatwo to zrobić w czasie <math>O(\log n)</math> z <math>n</math>
-procesorami. Dla <math>i>n/2</math>-ty procesor znajduje w pierwszej połówce sekwencyjnie metodš {\em binary search}
+procesorami. Dla <math>i>n/2</math>-ty procesor znajduje w pierwszej połówce sekwencyjnie metodą {\em binary search}
 najmniejszy element większy od <math>x[i]</math>. Wymaga to czasu <math>O(\log n)</math>.
 Potem każdy procesor{\em wie} gdzie wstawić {\em swój} element.
@@ Linia 300: / Linia 300: @@
 <!--%
 -->\newpage
-Być może najbardziej podstawowym modelem obliczeń równoległych sš układy arytmetyczne (lub logiczne):
+Być może najbardziej podstawowym modelem obliczeń równoległych są układy arytmetyczne (lub logiczne):
 acyckliczne grafy z przypisaniem pewnych operacji węzłom wewnętrznym.
-Każdy węzeł liczy pewnš warto�ć w momencie gdy warto�ci jego poprzedników sš policzone.
+Każdy węzeł liczy pewną wartość w momencie gdy wartości jego poprzedników są policzone.
-Podobnie jak w drzewie możemy zdefinować pojęcie li�cia: węzeł bez poprzedników.
+Podobnie jak w drzewie możemy zdefinować pojęcie liścia: węzeł bez poprzedników.
-Natomiast graf nie musi mieć jednego korzenia, zamiast korzenia w grafie wyróżniamy węzły wynikowe (na rysunku te z których wychodzi strzałka {\em do nikšd}).
+Natomiast graf nie musi mieć jednego korzenia, zamiast korzenia w grafie wyróżniamy węzły wynikowe (na rysunku te z których wychodzi strzałka {\em do nikąd}).
-Równoległy czas obliczenia odpowiada maksymalej wysoko�ci węzła. Poziomy definiujemy podobnie jak dla drzewa.
+Równoległy czas obliczenia odpowiada maksymalej wysokości węzła. Poziomy definiujemy podobnie jak dla drzewa.
 Algorytm równoległy w jednym równoległym kroku oblicza kolejny poziom.
 Liczba procesorów odpowiada z reguły maksymalnemu roziarowi poziomu, chociaż możemy inaczej
-rozplanować obliczenie gdy jedne poziomy sš duże, a drugie małe (ale możemy wtedy zmienić strukturę
+rozplanować obliczenie gdy jedne poziomy są duże, a drugie małe (ale możemy wtedy zmienić strukturę
 grafu tak aby temu odpowiadała).
 Przykładem układu arytmetycznego jest drzewo z rysunku powyżej, które opisuje sumowanie n elementów.
-Zajmiemy się teraz pewnym rozszerzeniem problemu sumowania. Niech <math>\oplus</math> będzie pewnš łšcznš operacjš arytmetycznš
+Zajmiemy się teraz pewnym rozszerzeniem problemu sumowania. Niech <math>\oplus</math> będzie pewną łączną operacją arytmetyczną
 (np. suma, mnożenie, maksimum, minimum, pozycja pierwszej jedynki z lewej strony, podobnie z prawej strony).
 \noindent'''Problem sum p[refiksowych.'''\
-dany wektor  <math>x</math>  rozmiaru <math>n</math>, obliczyć cišg <math>y</math> taki, gdzie
+dany wektor  <math>x</math>  rozmiaru <math>n</math>, obliczyć ciąg <math>y</math> taki, gdzie
 \myskip
 \begin{center}
@@ Linia 324: / Linia 324: @@
 gdzie
 \myskip
-Opiszemy dwa rekurencyjne algorytmy dla tego problemu. Niech <math>FirstHalf</math>, <math>SecondHalf</math> oznaczjš lewš
+Opiszemy dwa rekurencyjne algorytmy dla tego problemu. Niech <math>FirstHalf</math>, <math>SecondHalf</math> oznaczją lewą
-i prawš (odpowiednio) połówkę cišgu. Zakładamy, że n jest potęgš dwójki.
+i prawą (odpowiednio) połówkę ciągu. Zakładamy, że n jest potęgą dwójki.
 \myskip
 <!--%-----------------------------------------------------------------
@@ Linia 349: / Linia 349: @@
 -->
-Układ arytmetyczny odpowiadajšcy algorytmowi PrefSums1 jest przedstawiony na Rysunku&nbsp;[[#parallel_fig5]] dla
+Układ arytmetyczny odpowiadający algorytmowi PrefSums1 jest przedstawiony na Rysunku&nbsp;[[#parallel_fig5]] dla
-<math>n=4</math> i <math>n=8</math>. Zauważmy, że zasadniczš czę�Ciš układu dla <math>n=8</math>  sš dwie kopie układu dla <math>n=4</math>.
+<math>n=4</math> i <math>n=8</math>. Zauważmy, że zasadniczą częśCią układu dla <math>n=8</math>  są dwie kopie układu dla <math>n=4</math>.
-Dodatkowo dodajemy węzły odpowiadajšcej ostatniej instrukcji w algorytmie PrefSums1.
+Dodatkowo dodajemy węzły odpowiadającej ostatniej instrukcji w algorytmie PrefSums1.
 <!--%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%              %%
@@ Linia 358: / Linia 358: @@
 \mbox{\ }
 \includegraphics[width=11.5cm]{parallel_fig5.eps}
-\caption{Układ arytmetyczny odpowiadajšcy algorytmowi PrefSums1. Kolejne grafy powstajš jako podwójne kopie porzednich grafów (dla <math>n/2</math> elementów)
+\caption{Układ arytmetyczny odpowiadający algorytmowi PrefSums1. Kolejne grafy powstają jako podwójne kopie porzednich grafów (dla <math>n/2</math> elementów)
-z dodanymi elementami odpowiadajšcymi operacji <math>x[j]:= x[n/2] \oplus x[j]</math>. }
+z dodanymi elementami odpowiadającymi operacji <math>x[j]:= x[n/2] \oplus x[j]</math>. }
   <span id="parallel_fig5" \>
 \end{center}
@@ Linia 377: / Linia 377: @@
 \hspace*{1.2cm}<math>n:=size(x)</math>;\\
 \hspace*{1.2cm}\textbf{if} <math>n>1</math> \textbf{then } \\
-\hspace*{1.8cm} utwórz nowš tablicę y;\\
+\hspace*{1.8cm} utwórz nową tablicę y;\\
 \hspace*{1.8cm} '''for each } <math>1 \le i \le n/2</math> \textbf{do in parallel'''\\
 \hspace*{2.5cm} <math>y[i]\ :=\ x[2i-1]\oplus x[2i]</math>;\\
@@ Linia 390: / Linia 390: @@
 <!--%
 --><!--%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  mx            %%
--->Układ arytmetyczny odpowiadajšcy algorytmowi jest pokazany na rysunku &nbsp;[[#parallel_fig4]].
+-->Układ arytmetyczny odpowiadający algorytmowi jest pokazany na rysunku &nbsp;[[#parallel_fig4]].
 \begin{figure}[bhtp]
 \begin{center}
 \mbox{\ }
 \includegraphics[width=7.2cm]{parallel_fig4.eps}
-\caption{Układ arytmetyczny odpowiadajšcy PrefSums2. Kolejny graf składa się z pojedyńczej kopii
+\caption{Układ arytmetyczny odpowiadający PrefSums2. Kolejny graf składa się z pojedyńczej kopii
 poprzedniego grafu (dla <math>n/2</math>), oraz <math>n/2-1</math> dodatkowych operacji. }
   <span id="parallel_fig4" \>
 \end{center}
 \end{figure}
-<!--%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%my-->