Párhuzamos Erdős-Gallai algoritmus. TDK dolgozat

¨ tvo ¨ s Lora ´ nd Tudoma ´ nyegyetem Eo Informatikai Kar ´k Komputeralgebra Tansze

P´ arhuzamos Erd˝ os-Gallai algoritmus TDK dolgozat

Témavezet˝o: Dr. Iványi Antal Miklós egyetemi tanár

Kész´ıtette: Lucz Loránd II. évfolyam Programtervez˝o informatikus MSc

Budapest, 2011

Tartalomjegyz´ ek 1. Bevezet´ es

3

2. Algoritmusok 2.1. Havel-Hakimi algoritmus (HH) . . . . . . . . . 2.2. Erd˝ os-Gallai algoritmus (EG) . . . . . . . . . . 2.3. R¨ ovid´ıtett Erd˝ os-Gallai algoritmus (EGR) . . . 2.4. Ugr´ o Erd˝ os-Gallai algoritmus (EGU) . . . . . . 2.5. Line´ aris Ugr´ o Erd˝ os-Gallai algoritmus (EGLU)

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

3. Lesz´ aml´ al´ asi eredm´ enyek 4. A Holzhacker program 4.1. Kiszolg´ al´ o program . . . . . . . . . . . . 4.2. Feladatokat kioszt´ o algoritmus (DJ) . . 4.3. Kliens program . . . . . . . . . . . . . . 4.4. Felsorol´ o Erd˝ os-Gallai algoritmus (EGE)

4 4 5 5 6 6 7

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

10 12 15 16 18

5. A feladat r´ eszekre bont´ asa 5.1. Naiv megk¨ ozel´ıtés . . . . . . . . . . . . . 5.2. Feloszt´ as kor´ abbi n értékekre alapozva . . 5.3. Feloszt´ as a m˝ uveletszámok alapján . . . . 5.4. Feloszt´ as a p´ aros sorozatok száma alapján

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

22 22 22 23 23

6. Eredm´ enyek

26

¨ 7. Osszefoglal´ as

26

Hivatkoz´ asok

29

2

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus

1.

Bevezet´ es

A benn¨ unket k¨ or¨ ulvev˝ o vil´ agot sokféleképpen modellezhetj¨ uk. Az egyik lehetséges módszer a vil´ ag gr´ afokkal t¨ ortén˝o reprezentálása. A kör¨ ulött¨ unk lev˝o objektumokat logikailag ¨ osszekapcsolhatjuk, majd ezeket a kapcsolatokat ábrázolhatjuk gráfok seg´ıtségével. Egyszer˝ u példaként tekinthet¨ unk például egy családfát, ahol a gráf egy cs´ ucsa jel¨ ol egy személyt, a gráf élei pedig a sz¨ ul˝o-gyermek viszonyokat. Ez alapján mindenki a sz¨ uleivel és gyermekeivel áll közvetlen kapcsolatban. A gráfok cs´ ucsai minden esetben legfeljebb egyszeresek lehetnek és a kapott gráf hurokél mentes. Az ilyen gr´ afokat egyszer˝ u gr´ afnak nevezz¨ uk. Mivel manaps´ ag m´ ar szinte mindent szám´ıtógépekkel végz¨ unk, ezért fontos kérdés ezeknek a gr´ afoknak a tárolása. Ennek egyik lehetséges módja a cs´ ucsok foksz´ amainak t´ arol´ asa. Egy gráfból könnyedén fel´ırhatunk egy foksorozatot, megford´ıtva azonban m´ ar nem ilyen egyszer˝ u a probléma megoldása, hiszen nem sz¨ ukségszer˝ uen tartozik mint sorozathoz gráf és adott sorozathoz több gráf is tartozhat. Ezzel a kérdéssel sok helyen találkozhatunk. Landau [20] az állatok köz¨ ott fenn´ all´ o dominanci´ at modellezte ilyen módon, Hakimi [8] kémiai, Iványi és munkat´ arsai pedig sportbeli [10, 11, 13, 15] alkalmazásokra hivatkoztak. A problém´ ara els˝ oként V´ aclav Havel javasolt megoldást 1955-ben [9], majd t˝ole f¨ uggetlen¨ ul 1962-ben Louis Hakimi [8] is publikálta a módszert. Ezért a m´ odszert rendszerint Havel-Hakimi algoritmusként emlegetik. A módszernek bizonyos szempontb´ ol el˝ onye, másfel˝ol pedig hátránya, hogy a sorozatokat nem csup´ an megvizsg´ alja, hanem a hozzájuk tartozó gráfot is el˝oáll´ıtja, ezért a legrosszabb fut´ asi ideje nem lehet kisebb, mint négyzetes. Erd˝ os és Gallai 1960-ban [5] javasolt másik módszert a kérdés eldöntésére, amely már nem ´ all´ıtja el˝ o a gr´ afot, csupán ellen˝oriz. Az ˝o módszer¨ ukhöz kés˝obb Tripathi és Vijay [27] megadott két javaslatot, amellyel az eredeti módszer gyors´ıtható, de még ezeket felhaszn´ alva is nagyon komoly szám´ıtási igénnyel rendelkezik a feladat. Az eredeti algoritmusok ugyan csak egyszer˝ u gráfokra alkalmazhatóak, azonban a kés˝ obbiekben kiterjesztették ˝ oket egyszer˝ u irány´ıtott gráfokra [6, 18, 19], valamint irány´ıtatlan [4, 23] és ir´ any´ıtott [10, 11] multigráfokra is. 2011-ben megadtuk [13, 21] az Erd˝os-Gallai módszer egy olyan változatát (EGL), amellyel line´ aris id˝ oben elvégezhet˝o a vizsgálat. A módszer egy változatát a kés˝ obbiekben ismertetj¨ uk. Sloan interneten elérhet˝ o The On-Line Encyclopedia of Integer Sequences [24] nev˝ u adatb´ azis´ aban tal´ alhat´ oak adatok arra vonatkozóan, hogy n cs´ ucs´ u gráfok esetén pontosan h´ any k¨ ul¨ onb¨ oz˝o foksorozat létezik. Ezeknek a sorozatoknak a számát a kés˝ obbiekben Gn -nel jel¨ olj¨ uk. Az adatbázis n ≤ 23-ig tartalmazta ezeket az adatokat. n = 20-t´ ol n = 23-ig például Cohen adta meg ezeket az adatokat 2011. j´ ulius 9-én. A dolgozatban kés˝obbiekben ismertetett program felhasználásával megadtuk a Gn értékét egészen n = 29-ig. Eredményeink megtalálhatóak az OEIS adatb´ azis A004251-es sorozat´ aban [24]. Az EGL algoritmust tov´ abbfejlesztve, a minden szóba jöv˝o sorozat ellen˝orzésére kész´ıtett EGP algoritmussal nagyobb n értékekre is meghatároztuk a Gn 3

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus értékeit. Ezeket az értékeket egy – több szám´ıtógépen párhuzamosan futtatott – h´ al´ ozati program seg´ıtségével szám´ıtottuk ki, mivel a szám´ıtások futási ideje az n érték n¨ ovelésével minden lépésben kör¨ ulbel¨ ul négyszeresére n˝o [13]. Ez az exponenci´ alis n¨ ovekedés tette sz¨ ukségessé az algoritmus szám´ıtógépes megval´ os´ıt´ as´ anak p´ arhuzamos´ıtását. Dolgozatunk célja a sorozatok gyors ellen˝orzési módszereinek ismertetése, valamint a vizsg´ alatot elvégz˝ o program bemutatása. A dolgozat felép´ıtése a k¨ ovetkez˝o: a 2. részben ismertetj¨ uk a Havel-Hakimi és az Erd˝ os-Gallai algoritmusokat, le´ırjuk Tripathi és Vijay gyors´ıtásait, valamint a line´ aris Erd˝ os-Gallai ugr´ o algoritmust. A k¨ ulönböz˝o feltételeknek megfelel˝o sorozatok sz´ am´ aval kapcsolatos leszámlálási eredményeket tartalmazza a 3. rész. A sz´ am´ıt´ asokat elvégz˝ o programot a 4. részben ismertetj¨ uk, majd a 5. részben ´ırjuk le a probléma részekre bont´ asának technikáit, vég¨ ul az 6. részben összefoglaljuk a le´ırt m´ odszerekkel és a programmal elért eredményeinket.

2.

Algoritmusok

A dolgozatban szerepl˝ o algoritmusok forráskódjai megtalálhatóak a http://people.inf.elte.hu/lulsaai/Holzhacker honlapon, pszeudokódjai pedig a [13] cikkben és a [21] TDK dolgozatban. Miel˝ ott bevezetnénk a felhasznált algoritmusokat, definiáljuk a használt fogalmakat és megadjuk, hogy milyen alapvet˝o feltételezésekkel él¨ unk ezek kapcsán. A G gr´ af i-edik cs´ ucsa legyen Vi , Vi foka legyen fi és G foksorozata legyen F = (f1 , . . . , fn ). Egy F foksorozat szab´ alyos, ha n ≥ 1 és az fi (1 ≤ i ≤ n) értékek egész számok, tov´ abb´ a n − 1 ≥ f1 ≥ · · · ≥ fn ≥ 0. Egy szabályos foksorozatot megval´ os´ıthat´ onak vagy helyre´ all´ıthat´ onak nevez¨ unk, ha létezik olyan G egyszer˝ u gráf, amelynek foksorozata F . Egy F szabályos sorozat p´ aros, ha elemeinek összege páros. P Sz¨ ukség¨ unk lesz tov´ abb´ a a sorozat els˝o k elemének összegére, amit Hk = ki=1 fi -vel fogunk jel¨ olni.

2.1.

Havel-Hakimi algoritmus (HH)

