ALGORITMUSOK OPTIMÁLIS MEGVALÓSÍTÁSA PÁRHUZAMOS KÖRNYEZETBEN

Írta: Kurdi Zsombor Lektorálta: oktatói munkaközösség

ALGORITMUSOK OPTIMÁLIS MEGVALÓSÍTÁSA PÁRHUZAMOS KÖRNYEZETBEN PÁRHUZAMOS SZÁMÍTÁSTECHNIKA MODUL

PROAKTÍV INFORMATIKAI MODULFEJLESZTÉS 1

COPYRIGHT: 2011-2016, Kurdi Zsombor, Óbudai Egyetem, Neumann János Informatikai Kar LEKTORÁLTA: oktatói munkaközösség Creative Commons NonCommercial-NoDerivs 3.0 (CC BY-NC-ND 3.0) A szerző nevének feltüntetése mellett nem kereskedelmi céllal szabadon másolható, terjeszthető, megjelentethető és előadható, de nem módosítható. TÁMOGATÁS: Készült a TÁMOP-4.1.2-08/2/A/KMR-2009-0053 számú, “Proaktív informatikai modulfejlesztés (PRIM1): IT Szolgáltatásmenedzsment modul és Többszálas processzorok és programozásuk modul” című pályázat keretében

KÉSZÜLT: a Typotex Kiadó gondozásában FELELŐS VEZETŐ: Votisky Zsuzsa ISBN 978-963-279-559-1

2

KULCSSZAVAK: algoritmus, párhuzamosítás, kölcsönös kizárás, programozási tételek, rendezések, keresések, elosztott adatszerkezetek, Gauss elimináció, Fourier transzformáció, gráfalgoritmusok, tömörítés, titkosítás, mintaillesztés, geometriai algoritmusok

ÖSSZEFOGLALÓ: A tananyag leggyakoribb algoritmusok párhuzamosításának kérdésével foglalkozik. Az algoritmusok elemzésével és párhuzamosításával foglalkozó elméleti bevezető után a gyakorlatokra tevődik át a hangsúly. Ez az egyszerűbb algoritmusokkal, a programozási tételekkel – mint például a minimum/maximum keresés, számlálás, összegzés – kezdődik, majd a rendezésiek, keresések, gráfalgoritmusok után olyan bonyolultabb algoritmusok párhuzamosításáról is szó esik, mint a titkosítási, tömörítési és a geometriai problémákat megoldó algoritmusok. Minden esetben az algoritmus bemutatás után foglalkozunk a párhuzamosítás lehetőségével, valamint a soros és párhuzamos implementációval C# nyelven. Mindezek mellett a tananyagban megtalálható egy rövid fejezet, amely a fontosabb adatszerkezetek elosztott használatával foglalkozik, amely azért fontos, mert a párhuzamos algoritmusok gyakran használhatnak ilyen adatszerkezeteket, amelyeket ilyenkor speciálisan kell kezelnünk (például a kölcsönös kizárás megvalósításával).

3

Tartalomjegyzék • • • • • • • • • • • •

Bevezető Programozási tételek Keresések Mintaillesztések Rendezések (1) Rendezések (2) Mátrixműveletek Gráfalgoritmusok (1) Gráfalgoritmusok (2) Geometria Tömörítés Titkosítás

© Kurdi Zsombor, ÓE NIK

4

www.tankonyvtar.hu

1. óra Bevezető Algoritmus fogalma, tulajdonságai Algoritmusok elemzése Aszimptotikus jelölések Példák

Algoritmusok párhuzamosítása Módszerek Példák

Programok

Irodalomjegyzék


5

www.tankonyvtar.hu

Hallgatói tájékoztató A jelen bemutatóban található adatok, tudnivalók és információk a számonkérendő anyag vázlatát képezik. Ismeretük szükséges, de nem elégséges feltétele a sikeres zárthelyinek, illetve vizsgának. Sikeres zárthelyihez, illetve vizsgához a jelen bemutató tartalmán felül a kötelező irodalomként megjelölt anyag, a gyakorlatokon szóban, illetve a táblán átadott tudnivalók ismerete, valamint a gyakorlatokon megoldott példák és az otthoni feldolgozás céljából kiadott feladatok önálló megoldásának képessége is szükséges.


6

www.tankonyvtar.hu

Algoritmus fogalma, tulajdonságai


7

www.tankonyvtar.hu

Algoritmus • Algoritmuson olyan módszert (utasítások sorozatát) értünk, amely valamely problémára megoldást ad. • A fogalom a matematikában jelent meg, de az informatika népszerűvé válása ültette át a köznyelvbe. • Algoritmust lehet adni – – – – –

egy bútordarab összeszerelésére, egy étel elkészítésére, otthonunkból az iskolába való eljutásra, két szám legnagyobb közös osztójának kiszámítására. …


8

www.tankonyvtar.hu

Algoritmus definíciója • Turing: egy probléma megoldására adott utasítássorozat akkor tekinthető algoritmusnak, ha van egy vele ekvivalens Turing-gép, amely minden megoldható bemenetre megáll. • Alternatív definíciók – – – – –

Regisztergép Lambda-kalkulus Rekurzív függvények Chomsky-nyelvtanok Markov-algoritmusok

• Mindegyik definíció ekvivalens a Turing-féle meghatározással.


9

www.tankonyvtar.hu

Algoritmusok tulajdonságai • Alaptulajdonságok – Egy algoritmus egyértelműen leírható véges szöveggel (statikus végesség). – Egy algoritmus minden lépése ténylegesen kivitelezhető. – Egy algoritmus minden időpontban véges sok tárat használ (dinamikus végesség). – Egy algoritmus véges sok lépésből áll (termináltság).

• Ezek alapján az algoritmus fogalma – Egy algoritmus ugyanarra a bemenetre mindig ugyanazt az eredményt adja (determináltság). – Minden időpontban egyértelműen adott a következő lépés (determinisztikusság).


10

www.tankonyvtar.hu

Algoritmusok elemzése


11

www.tankonyvtar.hu

Algoritmusok elemzése • Befejeződés – Kiszámíthatóságelméleti feladat.

• Tár- és időigény – – – –

Bonyolultságelméleti feladat. Természetes számokon értelmezett függvények segítségével írható le. Aszimptotikus korlátokkal adható meg. A továbbiakban csak ezzel foglalkozunk.


12

www.tankonyvtar.hu

