Sieci sortujące artykuł 2

Sortowanie clogn w krokach równoległych

Mamy sieć sortującą cn log n porównań. Algorytm może być wykonywany w
c log n, kroków równoległych, gdzie równoległy krok porównuje n/2 par rozłącznych. W i-tym kroku algorytm porównuje zawartość rejestrów
i
, gdzie j(i), k(i)
są bezwzględnie stałe, a następnie zamienia ich zawartość lub nie, w zależności od wyniku porównania.

1. Wprowadzenie
Niech L będzie liniowo uporządkowanym zbiorem zawierającym n elementów. Elementy L są pierwotnie przechowywane w n rejestrach (R1, R2,…,Rn). Zestaw rejestrów będzie oznaczony przez R. Chcemy pokazać algorytm, który zmienia rozmieszczenia elementów w L , tak, że ostatni element L będzie znajdował się w R1, następny w R2 itd., a największy w Rn. Podstawowym krokiem tego algorytmu jest porównanie dwóch elementów a i a', znajdujących się w danych dwóch rejestrach R, R'. Mamy albo a<a' lub a>a'. W tych przypadkach możemy wymienić miejsca elementów lub pozostawić je bez zmian. Tak więc możemy mieć cztery różne zasady. Algorytm składa się teraz z sekwencji par (R, R') rejestrów i sekwencji związanymi regułami (tak jak powyżej). Innymi słowy otrzymamy sieci. Skonstruowana sieć może zawierać jedynie O (n log n) z powyższych czynności ((R, R ') i zasady), a my pokażemy, że pierwsze n/2 kroki mogą być wykonywane jednocześnie (tzn. pod warunkiem, że pary (R, R') są rozłączne), i tak samo drugie n/2 kroków, itp. W ten sposób otrzymujemy sortowanie. Algorytm działa w czasie O (log n) równoległych działań. W następujących równoległych krokach mamy na myśli zbiór co najwyżej n/2 rozłącznych podstawowych kroków.
Równoległe czasowo algorytmy sortowania są intensywnie badane. Do najbardziej znanych
równoległych algorytmów sortowania, z maksymalną równoległością (i rozłącznych porównań) zmniejsza sortowanie do minimum. Istnieją algorytmy, które wykorzystują jedynie logn kroków łączących (Batcher, Pratt i inni; zobacz Knuth [2]. Prowadzi to do algorytmów sortowania przy użyciu O ((log n)
) kroków.
Algorytm sortowania przedstawiony tutaj był pierwotnie algorytmem do losowania, ale
(przy wyraźnie podanym ekspanderze, patrz [1], [3]) możemy przekształcić go w deterministyczny. Zmieniamy algorytm w tą formę.
Zgodnie z sugestią D. Knuta, zmodyfikowano oryginalny algorytm w inny sposób, tak aby stał się rzeczywiście algorytmem sieci sortowania z O (n log n) modułów, patrz również Knuth [2].
Struktura algorytmu może być wizualizowana w najprostszy sposób, jako drzewo. Korzystamy z liści drzewa binarnego n (jeśli n jest potęgą 2), w którym
węzły na tym samym poziomie są sortowane. Rejestry są przypisane do niektórych węzłów,
pierwotnie każdy rejestr jest przypisany do korzenia (węzła najwyższego). Algorytm
jest podzielony na cykle, jeden cykl składa się z podprogramów i każdy podprogram przepisuje drzewo, czyli przypisuje rejestry do węzłów. Po jednym cyklu, rejestry przeniosły się o jakąś liczbę poziomów w dół lub w górę na drzewie. Chodzi o to, że większość przesunięta została w dół, i tylko kilka rejestrów przesunęło się w górę. Pokażemy
że po O (log n) takich cykli wszystkie rejestry będą przesunięte na dół, do liści, każdy rejestr do innego liścia, a kolejność liści definiuje kolejność elementów.
Na każdym etapie, istnieje najniższy poziom niepustych węzłów, a większość elementów
pozostanie na tym poziomie, liczba elementów na coraz wyższych poziomach będą stanowiły
serię geometryczną. W każdym cyklu wykonujemy kilka równoległych działań. Kolejność
równoległych kroków w cyklu
-tym oznaczamy przez
. Długość
będzie
mniejsza niż pewna stała c. Po cyklu, zbiór rejestrów przypisanych jest do elementu t drzewa, co oznaczamy przez

jest R jeśli t jest korzeniem, w przeciwnym razie jest to zbiór pusty. Ograniczenie funkcji
na stały poziom wysokości i oznaczamy przez

Będziemy definiować
i
przez rekursję na
.

2. Opis algorytmu
My zdefiniujemy nasz algorytm za pomocą stałych c1, c2, q1, q2,
, d1, g. Nie podajemy rzeczywistych wartości tych stałych tylko zwracamy uwagę na pewne nierówności między nimi.
Wybieramy stałe w następującej kolejności:
, tak aby

gdzie a<<b oznacza, że a jest dostatecznie małe w porównaniu z b (lub b jest wystarczająco
większe w stosunku do a).
Nie będziemy używać stałej q2 w samej definicji algorytmu, tylko w dowodach.

Definicje. Niech T będzie zbiorem wszystkich skończonych sekwencji 0,1 (w tym pusta
sekwencja 0). (Właściwie będziemy korzystać jedynie z sekwencji o długości mniejszej niż n.) Rozważamy T jak drzewo, którego poziomy (zbiór ciągów o takiej samej długości) są posortowane w leksykograficznej kolejności , to jest (a1,…,ak)<(b1,…,bk) wtedy i tylko wtedy są one różne, gdy ai<bi, gdzie i jest najmniejszym indeksem.

Jeśli t=(a1,…,ai) wtedy (t, b1, …, bj) oznaczać będzie sekwencję (a1,…,ai,b1,…,bj).
Dom (f) będzie oznaczać dziedzinę funkcji f, l(t) będzie długością sekwencji t.

Mapa jeden do jednego R na L, będzie nazwane pozycją. Jeśli
i F jest pozycją wtedy użyjemy następującej notacji:

Będziemy pomijać indeks F, jeśli jest unikalny, określany na podstawie kontekstu.
C jest łańcuchem, jeśli C jest funkcją określoną na pewnym poziomie T i dla wszystkich
x, y
Dom (C) mamy

Łańcuchy C1 i C2 są rozłączne wtedy i tylko wtedy, gdy
dla wszystkich

x
Dom (C1), y
Dom (C2).

Chcemy zdefiniować funkcję
tak, że
, by była łańcuchem dla wszystkich i.
Jeśli C jest łańcuchem, będziemy korzystać z następujących zapisów:

Dla pewnych (wszystkich) x
Dom(C)

Gdzie F jest pozycją.

Jeśli C1, C2 są rozłącznymi łańcuchami
będzie łańcuchem
określonym przez
dla wszystkich t
Dom(C1).

Teraz zdefiniujemy operacje na łańcuchach. W celu dokonania tej operacji unikalnie określonej, przypuścimy, że zestaw R jest sortowalny w sposób arbitralny, lecz ustalony.
Załóżmy, że C jest łańcuchem i 0 <q <l. Następnie CH1 (C, q) będzie łańcuchem o następujących właściwościach:

Zawiera pierwsze
elementy C(t), gdzie [x] oznacza integralną część liczby x.
CH2 (C, q) to sieć z tej samej domeny, określona przez:
(CH2 (C, q))(t)= C (t) - (CH1 (C, q) (t)).
Następujące lematy są niezbędne do określenia

.
Lemat 1. Niech C będzie łańcuchem, l(C) = i,
i przypuśćmy, że N(C)
2. Zefiniujmy łańcuch V (C, k) dla wszystkich k,
.

Jeśli l(t) = j niech (V(C, j))(t) będzie zbiorem składającym się z pierwszego elementu C(t0)
i pierwszego elementu C(t1), gdzie t0 i q są ciągami długości i są określone przez
t0 = (t, 0,..., 0), t1 = (t, 1, 0..... 0).
Jeśli j<k<i oraz l(t) = k niech (V(C,k))(t) będzie zbiorem, którego jedynym elementem jest
pierwszy element C(t0), gdzie t0=(t, 1, 0 ...., 0), l(t0) = i.
Jeśli l(t) =i niech
. Jeśli
i l(t) =k niech V(C, k)(t) =0. Wtedy V(C, k) jest łańcuchem dla wszystkich
i spełnione są następujące warunki:

Dla wszystkich t'
T,
otrzymujemy

Dla wszystkich t
Dom(C)

Dlatego są to bezpośrednie konsekwencje definicji V. Pomijamy dowód lematu.

Lemat 2. Załóżmy, że C jest łańcuchem l(C) =i oraz (ak),
jest sekwencją nieujemnych liczb całkowitych z następującymi właściwościami:

Oznacza dla wszystkich s<i. Wtedy, dla wszystkich k istnieje łańcuch W(C,k) dla którego równanie 1,2 i 4 jest prawdziwe przy j=0 i V=W i

Dla wszystkich

I funkcja W należąca do Dom(C) definiuje się jako

Jest łańcuchem i

Dowód. Dla każdego k, definiujemy ciąg łańcuchów przy

Definiujemy ciąg przez indukcję na s. Przypuśćmy, że

jest zdefiniowany dla wszystkich z
Niech j będzie największą liczbą całkowitą z następującą własnością oraz
dla wszystkich

Jeśli j nie istnieje, nie definiujemy . Załóżmy, że j <i. Dla wszystkich t, l(t) = i niech

Dla wszystkich niech , gdzie V jest funkcją określoną w
Lemacie 1, (z j podanym powyżej). Łatwo jest sprawdzić, czy W określone przez
równanie 6 spełnia wymagania lematu 2.

Teraz używając lematu 2 zdefiniujemy . zostało zdefiniowane przez

Załóżmy, że są zdefiniowane, wtedy definiujemy następująco:

Definicja. Jeśli C jest łańcuchem, wtedy łańcuchy są określone przez

Dla wszystkich

jest pierwsze elementem , jeśli
( jest określony tylko wtedy, gdy N(C) jest parzyste

jest określony tylko wtedy, gdy 4|N(C). Wyraźnie

Niech (dla = 0 niech ). Od dla wszystkich j, jest zawsze określone. Zastosujmy lemat 2 z

jeśli
Będziemy udowodniać przez indukcję na ,że ciąg (ak) spełnia warunki lematu 2 (patrz Lemat 7).
Niech W ( ) będą łańcuchami gwarantowanymi przez lemat 2 i k0 niech będzie najmniejszą liczbę całkowitą z

Teraz dla wszystkich umieścić

oraz dla k=k0

oraz k<k0, dla wszystkich l(t) = k. Pomijamy poprzednie wyrażenie jeśli

k = l i jeśli k0 = 0; możemy zastąpić w poprzednim wyrażeniu w równaniu 9

jeśli k0 = l i pominięcie wyrażenia jeśli k0 = 0,1. Dla k = pomijamy . Wreszcie definiujemy przez

Dlatego C (zawsze jest podzielne przez 4 operacje mogą być wykonywane w definicji . Później udowodnimy, że operacje
w ostatnim wyrażeniu można wykonać również.
By obliczyć ciąg musimy znać dalsze definicje.

Definicja 2.2. Załóżmy, że A i B są rozłącznymi zbiorami. Nazywamy graf G

ekspandera na <A,B>, jeżeli jest zbiorem wierzchołków G, żadna krawędź G nie jest w A lub B, i stopień każdego punktu wynosi co najwyżej k, a jeśli oznacza
zestaw sąsiadów zbioru X to dla wszystkich mamy

i dla wszystkich mamy

Lemat 3. Dla wszystkich istnieje liczba całkowita dodatnia k ( , c) taka, że
dla wszystkich rozłącznych A, B istnieje a (k, ) ekspandera na <A,B>.
Potwierdzenie Lematu i wyraźne tbr budowy wykresu łatwo
Z wyników Margulis [3], ale tylko udowodni istnienie funkcji
k (e, c). Gabber i Galil [1] dał funkcji k (e, e), jak również w wyraźnej formie.
(Zwykle definicji wykresu ekspandera różni się nieco od jednej danej
tutaj.) W kolejnych będziemy podejrzewać, że kte, c) jest stałą funkcją spełniającą
wymagania Lemat 3.
Definicja 3.1. Jeśli A, B są rozłączne podzbiory N i ~> -0, pozwól
być stałe (k (e, [[/ [BI), e) ekspandera na (A, B).
Zgodnie z uwagi po Lemat 3 można przypuszczać, że
jest w jakiś wyraźny sposób.
6 ~ (A, B)
G. (A, B)
Definicja 3.3. Niech J będzie uporządkowany zbiór S ~ J. S nazywany jest niższy (odp. góry)
sekcji J, jeśli dla wszystkich x, yEJ mamy yCS, x ~ _y (odp. x> = y) oznacza datki.
Definicja 3.2. Jeśli A, B są rozłączne podzbiory N, e> 0 pozwól E ~ (A, B) jest
zbiór wszystkich podstawowych kroków typu: R1, R2, jeśli zawartość jest R1
większa niż zawartość Rz następnie wymiany danych z tych rejestrów, w przeciwnym razie
pozostawić je bez zmian ", gdzie RI ~ A, B i R. ~ (R1, R2) jest krawędź
G (A, B).
Rola wykresy ekspandera w naszym algorytm opiera się na następujących
/ _, Emma się okazało później.
SORTOWANIA równolegle kroki 7
Lemat 4. Załóżmy, że A, B są rozłączne podzbiory ~ i ~> 0, to po podstawowym
kroki E ~ (A, B) zostały wykonane w dowolnym celu, mamy:
jeżeli S jest dolny odcinek Cont (AUB) i [S [= <[AI następnie [S - Cont (A) l
_ - <E] S [i posiada odpowiednie twierdzenie. Na górnej części.
Definicja 4.1. Jeśli i jest liczbą dodatnią, to i równoległe krokiem będzie zestaw rozłącznych
podstawowe kroki i co najwyżej elementów. Załóżmy, że Z jest kolejność kroków / równoległe
i dla niektórych i F to stanowisko, to Z (F) będzie oznaczać, że mamy stanowisko
po Z elementów została przeprowadzona w podanej kolejności. Załóżmy, że
111 .... , Hj są sekwencje il równoległe działania .... , / J równoległe działania. R-tego elementu
J
H, zostaną oznaczone H ~ (r). U H ~ oznaczać będzie kolejny, których r-ty wyraz
j s: l
H jest U (r). Jeśli podstawowe kroki różnych H, (r) jest stały dla każdego r
2 = 1
rozłączne (tzn. nie występuje w rejestrze elementaly kroki obu H, ~ (r) i H, 2 (r)
jeśli sl ¢ s2), a następnie H ~ jest ciągiem i, równoległe działania.
Definicja 4.2. Załóżmy, że C jest łańcuch, e> 0, dla i = 0, 1 definiujemy impi (C, e)
jak impi (C, e) = U (E, (CTS), C (t))] s, t są kolejne elementy Dora (C), s <t
i ostatni element s jest i). IMPI (C, e) będzie ustalona kolejność równolegle
kroki, aby każdy podstawowy krok imp ~ (C, e) jest zawarta w niektórych równolegle
krok i innych podstawowych czynności nie występują w żadnym członkiem kolejności. Możemy
Przypuszczam, że IMPS (C, e) znajduje się w wyraźnej formie i jego długość jest k (e, 1).
Niech IMP (C, ~) jest połączeniem o IMP (C, e) IMPI (C, e). IMPi (C, e)
będzie ciąg czynności składające się z równoległych i kopie IMP (C, ~). Jeśli ~ C, ..., Cj
J
łańcuchy są rozłączne wtedy U IMpi (cj -, e) jest ciągiem 2jik (e, i) = ~ ik (e, 1). 2
j s = l
równolegle kroki.
Definicja 4.3. Załóżmy, że C jest łańcuch i 0 <q <l. Następnie CH3 (C, q) jest
łańcuch z następujących właściwości:
(4.1) Dora (CH3 (C, q)) = Dom (C).
(4.2) (CH3 (C, q)) (t) składa się z pierwszych [1 / 21 (CH 2 (C, q)) (t) [] elementów (CH2 (c, q)) (t).
CH4 (C, q) należy do sieci określonych przez
(CH4 (C, q)) (t) = (CH2 (C, q)) (t) - (CH3 (C, q)) (t).
Definicja 4.4. Załóżmy, że C to sieć 0 <q <I, e> 0. Dla każdego tCDom (C) niech
i ~ (C, q, e) = E ~ (CH3 (C, q) (t), CH1 (C, q) (t))
I2, (C, q, ~) = E ~ (CH1 (C, q) (t), CH4 (C, q) (t)).
Podstawowych kroków i ~ (C, q, ~) mogą być wykonywane w ke, ~ równolegle
kroków N (C)> -4 / q. I niech w tym / (C, q, e) będzie ciągiem o długości równolegle kroki
co najwyżej do programu, - ~ q, którego elementy zawierają podstawowe etapy I / (C, q, 8)
8 m. AJTAI, J. KOML 6S, E. SZEMERISDI
a nie inne podstawowe st ~ ps. Niech IAC, q, ~) jest połączeniem I ~ (C, q, s)
i ~ (C, q, s). Niech w końcu
I (C, q, s) = [, 3 I (C, q, s).
t E Dora (C)
Następujący lemat, który jest bezpośrednią konsekwencją lematu 4
przedstawia wpływ I (C, q, s).
Lemat 5. Załóżmy, że C jest łańcuch, 0 <q <l, ~> 0, t ~ Dom (C) i S jest mniejsza
lub górnej części C (t). Jeśli
IS [<½ (IC (t) l-4 [¼ qlC (t )[]),
następnie po I (C, q, s) była wykonywana mamy
ISF "qCont (CHI (C, q) (t))] ~ cISI.
Teraz definiujemy P ~ kolejności równolegle etapów cyklu ~ c-th. Definiujemy
P ~ ~ c tylko to z 2 - ~-> C2. (S ~ jest określona dla tych ~ c 's.) sekwencji
P ~ będzie połączeniem sekwencji P ~ P ~, i Pg.
Niech P ~ = UI (S "i, g, TE. Będziemy udowodnić później, że N (S, I) = O lub
0 ~ i ~
4
N (S ~'~)>=, zatem można przypuszczać, że długość P ~ jest co najwyżej
1-g
P ~ ~ d = IMP (D ~, sl)
P = U IMPd ~ ~ (S ~ l + ";, ea) -
O ~ i ~
Zawartość rejestru po P ~ R została przeprowadzona zostanie oznaczona
~ F + X (R). ° F (R) jest oryginalna zawartość rejestru R. Ff (R) (odp. F ~ (R))
oznaczać będzie zawartość rejestru R po ~ P (odp. / ~ .2) zostały wykonane.
Niech P "jest połączeniem p0, ... ~ p, p", gdzie c (jest największym
integer z 2 - ~ 'Xn-> c..
Będziemy udowodnić, że po później P "była wykonywana elementów L
są niemal "na zamówienie" w tym sensie, co następuje:
Lemat 6. Istnieją stałe ~ u, u2, u3 takie, że jeśli cg - ul ~ ~ i-", a następnie
N (S "i) <= uz inaczej i N (I S ~ ') = O, ponadto jeśli dla wszystkich tETs' (t) oznacza
Numer 2-LCO] (t '<t[l(t')=l(t)}[, następnie .for tyłu q, t2~T s'(tO-s'(t~> u32 - ~ "i
xCContv ~ (~ S "(To), ycContF ~ '((S" t.,)) oznacza x> y, (tutaj można pozwolić, aby l (do ¢ l (~ t)).
Lemat 6 pociąga za sobą, że istnieje ciąg równoległych kroki P "z
stałej długości, tak aby po P 'i P "zostały wykonane z elementów
L znany jest w porządku. Jako ćwiczenie pozostawiamy dowód tego faktu do
czytelnika. W ten sposób zakończyliśmy definicji nasz algorytm.
SORTOWANIA równolegle kroki 9
3. Korzystania z wykresu ekspandera
W tej sekcji udowodnić lemat 6 oraz innych twierdzeń, które już
Przyjmujemy w ostatniej sekcji bez ich dowody.
Dowód lematu 4. Załóżmy, że nasze twierdzenie nie jest prawdziwe. Następnie [S ("lCont ~ (B) [>
e. [S], gdzie G jest stanowisko po ~ E (A, B) zostały wykonane. Niech X =
(R ¢ BIG (R)) i yc ES = zbiór sąsiadów z elementów X.
Definicja E, (A, B) oznacza, że
(6.1) zawartość rejestrów w maleje, ze stałych rejestrów
B wzrasta (niekoniecznie ściśle) w każdym kroku podstawowego E (A, B).
(6.2) Dla wszystkich RCX zawartość rejestru R jest elementem całej S
całego algorytmu.
(6,3) Dla wszystkich RC Y zawartość rejestru R jest elementem S na końcu
algorytmu (tj. G (R) E S).
(6.1) i (6.2) są bezpośrednie konsekwencje definicji. Przez (6.2), jeśli
R c Y treści Y jest w S po kroku podstawowego odpowiedniego do krawędzi
między R i element X zostały wykonane. Więc (6.1) oznacza, (6,3).
Mamy więc Cont ~ (X) UContG (Y) c = S. Z drugiej strony ~ Cont (X) (]
(] Conta (Y) = 0 i od G ~ (A, B) (k (a, IAI / [B]), e) ekspandera wykres
lCont (x) / + ICont (y) l> LSL + (1 = Isl LSL,
sprzeczność.
4. Podstawowe definicje
Definicja 6.1. Załóżmy, że C to sieć XCL i F to stanowisko. Pozwól
~ P (x) - IUCl-ti (yEContr (C) ly <= x) l.
Niech dla każdego TET
s (t) = 2 -'(') l (t "<TLL (t) = l (t)) l + 2 -'~')- l.
Jeśli C, D to łańcuchy, F jest tcDom pozycji (C) i t2 jest liczbą rzeczywistą
pozwól
~ G (t, To, C) = (XE Ll t ~ "¢ Dom (C) t"> = t, xECont ~ (C (t '))
i s (t)-p ~ (x)> Ix + ½ lC 1/1).
Hg (t, Ft, C) = (XE rl3t'E Dom (C) t "<= t, xEContr (C (t '))
i pg (x)-s (t)> ll + ½ C] 1/1).
Daj nam określić zależności QV, (C, D, Q, M), gdzie C, D, F są łańcuchy
pozycji, q, M są liczbami rzeczywistymi 0 <q <1. M> 0, a> 0; w następujący sposób:
Q, F, (C, D, P, M) wtedy i tylko wtedy dla wszystkich tEDom (C) i 2_-> mamy
IgG (t, ICI-2 ~ ~ -, C) I ~ M. QX i Hg] (t, IC1-12; ", C) I ~ M. qx.
t0 M. AJTAI, J. KOMLOS, E. SZEMERI ~ DI
Gdy D jest łańcuch z UD = N używamy następujących zapisów: p (x) = pg (x)
dla wszystkich XCL. (W tym przypadku ~ p (x) wyraźnie nie zależy od F.)
Ge (t, 1 ~, C) = ag (t, p, C)
~ H (t, ~, C) = ~ H (t, ~, C)
~ Q (C, q, ~ l) = P ~: (C, D, Q, M).
Lemat 7. Załóżmy, że 2-'-W> ce. Następnie S ~ jest zdefiniowane i nie dla wszystkich XEL
istnieje dokładnie jeden TET z xECont (S (t)). Ponadto S ~, ~ to sieć dla wszystkich
O <= i <= u i istnieje stała q2, że dla wszystkich O <= i <-c ~ następujące warunki
są spełnione.
(I) S ~, i to sieć amt N (S "~)<= ~ q-i2, ~ n,
(Ii) jeżeli q ~ -12 ~ - ~ <c~ n następnie N(S~'i)=O inaczej ~ N(S',i)>-_q - ~ 2-'-ln,
(Iii) Qf (S ~'', Q, q ~ - "2 - ~ n).
Najpierw musimy udowodnić, że Lemat 6 wynika z lematu 7. Definicji
~ "(I) i (ii) wyraźnie zakłada istnienie i u. ~ u, z wymaganych właściwości.
Teraz załóżmy, że TET z cd-l ~ u (t) <= c & Miejmy zastosowanie (iii) z ~ u = c "
oraz i = l (t), otrzymujemy
(7.1) ~ Ia = '(t, 2 -'(~) 2), S ~"')[ - <~ q "- ~ 2 - ~ ~ NQ
dla wszystkich 2 => 1.
Niech 2o_-> 1, u ~"~'- i9-~",~- u-,"~'°<. ~. (7,1) oznacza, że G ~ '(t, 2 - ~ 2 ~ S ~' ~) = 0, że
jest dla wszystkich z ~ ContF ~ '(S (t)) mamy
s (t) - p (z) <= 2-i2z0 +2 i-L
Podobnie jeśli używamy zamiast G H otrzymujemy - (s (t) - p (z)) <= 2 - ~ 2ao +2 -~-~.
Tak więc, jeśli ua> 2 (2 ~ 2 ~ "X +2 ~,-~) następnie s '(fi)-s' (t ~)> uz2 - ~" oznacza, że p (x)> p (y)
czyli x> y. II
5. Właściwości N (S ~, i)
Udowodnimy lemat 7 przez indukcję po c ~. Załóżmy, że twierdzenia
Lemat przytrzymaj dla pewnej ustalonej c ~ i 2 - (~ +1 ~-1N> c2. Ponieważ S ~, i to sieć dla wszystkich
O <~ iC-i ~ C ~ są jasno określone i są parami rozłącznych sieci. Jak
wymienionych po definicji D ~ ~ i S, k chaine ~ ~ 1C, rr2C ~ zawsze
zdefiniowane i S ~ + l, k jest określony dla k0 <k <_-l + jest to łańcuch i
różnych k w odpowiednie łańcuchy są rozłączne.
Musimy pokazać, że rq (C k ~ ° ~-I t2 C2k o - 2) jest definiowana w ko_ ~ 2. (Przypadku
k0 = 0 jest trywialny, bo k0 = l możemy udowodnić w ten sam sposób, że rqC ~ 0 - ~ jest
zdefiniowane.) Oczywiście, że wystarczy wykazać, że
(7,1) 2tN (C ~ "-2) i
(7.2) 2 W (C ~ o - "U ~ C ~ o-z).
Jeśli </ k0 - 2, który jest q ~+~-( i + ~) 2 -=- Zn <e ~ następnie
~ q-i2-~-b2 = 2ql-q ~ + l-(i +2) 2 -:-2n <2qlel - <ca
SORTOWANIA równolegle kroki 1 [
a zatem zgodnie z hipotezą indukcyjne
(7.3) N (~ S ~) = 0.
Z założenia indukcyjnego U = ~ (~ ~ USA "), a zatem przez (7.3)
O ~ i ~
U = USA (~+~'~) U (UK) U (UQ °-gu (UC ~ ° - ~)
ko <i ~ _a-l-1
gdzie K jest sumą pierwszych czterech kategoriach (2,9) i jest to łańcuch. Od sieci
z tego wzoru są parami rozłączne mamy
n = I ~ 1 = 27 21g (s = +1 "i) +2 k ° N (g) +
ko <i ~ l +
+ 2k °-IN (C ~ ° -1) + 2k ° - N ~ '(C ~ ° -2).
n jest potęgą 2, n => 4, k0 => 2, w związku z tym 2 [N (C ~ ° -2) i 2tN (C ~°-*)+
1/2N (C ~ ~ o-") co oznacza, (7,1) i (7.2).
Teraz udowodnimy, że (i) i (ii) posiadać dla wszystkich 0 <= i_ <-c ~ przez indukcję na a.
Dla a = 0, i = 0, N (S °'°)= n oznacza (i) i (ii). Załóżmy, że nasze twierdzenie
jest prawdziwe dla i udowodnimy to w c + 1 ~.
Z definicji CH
(7.4) N (CO = 4 [(¼) g. N (~ S, i)]
(7.5) N (Q) = N (S, ~) - 4 [(¼) N g (~ S ~)]
zatem
N (D ~) = 2 [+ GN (~ S ~)] + [1 GN (S.... 1)]
(Na ~ c = 0 drugi warunek zostanie pominięty).
W definicji (D ~, k) i razem kemma 2 oznacza, że dla wszystkich ko <-k <
(7,6) + ~ q-k2-~ - <~ 'n N = (W (D ~, k)) <= q ~ + l-k2-~-2n + 2.
Możemy oszacować innych warunków (2.8) i (2.9) za pomocą (7.4) i (7.5) i
indukcyjne hypothezis definicja 7h i 1-g <ql <1 <<el.
U (rc_l (C l] +)) <= 2 (l N (S ~ "+ k) -4 (KGn (S''k + l) - 1)) _-<
~ _ 2 (1 - g) N (~ S. K + ~) +8 ~ = 2 (1 - g) q ~ ~-k-2 - ~ n +8 = <
1 f, + l_kO_a: _ _ 1 2 ~ 1 = 20 ul - ". nTTg ~ ~ q-igq ~ + l-k2-~ - ~ + n
+ To1 q ~ + l-k2-~-2n-1 g ~ o ~ q g + l_kg-_ ~ _Zn •
N (n2C ~ -2) ~ ¼ 4 [¼ gu (~ S "k-2)] <= ¼ N (S, *- 2) <_
T = 4 /. ILR <ta - k +2 ") - ~ <= n + ~ q ¼ l-k2-~"-ln
W związku z tym ko k <<= ~ mamy
N (S ~ k + I.) <_ ~ + ~ q-k2-~-ln.
12 m. AJTAJ, J. KOMLOS, E. SZEMERI ~ DI
że jest
Ponieważ
Dla k = ko dwóch pozostałych kategoriach można oszacować w następujący sposób:
N (CKZ °) <= (1-g) N (S''° K) ~ (1 - g) ~ q-t ° 2-'n - <
- <- @ Q ~ + l-ko2-'-.
U (rq (C ~ 0 -) O 7r1C ~ ° - ') ~ ½ ((1 - g) U (S = "ko-1) +
N (S ~ + I, ko) ~ q (l +-O2-~ "-ln.
S ", k (t) = O dla wszystkich ko <k, l (t) = k udowodniliśmy (i) O ~ k - <współpracy
(Ii) jest bezpośrednią konsekwencją (7,6) oraz definicji
0 ~ k-<- ~. [/. Ll ~+~'~+ OS-<n-i +1 ,~+~[= 1S ~ 2 ~ +1 oznacza (i)
w tym przypadku (ii) jest konsekwencją
I Q-J (~ JS: ~ + I'i) [= n i
Ogi z ~ l +
U (US = + I ";) I_ <~ q ('+ l-i2-½ = 21N ~ n.
S = k dla
i = ct + 1, i
6. Stosunku pracy Q i IMP
Assertmns zawarte w następujących lematach są konsekwencje
indukcyjne hipotezy.
Lemat 8. Dla wszystkich i ct 0 ~ ~ mamy
(8.1) ~ QF (c ~, q2, q ql ~ ~ 3 - i 2 - o n ~)
(8.2) Qft (C ~, q2, qf-"2-~ n)
(8.3) O ~ (~ RHC, qa, q ~. ~ Q - "2 - ~ n)
(8.4) ~ Q (C ~ ~ z2, q,., Qa q ~ - ~ 2 - ~ n)
(8,5) Qf ~ (~ Tr-LC, q2, q2q ~ - ~ 2 -% 7) •
Dowód 8.1. Można przypuszczać, że N (S',~)~ O. Niech 2 - ~ 1. Musimy udowodnić, że
[GFI ~ (t, 2 - ~ 2 Z, C ~) [<= qgqf-i2-NQ ~ ~ "
dla wszystkich l (t) = i. (IHFr. ~ ... .. I może zostać udowodnione przez analogię).
(8,6) GFeu, 2-"2", C /) = [(xEContFr (C ~ (t ')) I
~ T 't
S] (t)-p (x)> 2 -, 2 "+2" -1).
SORTOWANIA równolegle KROKI 13
Zgodnie z hipotezą indukcyjny Q [(S ~ 'i, ql, q-i2-~' n), dlatego dla wszystkich
Tet, 2_-> 1, l (t) = l (t) = i mamy
(8.7) ~ [(xEfontr, (S ~, i (t ')) ts (t)-p (x)> 2-i2a +2 ~ -1)] <=
= <Q ~ - ~ 2 - ~ ~ NQ
Oznaczmy przez Ma (t) określonych w (8,6) odpowiada t "i przez Mz (t)
ustalić określone w odpowiednich okres (8.7). Wyraźnie Mz (t) jest w dolnej części
s ~ "(t"). (8.7), w (S',')= I> u ~ ~ - ~ - -~-~,,~,, Q <<l-g i lematu 5 pociąga, że
[Mx (t) = IM2 l (t) O ContF-(C ~ (t ')) [<= ea [ml (t) l.
W ten sposób przez el <<q2 (8.6) wynika z (8.7). (8.2) jest trywialne wyniku
Qf "(~ ~ S", q2, q ~ - "2 -" n). (8.3) i (8.4) łatwo wynika z (8.1) i (8.5) z (8.2). II
/ _, Emma 8 ". Załóżmy, że C jest łańcuch, F to stanowisko i QF (C, P, M) dla niektórych
J, Q, M, e> 0 i F '= IMP (C, e) (F), to Q ~' (C, P, M) posiada także.
Dowodu. Niech T ~ Dom (C), ~ / liczba rzeczywista, to zgodnie z definicją
IMP (C, e) mamy t IGP (, ~ /, C) i> IGV "(t, ~ ja, C) l i INR (t, ~ l, C) l>-_ [H '(t , ~ t, C) J,
co oznacza nasze twierdzenie. Ja
Definicja 8.1. Załóżmy, że A ~ L i = (ao .... ,,, ~), Gdzie i <i2 oznacza, ai, <~,
a / ~ jest pozytywną liczbą rzeczywistą. Pozwól
- ~ = (~ ~ ~ J +. . . . . ,, ~ _tB).
Jeżeli G jest to pozycja C q łańcucha, t2EDom (C), q <t2 następnie oznaczmy
przez RGB (q, t2) następujące oświadczenie: dla wszystkich xEConta ((fi)) P, ycfonta (C (t2)) ~ C
mamy x <y.
Lemat 9. Na wszystkie e> 0, j ~ l istnieje bo> 0 takie, że jeśli C jest łańcuch, F
pozycji 0 <q <¼, M <2N (C), b> bo, 0 <O <<e, F = (b IMP (C, 6)) (F), M
~ Q (C, Q, M), a następnie dla wszystkich fi, t ~ Edomu (C), q <t2 oznacza R ~ DW) (q, t2).
Się następujące definicje i lematach są niezbędne do dowodu lematu 9.
Definicja 9.1. Załóżmy, że G jest stanowisko AC = L i P ~ Dom (C) × Dom (C).
Pozwól
X. ~. E = ((x,, xe) ~ lx, xzCA i ~ (r, r) Ee, rt <rz
i X, C. Conto (C (r,)) i = 1,2 i x> x.)
Jeśli P = Dom (C) × Dom (C), to będziemy pisać X ~ zamiast XaUe.
Lemat 10. Załóżmy, że G jest miejsce, E jest elementarnym. Kroku zawarte w
IMP (C), G '= E (G), AC = L. Następnie IX ~ l-_> ~ lX "l.
Dowodu. Jeżeli G "= G nasze twierdzenie jest trywialne. Załóżmy, że G '~-G. Od E znajduje się w
IMP (C, 6), kolejne są
ta, t, ~ Dom (C), t ~ re <R ~ C (q), R ~ C (tz)
14 m. AJTAI, J. KOMLOS, E. SZEMERI ~ DI
takie, że G "(RO = G (R2), G (R2) = G (R1), G (RO <G" (R2) i G (R) = G (R) dla wszystkich
R ~ R1, R2 R #. Jeśli liczymy par w X ~, ~ XA "zawierające G '(R1) lub G" (Rz)
mamy wymagane twierdzenia. II
Lemat 11. Załóżmy, tl, t2 są kolejne elementy Dom (C), G jest stanowisko,
G '= IMP (C, 6) (G), AC = L, P = (tl, t2). Następnie
] X ~ I-IXAG "] @ IXg, p1-32 (N (C)) 2 - 26N (C).
Dowodu. Najpierw udowodnić następujące twierdzenie. Jeśli ostatni element jest i ti, G "=
IMPI (C, 5) (G), G '= IMPI_ ~ (C, 6) (G) i P = (tl, t2) to mamy
(11,1)! X2, el-1X. ~; P [> = [X2, EI - ~ c '(N (C)) 2 - 25N (C)
(11,2)] X ~ f '[[> = [X ~, Pi i
(11.3) IX ~ I - IX2 "Pito l> = IX2, p [-IXZ"
udowodnić (11.1) mamy pokazać, że] X ~ ~ pI <= 52 (N (C)) 2 +2 ~ N (C). To
nierówności łatwo wynika z lematu 4.
(11.2) wynika z faktu, że za ~ C (q), b ¢ C (t2): G ()> = (G)
i G "(b) <= G (b).
W celu udowodnienia (11.3) Napiszmy Dom (C) × Dom (C) w formie
PUQU YUZ gdzie Y = (VX (~ t, t2)) U ((tx, t ~) × V). O V = (tcDom (C) lt <q),
Z = (W / (q, t2)) U ((fi, t2) × W) gdzie W = (t ~ Dom (C) lt> t ~), Q = (Dom (C) -
- (T, t Dom ~})×( (C) - (fi, t,)).
definicji Bythe z IMPi, [X ~, v [= 1X ~ i'v [~ i IX, [w = [X ~ i'w [a więc
IX-IX ~ l ~ "l = IX2, ~ l - IxZ '~ I + Ix2, Qf - IxZ' ~ I
Możemy udowodnić nierówność IXGa, ol-LX ~ G ", o] = 0, przy użyciu tych samych argumentów, jak w
dowód lematu 10, a więc mamy (11.3).
Teraz udowodnimy lemat. Jeśli ostatni element to 0 ~ t następnie G '= X ~ IMP
(C, 5) (G3, gdzie G "= dokonującego (C, CS) (G), więc (11.1), (11.3) i lematu 10 powoduje
wymagane nierówności.
Jeśli ostatni element t ~ I to jest G '= IMPI (C, 5) (G'), gdzie G "= dokonującego ×
(C, 5) (G) stąd Lemat 10, (11.3), (II.l) i (11.2) oznacza nasze twierdzenie. |
Lemat 12. (A) Załóżmy, że C jest to łańcuch G stanowisko fl> 0, ~ t, t2EDom (C),
q <t e i R ~ ~ (ta, do). Potem są kolejne t ~ t, ~ t "CDom (C). z q = ~ q <p
~ t <= t2 i 7Ra (t, t ~). Gk i
(B) Załóżmy, tl, t cDom ~ (C), tl <te i IX~G, ((,~,t~>) [> 2 (N! C)) 2 do
około 2> 0, AC = L. Wówczas istnieją kolejne ~ t, ~ t Edomu (C), t ~ <t2 z
[G X )~,<<,,. 4>) k> l; TZ (U (C)).
Dowodu. (A) Niech tl być maksymalny element Dom (C) o następujących właściwościach:
R ~ (~ t, t;), tl = <tl-"<t2. Jeśli tz" jest elementem Dora (C), która obejmuje ~ t następnie
QR ~ (tx, ~ t).
(B) [X ~ ((t, t ~)}[> 2 (N (C)) oznacza, że e-qRX / ~ (c) (q, ~ t). Zastosowanie (a)
QR mamy ~ / Zu (c) (t ~, t'2) dla niektórych kolejnych qt, tzt, q <-t ~ f t2t_ <= ~: tz, a tym samym
[X ~ 6. (<"X.t ,~>~}. lo = 0z" / 4N (C). O |
SORTOWANIA równolegle KROKI 15
Dowód lematu 9. Załóżmy, że istnieją tl, t ~ Edomu (C), tl <~ t z
QR ~ N ~ c) (h, t ~). Według Lemat 12 (a) możemy przypuszczać, że tl, t2 są kolejne
elementów Dora (C). hs (e, j), s = l, 2 .... oznaczać będzie wystarczająco largo
pozytywny stałych zależności i wyłącznie na e j. Niech
A = (XEL s] (TL) - 2hl (~, S)-I (,) = ~ p (x) ~ s (~ t) +2 h ~ (8'J) - T (q)) .
Lemat 10 powoduje, że jeśli Fk = (k IMP (C, 6)) (F) (° F = F), a następnie [xFk [jest monotonnie
funkcją malejącą w k. QF (C, P, M) i lematu 8 "oznacza, że IIXF ~ [p -
6 2
- IXrA ~, PII <---~( N (C)) 2, gdzie P = ((q, ~ t)). X Ark, v <=- p ~ v.r4k więc wystarczy
udowodnić, że istnieje b0 (w zależności tylko od e i j) z następującej własności:
bo> k oznacza, X [~ [<e2 / 2 (N (C)) Z.
Będziemy udowodnić następujące wyraźniejsze: dla wszystkich k
(12.1), jeżeli IXa ~ l> e2 (N (C)) 2 a następnie [XaFkI - lX ~ ll ÷> 1 j)
(12,2) IXar L <h3 (e, j) (N (C)) 2.
(12,2) jest konsekwencją ~ Q (C, P, M) oraz definicji A. Istotnie,
IX ~ ° <I = IAI ~ <= (Z [(x [XeF ° NTR (f (t)) i xe)]) 2
tEDom (C)
(12,3) <- 2n (~ J) N (C) +. ~ [(Xe [xEContv (C (t)) [) z,
TEH
gdzie H = (t jest (t)-s (fi])> 2h ~ t ~. j) 2 - ~ (q)). QJ (C F, Q, M), M <= 2N (C), q <¼ i
definicje i H oznacza, że drugi termin (12,3) jest mniejsza niż
2MqJ <N (C), który jest
IX L - <_ 2h0 ~ J) (N (C)) 2.
Teraz załóżmy, że [XVa ~ I>-E2 / ~ (N (C)-f. Lemat 8 "oznacza, że Q ~ (C, Q, M).
Według definicji jest hg (e, j) tak, że jeśli y> hg (e, j) i
W (T) = (t [ls (t)-s (q) <= 2 l ~ m ~), l (t) = l (do)
następnie [U AOContrk (C (t)) l <N (C), a więc IAL hlo <(e, j) N (C). Zatem
t ¢ WFR)
jest hn (e, j) tak, że jeśli 7> hll (e, j), a następnie
1 e2
Jeżeli więc IX ~ I> ~ V ~ (N (C)) ~ a
iw związku z tym istnieją ~ r, ~ r W E (V) z
F ~ 1 N (C) ~.
IXA'{('"'~)}] ttT> (e, j-"- ~
16 m. AJTAL J. KOMLOS, E. SZEMERI ~ DI
Według Lemat 12 (b) istnieją kolejne £ r, ~ r
vu 1
] XA, {(,;, ,;_}) 1> h8 (5, j) (N (C)) 2 "
a zatem lematu 11 wynika zawarcia (12.1). II
Następstwem 9. Dla wszystkich j>-_l, O <q-<¼ 3bo, 6o> 0 takie, że dla wszystkich b> bo, 0 <6 <60
tf C jest łańcuch, F to stanowisko, ½ N (C) <-M <2N (C), Q ~ (C, P, M), F '=
= (IMW (C, 6)) (F) i [p (x) - PFC (x) l <½] C1-1 dla wszystkich xCfontv (C), to mamy
Qf (C, Q, M).
Dowodu. Najpierw udowodnić następujące twierdzenie: Dla każdego 7> 0, jeśli b jest wystarczająco
dużych i 6> 0 jest dostatecznie mała i tcDom (C), a następnie
(C.I) [(XE Contv, (c (t)) ILP (x) - s (t)! > L-21c) [VN <(C)
Niech l> q> 0. Twierdzimy, że istnieje fl0> 0 (w zależności od q, j, q)
takie, że dla wszystkich 0 <fi </ 30 mamy: xEContp, (C (t)) ~ oznacza, że
~ C.z)] (y> ~] ~ c <t. y ~ Cont. (0) 1 <, N (C)
Rzeczywiście, Q ~ '(C, q, M) oznacza, że
[(Y> xl-j t '. "S (t) <s (t)-h, ICL-a, y <Contv, (f (t))) I <7" N (C),
~ gdzie h> 0 może zależeć od q, j, q. Stosowania kemma 9 z dostatecznie małym
e mamy
] (Y> x [~ t ': s (t)-h ~ [C [- ~ <= s (t) <s (t), yEContp, (C (t))) [<WU N (C ),
co oznacza (C.2).
Teraz udowodnimy (C.1). Zgodnie z (C.2), jeżeli xEContF, (C (t) ~, a następnie
p ~ '(x) ~ 2-i (N (C))-a (- ~ IN (C) + ZN (C)) = ~ s (t)-ICI-L
"¢ r. ¢ = t
Podobnie mamy ~ p (x) - ~ s (t) + LC] - ~, więc lp ~ '(x)-p (x) [<½] Cl - oznacza ~ (C.1).
Przypuśćmy teraz, że 1 ~ 2 ~ j, i F "spełnia (CI) z ~ <<QJ. Ge "(t,] C [- ~ 2, M) -
U = M (t '), gdzie
M (t ') - (XE Contf, (C (t'))] s (t) - p (x)> IC [- ~ (2 ~ + ½))
~ Q (C, Q, M) oznacza, że ~! M (t ') l ~ ½ qJM, gdzie h jest na tyle ~
S (t)> S (r) D_] 121C] -1
większa w stosunku do j, i zgodnie z (C 1)
[M ~ '(t) <l - ¼ qJN (C) ~ Qim ½,

---