Az algoritmust els˝ oként Havel [9] ´ırta le, majd kés˝obb t˝ole f¨ uggetlen¨ ul Hakimi [8] is publik´ alta ugyanezt az eredményt, innen adódik a Havel-Hakimi algoritmus elnevezés. ´tel. (Havel, Hakimi [8, 9]) Az F = (f1 , . . . , fn ) (n ≥ 3) szab´ 1. Te alyos foksorozat akkor és csak akkor helyre´ all´ıthat´ o, ha az F 0 = (f2 − 1, f3 − 1, . . . , ff1 − 1, ff1 +1 − 1, ff1 +2 , . . . , fn−1 , fn ) sorozat is helyre´ all´ıthat´ o. Bizony´ıt´ as. L´ asd [8, 9]. Az algoritmust kés˝ obb kiterjesztették egyszer˝ u irány´ıtott gráfokra [6, 18, 19], valamint ir´ any´ıtatlan [4, 23] és irány´ıtott [10, 11] multigráfokra is. 4

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus A tétel felhaszn´ al´ as´ aval fel´ırható algoritmus nagy hátránya, hogy felhasználása során minden egyes lépésben u ´jra kell rendezni a sorozatot. Másrészt az algoritmus egyesével cs¨ okkenti a foksz´ amokat, ezért például az F = (n − 1, . . . , n − 1) sorozatnál Θ(n2 ) cs¨ okkentést végez. Ezért az algoritmus futási ideje legrosszabb esetben akkor is Ω(n2 ), ha line´ aris fut´ asi idej˝ u rendez˝o algoritmust használunk.

2.2.

Erd˝ os-Gallai algoritmus (EG)

Erd˝ os és Gallai 1960-ban adtak meg olyan ellen˝orzési módot, amely a sorozatot nem áll´ıtja el˝ o, csup´ an eld¨ onti, hogy az helyreáll´ıtható-e vagy sem. ´tel. (Erd˝ 2. Te os, Gallai [5]) A szab´ alyos F = (f1 , . . . , fn ) sorozat akkor és csak akkor helyre´ all´ıthat´ o, ha n X fi p´ aros (1) i=1

és

j X

fi − j(j − 1) ≤

i=1

n X

min(j, fk ) (j = 1, . . . , n − 1).

(2)

k=j+1

Bizony´ıt´ as. L´ asd [3, 5, 21].

A tétel felhaszn´ al´ as´ aval megvalós´ıtható algoritmus futási ideje a legjobb Θ(n) és legrosszabb Θ(n2 ) k¨ oz¨ ott v´ altozik. A k¨ ozelm´ ultban Tripathi és munkatársai [28] publikáltak egy konstrukt´ıv bizony´ıt´ ast, amely helyre´ all´ıtható sorozatok esetén a helyreáll´ıtást is elvégzi. Ennek az algoritmusnak a fut´ asi ideje legrosszabb esetben Θ(n3 ).

2.3.

R¨ ovid´ıtett Erd˝ os-Gallai algoritmus (EGR)

Tripathi és Vijay 2003-as cikk¨ ukben [27] le´ırtak egy lehetséges rövid´ıtési módot Erd˝os és Gallai m´ odszerére. A (2) egyenl˝otlenséget elegend˝o csak azokban az esetekben ellen˝ orizni, ahol a Hi > i(i − 1) feltétel teljes¨ ul. 1. Lemma. (Tripathi et al. [27]) Egy szab´ alyos F = (f1 , . . . , fn ) foksorozat akkor és csak akkor helyre´ all´ıthat´ o, ha Hn p´ aros (3) és Hi − i(i − 1) ≤

n X

min(i, fk ),

(4)

k=i+1

ahol i = 1, . . . , max (k | k(k − 1) < Hk ). 1≤k≤n

Bizony´ıt´ as. L´ asd [27].

(5) 5


2.4.

Ugr´ o Erd˝ os-Gallai algoritmus (EGU)

Tripathi és Vijay [27] megadtak egy további lehetséges rövid´ıtési módot is. A rövid´ıtés azt haszn´ alja ki, hogy ha egy ellen˝orizend˝o sorozatban egy fokszám többször is el˝ ofordul, akkor azt elegend˝o csupán egyszer ellen˝orizni, méghozzá abban a pontban, ahol teljes¨ ul, hogy fi 6= fi+1 . A sorozatok utolsó elemeit pedig nem sz¨ ukséges ellen˝ orizni. Vezess¨ uk be a gi jel¨ olést azokra az i indexekre, amelyekre teljes¨ ulnek az fi 6= fi+1 és az i 6= n feltételek. Ezeket a pontokat ellen˝ orz˝ opontoknak nevezz¨ uk. Ha q jelöli az ellen˝ orz˝ opontok sz´ am´ at, akkor az F sorozat fg1 , . . . , fgq elemei ellen˝orz˝opontok. ´tel. (Tripathi, Vijay [27]) A szab´ 3. Te alyos F = (f1 , . . . , fn ) sorozat akkor és csak akkor helyre´ all´ıthat´ o, ha Hn p´ aros (6) és Hgi − gi (gi − 1) ≤

n X

min(gi , fk ) (i = 1, . . . , q).

(7)

k=gi +1


2.5.

Line´ aris Ugr´ o Erd˝ os-Gallai algoritmus (EGLU)

Az algoritmust tov´ abb gyors´ıthatjuk, ha kihasználjuk az F sorozat monotonitását, teh´ at azt, hogy a feltételben szerepl˝o összegzést nem kell minden egyes iterációban elvégezni, mivel a szumm´ aban szerepl˝o min f¨ uggvény egy wi indexig (s´ ulypont) mindig az els˝ o, majd att´ ol kezdve mindig a második paraméterét fogja visszaadni. A monotonit´ as miatt pedig ez az érték csak az egyik irányban változhat, ´ıgy elég az egyes iter´ aci´ ok k¨ oz¨ ott néh´ any lépésben eltolni, ´ıgy nyer¨ unk egy explicit képletet a szumm´ ara. A szumm´ ak értékének kiszám´ıtása ´ıgy a legrosszabb esetben is csak line´ aris id˝ ot vesz igénybe. ´tel. A szab´ 4. Te alyos F = (f1 , . . . , fn ) sorozat akkor és csak akkor helyre´ all´ıthat´ o, ha Hn p´ aros (8) és