Algoritmusok elemzése • Legyen két függvény f, g: N → Z – Ha ∃c > 0 és n0, hogy ha n > n0, akkor 0 ≤ f(n) ≤ c⋅g(n), akkor a g függvényt f aszimptotikusan ÉLES felső korlátjának nevezzük (Jele: f(n) = O(g(n) vagy f = O(g)) – Ha ∃c > 0 és n0, hogy ha n > n0, akkor 0 ≤ f(n) < c⋅g(n), akkor a g függvényt f aszimptotikusan NEM ÉLES felső korlátjának nevezzük (Jele: f(n) = o(g(n) vagy f = o(g)) – Ha ∃c > 0 és n0, hogy ha n > n0, akkor 0 ≤ c⋅g(n) ≤ f(n), akkor a g függvényt f aszimptotikusan ÉLES alsó korlátjának nevezzük (Jele: f(n) = Ω(g(n) vagy f = Ω(g)) – Ha ∃c > 0 és n0, hogy ha n > n0, akkor 0 ≤ c⋅g(n) < f(n), akkor a g függvényt f aszimptotikusan NEM ÉLES alsó korlátjának nevezzük (Jele: f(n) = ω(g(n) vagy f = ω(g)) – Ha ∃c1,c2 > 0 és n0, hogy ha n > n0, akkor 0 ≤ c1⋅g(n) ≤ f(n) ≤ c2⋅g(n), akkor a g függvényt f aszimptotikusan éles korlátjának nevezzük (Jele: f(n) = Θ(g(n) vagy f = Θ(g)) © Kurdi Zsombor, ÓE NIK

13

www.tankonyvtar.hu

Algoritmusok elemzése


14

www.tankonyvtar.hu

Algoritmusok elemzése • A definíciók alapján triviális állítás – ∀f,g : N → Z függvényre f(n) = Θ(g(n)) ↔ f(n) = O(g(n)) és f(n) = Ω(g(n))

Azaz egy függvény pontosan akkor aszimptotikusan éles korlátja egy másik függvénynek, ha aszimptotikusan éles alsó és aszimptotikusan éles felső korlátja a függvénynek.


15

www.tankonyvtar.hu

Algoritmusok elemzése • Az O, o, Ω, ω és Θ jelölések mint bináris relációk tulajdonságai O, o, Ω, ω és Θ tranzitívak (pl.: f = ω(g) ∧ g = ω(h) → f = ω(h)) O, Ω és Θ reflexívek (pl. f = Θ(f)) Θ szimmetrikus (f = Θ(g) ↔ g = Θ(f)) O és Ω, valamint o és ω „felcserélten szimmetrikusak” (pl.: f = O(g) ↔ g = Ω(f)) – Rögzített h függvény mellett O(h), o(h), Ω(h), ω(h) és Θ(h) halmazok zártak az összeadásra és a pozitív számmal való szorzásra (pl.: f = ω(h) ∧ g = ω(h) → f + g = ω(h)) és (pl.: f = ω(h) ∧ c > 0 → c⋅f = ω(h)) – Összegben a nagyobb függvény határozza meg az aszimptotikát: f + g = Θ(max(f, g)) (A max ebben az esetben az aszimptotikusan nagyobb függvényt jelenti.)

– – – –


16

www.tankonyvtar.hu

Algoritmusok elemzése • Az O, o, Ω, ω és Θ jelölések mint bináris relációk tulajdonságai (folytatás) – Polinom esetén a legnagyobb fokú tag a meghatározó: aknk + ak-1nk-1 + … + a1n + a0 = Θ(n k) – Bármely két (1-nél nagyobb alapszámú) logaritmikus függvény aszimptotikusan egyenértékű: logan = Θ(logbn). Ezért az alap feltüntetése nem szükséges logan = Θ(logn) – Hatványfüggvények esetén különböző kitevők különböző függvényosztályokat jelölnek ki: a ≥ 0 és ε > 0 esetén na = O(na+ε) és na ≠ Θ(na+ε), tehát na = o(na+ε)


17

www.tankonyvtar.hu

Példa (Összegzés) • Bemenet: n db érték (elemek). • Kimenet: az input értékek összege. • Algoritmus: s=0 for i = 1 to n s = s + elemek[i]

• Lépésszám – – – –

Legjobb eset: n Legrosszabb eset: n Átlagos eset: n Függvényosztály: Θ(n)


18

www.tankonyvtar.hu

Példa (Számlálás) • Bemenet: n db érték (elemek). • Kimenet: az input értékek közül adott tulajdonságú elemek darabszáma. • Algoritmus: d=0 for i = 1 to n if χ(elemek[i]) d=d+1




19

www.tankonyvtar.hu

Példa (Maximumkeresés) • Bemenet: n db érték (elemek). • Kimenet: az input értékek közül a maximális elem. • Algoritmus: max = elemek[1] for i = 2 to n if elemek[i] > max max = elemek[i]




20

www.tankonyvtar.hu

Párhuzamos algoritmusok • A párhuzamos algoritmusok olyan algoritmusok, amelyek a feladatot több részre osztva, egymással párhuzamosan (több processzoron) egyidejűleg futnak. • Ezeket az algoritmusokat két nagy csoportba sorolhatjuk – Megosztott algoritmusok Az algoritmust alkotó folyamatok közös memóriát használnak, és azon keresztül kommunikálnak egymással. – Elosztott algoritmusok Az algoritmushoz tartozó folyamatok teljesen szeparált tárterületen dolgoznak, majd valamilyen módszerrel összegzik az eredményeket.


21

www.tankonyvtar.hu

Algoritmusok párhuzamosítása


22

www.tankonyvtar.hu

Algoritmusok párhuzamosítása • „Oszd meg és uralkodj” elv segítségével – Az adatok felosztása a processzorok (szálak v. folyamatok) között, majd az eredmények összefésülése Ebben az esetben valamennyi szál elvégzi a teljes algoritmust és az általuk szolgáltatott eredményeket kell valamelyik szálnak összefésülni (ez történhet új algoritmussal vagy a párhuzamosított algoritmus újbóli végrehajtásával). Olyan algoritmusok esetén hatékony megoldás, amelyek valamennyi inputadatot megvizsgálnak a futás során. (pl. összegzés). – A feladatok felosztása a processzorok (szálak v. folyamatok) között Ebben az esetben a szálak az algoritmusnak csak egy részét végzik el és az általuk számolt részeredményt a következő szálnak adják (futószalagszerű rendszer). Az algoritmus végeredményét az utolsó szál szolgáltatja. Olyan algoritmusok esetén hatékony megoldás, amelyek felbonthatók elemi lépések sorozatára, amelyeket az inputadatokon kell elvégezni, hogy megkapjuk az outputot. (Pl. sin számítás.)


23

www.tankonyvtar.hu

Adatmegosztás


24

www.tankonyvtar.hu

Feladatmegosztás


25

www.tankonyvtar.hu

Példa (Összegzés) • Párhuzamosítás adatmegosztással – Osszuk k részre az n értéket. – Összegezzük a részeket párhuzamosan. – Összegezzük az egyes részek eredményeit.


Legjobb eset: n / k + k Legrosszabb eset: n / k + k Átlagos eset: n / k + k Függvényosztály: Θ(n / k + k)


26

www.tankonyvtar.hu

Példa (Számlálás) • Párhuzamosítás adatmegosztással – Osszuk k részre az n értéket. – Végezzük el a számlálást a részeken párhuzamosan. – Összegezzük az egyes részek eredményeit.




27

www.tankonyvtar.hu

Példa (Maximumkeresés) • Párhuzamosítás adatmegosztással – Osszuk k részre az n értéket. – Keressük meg a részek maximumait párhuzamosan. – Keressük meg a maximumot a részeredmények között.




28

www.tankonyvtar.hu

Programok


29

www.tankonyvtar.hu

Példaprogramok • A tananyag további részében szereplő példaprogramok inputadatait a szamok.txt fájl tartalmazza – A fájl első sora a benne található inputadatok darabszámát tartalmazza. – Minden további sor egy-egy inputadatot tartalmaz.


30

www.tankonyvtar.hu

Adatbeolvasás 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private const string inputFile = "szamok.txt"; private static int[] Beolvas() { StreamReader input = new StreamReader(inputFile); int méret = Convert.ToInt32(input.ReadLine()); int[] számok = new int[méret]; for (int i = 0; i < számok.Length; ++i) számok[i] = Convert.ToInt32(input.ReadLine()); input.Close(); }

return számok;


Program.cs 31

www.tankonyvtar.hu

Példaprogramok • Minden példaprogram elején az inputfájl tartalmát beolvassuk egy tömbbe. • Ehhez az input fájl nevét egy konstansban tároljuk. • A beolvasást a Beolvas() nevű művelet végzi. • Az algoritmus futási idejét Stopwatch objektum segítségével mérjük. • A program végén az eredményt és a futási időt megjelenítjük a képernyőn.


32

www.tankonyvtar.hu

Program (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static Stopwatch stopper = new Stopwatch(); static void Main(string[] args) { int[] számok = Beolvas(); stopper.Start(); // algoritmus stopper.Stop(); }

// eredmény és futási idő kiírás


Program.cs 33

www.tankonyvtar.hu

Példa (Összegzés) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// algoritmus int s = 0; for (int i = 0; i < számok.Length; ++i) s += számok[i]; // eredmény és futási idő kiírás Console.WriteLine("A számok összege: {0}", s); Console.WriteLine("Összesen {0} db számot adtam össze.", számok.Length); Console.WriteLine("Futási idő: {0}", stopper.Elapsed);


Program.cs 34

www.tankonyvtar.hu

Példa (Számlálás) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// algoritmus int d = 0; for (int i = 0; i < számok.Length; ++i) if (Feltétel(számok[i]) ++d; // eredmény és futási idő kiírás Console.WriteLine("A feltételt teljesítő elemek darabszáma: {0}", d); Console.WriteLine("Összesen {0} db elemet vizsgáltam.", számok.Length); Console.WriteLine("Futási idő: {0}", stopper.Elapsed); // a Feltétel tetszőleges logikai értékű függvény lehet // most a páros számokat számláljuk private bool Feltétel(int n) { return n % 2 == 0; }


Program.cs 35

www.tankonyvtar.hu

Példa (Maximumkeresés) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// algoritmus int max = számok[0]; for (int i = 1; i < számok.Length; ++i) if (számok[i] > max) max = számok[i]; // eredmény és futási idő kiírás Console.WriteLine("A legnagyobb szám: {0}", max); Console.WriteLine("Összesen {0} db számot vizsgáltam.", számok.Length); Console.WriteLine("Futási idő: {0}", stopper.Elapsed);


Program.cs 36

www.tankonyvtar.hu

Program (Párhuzamos) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private struct SzálParaméter { public int SzálIndex; public int[] Számok; public int StartIndex; public int Hossz; } private static Stopwatch stopper = new Stopwatch(); private static object sync = new object(); private static int[] eredmények = new int[](); private static int lefutottSzálak = 0; static void Main(string[] args) { int[] számok = Beolvas(); stopper.Start(); for (int i = 0; i < szálakSzáma; ++i) { SzálParaméter paraméter; paraméter.SzálIndex = i;


Program.cs 37

www.tankonyvtar.hu


paraméter.SzálIndex = i; paraméter.Számok = számok; paraméter.Hossz = számok.Length / szálakSzáma; paraméter.StartIndex = paraméter.Hossz * i; }

ThreadPool.QueueUserWorkItem(new WaitCallback(Szálfüggvény), paraméter);

while (lefutottSzálak < szálakSzáma) Thread.Sleep(1); // összefésülés stopper.Stop(); }

// eredmény és futási idő kiírás

private static void Szálfüggvény(object obj) { SzálParaméter param = (SzálParaméter)obj; // soros algoritmus


Program.cs 38

www.tankonyvtar.hu


eredmények[param.SzálIndex] = /* az algoritmus eredménye */

}

lock (sync) { ++lefutottSzálak; }


Program.cs 39

www.tankonyvtar.hu

Példa (Összegzés) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// összefésülés int s = 0; for (int i = 0; i < eredmények.Length; ++i) s += eredmények[i]; // eredmény és futási idő kiírás Console.WriteLine("A számok összege: {0}", s); Console.WriteLine("Összesen {0} db számot adtam össze.", számok.Length); Console.WriteLine("Futási idő: {0}", stopper.Elapsed);


Program.cs 40

www.tankonyvtar.hu

Példa (Számlálás) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// összefésülés int d = 0; for (int i = 0; i < eredmények.Length; ++i) d += eredmények[i]; // eredmény és futási idő kiírás Console.WriteLine("A feltételt teljesítő elemek darabszáma: {0}", d); Console.WriteLine("Összesen {0} db elemet vizsgáltam.", számok.Length); Console.WriteLine("Futási idő: {0}", stopper.Elapsed); // a Feltétel tetszőleges logikai értékű függvény lehet // most a páros számokat számláljuk private bool Feltétel(int n) { return n % 2 == 0; }


Program.cs 41

www.tankonyvtar.hu

Példa (Maximumkeresés) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// összefésülés int max = eredmények[0]; for (int i = 1; i < eredmények.Length; ++i) if (eredmények[i] > max) max = eredmények [i]; // eredmény és futási idő kiírás Console.WriteLine("A legnagyobb szám: {0}", max); Console.WriteLine("Összesen {0} db számot vizsgáltam.", számok.Length); Console.WriteLine("Futási idő: {0}", stopper.Elapsed);


Program.cs 42

www.tankonyvtar.hu

Házi feladat Próbálja ki a példaprogramokat! Kíséreljen meg javítani a párhuzamos változatok hatékonyságán! Megjegyzés – Lehetőség szerint a programokat futtassa egy-, illetve többprocesszoros gépeken!


43

www.tankonyvtar.hu

Irodalomjegyzék •

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Új algoritmusok, Scolar Kiadó, 2003.


44

www.tankonyvtar.hu

2. óra Programozási tételek Programozási tételek Összegzés Számlálás Maximumkeresés Másolás Kiválogatás Szétválogatás Metszet Unió Irodalomjegyzék


45

www.tankonyvtar.hu

Programozási tételek


46

www.tankonyvtar.hu

Programozási tételek • Egy adott feladatosztályba tartozó összes feladatra általános megoldást adnak. • Csoportosításuk – Egy sorozathoz egy értéket rendelő feladatok. • Pl.: számítsuk ki n db szám összegét.

– Egy sorozathoz egy sorozatot rendelő feladatok. • Pl.: másoljuk egy sorozat elemeit fordított sorrendben egy másik sorozatba.

– Sorozathoz több sorozatot rendelő feladatok. • Pl.: válogassuk szét egy sorozat páros és páratlan elemeit.

– Több sorozathoz egy sorozatot rendelő feladatok. • Pl.: számítsuk ki két sorozat közös elemeit (metszetét).


47

www.tankonyvtar.hu

Összegzés


48

www.tankonyvtar.hu

Összegzés • Feladat – Számítsuk ki n db szám összegét.

• Sorozathoz értéket rendel. • Lásd: előző óra.


49

www.tankonyvtar.hu

Számlálás


50

www.tankonyvtar.hu

Számlálás • Feladat – Számláljuk meg n db számból hány telesíti F feltételt.

• Sorozathoz értéket rendel. • F feltétel tetszőleges logikai értékű függvény lehet. • Lásd: előző óra.


51

www.tankonyvtar.hu

Maximumkeresés


52

www.tankonyvtar.hu

Maximumkeresés • Feladat – Keressük meg n db szám közül a legnagyobbat.

• Sorozathoz értéket rendel. • A minimumkeresés is hasonlóan végezhető el. • Megkereshető a sorozat első, illetve utolsó maximuma (ha több maximum is van). • Feltétellel bővíthető, hogy a sorozat bizonyos (feltételt teljesítő) elemei közül keressük a maximumot = feltételes maximum keresés. • Lásd: előző óra.


53

www.tankonyvtar.hu

Másolás


54

www.tankonyvtar.hu

Másolás • Feladat – Másoljuk át egy sorozat (s) elemeit egy másik sorozatba (t).

• Sorozathoz sorozatot rendel. • Algoritmus: for i = 1 to n t[i] = s[i]


55

www.tankonyvtar.hu

Másolás • A másolás közben műveletet is végezhetünk az elemeken. – Egyszerű művelet (pl. gyökvonás). – Összetett művelet (pl. s[i]-edik Fibonacci-szám kiszámítása).




56

www.tankonyvtar.hu

Feladat Adott egy n számot tartalmazó tömb. Számolja ki a számok négyzetét egy új tömbbe/listába! Oldja meg a feladatot soros és párhuzamos algoritmussal is!


57

www.tankonyvtar.hu

Megoldás (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// a másolat int másolat = new int[számok.Length]; // másolás for (int i = 0; i < számok.Length; ++i) másolat[i] = számok[i] * számok[i]; // eredmény és futási idő kiírás for (int i = 0; i < számok.Length; ++i) Console.WriteLine("{0}^2 = {1}", számok[i], másolat[i]); Console.WriteLine("Összesen {0} db szám négyzetét számoltam ki.", számok.Length); Console.WriteLine("Futási idő: {0}", stopper.Elapsed);


Program.cs 58

www.tankonyvtar.hu

Megoldás (Párhuzamos) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// a szál-paraméterek szerkezete struct SzálParaméter { public int[] Számok; // a beolvasott számok public int SzálIndex; // most nincs jelentősége public int StartIndex; // ahonnan elkezdi a szál olvasni a Számok tömböt public int Hossz; // ahány elemet a szálnak fel kell dolgozni } // szálfüggvény private static void Szálfüggvény(object obj) { SzálParaméter param = (SzálParaméter )obj; for (int i = param.StartIndex; i < param.StartIndex + param.Hossz; ++i) Eredmény[i] = param.Számok[i] * param.Számok[i]; // a másolás az Eredmény tömbbe // szinkronizációra nincs szükség, mert a szálak a tömb diszjunkt részeit módosítják lock (sync) { változót ++lefutottSzálak; }


// a terminálás jelzésére a lefutottSzálak változót használjuk // itt szükséges a szinkronizáció, mert minden szál módosítja ezt a Program.cs 59

www.tankonyvtar.hu

Kiválogatás


60

www.tankonyvtar.hu

Kiválogatás • Feladat – Válogassuk ki egy sorozat elemeit, amelyek teljesítik az F feltételt.

• Sorozathoz sorozatot rendel. • Algoritmus: j=0 for i = 1 to n if F(s[i]) t[j] = s[i] j=j+1


61

www.tankonyvtar.hu

Kiválogatás • F feltétel tetszőleges logikai értékű függvény lehet. • Lépésszám – – – –



62

www.tankonyvtar.hu

Feladat Adott egy n számot tartalmazó tömb. Számolja ki a számok négyzetét egy új tömbbe/listába! Oldja meg a feladatot soros és párhuzamos algoritmussal is!


63

www.tankonyvtar.hu

Megoldás (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// az eredmény List négyzetszámok = new List(); // kiválogatás for (int i = 0; i < számok.Length; ++i) if (Feltétel(számok[i]) négyzetszámok.Add(számok[i]); // eredmény és futási idő kiírás Console.WriteLine("Négyzetszámok:"); for (int i = 0; i < négyzetszámok.Length; ++i) Console.WriteLine(négyzetszámok[i]); Console.WriteLine("Összesen {0} db számot vizsgáltam.", számok.Length); Console.WriteLine("Futási idő: {0}", stopper.Elapsed); // a feltétel private static bool Feltétel(int n) { return Math.Round(Math.Sqrt(n)) * Math.Round(Math.Sqrt(n)) == n; }


64

Program.cs www.tankonyvtar.hu


// a szál-paraméterek szerkezete struct SzálParaméter { public int[] Számok; // a beolvasott számok public int SzálIndex; // most nincs jelentősége public int StartIndex; // ahonnan elkezdi a szál olvasni a Számok tömböt public int Hossz; // ahány elemet a szálnak fel kell dolgozni } // szálfüggvény private static void Szálfüggvény(object obj) { SzálParaméter param = (SzálParaméter )obj; for (int i = param.StartIndex; i < param.StartIndex + param.Hossz; ++i) if (Feltétel(param.Számok[i])) // most szükséges a szinkronizáció, mert az Eredmény lock (Eredmény) // lista kezelése nem diszjunkt részekben történik Eredmény.Add(param.Számok[i]); lock (sync) ++lefutottSzálak;


// a terminálás jelzésére a lefutottSzálak változót használjuk // itt szükséges a szinkronizáció, mert minden szál módosítja ezt a // változót Program.cs 65

www.tankonyvtar.hu

Szétválogatás


66

www.tankonyvtar.hu

Szétválogatás • Feladat – Válogassuk szét egy sorozat F feltételt teljesítő és nem teljesítő elemeit egyegy sorozatba.

• Sorozathoz több sorozatot rendel. • Algoritmus: j1 = 0, j2 = 0 for i = 1 to n if F(s[i]) t1[j1] = s[i] j1 = j1 + 1 else t2[j2] = s[i] j2 = j2 + 1 © Kurdi Zsombor, ÓE NIK

67

www.tankonyvtar.hu

Szétválogatás • F feltétel tetszőleges logikai értékű függvény lehet. • Lépésszám – – – –



68

www.tankonyvtar.hu

Feladat Adott egy n számot tartalmazó tömb. Válogassuk szét a páros és páratlan elemeket két új tömbbe/listába! Oldja meg a feladatot soros és párhuzamos algoritmussal is!


69

www.tankonyvtar.hu

Megoldás (Soros) 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

// az eredmény List páros = new List(); List páratlan = new List(); // szétválogatás for (int i = 0; i < számok.Length; ++i) if (Feltétel(számok[i]) páros.Add(számok[i]); else páratlan.Add(számok[i]); // eredmény és futási idő kiírás Console.WriteLine("Páros számok:"); for (int i = 0; i < páros.Length; ++i) Console.WriteLine(páros[i]); Console.WriteLine("Páratlan számok:"); for (int i = 0; i < páratlan.Length; ++i) Console.WriteLine(páratlan[i]); Console.WriteLine("Összesen {0} db számot vizsgáltam.", számok.Length); Console.WriteLine("Futási idő: {0}", stopper.Elapsed); // a feltétel private static bool Feltétel(int n) { return n % 2 == 0; }


Program.cs 70

www.tankonyvtar.hu

Megoldás (Párhuzamos) 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

// a szál-paraméterek szerkezete struct SzálParaméter { public int[] Számok; // a beolvasott számok public int SzálIndex; // most nincs jelentősége public int StartIndex; // ahonnan elkezdi a szál olvasni a Számok tömböt public int Hossz; // ahány elemet a szálnak fel kell dolgozni } // szálfüggvény private static void Szálfüggvény(object obj) { SzálParaméter param = (SzálParaméter)obj; for (int i = param.StartIndex; i < param.StartIndex + param.Hossz; ++i) if (Feltétel(param.Számok[i])) // most szükséges a szinkronizáció, mert az Eredmény lock (Páros) // lista kezelése nem diszjunkt részekben történik Páros.Add(param.Számok[i]); else lock (Páratlan) Páratlan.Add(param.Számok[i]); lock (sync) ++lefutottSzálak; }


// a terminálás jelzésére a lefutottSzálak változót használjuk // itt szükséges a szinkronizáció, mert minden szál módosítja ezt a // változót Program.cs

71

www.tankonyvtar.hu

Metszet


72

www.tankonyvtar.hu

Metszet • Feladat – Másoljuk át két (vagy több) sorozat közös elemeit egy új sorozatba.

• Több sorozathoz egy sorozatot rendel. • Algoritmus for s in H1 if s not in H2 M = M U {s}


73

www.tankonyvtar.hu

Metszet • A másolás közben tetszőleges műveletet elvégezhetünk az elemeken. • Lépésszám – – – –

Legjobb eset: min{n,m} Legrosszabb eset: n*m Átlagos eset: ~n*m Függvényosztály: Θ(n*m)


74

www.tankonyvtar.hu

Feladat Adott egy n és egy m számot tartalmazó tömb. Másolja át a két tömb közös elemeit egy új tömbbe/listába! Oldja meg a feladatot soros és párhuzamos algoritmussal is!


75

www.tankonyvtar.hu

Megoldás (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// az eredmény List metszet = new List(); // metszet for (int i = 0; i < számok1.Length; ++i) { bool tartalmaz = false; for (int j = 0; j < számok2.Length && !tartalmaz; ++j) tartalmaz = számok1[i] == számok2[j];

}

if (tartalmaz) metszet.Add(számok1[i]);

// eredmény és futási idő kiírás Console.WriteLine("Metszet:"); for (int i = 0; i < metszet.Length; ++i) Console.WriteLine(metszet[i]); Console.WriteLine("Az 1. sorozat elemszáma: {0}", számok1.Length); Console.WriteLine("A 2. sorozat elemszáma: {0}", számok2.Length); Console.WriteLine("Futási idő: {0}", stopper.Elapsed);


Program.cs 76

www.tankonyvtar.hu

Megoldás (Párhuzamos) 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

// a szál-paraméterek szerkezete struct SzálParaméter { public int[] Számok1; // az egyik számsorozat public int[] Számok2; // a másik számsorozat public int SzálIndex; // most nincs jelentősége public int StartIndex; // ahonnan elkezdi a szál olvasni a Számok tömböt public int Hossz; // ahány elemet a szálnak fel kell dolgozni } // szálfüggvény private static void Szálfüggvény(object obj) { SzálParaméter param = (SzálParaméter)obj; for (int i = param.StartIndex; i < param.StartIndex + param.Hossz; ++i) { bool tartalmaz = false; for (int j = 0; j < param.Számok2.Length && !tartalmaz; ++j) tartalmaz = param.Számok1[i] == param.Számok2[j];

}

}

if (tartalmaz) // most szükséges a szinkronizáció, mert az Eredmény lock (Eredmény) // lista kezelése nem diszjunkt részekben történik Eredmény.Add(param.Számok1[i]);

lock (sync) ++lefutottSzálak;


// a terminálás jelzésére a lefutottSzálak változót használjuk // itt szükséges a szinkronizáció, mert minden szál módosítja ezt a változót Program.cs 77

www.tankonyvtar.hu

Unió


78

www.tankonyvtar.hu

Unió • Feladat – Másoljuk át két (vagy több) sorozat elemeit egy új sorozatba úgy, hogy a közös elemek csak egyszer szerepeljenek.

• Több sorozathoz egy sorozatot rendel. • Algoritmus E = H1 for s in H2 if s not in E E = E U {s}


79

www.tankonyvtar.hu

Unió • A másolás közben tetszőleges műveletet elvégezhetünk az elemeken. • Lépésszám – – – –

Legjobb eset: ~n+m Legrosszabb eset: n*m Átlagos eset: n*m Függvényosztály: Θ(n*m)


80

www.tankonyvtar.hu

Feladat Adott egy n és egy m számot tartalmazó tömb. Másolja át a két tömb elemeit egy új tömbbe/listába úgy, hogy a közös elemek csak egyszer szerepeljenek! Oldja meg a feladatot soros és párhuzamos algoritmussal is!


81

www.tankonyvtar.hu

Megoldás (Soros) 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

// az eredmény List unió = new List(); // unió for (int i = 0; i < számok1.Length; ++i) unió.Add(számok1[i]); for (int i = 0; i < számok2.Length; ++i) { bool tartalmaz = false; for (int j = 0; j < számok1.Length && !tartalmaz; ++j) tartalmaz = számok2[i] == számok1[j];

}

if (!tartalmaz) unió.Add(számok2[i]); // eredmény és futási idő kiírás Console.WriteLine("Unió:"); for (int i = 0; i < metszet.Length; ++i) Console.WriteLine(metszet[i]); Console.WriteLine("Az 1. sorozat elemszáma: {0}", számok1.Length); Console.WriteLine("A 2. sorozat elemszáma: {0}", számok2.Length); Console.WriteLine("Futási idő: {0}", stopper.Elapsed);


Program.cs 82

www.tankonyvtar.hu


// a szál-paraméterek szerkezete struct SzálParaméter { public int[] Számok1; // az egyik számsorozat public int[] Számok2; // a másik számsorozat public int SzálIndex; // most nincs jelentősége public int StartIndex; // ahonnan elkezdi a szál olvasni a Számok tömböt public int Hossz; // ahány elemet a szálnak fel kell dolgozni } // szálfüggvény (a Számok2 tömb elemeit a fő szálban másoljuk az Eredménybe) private static void Szálfüggvény(object obj) { SzálParaméter param = (SzálParaméter)obj; for (int i = param.StartIndex; i < param.StartIndex + param.Hossz; ++i) { bool tartalmaz = false; for (int j = 0; j < param.Számok1.Length && !tartalmaz; ++j) tartalmaz = param.Számok2[i] == param.Számok1[j];

}

}

if (!tartalmaz) // most szükséges a szinkronizáció, mert az Eredmény lock (Eredmény) // lista kezelése nem diszjunkt részekben történik Eredmény.Add(param.Számok1[i]);

lock (sync) ++lefutottSzálak;


// a terminálás jelzésére a lefutottSzálak változót használjuk // itt szükséges a szinkronizáció, mert minden szál módosítja ezt a változót Program.cs 83

www.tankonyvtar.hu

Házi feladat Próbálja ki a példaprogramokat! Kíséreljen meg javítani a párhuzamos változatok hatékonyságán! Megjegyzés – Lehetőség szerint a programokat futtassa egy-, illetve többprocesszoros gépeken!


84

www.tankonyvtar.hu




85

www.tankonyvtar.hu

3. óra Keresések Keresések Lineáris keresés Bináris keresés Visszalépéses keresés Irodalomjegyzék


86

www.tankonyvtar.hu

Keresések


87

www.tankonyvtar.hu

Lineáris keresés


88

www.tankonyvtar.hu

Lineáris keresés • Feladat – Keressük meg egy sorozat első F feltételt teljesítő elemét (vagy annak indexét).

• Sorozathoz értéket rendel. • Algoritmus for i = 1 to n if (F(s[i])) break


89

www.tankonyvtar.hu

Lineáris keresés • F feltétel tetszőleges logikai értékű függvény lehet. • Lépésszám – – – –

Legjobb eset: 1 Legrosszabb eset: n Átlagos eset: n/2 Függvényosztály: Θ(n)


90

www.tankonyvtar.hu

Feladat Adott egy n számot tartalmazó tömb. Keresse meg az első 2-vel, 3mal, 5-tel és 7-tel is osztható számot! Oldja meg a feladatot soros és párhuzamos algoritmussal is!


91

www.tankonyvtar.hu

Megoldás (Soros) 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

// keresés bool találat = false; int szám = 0; for (int i = 0; i < számok.Length && !találat; ++i) { if (Feltétel(számok[i])) { találat = true; szám = számok[i]; } } // eredmény és futási idő kiírás if (találat) Console.WriteLine("A feltételnek megfelelő szám: {0}", szám); else Console.WriteLine("Nincs a feltételnek megfelelő szám."); Console.WriteLine("Összesen {0} db számot vizsgáltam.", számok.Length); Console.WriteLine("Futási idő: {0}", stopper.Elapsed); // feltétel private static bool Feltétel(int n) { return n % 2 == 0 && n % 3 == 0 && n % 5 == 0 && n % 7 == 0; }


92


Lineáris keresés párhuzamosítása • Az eredmények tömbben a szálak futási állapotát is tároljuk. Ha egy érték. – –2 : még fut a szál. – – 1 : a szál lefutott, de nem talált a feltételnek megfelelő elemet. – Más érték: a szál lefutott és az érték a feltételnek megfelelő elem.

• A program akkor ér véget, amint a legkisebb indexű szál talált eredményt (vagy egyik szál sem talált megfelelő elemet).


93

www.tankonyvtar.hu


// inicializálás for (int i = 0; i < szálakSzáma; ++i) eredmények[i] = -2; … // lefutás ellenőrzés int index = 0; while (index < szálakSzáma && eredmények[index] < 0) { if (eredmények[index] == -1) ++index; }

Thread.Sleep(1);


Program.cs 94

www.tankonyvtar.hu


// a szál-paraméterek szerkezete struct SzálParaméter { public int[] Számok; // a beolvasott számok public int SzálIndex; // az eredmény tömbben erre az indexre írja a szál a futás eredményét public int StartIndex; // ahonnan elkezdi a szál olvasni a Számok tömböt public int Hossz; // ahány elemet a szálnak fel kell dolgozni } // szálfüggvény private static void Szálfüggvény(object obj) { SzálParaméter param = (SzálParaméter)obj; bool találat = false; int szám = 0; for (int i = param.StartIndex; i < param.StartIndex + param.Hossz; ++i) { if (Feltétel(param.Számok[i])) { találat = true; szám = param.Számok[i]; } }

}

if (találat) // szinkronizációra nincs szükség, mert a szálak az eredmény tömb különböző részét módosítják eredmények[param.SzálIndex] = szám; else eredmények[param.SzálIndex] = -1;


Program.cs

95

www.tankonyvtar.hu

Bináris keresés


96

www.tankonyvtar.hu

Bináris keresés • Feladat – Döntsük el, hogy egy rendezett sorozat tartalmazza-e az E elemet.

• Sorozathoz értéket rendel. • Algoritmus a = 1, f = n, találat = false while a <= f k = (a + f) / 2 if (s[k] = E) találat = true break else if (s[k] > E) f=k–1 else a=k+1 © Kurdi Zsombor, ÓE NIK

97

www.tankonyvtar.hu

Bináris keresés • Lépésszám – – – –

Legjobb eset: 1 Legrosszabb eset: log2n Átlagos eset: ~log2n Függvényosztály: Θ(log2n)


98

www.tankonyvtar.hu

Feladat Adott egy n számot tartalmazó rendezett tömb. Döntse el, hogy tartalmazza-e a tömb a 384-es számot! Oldja meg a feladatot soros és párhuzamos algoritmussal is!


99

www.tankonyvtar.hu

Megoldás (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// keresés int eleje = 0; int vége = számok.Length; while (eleje < vége) { int közepe = (eleje + vége) / 2;

}

if (számok[közepe] > keresettSzám) vége = közepe - 1; else if (számok[közepe] == keresettSzám) eleje = vége = közepe; else eleje = közepe + 1;

// eredmény és futási idő kiírás if (eleje == vége) Console.WriteLine("A tömb a(z) {0}. indexen tartalmazza a(z) {1} számot.", eleje, keresettSzám); else Console.WriteLine("A tömb nem tartalmazza a(z) {0} számot.", keresettSzám); Console.WriteLine("Összesen {0} db számot vizsgáltam.", számok.Length); Console.WriteLine("Futási idő: {0}", stopper.Elapsed);


Program.cs 100

www.tankonyvtar.hu

Bináris keresés párhuzamosítása • Az eredmények tömb helyett eleje és vége nevű tömbök tartalmazzák az egyes részeken végzett bináris keresések indexeit. • A korábbi adatfelosztás helyett új módszert alkalmazunk.

• A program akkor ér véget, amint egy szál megtalálta a keresett elemet, vagy minden szál lefutott. • Emiatt a keresés eredménye nemdeterminisztikus (de az eldöntéshez nem szükséges determinisztikus eredmény).


101

www.tankonyvtar.hu

Adatbelovasás 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// az adatfelosztási módszernek megfelelő beolvasás private static int[,] Beolvas() { StreamReader input = new StreamReader(inputFile); int méret = Convert.ToInt32(input.ReadLine()); int[,] számok = new int[szálakSzáma, méret / szálakSzáma]; for (int i = 0; i < méret; ++i) számok[i % szálakSzáma, i /szálakSzáma] = Convert.ToInt32(input.ReadLine()); input.Close(); }

return számok;


Program.cs 102

www.tankonyvtar.hu


// inicializálás for (int i = 0; i < szálakSzáma; ++i) { eleje[i] = 0; vége[i] = számok.GetLength(1) – 1; } … // lefutás ellenőrzés int index = -1; bool vanFutóSzál = true; while (vanFutóSzál && index < 0) { vanFutóSzál = false; for (int i = 0; i < szálakSzáma; ++i) { if (eleje[i] == vége[i]) index = eleje[i] * szálakSzáma + i; else vanFutóSzál = true; } }

Thread.Sleep(1);


Program.cs 103

www.tankonyvtar.hu


// a szál-paraméterek szerkezete struct SzálParaméter { public int[] Számok; // a beolvasott számok public int SzálIndex; // az eredmény tömbben erre az indexre írja a szál a futás eredményét public int Keresett Szám; // a keresett szám } // szálfüggvény private static void Szálfüggvény(object obj) { SzálParaméter param = (SzálParaméter )obj; while (eleje[param.SzálIndex] < vége[param.SzálIndex]) { int közepe = (eleje[param.SzálIndex] + vége[param.SzálIndex]) / 2;

}

}

if (param.Számok[param.SzálIndex, közepe] > param.KeresettSzám) vége[param.SzálIndex] = közepe - 1; else if (param.Számok[param.SzálIndex, közepe] == param.KeresettSzám) eleje[param.SzálIndex] = vége[param.SzálIndex] = közepe; else eleje[param.SzálIndex] = közepe + 1;


Program.cs 104

www.tankonyvtar.hu

Visszalépéses keresés


105

www.tankonyvtar.hu

Visszalépéses keresés • Feladat – Egy rendezett N-est (E1, E2, ... EN) keresünk, amely eleget tesz F feltételnek.

• A rendezett N-es minden komponense rögzített értékkészletből származhat (pl. E1 Є {R11, R12, ... R1k}). • Az Ei komponenseket részeredményeknek nevezzük. • Az egyes értékkészletek számosságát Mi-vel jelöljük. • Az F feltétel olyan logikai értékű függvény, amely esetében tetszőleges részeredmény esetében megállapítható, hogy az lehet-e (vagy sem) egy jó eredmény része.


106

www.tankonyvtar.hu

Visszalépéses keresés • Bemenet – N : a részeredmények száma. – Mi : a részeredmények értékkészletének számossága. – Rij : a részeredmények lehetséges értékei (értékkészlet).

• Kimenet (egy megoldást keresünk) – Van-e teljes megoldás. – Az egyes részeredmények értéke a megoldásban.

• Kimenet (minden megoldást keressük) – Az összes rendezett N-es, amely megoldás.


107

www.tankonyvtar.hu

Feladat Adott egy sakktábla. Helyezzen fel a táblára 8 királynőt úgy, hogy közülük semelyik kettő se üsse egymást! Találja meg a probléma összes lehetséges megoldását! Oldja meg a feladatot soros és párhuzamos algoritmussal is!


108

www.tankonyvtar.hu

Keresés (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static void Keresés(int[] királynők, int i, List<string> eredmény) { for (int j = 0; j < királynőkSzáma; ++j) { if (JóÁllás(királynők, i, j)) { királynők[i] = j; if (i < királynőkSzáma – 1) Keresés(királynők, i + 1, eredmény); else eredmény.Add(ToString(királynők)); } } }


Program.cs 109

www.tankonyvtar.hu

Segédfüggvény: JóÁllás 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static bool JóÁllás(int[] királynők, int i, int j) { bool nincsÜtés = true; for (int k = 0; k < i && nincsÜtés; ++k) { if (királynők[k] == j) nincsÜtés = false; if (királynők[k] == j + (i – k)) nincsÜtés = false;

} }

if (királynők[k] == j – (i – k)) nincsÜtés = false;

return nincsÜtés;


Program.cs 110

www.tankonyvtar.hu

Párhuzamosítás • A „rekurzió mentén” párhuzamosítunk: a Keresés() függvény rekurzív hívását külön szálon indítjuk el. • Minden szál saját másolattal rendelkezik a részeredményről. – Egyszerűbb szinkronizáció. – Nem szükséges az „eddig bejárt út” tárolása a visszalépéshez.

• A szálak lefutásának ellenőrzéséhez számláljuk az elindított és a már lefutott szálakat. – Ha minden szál lefutott (azaz a két számláló azonos értéken áll), akkor kiírjuk az eredményt.

• Ezzel a fajta párhuzamosítással nincs szükség visszalépésre, mert a visszalépés után bejárandó úton már egy másik szál dolgozik. © Kurdi Zsombor, ÓE NIK

111

www.tankonyvtar.hu

Keresés (Párhuzamos) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static void Szálfüggvény(object obj) { SzálParaméter param = (SzálParaméter)obj; for (int j = 0; j < KirálynőkSzáma; ++j) { if (JóÁllás(param.Királynők, param.OszlopIndex, j)) { param.Királynők[param.OszlopIndex] = j; if (param.OszlopIndex < királynőkSzáma – 1) { SzálParaméter paraméter; paraméter.Királynők = ÁllásMásol(param.Királynők); paraméter.OszlopIndex = param.OszlopIndex + 1; paraméter.Eredmény = param.Eredmény; lock (syncElindított) { ++ elindítottSzálak; } ThreadPool.QueueUserWorkItem(new WaitCallback(Szálfüggvény), paraméter); }


Program.cs 112

www.tankonyvtar.hu

Keresés (Párhuzamos) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

}

}

}

else { lock (param.Eredmény) { param.Eredmény.Add(ToString(param.Királynők)); } }

lock (syncLefutott) { ++lefutottSzálak; }


Program.cs 113

www.tankonyvtar.hu

Házi feladat Próbálja ki a példaprogramokat! Kíséreljen meg javítani a párhuzamos változatok hatékonyságán! Számítsa ki a párhuzamos algoritmusok lépésszámát! Megjegyzések – Lehetőség szerint a programokat futtassa egy-, illetve többprocesszoros gépeken! – A lépésszámot a legjobb, a legrosszabb és az általános esetre is adja meg!


114

www.tankonyvtar.hu

Irodalomjegyzék címsora •


•

Randomized Parallel Algorithms for Backtrack Search and Branch-and-Bound Computation http://rsim.cs.illinois.edu/arch/qual_papers/systems/7.pdf


115

www.tankonyvtar.hu

4. óra Mintaillesztések Mintaillesztések Brute-Force algoritmus Knuth–Morris–Pratt algoritmus QuickSearch algoritmus Irodalomjegyzék


116

www.tankonyvtar.hu

Mintaillesztések


117

www.tankonyvtar.hu

Mintaillesztés • Feladat – Adott elemek egy hosszabb (szöveg) és rövidebb (minta) sorozata. – Döntsük el, hogy a minta megtalálható-e a szövegben, VAGY – keressük meg a minta első előfordulását a szövegben, VAGY – keressük meg a minta összes előfordulását a szövegben.

• Leggyakoribb felhasználás: karaktersorozatok keresése hosszabb szövegben. • A példaprogramokban a szoveg.txt fájl tartalmát használjuk szövegként. © Kurdi Zsombor, ÓE NIK

118

www.tankonyvtar.hu

Brute-Force algoritmus


119

www.tankonyvtar.hu

Brute-Force algoritmus • Illesszük a mintát (k hosszú) a szöveg (n hosszú) minden indexére és ellenőrizzük, hogy a teljes minta illeszkedik-e ott. • Lépésszám – – – –

Legjobb eset: k Legrosszabb eset: k * n Átlagos eset: k * n / 2 Függvényosztály: Θ(n)


120

www.tankonyvtar.hu

Adatbelovasás 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static string Beolvas() { StreamReader input = new StreamReader(inputFile); string szöveg = input.ReadToEnd(); input.Close(); }

return szöveg;


Program.cs 121

www.tankonyvtar.hu

Program 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

static void Main(string [] args) { string szöveg = Beolvas(); bool egyezik = false; int i; for (i = 0; i < szöveg.Length – keresett.Length && !egyezik; ++i) { egyezik = true; for (int j = 0; j < keresett.Length && egyezik; ++j) { egyezik = szöveg[i + j] == keresett[j]; } } }

// eredmények kiíratása


Program.cs 122

www.tankonyvtar.hu

Feladat Készítse el a bemutatott algoritmus párhuzamos implementációját! Használja a lineáris keresésnél megismert módszereket!


123

www.tankonyvtar.hu

Knuth–Morris–Pratt algoritmus


124

www.tankonyvtar.hu

Knuth–Morris–Pratt algoritmus • Alapötlet – Amikor az illeszkedés elromlik, akkor nem feltétlenül kell a következő helyen újrailleszteni a mintát. – Amennyiben a mintában találhatók ismétlődő részek, akkor nagyobb lépés is megtehető az illesztésben.

• A prefix és szuffix szakaszok a minta ismeretében meghatározhatók. • Már a mintaillesztés kezdete előtt kiszámolható, hogyan kell áthelyezni a mintát, amikor az nem illeszkedik. © Kurdi Zsombor, ÓE NIK

125

www.tankonyvtar.hu

Mintaáthelyezések számítása 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static int[] KövetkezőSzámol() { int[] következő = new int[keresett.Length];

}

következő[0] = 0; for (int i = 1, j = 0; i < keresett.Length;) { if (keresett[i] == keresett[j]) { következő[i] = j; ++i; ++j; } else if (j == 0) { következő[i] = 0; ++i; } else j = következő[j]; } return következő;


Program.cs 126

www.tankonyvtar.hu

Program 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

static void Main(string [] args) { string szöveg = Beolvas(); int[] következő = KövetkezőSzámol(); int i, j; for (i = 0, j = 0; i < szöveg.Length && j < keresett.Length;) { if (szöveg[i] == keresett[j]) { ++i; ++j; } else if (j == 0) ++j; else j = következő[j]; } }



Program.cs 127

www.tankonyvtar.hu

Feladat Készítse el a bemutatott algoritmus párhuzamos implementációját! Használja a lineáris keresésnél megismert módszereket!


128

www.tankonyvtar.hu

QuickSearch algoritmus


129

www.tankonyvtar.hu

QuickSearch algoritmus • Alapötlet – A Knuth–Morris–Pratt algoritmushoz hasonló ugrásokkal csökkentsük az illesztések számát. – Amennyiben a minta utáni első helyen olyan elem van, amely nincs a mintában, ez után a jel után folytathatjuk az illesztést.


130

www.tankonyvtar.hu

Ugrások számítása 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static Dictionary<string , int> UgrásSzámol() { Dictionary<string , int> ugrás = new Dictionary<string , int>(); for (int i = 0; i < keresett.Length; ++i) { ugrás[keresett[i]] = keresett.Length – i; } }

return ugrás;


Program.cs 131

www.tankonyvtar.hu

Program 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

static void Main(string [] args) { string szöveg = Beolvas(); Dictionary<string , int> ugrás = UgrásSzámol(); int i, j; for (i = 0, j = 0; i < szöveg.Length – keresett.Length && j < keresett.Length;) { if (szöveg[i + j] == keresett[j]) ++j; else if (i == szöveg.Length – keresett.Length – 1) ++i; else i += ugrás.ContainsKey(szöveg[i + keresett.Length]) ? ugrás[szöveg[i + keresett.Length]] : keresett.Length + 1; } }



Program.cs 132

www.tankonyvtar.hu

Párhuzamosítás • Újfajta megoldás. • Daraboljuk fel a szöveget azon karakterek mentén, amelyek nem szerepelnek a mintában. • Az így keletkező részszövegekben elegendő illeszteni a mintát. • Ezt párhuzamosan is megtehetjük. • Ebben az esetben nem szükséges figyelni az átfedéseket az egyes részek között, mert a minta úgy nem illeszkedhet. • A módszer hatékonysága tovább javítható, ha csak azokat a részeket vizsgáljuk, amelyek nem rövidebbek a mintánál.


133

www.tankonyvtar.hu

Adatbeolvasás 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static string Beolvas() { StreamReader input = new StreamReader(inputFile); string szöveg = input.ReadToEnd(); input.Close(); int előző = 0; Dictionary részek = new Dictionary(); for (int i = 0; i < szöveg.Length; ++i) { if (!keresett.Contains(szöveg[i])) { if (i > előző + 1) { részek.Add(előző, szöveg.Substring(előző, i – előző)); }

} }

}

előző = i;

return szöveg;


Program.cs 134

www.tankonyvtar.hu

Házi feladat Próbálja ki a példaprogramokat! Kíséreljen meg javítani a párhuzamos változatok hatékonyságán!

Megjegyzés – Lehetőség szerint a programokat futtassa egy-, illetve többprocesszoros gépeken!


135

www.tankonyvtar.hu




136

www.tankonyvtar.hu

5. óra Rendezések (1) Rendezések

Buborékrendezés ShellSort HeapSort Irodalomjegyzék


137

www.tankonyvtar.hu

Rendezések


138

www.tankonyvtar.hu

Buborékrendezés


139

www.tankonyvtar.hu

Buborékrendezés • Feladat – Rendezzük egy sorozat elemeit növekvő sorrendbe.

• Sorozathoz sorozatot rendel. • A rendezés megoldható helyben, vagy másolat készíthető a sorozat elemeiről. • Lépésszám – – – –

Legjobb eset: 0 Legrosszabb eset: n2 Átlagos eset: ~n2 Függvényosztály: O(n2)


140

www.tankonyvtar.hu

Buborékrendezés


141

www.tankonyvtar.hu

Feladat Buborékrendező algoritmussal rendezze a szamok.txt fájl tartalmát növekvő sorrendbe! Oldja meg a feladatot soros és párhuzamos algoritmussal is!

Megjegyzés – A párhuzamos implementáció során célszerű az 1. órán megismert adatelosztást alkalmazni.


142

www.tankonyvtar.hu

Buborékrendezés (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

for (int i = számok.Length; i >= 2; --i) { for (int j = 0; j < i - 1; ++j) { if (számok[j] > számok[j + 1]) { int tmp = számok[j]; számok[j] = számok[j + 1]; számok[j + 1] = tmp; } } }


Program.cs 143

www.tankonyvtar.hu

Paraméterstruktúra 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

struct SzálParaméter { public int SzálIndex; public int[] Számok; public int StartIndex; public int Hossz; }


Program.cs 144

www.tankonyvtar.hu

Szálfüggvény 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static void Szálfüggvény(object obj) { SzálParaméter param = (SzálParaméter)obj; for (int i = param.StartIndex + param.Hossz; i >= param.StartIndex + 2; --i) { for (int j = param.StartIndex; j < i - 1; ++j) { if (param.Számok[j] > param.Számok[j + 1]) { int tmp = param.Számok[j]; param.Számok[j] = param.Számok[j + 1]; param.Számok[j + 1] = tmp; } } }

}



Program.cs 145

www.tankonyvtar.hu

Részeredmények összefésülése 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

int[] indexek = new int[szálakSzáma]; for (int i = 0; i < szálakSzáma; ++i) indexek[i] = i * számok.Length / szálakSzáma; int[] eredmény = new int[számok.Length]; for (int i = 0; i < számok.Length; ++i) { int min = -1; for (int j = 0; j < szálakSzáma; ++j) { if (indexek[j] < (j + 1) * számok.Length / szálakSzáma && (min == -1 || számok[indexek[j]] < számok[indexek[min]])) { min = j; } }

}

if (min >= 0) { eredmény[i] = számok[indexek[min]++]; }


Program.cs 146

www.tankonyvtar.hu

ShellSort


147

www.tankonyvtar.hu

ShellSort/Shell rendezés • Feladat – Rendezzük egy sorozat elemeit növekvő sorrendbe.

• Sorozathoz sorozatot rendel. • A rendezés megoldható helyben, vagy másolat készíthető a sorozat elemeiről. • A buborékrendezés javított változata. • Lépésszám – Függvényosztály: O(n * log2n)


148

www.tankonyvtar.hu

Feladat ShellSort algoritmussal rendezze a szamok.txt fájl tartalmát növekvő sorrendbe! Oldja meg a feladatot soros és párhuzamos algoritmussal is!



149

www.tankonyvtar.hu

Shell rendezés (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

int inkremens = 3; while (inkremens > 0) { for (int i = 0; i < számok.Length; ++i) { int j = i; int tmp = számok[i]; while (j >= inkremens && számok[j - inkremens] > tmp) { számok[j] = számok[j - inkremens]; j -= inkremens; } }

}

számok[j] = tmp;

if (inkremens / 2 != 0) inkremens /= 2; else if (inkremens == 1) inkremens = 0; else inkremens = 1;


Program.cs 150

www.tankonyvtar.hu

Shell rendezés (Párhuzamos) • Paraméterstruktúra – Azonos a buborékrendezésnél látottal

• Szálfüggvény – A buborékrendezésnél látotthoz hasonló

• Összefésülés – A buborékrendezésnél látotthoz hasonló


151

www.tankonyvtar.hu

HeapSort


152

www.tankonyvtar.hu

HeapSort/Kupac rendezés • Feladat – Rendezzük egy sorozat elemeit növekvő sorrendbe.

• Sorozathoz sorozatot rendel. • A rendezés megoldható helyben, vagy másolat készíthető a sorozat elemeiről. • Lépésszám – Függvényosztály: O(n*logn)


153

www.tankonyvtar.hu

Feladat HeapSort algoritmussal rendezze a szamok.txt fájl tartalmát növekvő sorrendbe! Oldja meg a feladatot soros és párhuzamos algoritmussal is!



154

www.tankonyvtar.hu

Heap sort (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static void Rendezés(int[] t, int start, int end) { int bal = start + (end - start) / 2; int jobb = end; int offset = start; while (bal >= start) { Süllyeszt(t, offset, bal, end); --bal; }

}

while (jobb > start) { int tmp = t[jobb]; t[jobb] = t[start]; t[start] = tmp; --jobb; Süllyeszt(t, offset, start, jobb); }


Program.cs 155

www.tankonyvtar.hu

Heap sort (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static void Süllyeszt(int[] t, int offset, int start, int end) { int gyökér = start; while ((gyökér - offset) * 2 + 1 <= end - offset) { int gyermek = (gyökér - offset) * 2 + 1 + offset; if (gyermek < end && t[gyermek] < t[gyermek + 1]) ++gyermek; if (t[gyökér] < t[gyermek]) { int tmp = t[gyökér]; t[gyökér] = t[gyermek]; t[gyermek] = tmp; gyökér = gyermek;

}

}

} else break;


Program.cs 156

www.tankonyvtar.hu

Szálfüggvény 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static void Szálfüggvény(object obj) { SzálParaméter param = (SzálParaméter)obj; Rendezés(param.Számok, param.StartIndex, param.StartIndex + param.Hossz - 1);

}



Program.cs 157

www.tankonyvtar.hu

Összefésülés 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

int[] indexek = new int[szálakSzáma]; for (int i = 0; i < szálakSzáma; ++i) indexek[i] = i * számok.Length / szálakSzáma; int[] eredmény = new int[számok.Length]; for (int i = 0; i < számok.Length; ++i) { int min = -1; for (int j = 0; j < szálakSzáma; ++j) { if (indexek[j] < (j + 1) * számok.Length / szálakSzáma && (min == -1 || számok[indexek[j]] < számok[indexek[min]])) min = j; }

}

if (min >= 0) { eredmény[i] = számok[indexek[min]++]; }


Program.cs 158

www.tankonyvtar.hu




159

www.tankonyvtar.hu




160

www.tankonyvtar.hu

6. óra Rendezések (2) Rendezések

MergeSort QuickSort RADIX rendezés Irodalomjegyzék


161

www.tankonyvtar.hu

Rendezések


162

www.tankonyvtar.hu

MergeSort


163

www.tankonyvtar.hu

MergeSort/Összefésüléses rendezés • Feladat – Rendezzük egy sorozat elemeit növekvő sorrendbe.

• Sorozathoz sorozatot rendel . • A rendezés megoldható helyben, vagy másolat készíthető a sorozat elemeiről. • Lépésszám – – – –

Legjobb eset: 0 Legrosszabb eset: n*logn Átlagos eset: ~n*logn Függvényosztály: O(n*logn)


164

www.tankonyvtar.hu

Feladat MergeSort algoritmussal rendezze a szamok.txt fájl tartalmát növekvő sorrendbe! Oldja meg a feladatot soros és párhuzamos algoritmussal is!

Megjegyzés – A szálak lefutásának ellenőrzéséhez célszerű valamilyen szemafór típust használni.


165

www.tankonyvtar.hu

MergeSort (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static void Rendezés(int[] t, int bal, int jobb) { if (jobb > bal) { int közép = (jobb + bal) / 2; Rendezés(t, bal, közép); Rendezés(t, közép + 1, jobb);

}

}

Összefésülés(t, bal, közép + 1, jobb);


Program.cs 166

www.tankonyvtar.hu

MergeSort (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static void Összefésülés(int[] t, int bal, int közép, int jobb) { int[] tmptömb = new int[t.Length]; int tmpindex = bal; int balvég = közép - 1; int jobbvég = közép; int elemszám = jobb - bal + 1; while (bal <= balvég && jobbvég <= jobb) { if (t[bal] <= t[jobbvég]) { tmptömb[tmpindex] = t[bal]; ++tmpindex; ++bal; } else { tmptömb[tmpindex] = t[jobbvég]; ++tmpindex; ++jobbvég; } }


Program.cs 167

www.tankonyvtar.hu

MergeSort (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

while (bal <= balvég) { tmptömb[tmpindex] = t[bal]; ++tmpindex; ++bal; } while (jobbvég <= jobb) { tmptömb[tmpindex] = t[jobbvég]; ++tmpindex; ++jobbvég; }

}

for (int i = 0; i < elemszám; ++i) { t[jobb] = tmptömb[jobb]; --jobb; }


Program.cs 168

www.tankonyvtar.hu


struct SzálParaméter { public int[] Számok; public int Bal; public int Jobb; public EventWaitHandle Szemafor; }


Program.cs 169

www.tankonyvtar.hu

Szálfüggvény 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static void Szálfüggvény(object obj) { SzálParaméter param = (SzálParaméter)obj; if (param.Jobb > param.Bal) { int közép = (param.Bal + param.Jobb) / 2; SzálParaméter paraméter1; paraméter1.Számok = param.Számok; paraméter1.Bal = param.Bal; paraméter1.Jobb = közép; paraméter1.Szemafor = new ManualResetEvent(); ThreadPool.QueueUserWorkItem(new WaitCallback(Szálfüggvény), paraméter1); SzálParaméter paraméter2; paraméter2.Számok = param.Számok; paraméter2.Bal = közép + 1; paraméter2.Jobb = param.Jobb; paraméter2.Szemafor = new ManualResetEvent();


Program.cs 170

www.tankonyvtar.hu

Szálfüggvény 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

ThreadPool.QueueUserWorkItem(new WaitCallback (Szálfüggvény), paraméter2); WaitHandle.WaitAll(new WaitHandle [] { paraméter1.Szemafor, paraméter2.Szemafor }); } }

Összefésülés(param.Számok, param.Bal, közép + 1, param.Jobb);

param.Szemafor.Set();


Program.cs 171

www.tankonyvtar.hu

QuickSort


172

www.tankonyvtar.hu

QuickSort/Gyorsrendezés • Feladat – Rendezzük egy sorozat elemeit növekvő sorrendbe.

• Sorozathoz sorozatot rendel. • A rendezés megoldható helyben, vagy másolat készíthető a sorozat elemeiről. • Lépésszám – – – –

Legjobb eset: 0 Legrosszabb eset: n * logn Átlagos eset: ~n * logn Függvényosztály: O(n * logn)


173

www.tankonyvtar.hu

Feladat QuickSort algoritmussal rendezze a szamok.txt fájl tartalmát növekvő sorrendbe! Oldja meg a feladatot soros és párhuzamos algoritmussal is!

Megjegyzés – A párhuzamos implementáció során célszerű a visszalépéses keresésnél megismert rekurzív szálindítási technikát alkalmazni.


174

www.tankonyvtar.hu

QuickSort (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static void Rendezés(int[] t, int bal, int jobb) { int balelem = t[bal]; int balindex = bal; int jobbindex = jobb; while (bal < jobb) { while (bal < jobb && t[jobb] >= balelem) --jobb; if (bal != jobb) { t[bal] = t[jobb]; ++bal; } while (bal < jobb && t[bal] <= balelem) ++bal;


Program.cs 175

www.tankonyvtar.hu

QuickSort (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

}

if (bal != jobb) { t[jobb] = t[bal]; --jobb; }

t[bal] = balelem; if (balindex < bal) Rendezés(t, balindex, bal - 1);

}

if (jobbindex > bal) Rendezés(t, bal + 1, jobbindex);


Program.cs 176

www.tankonyvtar.hu


struct SzálParaméter { public int[] Számok; public int Bal; public int Jobb; }


Program.cs 177

www.tankonyvtar.hu

Szálfüggvény 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static void Szálfüggvény(object obj) { SzálParaméter param = (SzálParaméter)obj; int balelem = param.Számok[param.Bal]; int balindex = param.Bal; int jobbindex = param.Jobb; // Rendezés if (balindex < param.Bal) { SzálParaméter paraméter; paraméter.Számok = param.Számok; paraméter.Bal = balindex; paraméter.Jobb = param.Bal - 1; lock (syncElindított) { ++elindítottSzálak; }


Program.cs 178

www.tankonyvtar.hu

Szálfüggvény 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

}


if (jobbindex > param.Bal) { SzálParaméter paraméter; paraméter.Számok = param.Számok; paraméter.Bal = param.Bal + 1; paraméter.Jobb = jobbindex; lock (syncElindított) { ++elindítottSzálak; } }

}




Program.cs 179

www.tankonyvtar.hu

RADIX rendezés


180

www.tankonyvtar.hu

RADIX rendezés • Feladat – Rendezzük egy sorozat elemeit növekvő sorrendbe.

• Sorozathoz sorozatot rendel. • A rendezés megoldható helyben, vagy másolat készíthető a sorozat elemeiről. • A Vödrös rendezés speciális formája. – Azonos hosszúságú sorozatok rendezésére használható.

• Lépésszám – Függvényosztály: Θ(n)


181

www.tankonyvtar.hu

Feladat RADIX/Vödrös rendezés algoritmussal rendezze a szamok.txt fájl tartalmát növekvő sorrendbe! Oldja meg a feladatot soros és párhuzamos algoritmussal is!


182

www.tankonyvtar.hu

RADIX (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

for (int i = 0; i < lépésekSzáma; ++i) { for (int j = 0; j < számok.Length; ++j) tárolók[Számjegy(számok[j], i)].Enqueue(számok[j]);

}

int index = 0; for (int j = 0; j < tárolók.Length; ++j) { while (tárolók[j].Count > 0) számok[index++] = tárolók[j].Dequeue(); }


Program.cs 183

www.tankonyvtar.hu


struct SzálParaméter { public int[] Számok; public int StartIndex; public int Hossz; public int Lépés; public int[] Tárolók; }


Program.cs 184

www.tankonyvtar.hu

Szálfüggvény 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static void Szálfüggvény(object obj) { SzálParaméter param = (SzálParaméter)obj; for (int i = param.StartIndex; i < param.StartIndex + param.Hossz; ++i) { lock (param.Tárolók) { ++param.Tárolók[param.Számok[i]]; } }

}



Program.cs 185

www.tankonyvtar.hu

Rendezett sorozat előállítása 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

for (int i = 0, index = 0; i < tárolók.Length; ++i) { for (int j = 0; j < tárolók[i]; ++j) számok[index++] = i; }


Program.cs 186

www.tankonyvtar.hu




187

www.tankonyvtar.hu




188

www.tankonyvtar.hu

7. óra Mátrixműveletek Mátrixszorzás Mátrixinvertálás Lineáris egyenletrendszerek megoldása Irodalomjegyzék


189

www.tankonyvtar.hu

Mátrixszorzás


190

www.tankonyvtar.hu

Fájlformátum (mátrix.txt) • 1. sor: a mátrix sorainak száma. • 2. sor: a mátrix oszlopainak száma. • 3. sortól: a mátrix elemei sorfolytonosan.


191

www.tankonyvtar.hu

Mátrixadatok beolvasása 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static int[,] Beolvas(string file) { StreamReader input = new StreamReader(file); int méret1 = Convert.ToInt32(input.ReadLine()); int méret2 = Convert.ToInt32(input.ReadLine()); int[,] mátrix = new int[méret1, méret2]; for (int i = 0; i < mátrix.GetLength(0); ++i) for (int j = 0; j < mátrix.GetLength(1); ++j) mátrix[i, j] = Convert.ToInt32(input.ReadLine()); input.Close(); }

return mátrix;


Program.cs 192

www.tankonyvtar.hu

Mátrixok szorzása • Feladat – – – –

Adott két mátrix M1 és M2 Számítsuk ki a két mátrix szorzatát. M1 mérete n x k, M2 mérete k x m A szorzat mérete n x m

• Lépésszám – Függvényosztály: Θ(n * k * m)


193

www.tankonyvtar.hu

Mátrixok szorzása


194

www.tankonyvtar.hu

Feladat Készítsen programot, amely a matrix.txt és matrix2.txt fájlokban található mátrixokat összeszorozza! Oldja meg a feladatot soros és párhuzamos algoritmussal is!

Megjegyzés – A párhuzamos implementáció során célszerű valamelyik dimenzió mentén adatfelosztást alkalmazni.


195

www.tankonyvtar.hu

Mátrixszorzás (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

for (int i = 0; i < mátrix1.GetLength(0); ++i) { for (int j = 0; j < mátrix2.GetLength(1); ++j) { szorzat[i, j] = 0; for (int k = 0; k < mátrix1.GetLength(1); ++k) szorzat[i, j] += mátrix1[i, k] * mátrix2[k, j]; } }


Program.cs 196

www.tankonyvtar.hu


struct SzálParaméter { public int[,] Mátrix1; public int[,] Mátrix2; public int StartIndex; public int Hossz; public int[,] Szorzat; }


Program.cs 197

www.tankonyvtar.hu

Szálfüggvény 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static void Szálfüggvény(object obj) { SzálParaméter param = (SzálParaméter)obj; for (int i = param.StartIndex; i < param.StartIndex + param.Hossz; ++i) { for (int j = 0; j < param.Mátrix2.GetLength(1); ++j) { param.Szorzat[i, j] = 0;

}

}

}

for (int k = 0; k < param.Mátrix1.GetLength(1); ++k) param.Szorzat[i, j] += param.Mátrix1[i, k] * param.Mátrix2[k, j];



Program.cs 198

www.tankonyvtar.hu

Mátrixinvertálás


199

www.tankonyvtar.hu

Mátrix invertálása • Feladat – Adott egy n x n-es négyzetes mátrix M. – Számítsuk ki azt az M-1 mátrixot, amelyre M * M-1 = I (egységmátrix).

• Lépésszám – Függvényosztály: Θ(n3)


200

www.tankonyvtar.hu

Mátrix invertálása • Rangtartó műveletek segítségével állíthatjuk elő. • Ezeket a műveleteket addig kell ismételni, amíg a mátrixot egységmátrixszá nem transzformáljuk. • Ezzel párhuzamosan egy egységmátrixon is végezzük el a transzformációkat. • Az egységmátrixból transzformált mátrix lesz az inverz (Gauss-elimináció).


201

www.tankonyvtar.hu

Mátrix invertálása


202

www.tankonyvtar.hu

Feladat Készítsen programot, amely kiszámítja a matrix.txt fájlban található mátrix inverzét! Oldja meg a feladatot soros és párhuzamos algoritmussal is!

Megjegyzések – A párhuzamos implementáció során célszerű a Gauss-elimináció „elimináció” és „visszahelyettesítés” fázisait összevonni. – Célszerű az elimináció belső (soronkénti) lépéseit párhuzamosítani.


203

www.tankonyvtar.hu

Mátrixinvertálás (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// elimináció for (int i = 0; i < mátrix.GetLength(0); ++i) { for (int j = i + 1; j < mátrix.GetLength(1); ++j) mátrix[i, j] /= mátrix[i, i]; for (int j = 0; j < inverz.GetLength(1); ++j) inverz[i, j] /= mátrix[i, i]; mátrix[i, i] = 1;

}

for (int k = i + 1; k < mátrix.GetLength(0); ++k) { for (int j = i + 1; j < mátrix.GetLength(1); ++j) mátrix[k, j] -= mátrix[i, j] * mátrix[k, i]; for (int j = 0; j < inverz.GetLength(1); ++j) inverz[k, j] -= inverz[i, j] * mátrix[k, i]; mátrix[k, i] = 0; }


Program.cs 204

www.tankonyvtar.hu

Mátrixinvertálás (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// viszahelyettesítés for (int i = mátrix.GetLength(0) - 1; i >= 0; --i) { for (int j = mátrix.GetLength(1) - 1; j > i; --j) mátrix[i, j] /= mátrix[i, i]; for (int j = 0; j < inverz.GetLength(1); ++j) inverz[i, j] /= mátrix[i, i]; mátrix[i, i] = 1;

}

for (int k = i - 1; k >= 0; --k) { for (int j = i - 1; j >= 0; --j) mátrix[k, j] -= mátrix[i, j] * mátrix[k, i]; for (int j = 0; j < inverz.GetLength(1); ++j) inverz[k, j] -= inverz[i, j] * mátrix[k, i]; mátrix[k, i] = 0; }


Program.cs 205

www.tankonyvtar.hu


struct SzálParaméter { public double[,] Mátrix; public int SorIndex; public int StartIndex; public int Hossz; public double[,] Inverz; }


Program.cs 206

www.tankonyvtar.hu

Szálfüggvény 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static void Szálfüggvény(object obj) { SzálParaméter param = (SzálParaméter)obj; for (int k = param.StartIndex; k < param.StartIndex + param.Hossz; ++k) { if (k != param.SorIndex) { for (int j = 0; j < param.Mátrix.GetLength(1); ++j) if (j != param.SorIndex) param.Mátrix[k, j] -= param.Mátrix[param.SorIndex, j] * param.Mátrix[k, param.SorIndex];

}

}

}

for (int j = 0; j < param.Inverz.GetLength(1); ++j) param.Inverz[k, j] -= param.Inverz[param.SorIndex, j] * param.Mátrix[k, param.SorIndex]; param.Mátrix[k, param.SorIndex] = 0;



Program.cs 207

www.tankonyvtar.hu

Szálkezelés 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

for (int i = 0; i < mátrix.GetLength(0); ++i) { for (int j = i + 1; j < mátrix.GetLength(1); ++j) mátrix[i, j] /= mátrix[i, i]; for (int j = 0; j < inverz.GetLength(1); ++j) inverz[i, j] /= mátrix[i, i]; mátrix[i, i] = 1; lefutottSzálak = 0; for (int j = 0; j < szálakSzáma; ++j) { SzálParaméter paraméter; paraméter.Mátrix = mátrix; paraméter.SorIndex = i; paraméter.Hossz = mátrix.GetLength(0) / szálakSzáma; paraméter.StartIndex = j * paraméter.Hossz; paraméter.Inverz = inverz; }

}


while (lefutottSzálak < szálakSzáma) Thread.Sleep(1);


Program.cs 208

www.tankonyvtar.hu

Lineáris egyenletrendszerek megoldása


209

www.tankonyvtar.hu

Lineáris egyenletrendszerek megoldása • Feladat – Oldjuk meg az A * x = b lineáris egyenletrendszert.

• Megoldás – x = A-1 * b

• A feladat megoldható a mátrixinvertálás és szorzás összeépítésével vagy az invertáláshoz hasonló Gausseliminációval. • Lépésszám – Függvényosztály: Θ(n3)


210

www.tankonyvtar.hu

Feladat Készítsen programot, amely megoldja a matrix.txt fájlban található mátrix és a vektor.txt fájlban található vektor által meghatározott lineáris egyenletrendszert! Oldja meg a feladatot soros és párhuzamos algoritmussal is! Megjegyzés – A párhuzamos implementációt célszerű az invertáláshoz hasonló módon elkészíteni.


211

www.tankonyvtar.hu




212

www.tankonyvtar.hu




213

www.tankonyvtar.hu

8. óra Gráfalgoritmusok (1) Gráfalgoritmusok

Szélességi keresés Mélységi keresés Tranzitív lezárt Irodalomjegyzék


214

www.tankonyvtar.hu

Gráfalgoritmusok


215

www.tankonyvtar.hu

Fájlformátum (graf.txt) • 1. sor: irányított-e a gráf. – I = irányított – N = irányítatlan

• 2. sor: a gráf csúcsainak száma. • 3. sor: a gráf éleinek száma. • 4. sortól: – A gráf csúcsainak cimkéje. – A gráf élei (csúcs1, csúcs2) formátumban.


216

www.tankonyvtar.hu

Fájlformátum (graf.txt)


217

www.tankonyvtar.hu

Gráfadatok beolvasása 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

private static Gráf<string, bool> Beolvas() { StreamReader input = new StreamReader(inputFile); Gráf<string, bool> gráf = null; string típus = input.ReadLine(); if (típus == "I") gráf = new IrányítottGráf<string, bool>(); else gráf = new IrányítatlanGráf<string, bool>(); int csúcsszám = Convert.ToInt32(input.ReadLine()); int élszám = Convert.ToInt32(input.ReadLine()); for (int i = 0; i < csúcsszám; ++i) gráf.ÚjCsúcs(input.ReadLine()); for (int i = 0; i < élszám; ++i) { string[] csúcspár = input.ReadLine().Split(','); gráf.ÚjÉl(csúcspár[0], csúcspár[1], true); } input.Close(); }

return gráf;


Program.cs 218

www.tankonyvtar.hu

Gráfok névtér • Gráf < Csúcscimke, Élcimke > osztály – A speciális gráfok közös absztrakt őse. – A csúcsokat listában tárolja. – Az éleket komplex asszociatív tömbben tárolja.

• IrányítottGráf < Csúcscimke, Élcimke > osztály – Irányított gráfokat reprezentáló osztály.

• IrányítatlanGráf < Csúcscimke, Élcimke > osztály – Irányítatlan gráfokat reprezentáló osztály. – Egy irányítatlan élt 2 irányított él formájában tárolja.

• GráfException osztály – Kivételosztály a hibák jelzésére.


219

www.tankonyvtar.hu

Szélességi keresés


220

www.tankonyvtar.hu

Szélességi keresés/Szélességi bejárás • Feladat – Soroljuk fel a gráf csúcsait úgy, hogy először a csúcs közvetlen szomszédait járjuk be, majd azok szomszédait és így tovább, amíg valamennyi csúcsot be nem jártunk.

• A felsorolás helyett/közben tetszőleges művelet végezhető a csúcsokkal. • Lépésszám – Függvényosztály: Θ(V + E)


221

www.tankonyvtar.hu

Feladat Implementálja a szélességi keresés algoritmusát! Jelenítse meg a graf.txt fájlban lévő gráf csúcsait a képernyőn a bejárás sorrendjében!


222

www.tankonyvtar.hu

Szélességi keresés (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

List<string> bejárt = new List<string>(); Queue<string> előjegyzett = new Queue<string>(); foreach (string cimke in gráf.Csúcsok) { előjegyzett.Enqueue(cimke); while (előjegyzett.Count > 0) { string aktuális = előjegyzett.Dequeue(); if (!bejárt.Contains(aktuális)) { Console.WriteLine(aktuális); // A bejáráskor a csúccsal végezendő művelet bejárt.Add(aktuális);

}

}

}

foreach (string c in gráf.Szomszédok(aktuális)) előjegyzett.Enqueue(c);


Program.cs 223

www.tankonyvtar.hu

Szélességi keresés párhuzamosítása • Nem lehet „általános” párhuzamos változatot készíteni. – A bejárás során nagyon fontos a sorrend! – Egy párhuzamos implementáció elronthatja ezt a sorrendet.

• A következő példa szélességi jellegű bejárást valósít meg. – Nagyon sok múlik a szálak ütemezésén. – A bejárás a szélességi keresés módszerét alkalmazza, de apróbb sorrendcserék előfordulhatnak. – Nem determinisztikus!!!

• Különböző párhuzamos architektúrákra optimalizált speciális algoritmusváltozatok előállíthatók.


224

www.tankonyvtar.hu

Szálak indítása 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

foreach (string cimke in gráf.Csúcsok) { if (!bejárt.Contains(cimke)) { előjegyzett.Enqueue(cimke); for (int i = 0; i < szálakSzáma; ++i) { SzálParaméter paraméter; paraméter.Gráf = gráf; paraméter.Bejárt = bejárt; paraméter.Előjegyzett = előjegyzett; ThreadPool.QueueUserWorkItem(new WaitCallback(Szálfüggvény), paraméter); }

}

}

while (lefutottSzálak < szálakSzáma) Thread.Sleep(1);


Program.cs 225

www.tankonyvtar.hu

Szálfüggvény 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

SzálParaméter param = (SzálParaméter)obj; while (true) { string aktuális = null; lock (param.Előjegyzett) { if (param.Előjegyzett.Count == 0) break; aktuális = param.Előjegyzett.Dequeue(); lock (param.Bejárt) { if (!param.Bejárt.Contains(aktuális)) { param.Bejárt.Add(aktuális); foreach (string c in param.Gráf.Szomszédok(aktuális)) param.Előjegyzett.Enqueue(c); }


Program.cs 226

www.tankonyvtar.hu

Szálfüggvény 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

}

}

}

else aktuális = null;

if (aktuális != null) // A bejáráskor a csúccsal végezendő művelet



Program.cs 227

www.tankonyvtar.hu

Mélységi keresés


228

www.tankonyvtar.hu

Mélységi keresés/Mélységi bejárás • Feladat – Soroljuk fel a gráf csúcsait úgy, hogy egy csúcsból végigjárjuk a belőle induló utakat (a visszalépéses kereséshez hasonló).

• A felsorolás helyett/közben tetszőleges művelet végezhető a csúcsokkal. • A szélességi kereséssel azonos implementáció. – A szélességi keresésnél sort használtunk a várakozó elemek tárolására. – Itt vermet kell használni.

• Lépésszám – Függvényosztály: Θ(V + E)


229

www.tankonyvtar.hu

Feladat Implementálja a mélységi keresés algoritmusát! Jelenítse meg a graf.txt fájlban lévő gráf csúcsait a képernyőn a bejárás sorrendjében! Készítse el a soros és a szélességi kereséshez hasonló párhuzamos implementációkat is!


230

www.tankonyvtar.hu

Tranzitív lezárt


231

www.tankonyvtar.hu

Tranzitív lezárt előállítása • Feladat – Adott egy G=(V, E) gráf. – Állítsuk elő azt a G’ gráfot, amelynek csúcsai azonosak G csúcsaival, élei pedig megfeleltethetők egy útnak G-ben (G’ a G tranzitív lezártja).

• Lépésszám – Függvényosztály: Θ(V * E2)


232

www.tankonyvtar.hu

Feladat Keresse meg a graf.txt fájlban lévő gráf tranzitív lezártját! Készítsen soros és párhuzamos implementációt is az algoritmusról!

Megjegyzés – A párhuzamosítást célszerű az egyes csúcsokból kiindulva elvégezni.


233

www.tankonyvtar.hu

Tranzitív lezárt előállítása (Soros) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Gráf<string, bool> lezárt = null; if (gráf is IrányítatlanGráf<string, bool>) lezárt = (IrányítatlanGráf<string, bool>)gráf.Clone(); else lezárt = (IrányítottGráf<string, bool>)gráf.Clone(); for (int i = 0; i < lezárt.Csúcsszám; ++i) { foreach (string c1 in lezárt.Csúcsok) { foreach (string c2 in lezárt.Csúcsok) { if (lezárt.VanÉl(c1, c2)) { foreach (string c3 in lezárt.Csúcsok) if (lezárt.VanÉl(c2, c3) && !lezárt.VanÉl(c1, c3)) lezárt.ÚjÉl(c1, c3, lezárt.Él(c2, c3)); } } } }


Program.cs 234

www.tankonyvtar.hu


struct SzálParaméter { public Gráf<string, bool> Lezárt; public string Csúcs; }


Program.cs 235

www.tankonyvtar.hu

Szálfüggvény 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static void Szálfüggvény(object obj) { SzálParaméter param = (SzálParaméter)obj; foreach (string c2 in param.Lezárt.Csúcsok) { if (param.Lezárt.VanÉl(param.Csúcs, c2)) { foreach (string c3 in param.Lezárt.Csúcsok) if (param.Lezárt.VanÉl(c2, c3) && !param.Lezárt.VanÉl(param.Csúcs, c3)) param.Lezárt.ÚjÉl(param.Csúcs, c3, param.Lezárt.Él(c2, c3)); } }

}



Program.cs 236

www.tankonyvtar.hu




237

www.tankonyvtar.hu




238

www.tankonyvtar.hu

9. óra Gráfalgoritmusok (2) Gráfalgoritmusok

Topológikus rendezés Erősen összefüggő komponensek Minimális súlyú feszítőfa Legrövidebb út Irodalomjegyzék


239

www.tankonyvtar.hu

Gráfalgoritmusok


240

www.tankonyvtar.hu

Topológikus rendezés


241

www.tankonyvtar.hu

Topológikus rendezés • Feladat – Rendezzük egy irányított gráf csúcsait úgy sorba, hogy semelyik csúcsot sem előz meg olyan, amelyikbe a csúcsból vezet irányított út.

• Megoldás – Végezzünk mélységi keresést a csúcsokon, majd amikor egy csúcsból induló minden utat bejártunk, helyezzük a csúcsot egy lista elejére.



242

www.tankonyvtar.hu

Topológikus rendezés


243

www.tankonyvtar.hu

Feladat Implementálja a topológikus rendezés algoritmusát a graf.txt fájlban lévő gráf csúcsainak rendezéséhez!


244

www.tankonyvtar.hu

Topológikus rendezés 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static void Rendez(Gráf<string, bool> gráf, string csúcs, List<string> bejárt, List<string> rendezett) { bejárt.Add(csúcs); foreach (string szomszéd in gráf.Szomszédok(csúcs)) { if (!bejárt.Contains(szomszéd)) Rendez(gráf, szomszéd, bejárt, rendezett); } }

rendezett.Insert(0, csúcs);


Program.cs 245

www.tankonyvtar.hu

Erősen összefüggő komponensek


246

www.tankonyvtar.hu

Erősen összefüggő komponensek keresése • Feladat – Rendezzük egy irányított gráf csúcsait úgy sorba, hogy semelyik csúcsot sem előz meg olyan, amelyikbe a csúcsból vezet irányított út.

• Megoldás – Végezzünk mélységi keresést a csúcsokon, majd amikor egy csúcsból induló minden utat bejártunk, helyezzük a csúcsot egy lista elejére.



247

www.tankonyvtar.hu

Erősen összefüggő komponensek keresése


248

www.tankonyvtar.hu

Feladat Határozza meg a graf.txt fájlban lévő gráf erősen összefüggő komponenseit!


249

www.tankonyvtar.hu

Erősen összefüggő komponensek keresése 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

List<string> bejárt = new List<string>(); List<string> rendezett = new List<string>(); foreach (string cimke in gráf.Csúcsok) { if (!bejárt.Contains(cimke)) Rendez(gráf, cimke, bejárt, rendezett); } Gráf<string, bool> transzponált = gráf.Transzponál(); Stack<string> előjegyzett = new Stack<string>(); bejárt.Clear(); foreach (string cimke in rendezett) { StringBuilder komponens = new StringBuilder(); előjegyzett.Push(cimke);


Program.cs 250

www.tankonyvtar.hu

Erősen összefüggő komponensek keresése 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

while (előjegyzett.Count > 0) { string aktuális = előjegyzett.Pop(); if (!bejárt.Contains(aktuális)) { komponens.AppendFormat("{0}\t", aktuális); bejárt.Add(aktuális);

}

}

}

foreach (string c in transzponált.Szomszédok(aktuális)) előjegyzett.Push(c);

if (komponens.Length > 0) Console.WriteLine("Komponens: {0}", komponens.ToString());


Program.cs 251

www.tankonyvtar.hu

Fájlformátum (graf.txt) • Élsúlyozott gráfok. • 1. sor: irányított-e a gráf. – I = irányított. – N = irányítatlan.

• 2. sor: a gráf csúcsainak száma. • 3. sor: a gráf éleinek száma. • 4. sortól: – A gráf csúcsainak cimkéje. – A gráf élei (csúcs1, csúcs2, súly) formátumban.


252

www.tankonyvtar.hu

Fájlformátum (graf.txt)


253

www.tankonyvtar.hu

Minimális súlyú feszítőfa


254

www.tankonyvtar.hu

Minimális súlyú feszítőfa meghatározása • Feladat – Adott egy G=(V, E) gráf. – Keressük meg azt a G’ gráfot, amelynek csúcsai azonosak G csúcsaival élei pedig G éleinek részhalmaza úgy, hogy G’ fa legyen és az élsúlyainak összege minimális legyen.

• Megoldás (Prim algoritmus) – Rendezzük G éleit súlyuk szerint növekvő sorrendbe. – Vizsgáljuk meg a fenti sorrendben G minden „e” élét, ha az él hozzáadásával G’-ben nem keletkezik kör, akkor vegyük hozzá G’ éleihez (különben ne).

• Lépésszám – Függvényosztály: Θ((E + V) * logV)


255

www.tankonyvtar.hu

Minimális súlyú feszítőfa meghatározása


256

www.tankonyvtar.hu

Feladat Határozza meg a graf.txt fájlban lévő gráf minimális súlyú feszitőfáját!


257

www.tankonyvtar.hu

Minimális súlyú feszítőfa meghatározása 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Dictionary>> élek = new Dictionary>>(); foreach (string csúcs in gráf.Csúcsok) { foreach (string csúcs2 in gráf.Csúcsok) { if (gráf.VanÉl(csúcs, csúcs2)) { if (!élek.ContainsKey(gráf.Él(csúcs, csúcs2))) élek[gráf.Él(csúcs, csúcs2)] = new List>();

}

}

}

élek[gráf.Él(csúcs, csúcs2)].Add(new KeyValuePair<string, string>(csúcs, csúcs2));


Program.cs 258

www.tankonyvtar.hu

Minimális súlyú feszítőfa meghatározása 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

for (int i = 0; i <= élek.Keys.Max(); ++i) { if (élek.ContainsKey(i)) { foreach (KeyValuePair<string, string> pár in élek[i]) { if (komponensek[pár.Key] != komponensek[pár.Value]) { feszítőfa.ÚjÉl(pár.Key, pár.Value, i); komponensek[pár.Value] = komponensek[pár.Key]; } } } }


Program.cs 259

www.tankonyvtar.hu

Legrövidebb út


260

www.tankonyvtar.hu

Legrövidebb út keresése • Feladat – Keressük meg egy gráfban két csúcs közötti legrövidebb utat.

• Megoldás (Dijkstra algoritmus) – A kiválasztott csúcsból kiindulva keressük meg a hozzá legközelebb lévő csúcsot, majd azt vegyük hozzá a kiindulási csúcshoz. – Az így kapott részgráfot folyamatosan bővítsük a csúcsaihoz legközelebbi csúccsal.

• Az algoritmus eredménye a kiválasztott csúcs és az összes többi közötti legrövidebb utak. • Lépésszám – Függvényosztály: Θ((E + V) * logV)


261

www.tankonyvtar.hu

Legrövidebb út keresése


262

www.tankonyvtar.hu

Feladat Határozza meg a graf.txt fájlban lévő gráfban a „második” csúcsból kiinduló legrövidebb utakat!


263

www.tankonyvtar.hu

Legrövidebb út keresése 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 a 29

while (csúcsok.Count > 0) { string minCsúcs = null; int minTávolság = int.MaxValue; foreach (string cimke in csúcsok) { if (távolság.ContainsKey(cimke) && távolság[cimke] < minTávolság) { minCsúcs = cimke; minTávolság = távolság[cimke]; } } if (minCsúcs == null) break; csúcsok.Remove(minCsúcs);

}

foreach (string szomszéd in gráf.Szomszédok(minCsúcs)) { if (!távolság.ContainsKey(szomszéd) || távolság[szomszéd] > távolság[minCsúcs] + gráf.Él(minCsúcs, szomszéd)) { távolság[szomszéd] = távolság[minCsúcs] + gráf.Él(minCsúcs, szomszéd); előző[szomszéd] = minCsúcs; } }


Program.cs 264

www.tankonyvtar.hu

Házi feladat Próbálja ki a példaprogramokat! Kísérelje meg elkészíteni azok párhuzamos változatait!


265

www.tankonyvtar.hu




266

www.tankonyvtar.hu

10. óra Geometria Elosztott rendszerek Algoritmusok

Legközelebbi pontpár Pontok konvex burka Irodalomjegyzék


267

www.tankonyvtar.hu

Elosztott rendszerek


268

www.tankonyvtar.hu

Algoritmusok


269

www.tankonyvtar.hu

Elosztott algoritmusok • Párhuzamos algoritmusok, amelyek részei különböző számítógépeken futnak. • Segítségükkel több egymagos géppel is lehet párhuzamos környezetet előállítani. • Előnyük, hogy alacsony számítási kapacitású eszközökből nagy számítási kapacitású rendszer rakható össze. • Hátrányuk az adatok elosztásából fakadó kommunikációs költség. • Leggyakoribb alkalmazásuk a nagy adatmennyiséget feldolgozó programok (pl. SETI@Home). © Kurdi Zsombor, ÓE NIK

270

www.tankonyvtar.hu

Elosztott algoritmusok megvalósítása • Egy szerver program, amely az adatok elosztásával és a beérkező részeredmények feldolgozásával foglalkozik. • Több kliens, amely a hozzájuk rendelt (elküldött) adatok feldolgozását végzi.

• Hasonlóan a korábbi párhuzamos algoritmusokhoz, itt is alkalmazhatunk adatmegosztást és feladatmegosztást is.


271

www.tankonyvtar.hu

Elosztott algoritmus adatmegosztással • Lásd Példaprogram (ElosztottLineárisKeresés).

• TCP/IP alapú kommunikáció. • A szerver várakozik a kliensekre. • Kliens csatlakozása esetén elküldi a feldolgozandó adat egy részét. • A kliensek válaszként elküldik az algoritmus eredményét, amelyből a szerver kiszámolja a végeredményt.


272

www.tankonyvtar.hu

Elosztott algoritmus feladatmegosztással • Lásd Példaprogram (ElosztottGyökvonás).

TCP/IP alapú kommunikáció. A szerver várakozik a kliensekre. Minden kliens egyben szerver is. Klienslánc épül fel, amelynek mindkét végén a szerver áll. A szerver az első kliensnek küldi a feldolgozandó adatokat. Minden kliens az utána következőnek küldi az általa kiszámolt részeredményt. • Az utolsó kliens a végeredményt állítja elő és küldi a szervernek.

• • • • • •


273

www.tankonyvtar.hu

Legközelebbi pontpár


274

www.tankonyvtar.hu

Legközelebbi pontpár keresése • Feladat – Adott n db pont a síkban. – Keressük meg azt a két pontot, amelyek euklideszi távolsága a legkisebb.

• Brute-Force megoldás – Számítsuk ki minden pontpár távolságát és ezek közül válasszuk ki a minimálisat. – Ez Θ(n2) lépésben megoldást ad.

• Gyorsabb megoldás – Oszd meg és uralkodj elve. – O(n * logn) lépésben megtalálja a megoldást.


275

www.tankonyvtar.hu

Legközelebbi pontpár keresése • Osszuk ketté a halmazt l függőleges egyenessel (PL és PR-re). – PL minden pontja az egyenestől balra esik, vagy illeszkedik l-re. – PR minden pontja az egyenestől jobbra esik, vagy illeszkedik l-re.

• Legyen – XL és XR a részhalmazok pontjai x koordinátáik szerint növekvően rendezve. – YL és YR a részhalmazok pontjai y koordinátáik szerint növekvően rendezve.

• Keressük meg a legközelebbi pontpárt PL-ben és PR-ben (rekurzívan alkalmazva az algoritmus lépéseit). – Legyen δL és δR a két legkisebb távolság. – δ = min{δL, δR}

• A legközelebbi pontpárok vagy a két részhalmazból kiválasztott pontpárok vagy az l középvonalú 2δ szélességű sávban lévő pontpárok valamelyike. © Kurdi Zsombor, ÓE NIK

276

www.tankonyvtar.hu

Legközelebbi pontpár keresése • A 2δ szélességű sáv ellenőrzése – Y’ legyen Y azon elemei, amelyek benne vannak a sávban.

– Y’ minden pontjához próbáljunk meg találni δ-nál közelebbi pontot (BruteForce algoritmussal).

– Ha találtunk ilyen pontot, akkor ezek közül a legközelebbiek adják a megoldást.


277

www.tankonyvtar.hu

Feladat Implementálja az előbb leírt algoritmust! Véletlenszerűen generált ponthalmazból válassza ki a két legközelebbi pontot! Készítse el a program elosztott változatát is!


278

www.tankonyvtar.hu

Pontok konvex burka


279

www.tankonyvtar.hu

Pontok konvex burkának meghatározása • Feladat – Adott n db pont a síkban. – Keressük meg azokat a pontokat, amelyeket összekötve egy olyan konvex sokszöget kapunk, amelyen kívül egyetlen pont sincs.

• Graham-pásztázás algoritmusa – Egy pontból kiindulva építi fel a burkot. – Alapgondolata: a konvex sokszög előállításához mindig ugyanabba az irányba szabad csak fordulni a pontokban. – O(n * logn) lépésben megtalálja a megoldást.


280

www.tankonyvtar.hu

Graham-pásztázás • Legyen p0 a pontok közül az, amelynek a legkisebb az y koordinátája (ha több ilyen is van, akkor ezek közül a legkisebb x koordinátájú). • p1,p2,p3,…,pn a többi pont p0-ra vonatkozó polárszögeik szerint az óramutató járásával ellentétes sorrendben (ha több azonos polárszögű pont is van, akkor csak a p0-tól legtávolabbit vegyük). • Tegyük bele egy verembe p0, p1 és p2-t. • Sorban a többi pontra vizsgáljuk, hogy a verem felső két eleme és a vizsgált pont alkotta szög bal fordulat-e (keresztszorzatokkal ellenőrizhető). – Ha nem, akkor vegyük ki a legfelső elemet a veremből (és vizsgáljuk újra). – Ha igen, akkor tegyük a vizsgált pontot a verem tetejére.


281

www.tankonyvtar.hu

Graham-pásztázás


282

www.tankonyvtar.hu

Feladat Implementálja az előbb leírt algoritmust! Határozza meg egy véletlenszerűen generált ponthalmaz konvex burkát! Készítse el a program elosztott változatát is!


283

www.tankonyvtar.hu




284

www.tankonyvtar.hu

11. óra Tömörítés Fogalmak Módszerek Példák Irodalomjegyzék


285

www.tankonyvtar.hu

Tömörítés


286

www.tankonyvtar.hu

Fogalmak


287

www.tankonyvtar.hu

Fogalmak • Információtartalom – Adott adathalmaz elemeinek tárolásához minimálisan szükséges bitek száma.

• Tömörítés – Adatok tárolása kisebb helyen.

• Kicsomagolás – Tömörített adatokból az eredeti visszaállítása.


288

www.tankonyvtar.hu

Módszerek


289

www.tankonyvtar.hu

Módszerek • A tömörítő módszerek az adatelemek (bitek/bitsorozatok) átkódolásával érik el a kisebb tárigényt. • Csoportosítás – Veszteségmentes • Az adat információtartalma nem változik. • Olyan adatoknál alkalmazható, ahol fontos az információtartalom megőrzése.

– Veszteséges • Az adat információtartalma csökken. • Olyan adatoknál alkalmazható, ahol a veszteség nem érzékelhető. (Pl. képek, hangok ...)


290

www.tankonyvtar.hu

Példák


291

www.tankonyvtar.hu

Példa • Tömörítendő adat: „ALMA” • ACSII kódolás: 01000001 01001100 01001101 01000001 (32bit) • Az adat információtartalma: 1,5 (bit) – A teljes adat tárolásához minimum 6 bit kell.

• Kódoljuk 2 biten a betűket (A = 00, L = 01, M = 10) – 00011000 (8 bit)

• Alkalmazzunk változó hosszú prefix kódot (A = 0, L = 10, M = 11) – 010110 (6 bit)


292

www.tankonyvtar.hu

Huffman-algoritmus • Az adatelemeket előfordulási gyakoriságuk alapján rendezi. • Minél gyakoribb egy elem, annál rövidebb kódot rendel hozzá.

• Módszer – A gyakoriságok alapján bináris fát kell felépíteni az adatelemekből (amelynek levelei az adatelemek). – A fa minden csúcsában a bal oldali gyermeket 0-val, a jobb oldalit 1-gyel címkézzük. – Az egyes levelek kódjai a gyökérből a levélig vezető út címkéi lesznek.


293

www.tankonyvtar.hu

Huffman-fa


294

www.tankonyvtar.hu

Feladat Implementálja a Huffman-algoritmust! Tömörítse a segítségével a szoveg.txt fájlban lévő szöveget! Készítse el a program párhuzamos változatát is!


295

www.tankonyvtar.hu




296

www.tankonyvtar.hu

12. óra Titkosítás Fogalmak Algoritmusok Példák Irodalomjegyzék


297

www.tankonyvtar.hu

Fogalmak


298

www.tankonyvtar.hu

Fogalmak • Titkosítás – Adatok mások számára értelmezhetetlenné tétele.

• Visszafejtés – Titkosított adatból az eredeti visszaállítása.

• Nyílt szöveg – A titkosítandó adat.

• Titkos szöveg – A titkosított adat.

• Kulcs – A titkosítási folyamat paramétere.


299

www.tankonyvtar.hu

Algoritmusok


300

www.tankonyvtar.hu

Algoritmusok csoportosítása • Kulcshasználat szerint egy titkosító algoritmus lehet – titkos kulcsú, – nyilvános kulcsú.

• Titkos kulcsú algoritmus – – – –

Egyetlen kulcsot használ titkosításra és visszafejtésre. Gyors. Körülményes kulcsmegosztás. Kommunikációtitkosítására használják.

• Nyilvános kulcsú algoritmus – – – –

Két kulcsot (privát és nyilvános kulcs) használ. Lassú. Egyszerű kulcsmegoldás. Tárolt adatok titkosítására használják.


301

www.tankonyvtar.hu

Titkos kulcsú algoritmus


302

www.tankonyvtar.hu

Nyilvános kulcsú algoritmus


303

www.tankonyvtar.hu

Példák


304

www.tankonyvtar.hu

Példák • Titkos kulcsú algoritmusok – – – – –

DES (Data Encryption Standard). AES (Advanced Encryption Standard). IDEA (International Data Encryption Algorithm). Blowfish. RC4.

• Nyilvános kulcsú algoritmusok – RSA. – Elliptikus görbék módszere.


305

www.tankonyvtar.hu

A DES algoritmus • • • • • •

1976-ban publikálták (a kutatás 1970 körül kezdődött). 2002-ben publikálták az AES (Rijndael) algoritmust a leváltására. Ma is használatban van. Gyenge/rövid távú védelmet biztosít. Többszöri alkalmazással növelhetjük a védelmi szintet (pl. 3DES). Működése – A nyílt szöveg 64 bites blokkjait titkosítja. – 64 bites kulcsot kell megadni. • Ebből csak 56 bitet használ az algoritmus. • 16 db 48 bites „részkulcs” formájában használja az algoritmus.


306

www.tankonyvtar.hu

A DES algoritmus (Kulcskezelés)


307

www.tankonyvtar.hu

A DES algoritmus (Titkosítás/Visszafejtés)


308

www.tankonyvtar.hu

A DES algoritmus (Feistel-függvény)


309

www.tankonyvtar.hu

Feladat Implementálja a DES algoritmust! Titkosítsa a szoveg.tx fájlban található szöveget!


310

www.tankonyvtar.hu

Párhuzamosítás • Mivel a blokkok titkosítása egymástól független, az adatelosztás módszerét könnyen alkalmazhatjuk. • A feladatelosztás módszere is használható: – A titkosítás/visszafejtés 16 lépése elvégezhető külön szálakon. – Az egyes szálak egy adott részkulcs felhasználásával transzformálják a hozzájuk kerülő blokkot. – Az utolsó szál állítja elő a titkosítás végeredményét. – Az egymás után következő szálat szinkronizációja fontos (célszerű a termelőfogyasztó modellt használni).


311

www.tankonyvtar.hu

Titkosítás 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

private static void Szálfüggvény(object obj) { int index = (int)obj; if (buffer != null) // ide írjuk a végeredményt { for (int i = 0; i < buffer.Length; ++i) { szemaforokÍrás[index].WaitOne(); // mergérkezett-e az input BitArray újBalFél = Rész(blokkok[index].JobbBlokk, 0, blokkok[index].JobbBlokk.Length); BitArray újJobbFél = blokkok[index].BalBlokk.Xor(F(blokkok[index].JobbBlokk, Kulcsok[index])); szemaforokOlvasás[index].Set();

// kiolvastuk az inputot (felülírható)

if (index < 15) { szemaforokOlvasás[index + 1].WaitOne(); // beírhatjuk-e a köv. szál inputját blokkok[index + 1].BalBlokk = újBalFél; blokkok[index + 1].JobbBlokk = újJobbFél;


312


Titkosítás 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

szemaforokÍrás[index + 1].Set(); // következő szál inputja megadva } else { // az utolsó szál előállítja a végeredményt a bufferben BitArray titkosítottBlokk = Permutáció(Összeilleszt(újBalFél, újJobbFél), FP); for (int j = 0; j < Blokkméret; ++j) { buffer[i * Blokkméret + j] = titkosítottBlokk[j]; }

}

}

}

++kiírtBlokkok; }


Program.cs 313

www.tankonyvtar.hu

Házi feladat Próbálja ki a példaprogramot! Kísérelje meg elkészíteni a párhuzamos implementációt!


314

www.tankonyvtar.hu



•

Data Encryption Standard http://en.wikipedia.org/wiki/Data_Encryption_Standard


315

www.tankonyvtar.hu

ALGORITMUSOK OPTIMÁLIS MEGVALÓSÍTÁSA PÁRHUZAMOS KÖRNYEZETBEN

Recommend Documents