( Hn − Hgi + gi (gi − 1), Hgi ≤ Hn − Hwi + gi (wi − 1),

ha wi ≤ gi ha wi > gi .

(9)

Bizony´ıt´ as. L´ asd [21]. Az ellen˝ orz˝ opontok elégségességét Tripathi és munkatársai [27] már bebizony´ıtott´ ak. A tételben megadott feltétel ezeket az ellen˝orzéseket végzi el, kihaszn´ alva a sorozat elemeinek monoton csökkenését, azaz a n X

min(i, fk )

(10)

k=gi +1

6

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus o¨sszeget nem sz´ amoljuk u ´jra minden esetben, pontosabban nem ebben a formában végezz¨ uk el a sz´ am´ıt´ ast, hanem explicit módon. A kifejezés értéke a (11) formában adható meg, mégpedig azért, mert a sorozat monotonit´ asa garant´ alja, hogy a wi s´ ulypontig a min(i, fk ) kifejezés értéke minden esetben i, majd a wi -nél nagyobb k-k esetében mindvégig fk . Ebb˝ol következik, hogy ( n X Hn − Hgi , ha wi ≤ gi (11) min(i, fn ) = H − H + g (w − g ), ha w > g . n w i i i i i i k=g +1 i

Az eddigiek alapj´ an az eredeti feltételt át´ırhatjuk a következ˝o alakba: ( Hn − Hgi , ha wi ≤ gi Hgi − gi (gi − 1) ≤ Hn − Hwi + gi (wi − gi ), ha wi > gi . A (12) egyenl˝ otlenséget ´ atrendezve megkapjuk a ( Hn − Hgi + gi (gi − 1), ha wi ≤ gi Hgi ≤ Hn − Hwi + gi (wi − 1), ha wi > gi kifejezést, ami pontosan egyezik a (9) egyenl˝otlenséggel.

(12)

(13)

´tel. A line´ 5. Te aris Erd˝ os-Gallai ugr´ o algoritmus fut´ asi ideje line´ aris. Bizony´ıt´ as. L´ asd [21].

3.

Lesz´ aml´ al´ asi eredm´ enyek

Ebben a részben a gr´ afsorozatok számára, valamint az n-szabályos és n-páros sorozatok sz´ am´ anak ar´ any´ ara vonatkozóan ismertet¨ unk néhány képletet. Megmutathat´ o, hogy ha l, u és m egészek, valamint u ≥ l, m ≥ 1 és l ≤ fi ≤ u (i = 1, . . . , m), akkor az (l, u, m)-szab´ alyos sorozatok száma K(l, u, m) = (u − l + 1)m .

(14)

Tudjuk, hogy (l´ asd [17], 65. oldal) ha l, u, m egészek és u ≥ l, m ≥ 1, u ≥ f1 ≥ · · · ≥ fn ≥ l, akkor az (l, u, m)-korl´ atos szabályos sorozatok száma u−l+m Q(l, u, m) = . (15) m Az ¨ osszes ´ altalunk vizsg´ alt sorozat számára vonatkozóan Sloane és Ploffe [25], valamint Stanley [26] k¨ onyveiben és a The On-Line Encyclopedia of Integer Sequences [24] honlapon tal´ alhatunk adatokat (lásd 1. táblázat). 1987-ben Ascher adott meg explicit formulát az n-hossz´ u páros sorozatok szám´ anak meghat´ aroz´ as´ ara. 7

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus 2. Lemma. (Ascher [1], Sloane, Pfoffe [25]) Ha n ≥ 1, akkor a p´ aros sorozatok sz´ ama 1 2n − 1 n−1 En = + . (16) 2 n n Bizony´ıt´ as. L´ asd [1].

A nagy mennyiség˝ u sorozatot ellen˝orz˝o program megvalós´ıtása során hasznos lesz a kés˝ obbiekben az Rn nagys´ agrendjére, valamint az Rn és En értékek arányára vonatkoz´ o lemma. 3. Lemma. Ha n ≥ 1, akkor

Rn+1 Rn+2 > , Rn+1 Rn

(17)

Rn+1 = 4, Rn

(18)

lim

n→∞

tov´ abb´ a

4n √ 4πn

1 4n 1 1− < Rn < √ 1− 2n 8n + 8 4πn


(19)

A k¨ ovetkez˝ o lemma megadja az En értékek nagyságrendjét. 4. Lemma. Ha n ≥ 1, akkor

En+2 En+1 > En+1 En

(20)

En+1 =4 n→∞ En

(21)

4n 4n √ (1 − D3 (n)) < En < √ (1 − D4 (n)) πn πn

(22)

lim

tov´ abb´ a

ahol a D3 (n) és D4 (n) monoton cs¨ okken˝ o és null´ ahoz tart. Bizony´ıt´ as. L´ asd [13].

Ahogy a 1. t´ abl´ azatb´ ol is leolvasható, az En /Rn arány monoton csökken és 1/2-hez tart. ¨ vetkezme ńy. Ha n ≥ 1, akkor 1. Ko

és

En+1 En < Rn+1 Rn

(23)

En 1 = . n→∞ Rn 2

(24)

lim

8


n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

1 4 16 63 247 973 3 824 15 033 59 132

1 4 17 68 269 052 116 123 205 959 469 345 633 290

1 5 20 77 300 166 537 672 923 128 049 715 801 303 266 712 300 249 782

1 6 24 92 352 352 200 058 558 540 803 567 631 264 937 481 363 841 218 474 824 380 770 430

Rn 1 3 10 35 126 462 716 435 310 378 716 078 300 300 760 195 110 650 900 410 220 860 800 550 876 052 056 220 520 712

2 8 31 123 486 1 912 7 516 29 566

2 8 34 134 526 058 061 602 979 734 172 816 145

2 10 38 150 583 268 836 461 564 024 358 901 652 635 861 660 644 429

3 12 46 176 676 600 030 781 273 407 795 340 678 560 917 034 596 961 837 612 219 943 994

En 1 2 6 19 66 236 868 235 190 252 484 270 612 008 096 315 990 980 260 394 988 288 616 814 516 176 328 260 559 736

En /Rn 1,0000000000 0,6666666667 0,6000000000 0,5428571429 0,5238095238 0,5108225108 0,5058275058 0,5027195027 0,5014397367 0,5006819806 0,5003572279 0,5001708481 0,5000888410 0,5000427753 0,5000221252 0,5000107057 0,5000055151 0,5000026787 0,5000013756 0,5000006702 0,5000003432 0,5000001676 0,5000000857 0,5000000419 0,5000000214 0,5000000105 0,5000000053 0,5000000026 0,5000000013 0,5000000007

1. t´ abl´ azat. A szab´ alyos és páros sorozatok száma és azok aránya.

9

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus Bizony´ıt´ as. L´ asd [13]. A k¨ ovetkez˝ o lemma megadja a nullmentes sorozatok arányát a szabályos sorozatokhoz viszony´ıtva. 5. Lemma. Az n-szab´ alyos nullmentes sorozatok sz´ ama 2n − 2 Rnz = n−1 és

Rnz 1 = . n→∞ Rn 2 lim

(25)

(26)

Bizony´ıt´ as. L´ asd [13]. Szimul´ aci´ os eredményeink szerint [13] az is igaz, hogy a páros sorozatoknak kör¨ ulbel¨ ul a fele nullmentes. A G értékek nagys´ agrendjére vonatkozóan Burns adott meg aszimptotikus korl´ atokat. 6. Lemma. (Burns [2]) Léteznek olyan c és C pozit´ıv konstansok, hogy a Gn értékre az al´ abbi korl´ atok adhat´ ok: 4n 4n √ . < Gn < cn (log n)C n

(27)

Bizony´ıt´ as. L´ asd [2]. Ebb˝ ol k¨ ovetkezik, hogy a grafikus sorozatok s˝ ur˝ usége a páros sorozatok között a null´ ahoz tart. ¨ vetkezme ńy. Ha n ≥ 1, akkor létezik olyan pozit´ıv C konstans, hogy 2. Ko

és

Gn 1 < En (log2 n)C

(28)

Gn = 0. n→∞ En

(29)

lim

Bizony´ıt´ as. (28) a (16) és a (27) közvetlen következménye és a (28) egyenl˝ otlenségb˝ ol k¨ ovetkezik a (29) határérték. Tov´ abbi eredmények és ¨ osszef¨ uggések találhatóak a [13] cikkben.

4.

A Holzhacker program

A Gn értékek meghat´ aroz´ asa komoly er˝oforrásigénnyel b´ır, ezért szám´ıtásainkat az alábbi technik´ ak felhaszn´ al´ as´ aval igyekezt¨ unk felgyors´ıtani: - a feladat részekre bont´ asa és szétosztása több szám´ıtógép között, 10

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus - a nyilv´ anval´ oan nem grafikus sorozatok elhagyása, - annak kihaszn´ al´ asa, hogy a lexikografikus sorrendben az u ´j sorozatok a részfeladaton bel¨ ul O(1) várható id˝o alatt el˝oáll´ıthatóak, - csak nullmentes sorozatok vizsgálata, - ellen˝ orzés elvégzése csak ugrópontokban, - annak kihaszn´ al´ asa, hogy az ellen˝orz˝opontok és s´ ulypontok listája a részfeladaton bel¨ ul O(1) várható id˝o alatt friss´ıthet˝o, ha a vizsgálandó nullmentes, p´ aros sorozatokat lexikografikus sorrendben áll´ıtjuk el˝o. A feladat p´ arhuzamos´ıt´ asa a processzorok számával arányosan csökkenti a sz¨ ukséges fut´ asi id˝ ot, azaz minél több szám´ıtógéppel dolgozunk, annál kevesebb ideig tartanak a sz´ am´ıt´ asok. Nyilv´ anval´ oan nem helyre´ all´ıtható sorozatoknak tekintj¨ uk azokat a sorozatokat, amelyekben a foksz´ amok ¨ osszege páratlan. A null´ as sorozatok vizsg´ alatának elhagyása pedig azért hasznos, mert a páros sorozatok megk¨ ozel´ıt˝ oleg felében szerepel nulla. Mivel minden egyszer˝ u gráfhoz tartoz´ o foksorozatra teljes¨ ul, hogy egy nullát hozzávéve a kapott sorozathoz továbbra is megadhat´ o hozz´ a egy gr´ af, ezért ezeket a sorozatokat felesleges megvizsgálnunk, mert Gn sz´ am´ıt´ asa sor´ an u ´jra leellen˝oriznénk minden Gn−1 szám´ıtása során kor´ abban m´ ar megvizsg´ alt sorozatot. Ezt az ötletet használja fel a következ˝o lemma. 7. Lemma. Ha n > 1, akkor az n cs´ ucs´ u gr´ afok sz´ ama megadhat´ o az n − 1 cs´ ucs´ u helyre´ all´ıthat´ o foksorozatok és az n hossz´ u helyre´ all´ıthat´ o nullmentes sorozatok ¨ osszegeként, azaz Gn = Zn + Gn−1 . Bizony´ıt´ as. L´ asd [13, 21].

Ennek k¨ ovetkezményeképp a Gn érték kiszám´ıtható az azt megel˝oz˝o G értékek felhaszn´ al´ as´ aval. ¨ vetkezme ńy. Ha n ≥ 1, akkor az n cs´ 3. Ko ucs´ u egyszer˝ u gr´ afok foksorozatainak sz´ ama megadhat´ o a 2 ≤ i ≤ n cs´ ucs´ u egyszer˝ u gr´ afok nullmentes foksorozatainak felhaszn´ al´ as´ aval a k¨ ovetkez˝ o m´ odon: Gn = 1 +

n X

Zn

(30)

i=2


A program m˝ uk¨ odésének le´ırása során d˝olt kisbet˝ uk jelölik a felhasznált változókat és d˝ olt nagybet˝ uk a konstansokat, valamint a fontosabb hálózati primit´ıveket. A programot négy részben ismertetj¨ uk, ezek pedig a következ˝ok: a 4.1. részben le´ırjuk a szerver program m˝ uködését, amit folyamatábrák seg´ıtségével ismertet¨ unk, 11

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus a 4.2. részben pszeudok´ oddal ismertetj¨ uk a szerver feladatokat kiosztó részét, azaz eltekint¨ unk a h´ al´ ozati kommunikációval kapcsolatos részek részletezését˝ol. A 4.3. részben a kliens m˝ uk¨ odését ´ırjuk le folyamatábrákkal, majd ezt a program grafikus sorozatokat lesz´ aml´ al´ o részének ismertetése követi a 4.4. részben, pszeudokódok felhaszn´ al´ as´ aval.

4.1.

Kiszolg´ al´ o program

Programunkban egy k¨ ozponti kiszolgáló program osztja ki a részfeladatokat a sz´ am´ıt´ asokhoz csatlakoz´ o kliensek között. Ennek kész´ıtésekor az els˝odleges szempontunk a lehet˝ o legnagyobb megb´ızhatóság, rugalmasság és sebesség elérése volt. Megb´ızhat´ os´ agon azt értj¨ uk, hogy a rendszer m˝ uködését k¨ uls˝o természeti vagy akár hum´ an tényez˝ ok ne befolyásolják. A kiszolgáló program ezért bármikor leáll´ıthat´ o és u ´jraind´ıthat´ o anélk¨ ul, hogy ez eredmények elvesztésével járna. A szerver le´ all´ asa a klienseket nem befolyásolja. Ez egyben azt is jelenti, hogy amennyiben sz¨ ukséges, a szerver programot egy komolyabb szám´ıtási projekt során bármikor kicserélhetj¨ uk vagy megváltoztathatjuk. A szerver rugalmass´ aga abban rejlik, hogy m˝ uködése semmilyen módon nem f¨ ugg ¨ ossze azzal, hogy a kliensekben mi történik, csupán annyi a teend˝oje, hogy részfeladatokat oszt ki és eredményeket gy˝ ujt be. Az sem jelent problémát, ha közben minden klienst meg´ all´ıtunk, mert ezzel a szerver egyáltalán nem foglalkozik. Ez els˝ ore ugyan érdektelennek t˝ unhet, de nem az, ha figyelembe vessz¨ uk, hogy a kliens b´ arki sz´ am´ ara szabadon elérhet˝o az interneten, ´ıgy szám´ıtani kell arra, hogy valaki u ´gy d¨ ont, hogy részt vesz egy komoly szám´ıtásban és elind´ıtja a klienst, majd meggondolja mag´ at és mégis inkább leáll´ıtja azt. Ehelyett gondolhatunk akár egy egyszer˝ u ´ aramsz¨ unetre is. Tovább lépve, mivel nincs álladó hálózati kapcsolat a kiszolg´ al´ o és a t¨ obbi gép k¨ oz¨ ott, ´ıgy nincs limitálva a résztvev˝o szám´ıtógépek száma sem. Ha valaki elind´ıt a sz´ am´ıtógépén egy klienst, az kap egy részfeladatot és számol. Harmadik szempontunk a sebesség volt, ezért programunkat C nyelven valós´ıtottuk meg. V´ alaszt´ asunk azért erre a nyelvre esett a kezdeti MATLAB programok helyett, mert a MATLAB ugyan egy nagyon kellemes és jól átláthat´ o fut´ asi fel¨ uletet biztos´ıt, de méréseink alapján C-vel megközel´ıt˝oleg százszoros gyorsul´ as érhet˝ o el. Programunk tehát C-ben kész¨ ult, Berkeley Socketek felhaszn´ al´ as´ aval. M˝ uk¨ odése pedig a következ˝o: - A szerver ind´ıt´ asakor létrehoz egy csatlakozót (SOCKET ), amit aztán egy csatlakoz´ asi ponthoz (PORT ) köt (BIND). A csatlakozási pont a programban el˝ ore defini´ alt érték. Amint létrejött a csatlakozási pont és a szerver alkalmas a kapcsolatok fogad´ as´ ara, ellen˝orzi, hogy van-e kész eredmény a naplófájlban. Amennyiben a napl´ o nem u ¨res, u ´gy az abban szerepl˝o részfeladatokat késznek jel¨ oli. Ezut´ an elkezd˝odhet a kliensek bejöv˝o kapcsolatainak kezelése (LISTEN ). - Mindaddig, am´ıg a befejezett részfeladatok száma (finished jobs) el nem éri az 12


1. ´ abra. A szerver m˝ uködésének folyamatábrája. osszes részfeladat sz´ ¨ am´ at (NUM JOB ), addig u ´jra és u ´jra klienseket fogadunk, majd a fogadott kliens u ¨zenetéb˝ol eldöntj¨ uk, hogy mi célból jött. A kliens két okb´ ol csatlakozhatott: u ´j részfeladatot kér vagy elkész¨ ult egy részeredménnyel és azt szeretné visszak¨ uldeni. - Ha a kliens u ´j részfeladatot kér, akkor a 2. ábrán látható módon kiosztjuk neki a soron k¨ ovetkez˝ ot a k¨ ovetkez˝o algoritmus alapján: + Megn¨ ovelj¨ uk az éppen aktuális részfeladat sorszámát tároló értéket (actual job), majd ellen˝orizz¨ uk, hogy nem lépt¨ unk-e t´ ul a lehetséges legnagyobb sorsz´ amon (NUM JOB ), valamint hogy a részfeladatok st´ atusz´ at t´ arol´ o vektorunk (job status) alapján nincs-e már teljes´ıtve a megadott részfeladat. + Addig ismételgetj¨ uk ezt a m˝ uveletet, am´ıg meg nem találtuk a kiosztandó részfeladatot. + Miut´ an a részfeladat kik¨ uldésre ker¨ ult, lebontjuk a kapcsolatot. Itt megjegyezz¨ uk, hogy ha elért¨ uk az utolsó részfeladatot, akkor módszeresen elkezdj¨ uk u ´jra kiosztani a már legrégebben kiadott részfeladatokat arra az esetre sz´ am´ıtva, hogy a kliens, amely azt a részfeladatot végezte volna, valamilyen okból (szám´ıtógép leáll´ıtása, áramsz¨ unet stb.) nem tudta azt befejezni. Ez nyilván azt eredményezi, hogy amikor már nagyon kevés munka van vissza, akkor sok kliens fogja ugyanazt a részfeladatot 13


´ részfeladat kiosztása a kliensnek. 2. ´ abra. Uj megkapni, ´ıgy a részfeladatok befejez˝odésével egyre robusztusabbá válik a rendszer.

3. ´ abra. Részfeladat eredményének mentése. - Ha a kliens eredményt k¨ uld, akkor azt a 3. ábrán látható algoritmus szerint a k¨ ovetkez˝ o m´ odon dolgozzuk fel: + Fogadjuk az u ¨zenetét és ellen˝orizz¨ uk, hogy a beérkez˝o eredmény nem szerepel-e m´ ar a teljes´ıtett részfeladatok listájában (job status); amennyiben nem szerepel, u ´gy elmentj¨ uk és befejezettnek tekintj¨ uk. + A mentés sor´ an a kliens által k¨ uldött u ¨zenet eredeti formában ker¨ ul hozz´ af˝ uzésre a napló fájlhoz (LOG FILE ). A napló fájlban csv form´ atumban ker¨ ulnek rögz´ıtésre az adatok. A fájl pontos formátumát a 4.3. részben ismertetj¨ uk. 14


4.2.

Feladatokat kioszt´ o algoritmus (DJ)

Az el˝ oz˝ o részben ismertetett kiszolgáló program feladatokat kiosztó részét ´ırjuk le ebben a részben, a feladatok kiosztására koncentrálva. Ebb˝ol kifoly´ olag a h´ al´ ozati kommunikációval kapcsolatos részeket a most következ˝o pszeudok´ od nem tartalmazza. A program teljes forráskódja elérhet˝o a http://people.inf.elte.hu/lulsaai/Holzhacker/ oldalon. Bemenet. n: a gr´ af cs´ ucsainak száma; N : a részfeladatok sz´ ama; M : a részfeladatok paramétereit tároló mátrix. Kimenet. Zn : Az n cs´ ucs´ u nullmentes grafikus sorozatok száma. Munkav´ altoz´ ok. S: a részfeladatok státuszát tároló vektor; f j: az elkész¨ ult részfeladatok száma; aj: a legut´ obb kiosztott részfeladat száma; ji: bej¨ ov˝ o részfeladat eredményének indexe; c: kliens azonos´ıt´ o (a h´ al´ ozati kommunikációnál ker¨ ul alkalmazásra); msg: a klienst˝ ol bej¨ ov˝ o u ¨zeneteket tárolja (szintén a hálózati kommunikációnál fontos). Distributing-Jobs(n, N, M ) 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22

S0 = true B 01–05. sor: részfeladatok státuszát tároló vektor beáll´ıtása SN +1 = true for j = 1 to N + 1 Sj = false end while f j < N B 06. sor: am´ıg el nem kész¨ ul minden részfeladat accept(c) B 07. sor: csatlakozó kliens fogadása recv(c, msg) B 08. sor: u ¨zenet fogadása a klienst˝ol if msg == 0 B 09. sor: a kliens u ´j feladatot kér aj = aj + 1 B 10. sor: az aktuális feladat indexét növelj¨ uk for i = Maj−1,0 to n B 11–13. sor: friss´ıtj¨ uk a kezd˝osorozatot Fi = n + Maj−1,1 end while Saj == true or aj > N B 14–22. sor: u ´j feladat keresése aj = aj + 1 if aj > N B 16. sor: t´ ullépt¨ unk a maximális indexen aj = 1 B 17. sor:visszalép¨ unk az els˝ohöz end for i = Maj−1,0 to n B 19–21. sor: kezd˝osorozat friss´ıtése Fi = n + Maj−1,1 end end 15

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus 23 if aj < N B 23–29. sor: feladat kilépési feltételeinek beáll´ıtása 24 a = Maj,0 25 b = n + Maj,1 26 else 27 a=1 28 b=1 29 end 30 send(c, F, a, b) B 30. sor: részfeladat elk¨ uldése a kliensnek 31 else 32 recv(c, ji, Finit , Flast , zn,m , time) B 32. sor: eredmények fogadása 33 if Sji == false B 33. sor: ha a feladat eddig nem volt kész 34 Sj = true B 34. sor: készre áll´ıtjuk 35 fj = fj + 1 B 35. sor: kész feladatok számát növelj¨ uk 36 Zn = Zn + zn,m B 36. sor: Zn részeredmény szám´ıtása 37 end 38 end 39 close(c) B 39. sor: hálózati kapcsolat bontása 40 end 41 return Zn B 41. sor: eredmények visszaadása

4.3.

Kliens program

A kliens program elkész´ıtésekor a f˝o cél a lehet˝o legnagyobb egyszer˝ uség elérése volt. Olyan programot akartunk kész´ıteni, amely nem igényel semmiféle felhasználói beavatkoz´ ast, be´ all´ıt´ ast vagy akármi mást az elind´ıtásán k´ıv¨ ul. Ez azért fontos, mert a sz´ am´ıt´ asokat a lehet˝ o legt¨ obb szám´ıtógép között szeretnénk szétosztani, tekintettel az óri´ asi fut´ asi id˝ okre. Fontos volt az is, hogy ha egy komolyabb szám´ıtás befejez˝odik, akkor se kelljen minden egyes gépen u ´jra és u ´jra elind´ıtani a programot, hanem az a lehet˝o legkisebb er˝oforr´ as igénnyel maradjon a háttérben és várjon mindaddig, am´ıg részt nem vehet egy u ´jabb sz´ am´ıt´ asban. Ez sokat seg´ıtett, amikor az u ´j G érték szám´ıtását végezt¨ uk több mint 200 sz´ am´ıt´ ogép felhasználásával. Ezek között a gépek között voltak olyanok, ahol a processzorban négy mag is volt, ´ıgy egyszerre négy klienst kellett volna u ´jraind´ıtani, amikor az egyik G érték kiszám´ıtását követ˝oen áttért¨ unk egy nagyobbra. Jogosan felmer¨ ul a kérdés, hogy miért nem elegend˝o egyetlen kliens futtatása több sz´ alon gépenként. A sz´ am´ıtásokat nem csak laborgépekkel végezt¨ uk, hanem programunkat publikusan elérhet˝ové tett¨ uk az interneten, ´ıgy bárki csatlakozhatott, ezért nem szerett¨ uk volna, hogy valaki, aki egy klienst futtatva a gépén seg´ıthetné munk´ ankat, azért ne haszn´ alja azt, mert az teljesen leterheli a szám´ıtógépét. A kliens program m˝ uk¨ odése a következ˝o: - Miut´ an létrehoztuk a csatlakozáshoz sz¨ ukséges csatlakozót (SOCKET ), megpr´ ob´ alunk csatlakozni a kiszolgáló programhoz. Ha ez nem lehetséges, mert a szerver nem elérhet˝o, akkor wait time ideig várakozunk és egy´ uttal 16

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus feladat sorsz´ ama

els˝ o sorozat utols´ o sorozat

futási id˝o

grafikus sorozatok száma

2. t´ abl´ azat. A kliens által k¨ uldött eredmények szerkezete. megkétszerezz¨ uk a v´ arakozási id˝ot. (A wait time a programban el˝ore definiált érték. Alapértelmezése DEFAULT WAIT TIME.) Ezt addig ismételgetj¨ uk, am´ıg fel nem ép¨ ul a kapcsolat vagy el nem érj¨ uk a MAX WAIT TIME értéket. Ezt k¨ ovet˝ oen m´ ar nem növelj¨ uk tovább a várakozás id˝otartamát. A módszer alap¨ otletét Jacobson 1988-as [16], lass´ u kezdést biztos´ıtó protokollja adta. Megjegyezz¨ uk, hogy a neve ellenére a módszer egyáltalán nem lass´ u, hiszen exponenci´ alis n¨ ovekedést eredményez. - A kapcsolat létrej¨ ottét követ˝oen u ¨zenetet k¨ uld¨ unk a szerver programnak, amellyel egy részfeladatot kér¨ unk t˝ole, majd miután megkaptuk azt, lebontjuk a h´ al´ ozati kapcsolatot és a 4.4. részben ismertetett algoritmus seg´ıtségével el˝ o´ all´ıtjuk és ellen˝ orizz¨ uk a kiosztott részfeladatba tartozó sorozatokat. - A kliens az ellen˝ orzések során csak olyan sorozatokat áll´ıt el˝o és ellen˝oriz, amelyek p´ arosak és nullmentesek. Ez alól egyetlen kivétel lehetséges: páratlan n értékek esetén az utolsó ellen˝orzött sor nem az 1, 1, . . . , 1, hanem a −1, −1, . . . , −1, mivel a sorozatokat generáló algoritmus kettesével lépteti a sorozatok tagjait anélk¨ ul, hogy 0 el˝ofordulna, ´ıgy az utolsó el˝otti ellen˝orzött sorozat a 2, 1, 1, . . . , 1, amely a következ˝o lépésben – mivel nulla nem lehet – −1, −1, . . . , −1-re v´ alt. Ez azonban nem jelent problémát, mert az ellen˝orz˝o algoritmus elutas´ıtja. - A sz´ am´ıt´ asok végeztével a kapott eredményeket elk¨ uldj¨ uk a szervernek, amely azt´ an azokat a 2. t´ abl´ azatban látható formátumban menti. A táblázat u ¨res cell´ ai kés˝ obbi felhaszn´ al´ asra vannak fenntartva. - A kisz´ am´ıtott eredmények elk¨ uldése is hasonló módon történik, mint ahogy a részfeladatot kért¨ uk a szervert˝ol. Azonban most nem próbálkozunk ¨ a végtelenségig. Osszesen MAX RECONNECT TRY alkalmat követ˝oen abbahagyjuk a pr´ ob´ alkozást. Ez azért fontos, mert ha a szerver megkapott minden részeredményt, leáll, de a kliensek tovább dolgoznak. Ezzel az els˝ odleges célunk, hogy ne kelljen a klienseinket minden egyes projekt esetén u ´jra és u ´jra elind´ıtani minden¨ utt, hanem ha a szerver huzamosabb ideig nem érhet˝ o el, akkor dobják el részeredményeiket és folytassák a normális m˝ uk¨ odést, azaz kérjenek u ´j részfeladatot, pontosabban várakozzanak u ´j részfeladatra. Ezzel ismét csak a rendszer használatának egyszer˝ us´ıtését és nagyobb hibat˝ urést akartunk elérni.

17


4.4.

Felsorol´ o Erd˝ os-Gallai algoritmus (EGE)

A 2.5. részben ismertetett lineáris idej˝ u algoritmust felhasználva megadható egy olyan algoritmus, amely lexikografikus sorrendben el˝oáll´ıtja az összes nullmentes, páros sorozatot és ellen˝ orzi azokat. Ez az algoritmus képezi a 4.3. részben ismertetett program alapj´ at, méghozz´ au ´gy, hogy az el˝oz˝o részben ismertetett program részeként párhuzamosan t¨ obb sz´ am´ıt´ ogépen, több példányban fut és számol. Az algoritmus megtal´ ahat´ o a [12] cikk¨ unkben, angol nyelven. Az algoritmust a k¨ onnyebb érthet˝oség érdekében két részre bontottuk: az els˝o ˝ s-Gallai-Check) a sorozat ellen˝orzését elvégz˝o algoritmust, a második rész (Erdo ˝ s-Gallai-Enumerating) az ellen˝orizend˝o sorozatok el˝oáll´ıtását és a pedig (Erdo hozz´ ajuk kapcsol´ od´ o tov´ abbi értékek (F, H, c, D) friss´ıtését végz˝o programot. Bemenet. F = (f1 , . . . , fn ): ellen˝orizend˝o sorozat; H: els˝ o i elem ¨ osszegét tartalmazó értékek; c: ellen˝ orz˝ opontok sz´ ama; D: ellen˝ orz˝ opontok. Munkav´ altoz´ o. J: dinamikusan változó méret˝ u vektor, ami a s´ ulypontokat tárolja. Kimenet. L: logikai érték, ami true, ha a sorozat helyreáll´ıtható, és false, ha a sorozatot nem lehet helyre´ all´ıtani. ˝ s-Gallai-Check(F, H, c, D) Erdo 01 i = 1 02 while i < c and Hi > i(i − 1) 03 p = Di 04 while Jp < n and fJp+1 > p 05 Jp = Jp + 1 06 end 07 while Jp > p and fJp ≤ p 08 Jp = Jp − 1 09 end 10 if Hp > Hn − HJp + p(Jp − 1) 11 L = f alse 12 return L 13 end 14 i=i+1 15 end 16 L = true 17 return L

B 01. sor: i kezd˝oértékének beáll´ıtása B 02–15. sor: sorozat ellen˝orzése B 03. sor: kezdeti s´ ulypont B 04–09. sor: s´ ulypont friss´ıtése

B 10. sor: ellen˝orzés B 12. sor: rossz sorozat

B 17. sor: helyreáll´ıtható sorozat

Bemenet. n: a cs´ ucsok sz´ ama; F : az els˝ o részfeladat esetében a kezd˝osorozat, egyébként az aktuális részfeladatot 18

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus megel˝ oz˝ o feladat utols´ o ellen˝ orzött sorozata; a: az utols´ o sorozat azonos´ıt´ asára használt index; b: az utols´ o sorozat a-adik elemének értéke. Kimenet. zn,m : a Zn m-edik részletösszege (Zn jelöli azoknak a helyreáll´ıtható sorozatoknak a sz´ am´ at, amelyek nem tartalmaznak nullát, azaz nullmentesek ). ˝ s-Gallai-Enumerating(n, F, a, b) Erdo 01 H1 = f1 B 01. sor: H1 beáll´ıtása 02 for i = 2 to n B 02–04. sor: H értékek szám´ıtása 03 Hi = Hi−1 + fi 04 end 05 if fn 6= n − 1 B 05. sor: ha nem a teljes gráf foksorozata 06 if Hn p´ aratlan B 06–12. sor: aktualizálás 07 fn = fn − 3 08 Hn = Hn − 3 09 else 10 fn = fn − 2 11 Hn = Hn − 2 12 end 13 end 14 for i = 1 to n B 14–16. sor: s´ ulypontok el˝okész´ıtése 15 Ji = n − 1 16 end 17 c = 0 B 17. sor: ellen˝orz˝opontok számának beáll´ıtása 18 for i = 1 to n − 2 B 18–23. sor: ellen˝orz˝opontok meghatározása 19 if fi 6= fi+1 and fi 6= fn 20 c=c+1 B 20. sor: ellen˝orz˝opontok számának növelése 21 Dc = i 22 end 23 end ˝ s-Gallai-Check(F, H, c, D) 24 L = Erdo B 24. sor: els˝o sorozat ellen˝orzése 25 zn,m = zn,m + L 26 while fa > b B 26. sor: am´ıg el nem érj¨ uk az utolsó ellen˝orizend˝o sort 27 k=n B 27. sor: munkaváltozó inicializálása 28 if fk == 1 B 28. sor: ha a sorozat 1-re végz˝odik 29 j =n−1 B 29–32. sor: nem 1 tagjainak meghatározása 30 while fj ≤ 1 31 j =j−1 32 end 33 if fj == 2 B 33. sor: ha az 1-et nem tartalmazó rész 2-re végz˝odik 34 fj−1 = fj−1 − 1 B 34. sor: a sorozat friss´ıtése 35 Hj−1 = Hj−1 − 1 B 35. sor: H értékek friss´ıtése 36 if j > 2 B 36–49. sor: ellen˝orz˝opontok friss´ıtése 19

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

if (c ≤ 2 or (c > 2 and Dc−2 6= j − 2)) and (c > 1 and Dc−1 6= j − 2) if c > 1 and Dc−1 > j − 2 Dc+1 = Dc Dc = Dc−1 Dc−1 = j − 2 c=c+1 else Dc+1 = Dc Dc = j − 2 c=c+1 end end end for k = j to n fk = fj−1 B 51. sor: a sorozat végének friss´ıtése Hk = Hk−1 + fk B 52. sor: H értékek friss´ıtése end while c > 1 and Dc > j − 1 B 54–56. sor: ellen˝orz˝opontok c=c−1 end if Hn p´ aratlan B 57. sor: rossz paritás esetén fn = fn−1 − 1 B 58. sor: sorozat friss´ıtése Hn = Hn−1 + fn B 59. sor: H szám´ıtása c=c+1 B 60–61. sor: ellen˝orz˝opontok b˝ov´ıtése Dc = n − 1 end else fj = fj − 1 B 64. sor: sorozat friss´ıtése Hj = Hj − 1 B 63. sor: H friss´ıtése if j > 1 B 66–74. sor: ellen˝orz˝opontok friss´ıtése if (c == 1 and Dc 6= j − 1) or (c > 1 and Dc−1 6= j − 1) if c > 0 and Dc > j − 1 Dc+1 = Dc Dc = j − 1 c=c+1 end end end for k = j + 1 to n fk = fj B 76. sor: sorozat friss´ıtése Hk = Hk−1 + fk B 77. sor: H szám´ıtása end while c > 1 and Dc > j − 1 B 79–81. sor: ellen˝orz˝opontok 20

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 end

c=c−1 end if Hn p´ aratlan fn = fn − 1 Hn = Hn − 1 c=c+1 Dc = n − 1 end

B 82. sor: paritás ellen˝orzése B 83. sor: sorozat friss´ıtése B 84. sor: H szám´ıtása B 85. sor: ellen˝orz˝opontok számának növelése B 86. sor: u ´j ellen˝orz˝opont hozzáadása

end else if fk == 2 fk−1 = fk−1 − 1 B 91. sor: sorozat friss´ıtése Hk−1 = Hk−1 − 1 B 92. sor: H friss´ıtése if (c == 1 and Dc 6= n − 2) B 93–101. sor: ellen˝orz˝opontok or (c > 1 and Dc−1 6= n − 2 and Dc 6= n − 2) if c > 0 and Dc > n − 2 Dc+1 = Dc Dc = n − 2 else c=c+1 Dc = n − 2 end end if fk−1 p´ aratlan B 102. sor: paritás ellen˝orzése fk = fk−1 B 103. sor: sorozat friss´ıtése if c > 0 and Dc == n − 1 c=c−1 B 105. sor: ellen˝orz˝opontok end else fk = fk−1 − 1 B 108. sor: sorozat friss´ıtése end Hk = Hk−1 + fk B 110. sor: H szám´ıtása else fk = fk − 2 B 112. sor: sorozat friss´ıtése Hk = Hk − 2 B 113. sor: H szám´ıtása if c < 1 or Dc 6= n − 1 B 114–117. sor: ellen˝orz˝opontok c=c+1 Dc = n − 1 end end end ˝ s-Gallai-Check(F, H, c, D) B 120. sor: ellen˝orzés zn,m = zn,m + Erdo

Ez az algoritmus lehet˝ ové teszi, hogy egyszerre párhuzamosan több géppel 21

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus végezz¨ uk a Z értékek kisz´ am´ıtását, u ´gy, hogy a kezd˝osorozattól az utolsó sorozatig minden sorozatot tesztel¨ unk. Az utolsó sorozatot – a kezd˝o sorozattal ellentétben – nem adjuk meg bemenetként, csupán az azonos´ıtásához használt két értéket: a, b. Ezekkel az értékekkel a k¨ ovetkez˝o módon azonos´ıtható a sorozat: mivel a sorozatokat lexikografikus sorrendben ´ all´ıtjuk el˝o, a sorozat egyetlen elemének ellen˝orzésével (fa ) eldönthet˝ o, hogy elért¨ uk-e m´ ar az utolsó ellen˝orizend˝o sorozatot, azaz teljes¨ ul-e, hogy fa < b. Ha igen, akkor a kiosztott részfeladatot elvégzettnek tekintj¨ uk.

5.

A feladat r´ eszekre bont´ asa

A programok m˝ uk¨ odését korábban már ismertett¨ uk. Most le´ırjuk azt is, hogy a problém´ at milyen technik´ ak seg´ıtségével osztottuk fel a szám´ıtógépek között. Els˝ oként le´ırjuk a legegyszer˝ ubb naiv megközel´ıtést, amely kisebb n értékek esetén még megfelel˝ o, majd ´ attér¨ unk arra, hogy nagyobb n-eknél milyen módszerekkel prób´ altuk kiegyens´ ulyozni az egyes szám´ıtógépek terhelését.

5.1.

Naiv megk¨ ozel´ıt´ es

Legels˝ o megk¨ ozel´ıtés¨ unk szerint a problémát kisebb n értékek esetén tapasztalt futási id˝ ok alapj´ an igyekezt¨ unk azonos méret˝ u darabokra osztani. Ez G24 esetén még elfogadhat´ o eltéréseket eredményezett, de sajnos nagyobb n-ekre már olyan mérték˝ u lett volna az eltérés, ami rontotta volna a párhuzamos´ıtás hatékonyságát. Ezt a megk¨ ozel´ıtést felhasználva a problémát összesen 23 részproblémára (szelet, job) bontottuk. A fut´ asi id˝ okre vonatkozó adataink közlését˝ol eltekint¨ unk, tekintve, hogy a részfeladatok t¨ obb, egymástól eltér˝o hardverrel felszerelt szám´ıtógépen futottak.

5.2.

Feloszt´ as kor´ abbi n ´ ert´ ekekre alapozva

Az el˝ oz˝ o megk¨ ozel´ıtés legnagyobb hiányossága a rendszertelenség volt, hiszen se az összesen megvizsg´ alt sorozatok számát, sem az elfogadott sorozatokat nem vette szám´ıt´ asba. Az elfogadott sorozatok számát fontos tényez˝oként kell kezelni, hiszen ezekben az esetekben a teszt minden egyes ellen˝orz˝opontban lefut, ´ıgy ezek a tesztek veszik igénybe a legt¨ obb id˝ ot. A sorozatok szerinti felosztást a következ˝o módon generáltuk. A korábban sorozatok gener´ al´ as´ ara felhasznált programunkat u ´gy alak´ıtottuk át, hogy a tesztet eltávol´ıtottuk, csup´ an azt figyelt¨ uk, hogy hány sorozaton vagyunk t´ ul. Mivel az összes és a p´ aros sorozatok számát ismert¨ uk, ´ıgy könnyedén meghatározható volt, hogy mikor vagyunk két lehetséges részfeladat határán. A kapott sorozatot teljes egészében t´ arolni azonban nem lett volna célszer˝ u, hiszen az rendk´ıv¨ ul nagy mértékben lass´ıtan´ a a sz´ amolást, ha minden egyes sorozat ellen˝orzését követ˝oen ellen˝ orizn¨ unk kellene az éppen aktuális sorozat minden elemét, hogy nem ért¨ uk-e el az utols´ o ellen˝ orizend˝ o sort. A kapott sorozatokról tehát csak annyi információt tároltunk, hogy mi az els˝ o elem indexe, ami eltér az azt megel˝oz˝o sorozattól, és 22

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus hogy mi ez az érték. Ezeket az információkat felhasználva már elegend˝o egyetlen ellen˝ orzést elvégezni, hogy eldönthess¨ uk, végezt¨ unk-e a kapott részfeladattal. Ez a csonkol´ as” azonban u ´jra csak azt eredményezi, hogy a részfeladatok eltér˝o ” méret˝ uek lesznek. Ez a probléma aztán egyre nagyobb eltéréseket okoz, ha az n érték növekszik. Ezzel a technik´ aval egy 435 részfeladatot tartalmazó felosztást kész´ıtett¨ unk és haszn´ altunk fel a Z25 és Z26 értékek szám´ıtásához. Ezekben az esetekben már nem a G értékeket sz´ am´ıtottuk. Ennek oka, hogy a 7. lemma alapján G értékét könnyedén meghat´ arozhatjuk Z ismeretében és ´ıgy a sz¨ ukséges számolási id˝o a szab´ alyos bemenetekhez tartozó id˝o 14 -ére csökken [13].

5.3.

Feloszt´ as a m˝ uveletsz´ amok alapj´ an

Az el˝ oz˝ o megold´ asunk m´ ar viszonylag jó eloszlást biztos´ıtott a futási id˝ok tekintetében, azonban el˝ ofordul benne 2–3 óriás részfeladat is, amelyek megoldása akár t´ızszer annyi ideig is tartott, mint a többieké. Ezt a jelenséget az alábbi módon prób´ altuk meg kik¨ usz¨ ob¨ olni. A gener´ alt részsorozatokat már nem futási idej¨ uk vagy az ellen˝orzött sorozatok száma alapj´ an osztottuk fel, hanem az ellen˝orzések során elvégzett m˝ uveletek száma adta a sorozatok k¨ ozti hat´ arokat. Ezt u ´gy hajtottuk végre, hogy egy alacsonyabb n értékre kisz´ am´ıtottuk a teljes m˝ uveletigényt, majd ennek ismeretében generáltuk az u ´j részfeladatokat. Nyilv´ an ennek a felosztásnak is velejárója volt, hogy sorozatainkat csonkoltuk” a nagyobb sebesség elérésének érdekében. ” A Z28 értékét ezt a feloszt´ ast felhasználva szám´ıtottuk ki.

5.4.

Feloszt´ as a p´ aros sorozatok sz´ ama alapj´ an

A kor´ abbi megval´ os´ıt´ asok ugyan közel´ıt˝oleg megfelel˝o felosztást eredményeztek, azonban mindegyikben fordultak el˝o – még ha csak kis számban is – mamutok (az átlagos fut´ asi id˝ o t¨ obbsz¨ or¨ osét igényl˝o részfeladatok). Ennek elker¨ uléséhez hasznos a (15) egyenlet. A (15) egyenletb˝ ol kiindulva kiszám´ıtható, hogy hány olyan sorozat létezik, amelyiknek m-edik tagja p. Ezt felhasználva megadható egy mátrix, amely megadja, hogy k¨ ozel´ıt˝ oleg h´ any olyan sorozat van, amely az f1 értékkel kezd˝odik és f2 értékkel folytat´ odik stb. Ezt a t´ abl´ azatot felhasználva a következ˝o módon adható meg a feloszt´ as: - V´ alasszuk meg a maximális részfeladat méretet (eset¨ unkben ez akkora szeleteket jelentett, amelyek egy éjszaka alatt kiszám´ıthatóak). - Induljunk el a m´ atrix alsó sorának els˝o elemét˝ol és kezdj¨ uk a mátrix további sorait kiolvasni és ¨ osszegezni mindaddig, am´ıg az aktuális kapacitás vagy a kiolvasand´ o értékek el nem fogytak. - Ha egy érték t´ ul nagy az adott maximális mérethez viszony´ıtva, akkor lépj¨ unk egy sorral feljebb és kezdj¨ uk el azt a sort kiolvasni addig az oszlopig, ahonnan 23

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus 1 1 1 1 1

1 2 3 4 5

1 3 6 10 15

1 4 10 20 35

3. t´ abl´ azat. A felosztáshoz használt mátrix n = 5 esetén. 2, 3, 3, 4, 4, 4, 4,

2, 2, 3, 2, 3, 4, 4,

2, 2, 3, 2, 3, 3, 4,

2, 2, 3, 2, 3, 3, 4,

2 2 3 2 3 3 4

4. t´ abl´ azat. n = 5-ös felosztás határsorozatai. fellépt¨ unk. - Folytassuk ezt az algoritmust, am´ıg az utolsó sor végére nem ért¨ unk. A kor´ abban ismertetett algoritmus szerint n = 5-re a 3. táblázatból kiolvasható a 4. t´ abl´ azatban l´ athat´ o feloszt´ as. A t´ abl´ azatban l´ athat´ o sorozatok a következ˝o módon értend˝oek: az els˝o szelet az 1, 1, 1, 1, 1 sorozatt´ ol a 2, 2, 2, 1, 1 sorozatig tart, a második pedig a 2, 2, 2, 2, 2 sorozatt´ ol a 3, 2, 2, 1, 1 sorozatig és ´ıgy tovább. Ez a m´ odszer ugyan nem garantálja, hogy a részfeladatok hossza pontosan ugyanakkora legyen, azonban megsz¨ unteti a korábbiakban tapasztalt mamut” ” hat´ ast. Ezt a m´ odszert haszn´ altuk fel Z29 kiszám´ıtásakor. A teljes szám´ıtást összesen több mint 15.000 részfeladatra felosztva végezt¨ uk. A teljes feloszt´ as gener´ al´ asának els˝o lépése a 3. táblázathoz hasonló mátrix el˝oáll´ıt´ asa a megfelel˝ o n értékhez. A mátrix feltöltését végzi el az alábbi program. Bemenet. n: a cs´ ucsok sz´ ama (n ≥ 4); M axSize: a maxim´ alis megengedett szeletméret” (nullmentes páros sorozatok ” maxim´ alis sz´ ama a szeletben). Kimenet. A képerny˝ ore ´ırjuk a szeleteket határoló sorozatokat. GenMatrix(n, M axSize) 01 for j = n − 1 downto 1 02 M1,j = 1 03 end

B 01–03. sor: a mátrix els˝o sorának kitöltése

24

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus 04 for i = n downto 2 B 04–08. sor: a mátrix feltöltése 05 for j = 1 to n − 1 06 Mi,j = i+j−2 i−1 07 end 08 end 09 GenSequences(M, n, n, 1, n − 1, M axSize, 0) B 09. sor: szelet generálás Miut´ an megvan a m´ atrixunk, már csak ki kell olvasnunk bel˝ole a szeletek hat´ arsorozatait (a 4. t´ abl´ azathoz hasonló alakban) az alábbi algoritmus seg´ıtségével. Bemenet. M : a feloszt´ ashoz tartozó mátrix, amit a GenMatrix algoritmussal kaptunk; n: a cs´ ucsok sz´ ama (n ≥ 1); i, j, J: rekurz´ıv segédparaméterek; M axSize: a maxim´ alis megengedett szeletméret (nullmentes páros sorozatok maxim´ alis sz´ ama a szeletben). Kimenet. A szeleteket hat´ aroló sorozatok (rekurz´ıv). GenSequences(M, n, i, j, jm , M axSize, J) 01 C = 0 B 01. sor: a szelet méretének inicializálása 02 while j < jm + 1 03 if C + Mi,j ≤ M axSize B 03. sor: ha b˝ov´ıthet˝o a szelet 04 C = C + Mi,j B 04. sor: b˝ov´ıtés 05 if j ≤ jm B 05–07. sor: tovább lép¨ unk a mátrixban 06 j =j+1 07 end 08 else B 08. sor: nem b˝ov´ıthet˝o a szelet 09 if C 6= 0 B 09. sor: a szelet nem u ¨res 10 for k = 2 to size(J, 2) B 10–16. sor: ki´ırás 11 print(Jk ) 12 end 13 for k = 1 to n − size(J, 2) + 1 14 print(j − 1) 15 end 16 print newline B 16. sor: sortörés 17 C=0 18 end 19 if Mi,j > M axSize and j ≤ jm B 19. sor: felbonthatóság ellen˝orzése 20 GenSequences(M, n, i − 1, 1, j, M axSize, [J, j]) 21 j =j+1 22 end 23 end 24 end 25 if C 6= 0 B 25. sor: az utolsó szelet nem u ¨res 25

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus 26 for k = 2 to size(J, 2) 27 print(Jk ) 28 end 29 for k = 1 to n − size(J, 2) + 1 30 print(J(size(J, 2))) 31 end 32 print newline 33 end

6.

B 26–32. sor: utolsó szelet ki´ırása

Eredm´ enyek

A kor´ abban ismertetett Holzhacker program seg´ıtségével b˝ov´ıtett¨ uk a The OnLine Encyclopedia of Integer Sequences [24] adatbázist, amely G23 -ig tartalmazta a foksorozatok sz´ am´ at. Programunk seg´ıtségével megadtuk a hiányzó értékeket egészen G29 -ig. Ezek az értékek megtalálhatóak a 5. táblázatban (az u ´j értékek félkövérek). Sz´ am´ıt´ asaink sor´ an igénybe vett¨ unk laborgépeket (Komputeralgebra labor, Nyelvi labor, Adatb´ azis labor, Lovarda) valamint magánszemélyek seg´ıtségét is. A szám´ıt´ ogépek sz´ am´ıt´ asi teljes´ıtményét összegezve azt mondhatjuk, hogy szám´ıtási kapacit´ asunk elméleti maximuma elérte a 6 TFLOPS sebességet. Részletesebb adatok tal´ alhat´ oak a 6. t´ abl´ azatban. A táblázat helyenként hiányos, mivel a gyártók honlapjain sajnos nem minden processzor t´ıpus esetén érhet˝oek el a táblázatban szerepl˝ o teljes´ıtmény adatok. A sz´ am´ıt´ asok sor´ an létrej¨ ott naplófájlok a forráskódokkal egy¨ utt megtalálhatóak a honlapomon (http://people.inf.elte.hu/lulsaai/Holzhacker). Az ´ altalunk kisz´ am´ıtott Gn értékek naplói köz¨ ul a legrövidebbet tartalmazza a 7. tábl´ azat r¨ ovid´ıtett form´ aban, azaz nem tartalmazza a szeletek kezd˝o és befejez˝o sorozatait, csak a sorsz´ amot, futási id˝ot és az elfogadott sorozatok számát. Itt megjegyezz¨ uk, hogy ebben a szám´ıtásban még nem vettek részt a laborok gépei. A k¨ ul¨ onb¨ oz˝ o Zn értékek részfeladatainak futási id˝ot összegezve megkaphatjuk, hogy a teljes sz´ am´ıt´ as egy géppel mennyi id˝ot vette volna igénybe. Ezeket az adatokat tartalmazza a 8. t´ abl´ azat.

7.

¨ Osszefoglal´ as

A dolgozat tém´ aja gr´ afok foksorozatainak gyors tesztelése. A klasszikus módszerek ismertetése mellett megadtunk egy u ´j, lineáris futási idej˝ u módszert, bemutattunk egy foksorozatokat leszámoló párhuzamos programot és az azzal elért eredményeinket. Az els˝ o részben r¨ oviden bemutattuk az alap problémát, annak alkalmazási ter¨ uleteit és a dolgozatban elérni k´ıvánt célokat. A m´ asodik részben ismertett¨ uk az eredeti Erd˝os-Gallai módszert és a Tripathi ´ ris-Erdo ˝ s-Gallaiés Vijay ´ altal megadott gyors´ıtásokat. Ezután le´ırtuk a linea 26


n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 3 29 15

1 4 16 63 247 973 824 033

1 4 17 68 269 052 116 123 205 959 469 345 633

1 5 20 77 300 166 537 672 923 128 049 715 801 303 266 712 300 249

1 6 24 92 352 352 200 058 558 540 803 567 631 264 937 481 363 841 218 474 824 380 770

Rn 1 3 10 35 126 462 716 435 310 378 716 078 300 300 760 195 110 650 900 410 220 860 800 2 550 8 876 31 052 123 056 486 220 1 912 520 7 516

2 8 34 134 526 058 061 602 979 734 172 816

2 10 38 150 583 268 836 461 564 024 358 901 652 635 861 660 644

3 12 46 176 676 600 030 781 273 407 795 340 678 560 917 034 596 961 837 612 219 943

En 1 2 6 19 66 236 868 235 190 252 484 270 612 008 096 315 990 980 260 394 988 288 616 814 516 176 328 260 559 2

2 8 34 132 518 022

Gn 1 2 4 11 31 102 342 1 213 4 361 16 016 59 348 222 117 836 315 3 166 852 12 042 620 45 967 479 176 005 709 675 759 564 2 600 672 458 10 029 832 754 38 753 710 486 149 990 133 774 581 393 603 996 256 710 139 346 770 547 818 956 125 389 919 850 919 443 189 544 232 001 761 434 337 118 015 338

5. t´ abl´ azat. Szab´ alyos, páros és helyreáll´ıtható sorozatok száma.

27

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus Labor / Tulajdonos Adatb´ azis labor Komputeralgebra labor Lovarda Nyelvi labor Ballagi D´ aniel K´ asa Zolt´ an K´ asa Zolt´ an ´ M´ anyoki Ad´ am ´ am M´ anyoki Ad´ ´ am M´ anyoki Ad´ Méreg Bal´ azs

Gép 60 20 110 60 1 1 1 2 1 1 1

Processzor i5-650 E 5300 E 7500 i5-650 E7300 875P i7-2600 E5405 Q6600 X4 920 T4500

Mag 2 2 2 2 2 ? 4 ? 4 4 2

GFLOPS 25.6 20.8 23.4 25.6 21.2 ? 70.3 ? 38.4 52.9 ?

6. t´ abl´ azat. A sz´ am´ıt´ asaink során felhasznált szám´ıtógépek adatai. Sorsz´ am 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Futási id˝o 886m38.590s 936m21.676s 505m47.829s 547m59.627s 511m25.114s 508m55.076s 542m10.017s 488m0.130s 643m54.655s 1518m44.534s 776m9.764s 585m91.666s 429m36.930s 429m26.178s 396m12.822s 375m33.124s 462m35.083s 471m41s 697m17.387s 565m3.692s 393m20.431s 549m59.291s 678m19,125s

10 28 41 69 58 102 118 151 78 147 70 99 49 58 118 80 115 56 207 133 151 158 148

029 723 658 578 589 412 800 600 547 524 426 949 782 135 914 117 347 764 784 860 426 301 434

G24,m 832 755 877 732 148 450 274 838 929 879 209 899 436 447 893 997 565 915 314 179 738 550 294 037 771 161 313 980 450 088 065 415 245 437 861 564 332 910 267 289 892 693 007 132 414 999

7. t´ abl´ azat. A G24 szám´ıtásának rövid´ıtett naplója. 28

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus n 25 26 27 28 29

Fut´ asi id˝o (nap) 26 70 316 1130 6733

Részfeladatok száma 435 435 435 2 001 15 119

8. t´ abl´ azat. A sz´ am´ıt´ asok sor´ an mért futási id˝ok összege és a részfeladatok száma. ´ algoritmust, amit a kés˝obbiekben a gráfsorozatokat leszámláló programban ugro felhaszn´ altunk. A harmadik részben ismertett¨ unk néhány eredményt az összes n-szabályos és npáros sorozat sz´ am´ aval és azok arányával kapcsolatban. A dolgozat negyedik részében adtuk meg a Holzhacker program le´ırását, kitérve a program f˝ obb saj´ atoss´ agaira, valamint a megvalós´ıtását meghatározó f˝obb irányelvekre és célokra. Ebben a részben ismertett¨ uk a szerver és a kliens program lesz´ amol´ assal kapcsolatos részeinek pszeudokódjait is, azaz a Distribute-Jobs és ˝ s-Galla-Enumerating algoritmusokat. az Erdo Az ¨ ot¨ odik rész tartalmazta azokat a módszereket és algoritmusokat, amelyeket felhaszn´ altunk az u ´j Z és G értékek kiszám´ıtásakor. A dolgozat hatodik részében ismertett¨ uk eredményeinket (az u ´jonnan megadott Zn és Gn értékeket, az u ´j algoritmus és a régi algoritmus futási idejének összehasonl´ıt´ as´ at), valamint néhány technikai részletet a szám´ıtások elvégzésének kör¨ ulményeir˝ ol (napl´ of´ ajlok és elérhet˝oség¨ uk, felhasznált szám´ıtógépek t´ıpusa, rendelkezésre ´ all´ o maxim´ alis szám´ıtási teljes´ıtmény). Az ebben a részben ismertetett, általunk kisz´ amolt u ´j Gn értékek 2011. november 15. óta megtalálhatóak az OEIS adatb´ azis A004251-es sorozat´ aban [24]. A dolgozatban le´ırt eredményeket a [12, 13, 14] cikkekben publikáltuk. Az eddig elért eredményeket szeretnénk a kés˝obbiekben felhasználni focisorozatok [7, 22] és p´ aros gr´ afok sorozatainak ellen˝orzése során, mivel ezeknek a problémáknak része az egyszer˝ u gr´ afok foksorozatainak ellen˝orzése.

Hivatkoz´ asok [1] Ascher, M.: Mu torere: an analysis of a Maori game. Math. Mag. 60, (1987) 90–100. ⇒ 8 [2] Burns, J. M.: The Number of Degree Sequences of Graphs. PhD Dissertation, MIT, 2007. ⇒ 10 [3] Choudum, S. A.: A simple proof of the Erd˝ os-Gallai theorem on graph sequences. Bull. Austral. Math. Soc. 33, (1986) 67–70. ⇒ 5 29

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus [4] Chungphaisan, V.: Conditions for sequences to be r-graphical. Discrete Math. 7, (1974) 31–39. ⇒ 3, 4 ˝ s, P., Gallai, T.: Gr´ [5] Erdo afok el˝ o´ırt fok´ u pontokkal. Mat. Lapok 11, (1960) 264–274. ⇒ 3, 5 ˝ s, P. L., Miklo ´ s, I., Toroczkai, Z.: A simple Havel-Hakimi type [6] Erdo algorithm to realize graphical degree sequences of directed graphs. Elec. J. Comb. 17, (2010) R66. ⇒ 3, 4 [7] Frank, A.: Connections in Combinatorial Optimization. Calderon Oxford Univ. Press, Oxford, (2011) 640 p. ⇒ 29 [8] Hakimi, S. L.: On the realizability of a set of integers as degrees of the vertices of a simple graph. J. SIAM Appl. Math. 10, (1962) 496–506. ⇒ 3, 4 ˘ [9] Havel, V.: A remark on the existence of finite graphs (Czech). Casopis P˘est. Mat. 80, (1955) 477–480. ⇒ 3, 4 ´ nyi, A.: Reconstruction of complete interval tournaments. Acta Univ. [10] Iva Sapientiae, Inform. 1, (2009) 71–88. ⇒ 3, 4 ´ nyi, A.: Reconstruction of complete interval tournaments. II. Acta Univ. [11] Iva Sapientiae, Math. 2, (2010) 47–71. ⇒ 3, 4 ´ nyi, A., Lucz, L., Pirzada, S.: Parallel Erd˝ [12] Iva os-Gallai algorithm. CEJOR Cent. Eur. J. Oper. Res., (2011) beny´ ujtva. ⇒ 18, 29 ´ nyi, A., Lucz, L., Mo ´ ri, F. T., So ´ te ´r, P.: On the Erd˝ [13] Iva os-Gallai and Havel-Hakimi algorithms. Acta Univ. Sapientiae, Inform. 3(2), (2011) 230–268. Elérhet˝ o: http://www.acta.sapientia.ro/acta-info/ ⇒ 3, 4, 8, 10, 11, 23, 29 ´ nyi, A., Lucz, L., Mo ´ ri, F. T.: Line´ [14] Iva aris Erd˝ os-Gallai teszt. Alk. Mat. Lapok., (2011) beny´ ujtva. ⇒ 29 ´ nyi, A., Pirzada, S.: Comparison based ranking. In (ed. A. Iványi): [15] Iva Algorithms of Informatics, 3, AnTonCom, Budapest, 2011, 1209–1256. ⇒ 3 [16] Jacobson, V.: Congestion avoidance and control. In: Proc. of SIGCOMM ’88, Stanford, CA (1988), ACM, 314–329. ⇒ 17 ´ rai, A. (szerk.): Bevezetés a matematik´ [17] Ja aba. ELTE Eötvös Kiadó, Budapest, (2005). ⇒ 7 [18] Kleitman, D. J., Wang, D. L.: Algorithms for constructing graphs and digraphs with given valences and factors. Disc. Mat., 6, (1973) 79–88. ⇒ 3, 4 [19] LaMar, M. D.: Algorithms for realizing degree sequences of directed graphs. arXiv (2009). Elérhet˝ o: http://arxiv.org/abs/0906.0343 ⇒ 3, 4 30

Lucz Lor´ and - P´ arhuzamos Erd˝ os-Gallai algoritmus [20] Landau, H. G.: On dominance relations and the structure of animal societies. III. The condition for a score sequence. Bull. Math. Biophys. 15, (1953) 143–148. ⇒3 ´ te ´r, P.: Foksorozatokat ellen˝ [21] Lucz, L., So orz˝ o algoritmusok. TDK dolgozat, ELTE IK, Budapest, 2011. ⇒ 3, 4, 5, 6, 7, 11 ´ nyi, A.: Testing and enumeration of football sequences. In (ed. [22] Lucz, L., Iva Z. Cs¨ ornyei): Abstracts of MaCS 2012, Siófok, Február 9–12, 2012. ⇒ 29 ¨ [23] Ozkan, S.: Generalization of the Erd˝ os-Gallai inequality. Ars Combin. 98 (2011) 295–302. ⇒ 3, 4 [24] Sloane, N. J. A.: Number of graphical partitions. In (ed. N. J. A. Sloane): The On-line Encyclopedia of Integer Sequences (2011). Elérhet˝o: http://oeis.org/ ⇒ 3, 7, 26, 29 [25] Sloane, N. J. A., Plouffe, S.: The Encyclopedia of Integer Sequences., Academic Press, 1995. ⇒ 7, 8 [26] Stanley, R. P.: Enumerative Combinatorics, Cambridge University Press, Cambridge, 1997. ⇒ 7 [27] Tripathi, A., Vijay, S.: A note on a theorem of Erd˝ os & Gallai. Disc. Math. 265, (2003) 417–420. ⇒ 3, 5, 6 [28] Tripathi, A., Venugopalan, S., West, D. B.: A short constructive proof of the Erd˝ os-Gallai characterization of graphic lists. Disc. Math. 310, (2010) 833–834. ⇒ 5

31

Párhuzamos Erdős-Gallai algoritmus. TDK dolgozat

Recommend Documents