1. Funkcionális programozás paradigma (Balázs)(Shagreen) 2. Logikai programozás paradigma(még kidolgozás alatt Shagreen) 3. Strukturált programozás paradigma(Shagreen) 4. Alapvető programozási tételek (N-1) (összegzés, számlálás, maximumkeresés, lineáris keresés, logaritmikus keresés) (AB) 5. Alapvető programozási tételek (N-N) (szétválogatás, halmazműveletek) (AB) 6. Programozási tételek összeépítése (AB) 9. n*n-es rendezések (alapelvek, algoritmusok) (AB) 10. Haladó rendezések I. (Kupacrendezés, Shell rendezés) (AB) 11. Haladó rendezések II. (Szétosztó-, Leszámláló-, Radix-, Edényrendezés) (Shagreen) 15. Rekurzió fogalma, gyakorlati megvalósítása(Shagreen) 16. Visszalépéses keresés (általános formája, gyakorlati példák)(Shagreen) 17. Programtranszformációk (rekurzív – iteratív átalakítások)(Shagreen) 18. Adatszerkezetek, láncolt listák, egyszerű láncolt listák műveletei I. (új elem felvétele, bejárás, törlés)(Shagreen) 19. Adatszerkezetek, láncolt listák, speciális listák műveletei II. (rendezett láncolt lista, többirányú, többszörösen láncolt lista, strázsa)(Shagreen) 20. B-fa adatszerkezet, B-fába való beszúrás algoritmusa (B-fa jellemzői, előnyei, felépítése, új elem felvétele)(Shagreen) 21. B-fa adatszerkezet, B-fából való törlés algoritmusa (B-fa jellemzői, előnyei, felépítése, törlés)(Shagreen) 22. Fa adatszerkezetek, bináris fák alapműveletei (új elem felvétele, bejárások, törlés)(Shagreen) 23. Fa adatszerkezetek, piros-fekete fa adatszerkezet (forgatások, új elem felvétele, törlés)(Shagreen) 24. Gráfok I. (körmentes út keresése (labirintus); legrövidebb út keresése Dijkstra algoritmusával)(Shagreen) 25. Gráfok II. (Kruskal algoritmus és alkalmazásai) (Shagreen) 26. Gráfok III. (topológiai rendezés és alkalmazásai)(Shagreen) 27. Hasító táblázatok (alapelvek, hasító függvények, kulcsütközések feloldása)(Shagreen) 64. Hagyományos tesztelési és hibakeresési módszerek(Shagreen) 65. Kivételkezelés (elvi háttere, gyakorlati megvalósítása)(Shagreen)
1
Tartalom 1. Tétel: Funkcionális programozás paradigma ....................................................................................... 4 3. Strukturált programozás paradigma ................................................................................................. 10 4. Alapvető programozási tételek (N-1) ................................................................................................ 12 5. Alapvető programozási tételek (N-N)................................................................................................ 17 6. Programozási tételek összeépítése ................................................................................................... 27 9. N*N -es rendezések (alapelvek, algoritmusok) ................................................................................. 29 10. Haladó Rendezések 1(Kupac & Shell) .............................................................................................. 36 11. Haladó rendezések II ( Szétosztó-, Leszámoló-, Radix-, Edény rendezés ) ...................................... 40 15. Rekurzió fogalma, gyakorlati megvalósítása ................................................................................... 44 16. Visszalépéses keresés (általános formája, gyakorlati példák) ................................................... 47 17. Program transzformációk (rekurzív – iteratív átalakítások) ............................................................ 49 18. Adatszerkezetek, láncolt listák, egyszerű láncolt listák műveletei I. (új elem felvétele, bejárás, törlés) .................................................................................................................................................... 52 Láncolt Lista ....................................................................................................................................... 52 Bejárás ............................................................................................................................................... 54 Új elem felvétele ............................................................................................................................... 54 Törlés ................................................................................................................................................. 54 Teljes lista törlése .............................................................................................................................. 54 19. Adatszerkezetek, láncolt listák, speciális listák műveletei II. (rendezett láncolt lista, többirányú, többszörösen láncolt lista, strázsa) ....................................................................................................... 55 Rendezett láncolt lista ....................................................................................................................... 55 Keresés .......................................................................................................................................... 55 Beszúrás ......................................................................................................................................... 55 Strázsa ............................................................................................................................................... 55 Kétirányú láncolt lista ........................................................................................................................ 56 Többszörösen láncolt lista ................................................................................................................. 56 Ciklikusan láncolt lista ....................................................................................................................... 57 20-21 B-fa adatszerkezet, B-fába való beszúrás algoritmusa (B-fa jellemzői, előnyei, felépítése, új elem felvétele, törlés) ........................................................................................................................... 58 Általánosan a B-fákról: ...................................................................................................................... 58 B-fák műveletei: ................................................................................................................................ 59 Beszúrás:........................................................................................................................................ 59 Törlés ............................................................................................................................................. 60 22. Fa adatszerkezetek, bináris fák alapműveletei (új elem felvétele, bejárások, törlés) .................... 63 2
Fa adatszerkezet ................................................................................................................................ 63 Bináris Fa ........................................................................................................................................... 64 Bináris keresőfa (BST) .................................................................................................................... 64 23. Fa adatszerkezetek, piros-fekete fa adatszerkezet (forgatások, új elem felvétele, törlés)............. 68 Piros fekete fa:................................................................................................................................... 68 Forgatás ......................................................................................................................................... 69 Beszúrás ......................................................................................................................................... 70 Egyéb műveletek ............................................................................................................................... 71 24. Gráfok 1 (Labirintus & Dijkstra) ....................................................................................................... 72 Gráf elmélet:...................................................................................................................................... 72 Labirintus ........................................................................................................................................... 73 Dijkstra............................................................................................................................................... 76 Felhasznált Irodalom ......................................................................................................................... 78 25. Gráfok II. (Kruskal algoritmus és alkalmazásai) ............................................................................... 80 Kruskál ............................................................................................................................................... 81 Példa az algoritmus megvalósítására ................................................................................................ 82 26. Gráfok III. (topológiai rendezés és alkalmazásai) ............................................................................ 83 Topológiai sorrend meghatározásának egy lehetséges megoldása .................................................. 84 27. Hasító táblázatok (alapelvek, hasító függvények, kulcsütközések feloldása) ................................. 85 Hasító függvény: ................................................................................................................................ 85 64. Hagyományos tesztelési és hibakeresési módszerek ...................................................................... 90 Tesztelés: ........................................................................................................................................... 90 Hibakeresés és javítás: ...................................................................................................................... 91 65. Kivételkezelés (elvi háttere, gyakorlati megvalósítása)................................................................... 93 Hagyományos hibakezelés: ............................................................................................................... 93 Kivételkezelés beépített osztályok használatával: ............................................................................ 93 Saját kivételek ................................................................................................................................... 94
3
1. Tétel: Funkcionális programozás paradigma Alapfogalmak, jellemzés: Paradigma, programozási paradigma: Paradigmának nevezzük egy tudományterület általánosan elfogadott nézeteit (fogalmait, szakkifejezéseit) egy adott korszakban, időpontban. Minden feladatmegoldás során paradigmákat használnak a számítástechnikában. A paradigmák egy szemléletmódot, egy probléma - megközelítést, szabályrendszert fogalmaznak meg, amely segítségével egy feladat megoldásának lépései és azok sorrendisége megfogalmazható. A paradigmák gyakorlatban történő megvalósítása a számítási modellek segítségével történik.
Paradigmák szerint 3 nagy csoportra bonthatjuk a programozási nyelveket: 1. Imperatív (procedurális) nyelvek: Az imperatív programozási nyelvek -- például a PASCAL, a C, FORTRAN -- esetében a számítógépnek minden utasítást a programozónak kell megadnia. Ezen nyelvek közös jellemzője, hogy a program fejlesztése értékadó utasítások megfelelő sorrendben történő kiadására koncentrálódik. Az értékadó utasítás baloldalán egy változó áll, a jobb oldalán pedig egy megfelelő típusú kifejezés. A szelekció (elágazás) csak azt a célt szolgálja, hogy bizonyos értékadó utasításokat csak adott esetben kell végrehajtani. A ciklusok pedig azért vannak, hogy az értékadó utasításokat többször is végrehajthassunk. Az értékadó utasítások során részeredményeket számolunk ki – végül megkapjuk a keresett végeredményt.
2. Deklaratív programozási nyelvek A deklaratív programok esetében "magasabb szintű" programokat írunk. Vagyis, az immár klasszikus szófordulattal élve, nem a feladat elvégzésének hogyanjával törődünk, hanem azt programozzuk, hogy MIT szeretnénk a programmal elvégeztetni. A funkcionális nyelveken a kiszámolandó kifejezést adjuk meg, megfelelő mennyiségű bemenő adattal. A programozó munkája a kifejezés kiszámításának leírására szolgál. A program futása közben egyszerűen kiszámítja a szóban forgó kifejezést. Egy funkcionális nyelvben nincs változó, általában nincs ciklus (helyette rekurzió van). Értékadó utasítás sincs, csak függvény visszatérési értékének megadása létezik. A funkcionális nyelvek tipikus felhasználási területének a természettudományos alkalmazások és szakértői rendszerek tekinthetőek. A végrehajtás, a nyelv értelmező, fordító programjától függ. Nem mindig követhetőek a végrehajtott lépések. A változó: a matematikából ismert fogalomnak felel meg,
4
I.
Funkcionális programozás:
A funkcionális programozásban minden entitás függvény. A program legfőbb jellemzője, hogy nincsenek benne változók - ez nagyon megkönnyíti az illető programozási nyelven írt programok helyességének a bizonyítását, illetve megkönnyíti azt, hogy modulokból bizonyítottan helyes programokat rakjunk össze. Funkcionális programozási eszközökkel minden olyan feladat megoldható, amelyik megoldható imperatív nyelven. Egy programban előforduló konstansok is függvényként léteznek (bemenő paraméterrel nem rendelkeznek). A következmény, hogy a "változók" nem változtatják értéküket: minden változó, ha egyszer értéket rendeltünk hozzá, akkor az életciklusa alatt az értéke nem változik. Ez utóbbi tulajdonság nagyon megkönnyíti a funkcionális nyelvekben implementált programok helyességének a bizonyítását. Mivel a funkcionális nyelven írt programok rendkívül megbízhatóak, a nagy kockázatú rendszereknél (pl. a párizsi metró irányító rendszerénél) használják nagy előszeretettel. II.
Logikai programozás:
A logikai programozás esetében a programokat relációkkal specifikáljuk. Az ilyen jellegű nyelvekkel tényeket fogalmazunk meg, és logikai állításokat írunk le. A program futása a logikai következtetésen alapszik, melynek értékét a programozási nyelv a beépített kiértékelő algoritmusa segítségével, a tények és szabályok figyelembevételével, határoz meg. A logikai nyelvek tipikus felhasználási területe a szakértői rendszerek létrehozásához kapcsolódik. A logikai programozás alapjai a tények és az ezeket jellemző szabályok, melyeket együttesen tudásbázisnak nevezünk. 3. Objektum-orientált nyelvek: Az OOP nyelvekben a program működése során egymással kölcsönhatásban álló objektumok kommunikálnak. Az objektumok egymás műveleteit aktiválják, melyeket interface-ek írnak le. Ha egy művelet nem végrehajtható, akkor az adott objektum a hívó félnek szabványos módon (kivételkezelés) jelzi a probléma pontos okát.
Funkcionális programozás paradigma: Összegezve a fentieket a program függvénydefiníciók és függvényhívások sorozata, ezek a függvények kifejezéseket értékelnek ki. Egy függvény ugyanazokkal az argumentumokkal (argumentum = változó) ugyanazt az eredményt adja, nincsenek más állapotok és mellékhatások, csak értékkiszámítás van. Nem számít, hogy mikor hívjuk a függvényt, csak az, hogy melyiket hívjuk. A nyelv alapvető építőkövei a funkciók. Minden függvénynek van neve és nulla vagy több argumentuma. Ugyanazokkal az argumentumokkal a függvény mindig ugyanazt az értéket szolgáltatja. 5
A függvény argumentumai értékek ( lehetnek összetettek ), amiket névvel ellátott, vagy név nélküli adatok, kifejezések, vagy éppen függvények biztosítanak. A rekurzió abszolút természetes a funkcionális nyelvekben, ismétlések és ciklusok helyett éppen a rekurziót használhatjuk.
Gyakorlati alkalmazás DrScheme program segítségével: A DrScheme nevű program egy kevert, azaz imperatív és funkcionális elemeket is tartalmazó program, mely nyelvi szintek hierarchiáját nyújtja ( Begining student: functions, structures, lists ; Intermediate student ; Advanced student ; Scheme language level ), ahol a szintek mind szemantikus, mind szintaktikus, mind a hibaüzenetek szintjén eltérnek. Egy definíciós ablakot és egy interakciós ablakot biztosít a felhasználói kezelőfelülete. Példa egy függvényre: (define fac (lambda (n) (if (= n 0) 1 (* n (fac (- n 1)))))) A Scheme program függvénydefiníciók halmaza, melyeket egymásba lehet ágyazni. A program végrehajtása egy kifejezés kiértékelését jelenti. A matematikai kifejezéseket a lengyel jelölés ( operátor, operandusok ) szerint kell leírni, melynek előnye, hogy nincs szükségünk zárójelek és precedencia-szabályok ismeretére. A függvények formája: (Függvénynév argumentumok ). Az aritmetikai műveletek is lehetnek több argumentumúak (+ 2 3 4 0 10). // Függvényhívás DrScheme nyelvben (define (fgv-név bemenetiparaméter) (művelet bemenetiparaméter bemenetiparaméter)) (define (negyzet n) ( * n n) ) (define nagy-szam ( + (expt 2 10) (expt 3 100))) //210 + 3100 ---> (negyzet 5) 25 > nagy-szam 515377520732011331036461129765621272702107523025
// Függvény definiálás DrScheme nyelvben A felhasználó által definiált függvények névvel nem rendelkező ún. lambda kifejezéseket használnak: (lambda (formális paraméter) kifejtés) Példa: ((lambda (x) ( * x x)) 3) ; 9 ((lambda (x y) (+ x y)) 3 4) ; 7
6
Beépített függvények: •
length, mely megadja az adott lista hosszát
Példa: (length ’(+ 1 2 3)), ahol „ ’ ” jel, megakadályozza a kifejezés kiértékelést, tehát nem 1+2+3=6 lesz, hanem egy 4 elemű lista {+,1,2,3} •
cons ( construct szóbol ), melynek két argumentuma van, és egy rendezett listát vagy párt ad vissza
Példák: (cons '1 '2) mely (1.2) ; (cons '1 ' ( 2 3 4)) mely (1 2 3 4); (cons '(1 2 3) '(4 5 6)) mely ((1 2 3) 4 5 6) •
car, mely a rendezett lista vagy pár első elemét adja vissza
Példák: (car '(123 245 564 898)) mely 123 ; (car '(egy ketto harom) mely egy •
cdr, mely a rendezett pár második elemét vagy a lista fej nélküli részét szolgáltatja
Példák: (cdr '(7 6 5)) mely (6 5) ; (cdr '(5 . 16)) mely 16 listaelem!! ; (cdr '(5 26)) mely (26) lista!! ; (cdr '(it rains every day)) mely (rains every day) ; (cdr (cdr '(a b c d e f))) mely (c d e f) •
list, mely készít egy listát a listaelemekből
Példák: (list 'a) mely (a) ; (list 'a 's 'd) mely (a s d) ; (list '(a b c) '(d e f) '(g h i)) mely ((a b c)(d e f)(g h i))
7
Példák: Általános példák: •
(append '(a b c) '()) mely (a b c)
•
(list '(a b c)
•
(cons '(a b c) '() ) mely ((a b c) )
'() ) mely ((a b c) ())
A cons és a list közötti különbségekre példák: •
(cons '1 '2) mely (1 . 2)
•
(list '1 '2) mely (1 2)
•
(cons '(3 4) '(5 6)) mely ((3 4) 5 6)
•
(list '(3 4) '(5 6)) mely
((3 4) (5 6))
Példa a length, reserve, append hármasra: •
(length '(1 2 3 4 5)) mely 5
•
(length '((1 2 3 4 5) (7 8 9))) mely 2
•
(reverse '( 1 2 3)) mely (3 2 1)
•
(append '(1 2) '(6 7 8 9)) mely (1 2 6 7 8 9)
Egy példa alaklmazás: Tekintsük a (minden x (ha (ember x) (halando x))) listát, és adjuk meg a Scheme kódot, ami a minden, ha illetve ember szavakat előállítja! •
Minden: (car '(minden x (if (ember x) (halando x))))
•
Ha ( vagyis if ): (car (car (cdr (cdr '(minden x (if (ember x) (halando x)))))))
•
Ember: (car (car (cdr(car (cdr (cdr '(minden x (if (ember x) (halando x))))))))).
Matematikai alkalmazások: •
Fibonacci sorozat: (define fib (lambda (n) (if (= n 0) 0 (if (= n 1) 1 (+ (fib (- n 1)) (fib (- n 2)))))))
•
Legnagyobb közös osztó:
•
(define gcd (lambda (a b) (if (= a b) a (if (> a b) (gcd (- a b) b) (gcd a (- b a)))))) Megjegyzés: a program szerint a gcd mint név nem szerepelhet mert beépített név
8
•
Ackermann függvény: A(x,y)={ y+1 ha x=0 ; A(x-1,1) ha y=0 ; A(x-1,(A(x,y-1))) minden más esetben }. Scheme kódja: (define ack (lambda (m n) (if (= m 0) (+ n 1) (if (= n 0) (ack (- m 1) 1) (ack (- m 1) (ack m (- n 1))))))). Az Ackermann függvény példa a kiszámítható, de nem primitíven kiszámítható függvényre.
•
Listaelemek összeadása: (define sum (lambda (lt) (if (null? lt) 0 (+ (car lt) (sum (cdr lt)))))) Példafuttatás: (sum ' (1 2 3)) mely 6. Itt fontos az aposztof használata (') .
•
Listaelemk szorzata: (define szoroz (lambda (lt) (if (null? lt) 1 (* (car lt) (szoroz (cdr lt)))))) Példafuttatás: (sum ' (1 2 3 4)) mely 24. Itt fontos az aposztof használata (') .
Források: http://hu.wikipedia.org/wiki/Sz%C3%A1m%C3%ADt%C3%B3g%C3%A9pes_program http://csharptk.ektf.hu/online/index.html http://cs.ubbcluj.ro/~csatol/log_funk/ http://www.ms.sapientia.ro/~mgyongyi/Funk_Log/logikaifunkcionalis1.pdf
9
3. Strukturált programozás paradigma Paradigma, programozási paradigma: Paradigmának nevezzük egy tudományterület általánosan elfogadott nézeteit (fogalmait, szakkifejezéseit) egy adott korszakban, időpontban. Minden feladatmegoldás során paradigmákat használnak a számítástechnikában. A paradigmák egy szemléletmódot, egy probléma-megközelítést, szabályrendszert határoznak meg, amely segítségével egy feladat megoldásának lépései és azok sorrendisége megfogalmazható. A paradigmák gyakorlatban történő megvalósítása a számítási modellek segítségével történik.
Strukturált programozási paradigma az utasítások szekvenciális végrehajtására alapozza a feladatmegoldást. Szekvenciális végrehajtás alatt az utasítások egymás utáni végrehajtását értjük. Ezt a paradigmát követi a Neumann modell. Neumann modell jellemzői: • • • • •
utasításorientált az egyes műveletek megismételhetők többszörös értékadás jellemző változókon végzi a számításokat soros végrehajtást feltételező modell
Szekvenciális végrehajtás: Az ábra S1-el és S2-vel jelöli a végrehajtandó utasításokat. A végrehajtás során fentről lefelé haladva hajtjuk végre az utasításokat. Először az S1 utasítást hajtjuk végre, majd utána az S2 utasítást. Például: Először felkészülök egy vizsgára, és utána elmegyek vizsgázni. Ábrázolás struktogrammal:
Ábrázolás pszeudokóddal:
10
A szekvenciális végrehajtásban két vezérlési struktúra használható: •
ciklus: Az ábrán L jelöli a ciklusba bekerülés és bennmaradás értékét, S jelöli a ciklusmagot. A ciklusmag addig hajtódik végre, ameddig az L feltétel nem teljesül. Az L feltétel lehet egyszerű és összetett. Egyszerű feltétel például: Addig tanulok, ameddig nem tudom a tananyagot. Összetett feltétel például: Addig tanulok, ameddig nem tudom a tananyagot vagy már levizsgáztam. Ábrázolás struktogrammal: Ábrázolás pszeudokóddal:
•
elágazás: Az ábrán L jelöli az eldöntendő feltételt, az S1 és az S2 pedig a végrehajtandó utasításokat. A végrehajtás során megvizsgáljuk az L feltételt, amennyiben a feltétel igaz, az S1 utasítás hajtódik végre, ellenkező esetben az S2 utasítás. Például: Ha megfelelően felkészültem a vizsgára, akkor sikeresen leteszem, egyébként ismételnem kell. Ábrázolás struktogrammal: Ábrázolás pszeudokóddal:
11
4. Alapvető programozási tételek (N-1) •
•
•
A programozási tételek jól megválasztott, egyszerű feladatok megoldásai – segítségükkel a gyakorlatban szükséges feladatok jelentős része megoldható – helyességük egyszerűen bizonyítható – használatuk célszerű, hiszen (mások által is) jól áttekinthető kódot eredményeznek Egy lehetséges csoportosításuk – egy sorozathoz egy értéket rendelő feladatok – egy sorozathoz egy sorozatot rendelő feladatok – egy sorozathoz több sorozatot rendelő feladatok – több sorozathoz egy sorozatot rendelő feladatok Feldolgozandó intervallum alapján megkülönböztetünk – rögzített intervallumos programozási tételeket – feltételig tartó programozási tételeket (ezeket a változatokat nem tárgyaljuk)
Sorozatszámítás: – adatok sorozatához egy értéket rendelő függvényt helyettesít– minden olyan esetben használható, ha ezt a függvényt felbonthatjuk értékpárokon kiszámított függvények sorozatára – az induláskor használt nullértéket értelemszerűen a kérdéses függvény (esetleg a feladat) alapján kell megválasztani összegzés faktoriális elemek uniója R0 0 1 {} művelet R ← R + A[i] R ← R * A[i] R ← R ∪ A[i] Pszeudo kód: Eljárás Sorozatszámítás(A, N, R) R ← R0 Ciklus i ← 1-től N-ig R ← R művelet A[i] Ciklus vége Eljárás vége C# kód (pl. elemek szorzata): static int Sorozatszamitas(int[] a) { int r = 1; foreach (int e in a) { r *= e; } return r; }
beépített: int szorzat = a.Aggregate((e, next) => e * next); Az „a” a tömb, vagy valamilyen felsorolható típus. Az Aggregate metódus paramétere egy lambda metódus. Zárójelben, vesszővel elválasztva a paraméterek, a nyíl után pedig a metódus törzse. Pl. két szám összegét kiszámító lambda metódus így nézne ki: (a, b) => { int sum = a + b; return sum; }
Ha csak egy paraméter van, a zárójel elhagyható. Ha csak egy utasítás van a metódus törzsben, akkor a kapcsos zárójel elhagyható. A return kiírása nem kötelező ez esetben, és a pontosvessző is elhagyható. Lambda metódus helyett egy megfelelő szignatúrájú metódus nevét is beírhattuk volna. 12
Eldöntés: – a T tulajdonság helyes megválasztásával a tétel sokféle szituációban alkalmazható – a „minden elem T tulajdonságú” feladatot egyszerűen visszavezethetjük az eldöntésre a T tulajdonság tagadásával – a sorozatszámításnál megismert módszerrel ellentétben ez az algoritmus az első T tulajdonságú elem megtalálása után már nem folytatja a keresést Pszudo kód: Eljárás Eldöntés(A, N, VAN) i←1 Ciklus amíg (i ≤ N) és ¬(A[i] teljesíti T-t) i←i+1 Ciklus vége VAN ← (i ≤ N) Eljárás vége C# kód: static bool Eldontes(int[] a) { foreach (int e in a) { if (T(e)) { return true; } } return false; }
A T metódus állapítja meg, hogy a szám T tulajdonságú e, jelen esetben hogy páros e. static bool T(int x) { return x % 2 == 0; }
beépített: a.Any(T); illetve, ha arra vagyunk kíváncsiak, hogy mind T tulajdonságú e: a.All(T); Kiválasztás: – az eldöntéssel ellentétben ez visszaadja az első T tulajdonságú elem sorszámát – a tétel feltételezi, hogy biztosan van legalább egy ilyen tulajdonságú elem! – sorszám helyett visszaadhatjuk az elem értékét is, de célszerűbb a sorszám használata (ez alapján az elem is azonnal meghatározható) Pszeudo kód: Eljárás Kiválasztás(A, N, SORSZ) i←1 Ciklus amíg ¬(A[i] teljesíti T-t) i←i+1 Ciklus vége SORSZ ← i Eljárás vége C# kód: Mi legyen a SORSZ default értéke? 0 nem lehet, mert az is indexet jelöl, legyen -1, ekkor a lineáris keresést kapjuk.
13
Lineáris keresés: – tekinthető az eldöntés és a kiválasztás tétel ötvözetének is: választ ad arra, hogy van-e T tulajdonságú elem a sorozatban, és ha van, akkor visszaadja a sorszámát is – értelemszerűen így nem feltételezi, hogy biztosan van ilyen elem a listában. ha nincs, akkor a VAN változó értéke hamis, ilyenkor a SORSZ mező nem kap értéket – rendezett lista esetén használható a már ismert logaritmikus keresés Pszeudo kód: Eljárás Keresés(A, N, VAN, SORSZ) i←1 Ciklus amíg (i ≤ N) és ¬(A[i] teljesíti T-t) i←i+1 Ciklus vége VAN ← (i ≤ N) Ha VAN akkor SORSZ ← i Eljárás vége C# kód: static int LinearisKereses(int[] a, int n) { for (int i = 0; i < n; i++) { if (T(a[i])) { return i; } } return -1; }
beépített: Array.FindIndex(a, T); Bináris keresés (Logaritmikus keresés), rendezett lista esetén: Pszeudo kód: Eljárás Logaritmikus_keresés(A, N, X, VAN, SORSZ) //X a keresendő elem kulcsa AL ← 1 FE ← N Ciklus K ← |_(AL+FE)/2_| // |_ _| lefele kerekítést jelöl Ha A[K]<X akkor AL ← K+1 Ha A[K]>X akkor FE ← K−1 amíg AL<=FE és A[K] ≠ X Ciklus vége VAN ← AL<=FE Ha VAN akkor SORSZ ← K Eljárás vége
14
C# kód: static int BinarisKereses(int[] a, int n, int keresett) { int bal = 0; int jobb = n - 1; for (int kozep = (bal+jobb)/2; bal <= jobb; kozep = (bal+jobb)/2) { if (a[kozep] == keresett) { return kozep; } else { if (keresett < a[kozep]) { jobb = kozep - 1; } else { bal = kozep + 1; } } } return -1; } beépített: Array.BinarySearch(a, keresett);
Rekurzív bináris keresés: C# kód: static int RekBinKer(int[] a, int keresett, int bal, int jobb) { if (jobb < bal) return -1; int kozep = (bal + jobb) / 2; if (a[kozep] == keresett) { return kozep; } else { if (keresett < a[kozep]) { return RekBinKer(a, keresett, bal, kozep - 1); } else { return RekBinKer(a, keresett, kozep + 1, jobb); } } }
Megszámlálás: – amennyiben nincs T tulajdonságú elem a listában, akkor értelemszerűen 0 kerül a DB változóba – valójában egy sorozatszámítás, amely minden T tulajdonságú elem esetén 1-et hozzáad a DB értékéhez
15
Pszeudo kód: Eljárás Megszámlálás(A, N, DB) DB ← 0 Ciklus i ← 1-től N-ig Ha (A[i] teljesíti T-t) akkor DB ← DB + 1 Elágazás vége i ← i + 1 // Ez ide nem kell, mert ez csak a ciklusváltozó Ciklus vége Eljárás vége C# kód: static int Megszamlalas(int[] a) { int db = 0; foreach (int e in a) { if (T(e)) { db++; } } return db; } //beépített: a.Count(T);
Maximumkiválasztás: – reláció megfordításával értelemszerűen minimumkiválasztás lesz a tétel célja – sorszám helyett visszaadhatjuk az elem értékét is, de célszerűbb a sorszám használata (ez alapján az elem is azonnal meghatározható) – feltételezzük, hogy legalább egy elem létezik a listában – több maximális elem esetén az elsőt adja vissza Pszeudo kód: Eljárás Maximumkiválasztás(A, N, MAX) MAX ← 1 Ciklus i ← 2-től N-ig Ha A[i] > A[MAX] akkor MAX ← i Elágazás vége Ciklus vége Eljárás vége C# kód: static int Maximumkivalasztas(int[] a, int n) { int max = 0; for (int i = 1; i < n; i++) { if (a[i] > a[max]) { max = i; } } return max; } //beépített: a.Max(); a.Min(); // Értéket ad vissza, nem indexet
16
5. Alapvető programozási tételek (N-N) Másolás: – az eredmény mindig ugyanannyi elemszámú, mint a bemenet – a művelet segítségével az egyszerű másoláson túl az egyes elemekkel egy-egy elemi műveletet is el lehet végezni (pl. másoljuk át az abszolútértéküket) – nincs azonban lehetőség az elemek közötti összefüggésekre építeni Pszeudo kód: Eljárás Másolás(X, N, Y) Ciklus i ← 1-től N-ig Y[i] ← művelet X[i] Ciklus vége Eljárás vége C# kód: static int[] Masolas(int[] a, int n) { int[] b = new int[n]; for (int i = 0; i < n; i++) { b[i] = Math.Abs(a[i]); } return b; }
rövidebb változat: static IEnumerable
Masolas(IEnumerable a) { foreach (var e in a) { yield return Math.Abs(e); } }
beépített: a.Select(e => Math.Abs(e)); Kiválogatás: – az X[i] helyett néha csak az i index értékét másoljuk az Y-ba – egyszerű módosítással megoldható, hogy nem másik listába, hanem az eredeti elemeket tartalmazó X lista elejére gyűjtjük a megfelelő elemeket – szintén gyakran használatos változat, ha csak megjelöljük az eredeti listában a megfelelő elemeket Pszeudo kód: Eljárás Kiválogatás(X, N, Y, DB) DB ← 0 Ciklus i ← 1-től N-ig Ha (X[i] teljesíti T-t) akkor DB ← DB + 1 Y[DB] ← X[i] Elágazás vége Ciklus vége Eljárás vége
17
C# kód: static int?[] Kivalogatas(int[] a, int n) { int?[] b = new int?[n]; int db = 0; for (int i = 0; i < n; i++) { if (T(a[i])) { b[db++] = a[i]; } } return b; }
Az int? abban különbözik az int-től, hogy előbbi nullable. Tehát default értéke nem 0, hanem null lesz. Ezáltal meg tudjuk különböztetni a 0 értéket a még értékkel fel nem töltött változótól. Kiválogatásnál pl. fogjuk tudni, hogy 0-át válogattunk ki, vagy csak üres az a tömbindex. (Persze generikus lista használata kézenfekvőbb lenne.) rövidebb változat: static IEnumerable Kivalogatas(IEnumerable a) { foreach (var e in a) { if (T(e)) { yield return e; } } }
beépített: a.Where(T); Szétválogatás: – egyszerűen megoldható, hogy csak egy sorozatba helyezzük át az elemeket (a T tulajdonságú elemek kerüljenek az elejére, a nem T tulajdonságúak pedig a végére) – érdemes átgondolni, hogyan lehetne egyszerűen megoldani a szétválogatást az eredeti sorozatban Pszeudo kód: Eljárás Szétválogatás(X, N, Y, DBY, Z, DBZ) DBY ← 0 DBZ ← 0 Ciklus i ← 1-től N-ig Ha (X[i] teljesíti T-t) akkor DBY ← DBY + 1 Y[DBY] ← X[i] különben DBZ ← DBZ + 1 Z[DBZ] ← X[i] Elágazás vége Ciklus vége Eljárás vége
18
C# kód: static void Szetvalogatas(int[] a, int?[] b, int?[] c) { int bdb = 0; int cdb = 0; foreach (int e in a) { if (T(e)) { b[bdb++] = e; } else { c[cdb++] = e; } } }
Szétválogatás egy tömbbe: C# kód: static int[] SzetvalogatasEgyTombbe(int[] a, int n) { int[] b = new int[n]; int bal = 0; int jobb = n - 1; foreach (int e in a) { if (T(e)) { b[bal++] = e; } else { b[jobb--] = e; } } return b; }
Szétválogatás az eredeti sorozaton belül: C# kód: static void SzetvalogatasAzEredetiSorozatban(int[] a, int n) { int bal = 0; int jobb = n - 1; while (bal < jobb) { if (!T(a[bal])) { while (bal < jobb && !T(a[jobb])) { jobb--; } Csere(ref a[bal++], ref a[jobb--]); } else { bal++; } } }
19
Halmazműveletek A sorozatokban egy elem legfeljebb csak egyszer szerepel. Metszet: – felismerhető benne egy kiválogatás tételbe ágyazott eldöntés tétel kódja – gyakran nincs szükség az összes metszetbeli elemre, csak egy elemről kell eldönteni, hogy az benne van-e a metszetben Pszeudo kód: Eljárás Metszet(X, N, Y, M, Z, DB) DB ← 0 Ciklus i ← 1-től N-ig j←1 Ciklus amíg (j ≤ M) és (X[i] ≠ Y[j]) j←j+1 Ciklus vége Ha j ≤ M akkor DB ← DB + 1 Z[DB] ← X[i] Elágazás vége Ciklus vége Eljárás vége C# kód: static int?[] Metszet(int[] a, int[] b) { int n = a.Length; int m = b.Length; int?[] metszet = new int?[Math.Min(n, m)]; int k = 0; for (int i = 0; i < n; i++) { int j; for (j = 0; j < m && a[i] != b[j]; j++) { } if (j < m) metszet[k++] = a[i]; // Ha itt j == m lenne, akkor az a két halmaz különbségét adná ereményül a metszet helyett, vagyis: A \ B -t } return metszet; } rövidebb változat: static IEnumerable Metszet(int[] a, int[] b) { foreach (var e in a) { if (b.Contains(e)) // Ha itt !b.Contains(e) lenne, akkor különbség { yield return e; } } } beépített: var metszet = h1.Intersect(h2); // Egy elem előfordulhat többször is, az var kulonbseg = h1.Except(h2); // azonosokat előtte kiszűri
20
Unió: – amennyiben a két lista rendezett, lehetőségünk van jóval hatékonyabb algoritmusok készítésére (összefuttatás, összefésülés) Pszeudo kód: Eljárás Egyesítés(X, N, Y, M, Z, DB) Z←X DB ← N Ciklus i ← 1-től M-ig j←1 Ciklus amíg (j ≤ N) és (X[j] ≠ Y[i]) j←j+1 Ciklus vége Ha j > N akkor DB ← DB + 1 Z[DB] ← Y[i] Elágazás vége Ciklus vége Eljárás vége C# kód: static int?[] Unio(int[] a, int[] b) { int n = a.Length; int m = b.Length; int?[] unio = new int?[n + m]; int k = 0; for (int i = 0; i < n; i++) { unio[k++] = a[i]; } for (int j = 0; j < m; j++) { int i; for (i = 0; i < n && b[j] != a[i]; i++) { } if (i == n) { unio[k++] = b[j]; } } return unio; }
beépített: var unio = h1.Union(h2); // Egy elem előfordulhat többször is, az azonosokat előtte kiszűri
21
Azonosak kiszűrése: Ha halmazzá akarunk alakítani egy sorozatot, hogy utána halmazként dolgozhassunk vele. C# kód: static int?[] Egyedi(int[] a) { int n = a.Length; int?[] egyedi = new int?[n]; int k = 0; for (int i = 0; i < n; i++) { int j; for (j = 0; j <= k && a[i] != egyedi[j]; j++) { } if (j > k) { egyedi[k++] = a[i]; } } return egyedi; }
rövidebb változat: static int?[] Egyedi(int[] a) { int n = a.Length; int?[] egyedi = new int?[n]; int k = 0; foreach (int e in a) { if (!egyedi.Contains(e)) { egyedi[k++] = e; } } return egyedi; }
beépített változat: var egyedi = h1.Distinct();
A beépített metódusok általában IEnumerable -t adnak vissza, .ToArray() -el tömbbé alakíthatjuk a sorozatot. var egyedi = h1.Distinct().ToArray(); Így a változó típusa tömb lesz, var-t csak akkor használhatunk, ha rögtön értéket is adunk a
változónak deklaráláskor, így meg tudja határozni a fordító a változó típusát még futtatás előtt. Ez akkor lehet hasznos, ha túl hosszú a típus neve, vagy nem akarunk utánanézni milyen típust kellene odaírni, vagy névtelen típusú változót deklarálunk, aminek nem is tudnánk típust megadni.
22
Halmazműveletek rendezett halmaz esetén A halmaz elemei rendezve vannak a sorozatban. Ezt kihasználva a halmazműveletek kevesebb lépésszámot igényelnek. Metszet: C# kód: static int?[] MetszetSpecialis(int[] a, int[] b) { int n = a.Length; int m = b.Length; int?[] metszet = new int?[Math.Max(n, m)]; int i = 0; int j = 0; int k = 0; while (i < n && j < m) { if (a[i] == b[j]) { metszet[k++] = a[i]; i++; j++; } else { if (a[i] < b[j]) { i++; } else { j++; } } } return metszet; }
23
Különbség: C# kód: static int?[] KulonbsegSpecialis(int[] a, int[] b) { int n = a.Length; int m = b.Length; int?[] kulonbseg = new int?[n]; int i = 0; int j = 0; int k = 0; while (i < n && j < m) { if (a[i] < b[j]) { kulonbseg[k++] = a[i]; i++; } else { if (b[j] < a[i]) { j++; } else { i++; j++; } } } for (int l = i; l < n; l++) { kulonbseg[k++] = a[l]; } return kulonbseg; }
24
Unió: Az összefésüléses rendezésnél (mergesort) is szokták használni. Nem összetévesztendő a fésűs rendezéssel (combsort). A rendezésről: Felosztjuk a sorozatot két kb. egyenlő hosszú sorozatra majd ezt addig ismételjük amíg 1 vagy 0 elemű lesz az alsorozat, ezután összefésüljük őket. Összehasonlító, rekurzív, stabil rendezés. O(n * log n) az átlagos lépésszám, O(n) extra tárhelyet igényel. Láncolt listák rendezésére ez a leghatékonyabb rendezés (és ráadásul ekkor csak O(1) extra tárhelyet igényel). Iskolánk névadója találta fel 1945-ben. C# kód: static int?[] UnioSpecialis(int[] a, int[] b) { int n = a.Length; int m = b.Length; int?[] unio = new int?[n + m]; int i = 0; int j = 0; int k = 0; while (i < n && j < m) { if (a[i] < b[j]) { unio[k++] = a[i++]; } else { if (a[i] == b[j]) { unio[k++] = a[i++]; j++; } else { unio[k++] = b[j++]; } } } for (int l = i; l < n; l++) { unio[k++] = a[l]; } for (int l = j; l < m; l++) { unio[k++] = b[l]; } return unio; }
25
Azonosak kiszűrése: C# kód: static int?[] EgyediSpecialis(int[] a) { int n = a.Length; int?[] egyedi = new int?[n]; int elozo = a[0]; egyedi[0] = a[0]; int k = 1; for (int i = 1; i < n; i++) { if (a[i] != elozo) { egyedi[k++] = a[i]; } elozo = a[i]; } return egyedi; }
26
6. Programozási tételek összeépítése • •
Összetettebb programok esetén szintén használhatjuk a programozási tételeket, ilyenkor gyakran szükség van az egymásbaépítésükre Gyakori megvalósítások – tételek egymás után – tételek egymásba ágyazva – egyéb (optimalizált) megoldások
Példák tételek összeépítésére: • Megszámolás-eldöntés – pl. egy N elemű sorozatban van-e legalább K darab T tulajdonságú elem? Pszeudo kód: Eljárás SzámolásÉsEldöntés(N, A, K, VAN) i←1 DB ← 0 Ciklus amíg (i ≤ N) és (DB < K) Ha (A[i] teljesíti T-t) akkor DB ← DB + 1 Elágazás vége i←i+1 Ciklus vége VAN ← (DB = K) Eljárás vége C# kód: static bool MegszamlalasEldontes(int[] a, int k) { int db = 0; foreach (int e in a) { if (T(e)) { if (++db == k) { return true; } } } return false; }
• • • • •
Megszámolás-kiválasztás – pl. hol van a K-adik T tulajdonságú elem? Megszámolás-keresés – pl. van-e K darab T tulajdonságú elem, és ha igen, hol található a sorozatban a K-adik? Maximumkiválasztás-megszámlálás – pl. hány darab maximális elem van a listában? Maximumkiválasztás-kiválogatás – pl. melyek a maximális elemek a listában? (értelemszerűen az indexeket várjuk) Kiválogatás-sorozatszámítás – pl. adjuk össze az összes T tulajdonságú elemet! 27
• • • • •
Kiválogatás-maximumkiválasztás – pl. keressük meg a T tulajdonságú elemek közül a maximálisat! Kiválogatás-másolás – pl. másoljuk le a sorozat T tulajdonságú elemeit (esetleg végezzünk rajtuk valamilyen elemi műveletet is)! Másolás-sorozatszámítás – pl. adjuk meg a sorozat elemeinek négyzetösszegét! Másolás-maximumkiválasztás – pl. adjuk meg a sorozat elemei közül azt, amelyiknek maximális az abszolútértéke! Egyéb összeépítések
Néhány egyszerű példa: Egy N elemű sorozat Kmin és Kmax közötti számokat tartalmaz, határozzuk meg, hogy - van-e olyan szám, amelyik többször szerepel a sorozatban? var vanEAmiTobbszorSzerepel = (from e in a group e by e into g where g.Count() > 1 select g.Key).Any();
-
hány szám szerepel többször is a sorozatban?
var hanySzamSzerepelTobbszor = (from e in a group e by e into g where g.Count() > 1 select g.Key).Count();
-
melyik számból van a legtöbb a sorozatban?
var melyikSzambolVanALegtobb = (from e in a group e by e into g orderby g.Count() descending select g.Key).First();
-
hány elemből áll a leghosszabb azonos számokból álló részsorozat? ezt inkább ciklussal érdemes adjon megoldást a fentiekre, amennyiben a sorozat rendezett! adjon megoldást a fentiekre, amennyiben tetszőleges számok szerepelhetnek a sorozatban (Kmin, Kmax ismeretlen)!
28
9. N*N -es rendezések (alapelvek, algoritmusok) Problémakör: Adott egy halmaz melyben ”N” darab elem valamilyen egyértelműen eldönthető szempont szerint rendezetlenül helyezkedik el. A rendezetlen halmaz rendezetté alakításával a cél. A halmaz rendezése több szempont szerint történhet: - a sorozat elemei olyanok, amelyekre a <, ≤ relációk léteznek. (vagy más egyéb reláció, ami alapján egyértelműen sorba rendezhető) - a sorozathoz létezik indexelés művelet (melyekkel az egyes elemekre tudunk hivatkozni a halmazon belül) A módszerek összehasonlításának alapja: - tárigény - idő (végrehajtott műveletek száma) - (bonyolultság) Rendezés típusok: - összehasonlító rendezések - nem összehasonlító rendezések Bemenő paraméterek minden rendezésnél: - ”A” a rendezendő tömb - ”N” az ”A” tömb hossza Pszeudo kód esetében: - ha nincs megadva a ciklusnál a léptetés mértéke, akkor az mindig 1 - a ciklusoknál a kezdeti és végső érték ”inclusive” értendő, tehát az még beleszámít - a tömb első elemének indexe 1 és az utolsójának ”N” Egyszerű cserés rendezés: Az algoritmus alapelve a számok cserélgetése egészen addig, amíg a teljes vektor rendezett nem lesz. A rendezés alapgondolata, hogy minden i. lépésben próbáljuk biztosítani, hogy az első i db szám a helyére kerüljön. Tehát a tömb első i db elemei a legkisebb elemek legyenek a megfelelő sorrendben. Ez a gondolatmenet jól látható az algoritmus vizsgálata során. A külső ciklus a vektor elejétől kezdve végigmegy minden egyes elemen, és a belső ciklus segítségével biztosítja, hogy az i. lépésben az első i db szám már a helyére kerüljön. Ennek eléréséért a belső ciklus a felelős. Fontos észrevennünk, hogy a fenti elérendő cél egyben segítséget is jelent, hiszen ha az algoritmusunk jól működik, akkor az i. lépés megkezdésekor az első i1 db elem már egészen biztosan a helyén van. A belső ciklusnak tehát az i. elemet kell csak megtalálnia és a helyére illesztenie, ez pedig nem lesz más, mint a maradék elemek közül a legkisebb. Tehát végignéz minden elemet, és az aktuálisan talált legkisebbel kicseréli az i. helyen állót, így a ciklus lefutása után garantáltan az első i db legkisebb elem lesz a vektor elején. A külső ciklus ezt követően folytatja a működését, egészen addig, amíg elér az utolsó elemig. Ezt már felesleges vizsgálnia, hiszen ez biztosan a legnagyobb lesz az egész vektorban, az előtte levők pedig mind rendezettek. Így a feladatot elvégeztük. Tárigény: N+1 Lépésszám: Hasonlítás: N*(N-1)/2 Mozgatás: 0 – 3*N*(N-1)/2
O(n2) O(n2)
29
Pszeudo kód: Eljárás Rendezés(N, A) Ciklus i←1-től N-1-ig Ciklus j ← i+1-től N-ig Ha A[i] > A[j] akkor A[i] ↔ A[j] Elágazás vége Ciklus vége Ciklus vége Eljárás vége C# kód: static void Csere(ref int a, ref int b) { int temp = a; a = b; b = temp; } static void EgyszeruCseresRendezes(int n, int[] a) { for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (a[i] > a[j]) { Csere(ref a[i], ref a[j]); } } } } Minimumkiválasztásos rendezés: Az egyszerű cserés rendezésnek van egy nagy hátránya: sok felesleges cserét végez. Ez rontja az algoritmus teljesítményét, ezért valahogy próbáljuk a cserék számát csökkenteni. Vegyük észre, hogy a belső ciklus amikor keresi az i. helyre való elemet, minden egyes (az eddig találtnál) kisebb elem esetén elvégez egy cserét. Ezek nagy része teljesen felesleges, elég lenne csak a legutolsó cserét végrehajtani. Tehát először egy minimumkiválasztással meg kell keresni az i. elem utáni legkisebb elemet (beleértve magát az i. elemet is, hátha nincs nála kisebb) és ezzel kell elvégezni a cserét. A külső ciklus tulajdonképpen nem változik, a belső ciklus pedig pontosan megfelel a már ismert minimumkiválasztásnak. Ezzel elérhető, hogy a külső ciklus minden egyes iterációjában pontosan egy darab csere történjen csak. Az összehasonlítások száma nem változik az egyszerű cserés rendezéshez képest. Tárigény: N+1 Lépésszám: Hasonlítás: N*(N-1)/2 Mozgatás: 0 – 3*(N-1)
O(n2) O(n) 30
Pszeudo kód: Eljárás Rendezés(N, A) Ciklus i ← 1-től N-1-ig MIN ← i Ciklus j ← i+1-től N-ig Ha A[MIN] > A[j] akkor MIN ← j Ciklus vége A[i] ↔ A[MIN] Ciklus vége Eljárás vége C# kód: static void MinimumkivalasztasosRendezes(int n, int[] a) { for (int i = 0; i < n - 1; i++) { int min = i; for (int j = i + 1; j < n; j++) { if (a[min] > a[j]) { min = j; } } Csere(ref a[i], ref a[min]); } } Buborékos rendezés: Az algoritmus alapelve, hogy összehasonlítjuk az egymás melletti számokat, és ha a magasabb indexű elem értéke kisebb mint az alatta levő, akkor megcseréljük őket. Különösebb bizonyítás nélkül is érthető talán, hogy ha megfelelő ideig folytatjuk ezt a cserét, akkor a teljes vektor rendezett lesz. A felesleges műveletek elkerülése végett az összehasonlításokat és cseréket a megfelelő sorrendben kell végrehajtani. Ebben az esetben a vektor végétől indulva az eleje felé összehasonlítunk minden szomszédos elemet, és ha szükséges, megcseréljük őket. Így mire elérjük a vektor elejét, garantált, hogy az első helyen a legkisebb elem lesz. A többi elem azonban még nem rendezett, ezért ismét el kell indulni a vektor végétől a cserélgetéssel, viszont ekkor már az első elem ellenőrzése felesleges, hiszen azt tudjuk, hogy a legkisebb, ezért csak a 2. elemig kell haladni. A második ciklus felelős a cserét végző belső ciklus többszöri futtatásáért, és ez határozza meg azt is, hogy a belső ciklusnak hány vizsgálatot kell elvégeznie. A külső ciklus futásának befejezésekor tehát a vektor rendezett lesz. Az algoritmus megírható úgy is, hogy a külső ciklus lépked előre a belső pedig visszafelé. Az algoritmus elnevezése is innen ered, ilyenkor ugyanis a belső ciklus miatt a legkisebb elem folyamatosan "emelkedik" a vektor elejére, mint egy buborék a folyadékban. Ebben a megvalósításban pedig a nagyobb elemek folyamatosan "lesüllyednek" a magasabb indexű cellák felé.
31
Tárigény: N+1 Lépésszám: Hasonlítás: N*(N-1)/2 Mozgatás: 0 – 3*N*(N-1)/2
O(n2) O(n2)
Pszeudo kód: Eljárás Rendezés(N, A) Ciklus i ← N-től 2-ig (-1)-esével Ciklus j ← 1-től i-1-ig Ha A[j] > A[j+1] akkor A[j] ↔ A[j+1] Elágazás vége Ciklus vége Ciklus vége Eljárás vége C# kód: static void BuborekosRendezes(int n, int[] a) { for (int i = n - 1; i > 0; i--) { for (int j = 0; j < i; j++) { if (a[j] > a[j + 1]) { Csere(ref a[j], ref a[j + 1]); } } } } Javított buborékos rendezés: A buborékos rendezés jól működik, azonban nem használtunk ki egy fontos információt, hogy az elemek a helyük felé mozdulnak. A legegyszerűbb esetben például, ha a belső ciklus futása során nem történt egy csere sem, akkor az nyílván azt jelenti, hogy az egész vektor rendezett. Ilyenkor a külső ciklus minden további lépése felesleges, így ez csak rontja a hatékonyságot. Ehhez hasonlóan, ha a belső ciklus utolsó cseréje a cs. elemnél történt, akkor ez azt jelenti, hogy a cs. utáni elemek közt már csak összehasonlításokat végzett az algoritmus, csere nem történt. Ebből szintén arra lehet következtetni, hogy a cs. utáni elemek már a helyükön vannak, a következő külső ciklust tehát már csak idáig kell futtatni. A rendezés ettől eltekintve nem változott, csak a fentiek miatt a külső számlálós ciklusról át kell térni előltesztelős ciklusra, ami mindig csak az utolsó csere helyéig halad. Ezt a helyet pedig a belső ciklusban elvégzett cserék során fokozatosan feljegyezzük.
Tárigény: N+1 Lépésszám: Hasonlítás: O(n2) Mozgatás: O(n2)
32
Pszeudo kód: Eljárás Rendezés(N, A) i←N Ciklus amíg i ≥ 2 CS ← 0 Ciklus j ← 1-től i-1-ig Ha A[j] > A[j+1] akkor A[j] ↔ A[j+1] CS ← j Elágazás vége Ciklus vége i ← CS Ciklus vége Eljárás vége C# kód (átírva for-ra): static void JavitottBuborekosRendezes(int n, int[] a) { int cs; for (int i = n - 1; i > 0; i = cs) { cs = 0; for (int j = 0; j < i; j++) { if (a[j] > a[j + 1]) { Csere(ref a[j], ref a[j + 1]); cs = j; } } } } Beillesztéses rendezés: Az eddigi rendezési módszerek mindegyike olyan volt, hogy a sorozatot felosztotta egy már kész, rendezett szakaszra, és a rendezést a másik szakasz elemei között folytatta. A beillesztéses rendezéssel megismerünk egy új elvet, ami leginkább talán a kártyalapok rendezéséhez hasonlítható. Van egy már rendezett sorozatunk, és kapunk egy új elemet, amit el kell helyezni ebben a sorozatban. A kártyalapok hasonlatnál maradva, az új lapot elhelyezzük a többi lap mögött, majd folyamatosan cserélgetünk egészen addig, amíg az elérkezik a helyére. Ezt hajtja végre a belső ciklus, ami folyamatos cserékkel egyre alacsonyabb indexű helyekre viszi a beszúrandó elemet. Ennek köszönhetően ismét egy rendezett sorozatot kapunk. A külső ciklus pedig folyamatosan adja az új elemeket a belső ciklusnak, mivel azt mindig a vektor egyel nagyobb részére hívja meg. Így az i. lépéskor az első i-1 darab elem már rendezett (de fontos különbség az eddigiekkel szemben, hogy még nem biztos, hogy minden elem a végleges helyén van!) az i. elemet pedig a belső ciklus elhelyezi majd ebben a rendezett részsorozatban. Az algoritmus egy további specialitása az eddigiekhez képest, hogy nem igényli a futás elején az összes elem meglétét. Tehát ideális olyan rendezésekhez, amikor az egyes új elemeket csak a rendezés közben kapjuk meg (például egy fájlból folyamatosan olvasunk be számokat). 33
Tárigény: N+1 Lépésszám: Hasonlítás: O(n2) Mozgatás: O(n2) Pszeudo kód: Eljárás Rendezés(N, A) Ciklus i ← 2-től N-ig j ← i-1 Ciklus amíg (j > 0) és (A[j] > A[j+1]) // Hibás a PPT dia, mert ott j>=0 van A[j] ↔ A[j+1] j←j-1 Ciklus vége Ciklus vége Eljárás vége C# kód (átírva for-ra): static void BeillesztesesRendezes(int n, int[] a) { for (int i = 1; i < n; i++) { for (int j = i - 1; j >= 0 && a[j] > a[j + 1]; j--) { Csere(ref a[j], ref a[j + 1]); } } } Javított beillesztéses rendezés: A beillesztéses rendezésnél észrevehető, hogy a belső ciklus futása során minden elem csak egyszer mozdul el felfelé. Ezen a felismerésen alapszik a javítási lehetőség is. Az algoritmus így talán még jobban hasonlít a kártyalapok rendezésére, hiszen ilyenkor az ember valójában nem cserélgeti a kártyákat, hanem a beszúrandót kiemeli a lapok közül, majd a helyét keresve a többi kártyát előrébb mozdítja és végül az így keletkezett üres helyre elhelyezi az új lapot. A belső ciklus ehhez hasonlóan működik, a beszúrandó elemet elmenti az y változóba. Ezt követően elkezdi az alatta levő de nála nagyobb elemeket egy indexel feljebb másolni. Amikor talál egy nála kisebb (vagy vele egyenlő) értéket, akkor azt már nem mozdítja tovább, a megmaradt helyre pedig bemásolja az y értékét. A külső ciklus a beillesztéses rendezésnél megismert módon működik, folyamatosan beteszi az új rendezendő elemeket. Ez a módosítás nem változtatja meg azt a tulajdonságot, hogy az algoritmus elindításához nincs szükség az összes elem ismeretére.
Tárigény: N+1 Lépésszám: Hasonlítás: O(n2) Mozgatás: O(n2)
34
Pszeudo kód: Eljárás Rendezés(N, A) Ciklus i ← 2-től N-ig j ← i-1 Y ← A[i] Ciklus amíg (j > 0) és (A[j] > Y) // Hibás a PPT dia, mert ott j>=0 van A[j+1] ← A[j] j←j-1 Ciklus vége A[j+1] ← Y Ciklus vége Eljárás vége C# kód (átírva for-ra): static void JavitottBeillesztesesRendezes(int n, int[] a) { for (int i = 1; i < n; i++) { int y = a[i]; int j; for (j = i - 1; j >= 0 && a[j] > y; j--) { a[j + 1] = a[j]; } a[j + 1] = y; } }
35
10. Haladó Rendezések 1(Kupac & Shell) Kupacrendezés A kupacrendezés összehasonlító rendezési algoritmus, és a kiválasztó rendezések családjába tartozik. Helyben rendező, nem stabil rendezés. Gyakorlati alkalmazása: elsőbbségi sorok. Futásidő: - Átlagos eset: O(n * log n) - Legjobb eset: O(n * log n) - Legrosszabb eset: O(n * log n) (jobb, mint a gyorsrendezésé, ami O(n2)) Műveletei: • Beszúrás • Maximum • Kivesz-maximum • Kupacba-beszúr Kupac adatszerkezet: • Bináris kupac: Egy majdnem teljes bináris fa egy tömbben ábrázolva • A tömb mérete = kupac mérete = N • Fa – kupac megfeleltetés: o Szülő(i): |_ i / 2_| o Bal(i): 2*i o Jobb(i): 2*i+1 Kupactulajdonság: • Kupac tulajdonság: A kupac minden i, gyökértől különböző eleme esetén: A[Szülő(i)] ≥ A[i] • Tehát egy olyan bináris fát képvisel, amelyre igaz, hogy minden csúcs bal és jobb oldali részfájában csak kisebb vagy egyenlő értékek találhatók. • Ez nem azonos a tanult bináris keresőfa adatszerkezettel! Kupactulajdonság fenntartása: Feltételezzük, hogy a bal és jobb oldali részfák kupac szerkezetűek. Ha A[i] kisebb valamelyik gyerekénél, akkor megsérti a kupactulajdonságot. Pszeudo kód: Eljárás Kupacol(A, i, N) b ← Bal(i); j ← Jobb(i) Ha b ≤ N és A[b] > A[i] akkor MAX ← b különben MAX ← i Ha j ≤ N és A[j] > A[MAX] akkor MAX ← j Ha MAX ≠ i akkor A[i] ↔ A[MAX] Kupacol(A, MAX, N) Elágazás vége Eljárás vége 36
C# kód: static void Csere(ref int a, ref int b) { int temp = a; a = b; b = temp; } static int Szulo(int i) { return i / 2; } static int Bal(int i) { return 2 * i; } static int Jobb(int i) { return 2 * i + 1; } static void Kupacol(int[] a, int i, int n) { int b = Bal(i); int j = Jobb(i); int max; if (b < n && a[b] > a[i]) { max = b; } else { max = i; } if (j < n && a[j] > a[max]) { max = j; } if (max != i) { Csere(ref a[i], ref a[max]); Kupacol(a, max, n); } }
37
Kupac építése: • Az A tömböt alulról felfelé haladva kupaccá alakítjuk • Az |_N/2_|-től N-ig terjedő index elemek levelek, tehát egy elemű (a kupactulajdonságot teljesítő) fáknak tekinthetőek, így csak a többi csúcsot kell ellenőrizni • A feldolgozás sorrendje garantálja a Kupacol eljárás előfeltételét Pszeudo kód: Eljárás Kupacot-épít(A) N ← Tömb_méret(A) Ciklus i ← |_N/2_|-től 1-ig Kupacol(A, i, N) Ciklus vége Eljárás vége
//”|_ _|” egészrészre kerekítést lefelé
C# kód: static void KupacotEpit(int[] a, int n) { for (int i = n / 2; i >= 0; i--) { Kupacol(a, i, n); } } Kupacrendezés: • A kupacban a gyökérelem biztosan a legnagyobb • Ötlet: ezt helyezzük a tömb végére, zárjuk ki a kupacból, majd a maradék elemekből építsünk újra kupacot Pszeudo kód: Eljárás Kupacrendezés(A) Kupacot-épít(A) Ciklus i ← N-től 2-ig A[1] ↔ A[i] N←N–1 Kupacol(A, 1, N) Ciklus vége Eljárás vége C# kód: static void Kupacrendezes(int[] a, int n) { KupacotEpit(a, n); for (int i = n - 1; i > 0; i--) { Csere(ref a[0], ref a[i]); n--; Kupacol(a, 0, n); } }
38
Shell rendezés A shell rendezés összehasonlító rendezési algoritmus, és a beillesztéses rendezések családjába tartozik. Helyben rendező, nem stabil rendezés. A javított beillesztéses rendezés módosított változata. Az eredeti megvalósítás O(n 2) összehasonlítást és mozgatást végzett a legrosszabb esetben. Ez a módosítás hatására O(n log2 n) –re javult, ami még mindig rosszabb az optimális összehasonlító rendezésekhez képest, amik O(n log n) lépésszámúak. A módosítás: A sorozatnak csak minden L-edik elemét vizsgáljuk meg, és ezeket rendezzük beillesztéses rendezéssel, utána a lépésközt csökkentjük, és ezután még annyiszor végigmegyünk a sorozaton evvel a módszerrel, amíg a lépésköz 1 nem lesz, ekkor a sorozat már szinte teljesen rendezett, ekkor már tulajdonképpen csak egy sima beillesztéses rendezés fut le. A tapasztalatok azt mutatják, hogy ha az új lépésköz az előző lépésköz 2.2-ede, akkor optimálisan működik az algoritmus. A kezdő lépésköz |_N / 2_|, ahol N a sorozat elemszáma. Pszeudo kód: Eljárás Rendezés(N, A, L0) L ← L0 Ciklus amíg L ≥ 1 Ciklus k ← L+1-től 2*L-ig Ciklus i ← k-tól N-ig L-esével j←i–L y ← A[i] Ciklus amíg (j > 0) és (A[j] > y) A[j + L] ← A[j] j←j–L Ciklus vége A[j + L] ← y Ciklus vége Ciklus vége L ← Következő_L(L) Ciklus vége Elágazás vége C# kód (átírva for-ra): // Ugyanaz, mint a javított beillesztéses rendezés, csak ott nincs a legkülső ciklus, és ahol itt inc van, ott 1. public static void ShellSort(int n, int[] a) { for (int inc = n / 2; inc > 0; inc = (inc == 2 ? 1 : (int)Math.Round(inc / 2.2))) { for (int i = inc; i < n; i++) { int y = a[i]; int j; for (j = i - inc; j >= 0 && a[j] > y; j -= inc) { a[j + inc] = a[j]; } a[j + inc] = y; } } }
39
11. Haladó rendezések II ( Szétosztó-, Leszámoló-, Radix-, Edény rendezés ) Szétosztó rendezés A szétosztó rendezés esetében feltesszük, hogy a rendezendő elemek olyan rekordok, melynek kulcsmezője (vagy az abból kiszámolt számérték) 1..N közti természetes szám lehet és nincs két azonos kulcsú rekord. A kulcsmező itt egyértelműen megadja azt a helyet, ahová az elemet tenni kell, így hasonlításra nincs szükség. A módszerhez azonban egy újabb tömbre ( B tömb ) van szükség, ahová az eredményt elhelyezzük. Bemeneti paraméterek: //A rendezendő tömb //B az „A” legnagyobb kulcs értéke a tömb mérete //N „A” tömb hossza
Eljárás SzétosztóRendezés( A, B, N ) Ciklus i 1 től N –ig B[A[i].kulcs] A[i] Ciklus vége Eljárás vége Figyelni kell kiíratásnál a „B” tömb üres elemeire. Lépésszám: O(n)
Leszámoló rendezés A leszámoló rendezés esetében feltesszük, hogy a rendezendő elemek olyan rekordok, melynek kulcsmezője (vagy az abból kiszámolt számérték) 1..N közti természetes szám lehet és van azonos kulcsú rekord (akár több is).
40
1. lépés: megszámoljuk, hogy melyik érdemjegyből hány darab van 2. lépés: A C tömb véglegesítése minden elem (a másodiktól kezdve) önmagának és az előtte lévőnek az összege. 3. lépés: A C tömbben tárolt kulcsok vég sorszámai szerint töltjük fel az eredmény tömböt. Miután egy elemet már beillesztettünk a helyére, akkor a C tömbben a kulcshoz rendelt sorszámot csökkentjük. Például: Teri kulcsa „3”-as így a 8. helyre tesszük B tömbben és a C tömbben lévő hármasokból levonunk egyet, hiszen egy helyet már elhasználtunk. (lásd az ábrán) Eljárás LeszámolóRendezés ( A , N , B, K ) C[] 0 Ciklus i 1 től N –ig C[A[i].kulcs] C[A[i].kulcs] +1 Ciklus vége Ciklus i 2 től K –ig C[i] C[i] + C[i-1] Ciklus vége Ciklus i N től 1 –ig B[C[A[i].kulcs]] A[i] C[A[i].kulcs] C[A[i].kulcs] – 1 Ciklus vége Eljárás vége
// N az A[] tömb hossza
// C[A[i].kulcs]++ (darabszám növelése) // K a C[] tömb hossza // C[i] += C[i-1] (előző darabszámmal való növelés) // visszafele kell menni, hogy stabil maradjon // C[A[i].kulcs]-- (egy a helyére került ebből a // fajtából (kulcsból, jegyből), csökkentjük a // darabszámot 1-el
Lépésszám: O(n) Stabil rendezésnek mondhatjuk, mert megtartja az azonos kulcsúak sorrendjét.
41
Radix rendezés
A radixrendezés egymásra épülő hierarchiát használ ki (tehát pl. számjegyek között, év-hónap-nap: helyi értékek szerint hátulról előre haladva elven rendezünk)
Eljárás RadixRendezés( A , D ) //D a számjegyek száma Ciklus i 1 től D –ig { „stabil rendezés az i –ik számjegyen” } Ciklus vége Eljárás vége
Csak azonos hosszúságú számokat tud rendezni. Lépésszám: O(n)
Gyakorlati megvalósítása lyukkártya számjegyenkénti rendezés szövegek rendezése
Edényrendezés
Az edényrendezés azt használja ki mint a radix, van egy adag sorrendbe rakott edényünk, és ezekbe szétszórjuk az elemeket. Edényekbe történő leképezés hasító függvény alkalmazásával történik. Az edényekben tetszőleges módon sorba rendezünk az elemeket, és utána az edényekből sorba haladva kiszedjük az elemeket, akkor rendezett sort kapunk. Ez azért jó, mert az edények mérete kisebb lesz mint az egész tömb => gyorsabb...
Tudom, hogy az edények között milyen reláció áll fenn, vagyis az első edénybeli elemek kisebbek a második edénybelieknél, a másodikak meg kisebbek a harmadik edénybelieknél. Így ha rendezem az egyes edényeket, és utána egymás után rakom a tartalmukat, akkor rendezett lesz az egész tömb.
42
Eljárás EdényRendezés Ciklus i 1 től N –ig ListábaBeszúrás ( B[f(A[i])] , A[i]) Ciklus vége Ciklus i 1 tól M –ig ListaRendezés(B[i]) Ciklus vége Ciklus i 1 tól M –ig ListaÖsszefűzése( C, B[i] ) Ciklus vége Eljárás vége
// edénybe tevés
// az edényekben lévő elemek rendezése
// edényekből sorban kivétel és egymás után tevés
M darab edény. A tömb: rendezendő lista B tömb: edények. C tömb: rendezett lista
43
15. Rekurzió fogalma, gyakorlati megvalósítása Rekurziót használunk olyan feladatok megoldására, amelyeknél a megoldandó feladat egymással összefüggő részfeladatokra bontható. A részfeladatok összefüggősége miatt sok esetben nem minden adat áll rendelkezésre. A feladatot addig bontjuk fel, amíg nem találunk egy olyan részfeladatot, amit meg tudunk oldani. A megkapott eredményt visszahelyettesítve az eggyel korábbi részfeladatba az megoldhatóvá válik. A helyettesítést addig végezzük, amíg a teljes feladat eredményét nem kapjuk meg.
A részfeladatra bontás során két esetet különböztetünk meg: •
Egy általános esetet, amely teljes indukciós feltevést alapul véve a feladatot tovább bontja újabb részfeladatra. Egészen addig érvényesül ez az eset, amíg a részfeladat egyértelmű megoldását nem kapjuk.
•
Egy egyértelmű megoldás, amely a rendelkezésre álló információból ki tudja számolni a részfeladat eredményét. A kiszámolt eredményt a teljes indukción keresztül visszahelyettesíti addig, amíg a feladat végeredménye meghatározásra nem kerül.
Technikai értelemben rekurzív algoritmusnak azt tekintjük, ami közvetve (közvetlen rekurzió) vagy más függvények közbeiktatásával (közvetett rekurzió) meghívja önmagát.
Rekurzióval csak olyan esetek oldhatóak meg, amelyeknél biztosítani tudjuk, hogy véges számú általános lépés után elérjük a triviális megoldást. Rekurzív hívás esetén a függvény általában nem csak önmagát hívja, hanem ez előtt és után van lehetősége műveleteket végezni a továbbítandó paramétereken. Rekurzív hívás pszeudokód mintája:
44
A pszeudokódban található függvényhívások feladattól függően jelenthetnek tetszőleges összetett műveleteket.
Az implementált programot minden esetben Neumann elvű (tehát nem rekurzív) gépen hajtjuk végre.
Egyik gyakorlati megvalósítása a Verem adat szerkezet. Mindig az utoljára belehelyezett elemet (push) tudjuk belőle kiolvasni (pop)(vagyis LIFO – Last In First Out). Kiolvasáskor a kiolvasott elem törlődik. Gyakorlati megvalósítás: Gyakran használt adatszerkezet az operációs rendszer, illetve a processzor működése során eljárások hívásakor a verem tárolja el a hívó utasítást követő utasítás címét, és veremben tárolódnak a meghívott eljárás paraméterei, lokális változói, stb. Minden függvényhíváskor eltárolódik a visszatérési cím, illetve a függvény lokális változói. Visszatéréskor ezek törlődnek a veremből. Az általuk látott adatok szempontjából az egymás után hívott függvények valójában egymástól függetlenek. Az ugyanolyan nevű lokális változók emiatt nincsenek egymásra hatással.
Bemeneti paraméterek: •
Bemenet biztosítása külső változókon keresztül lehetőséget nyújt számunkra, hogy figyelemmel kísérjük az egyes lépések során a változók alakulását. Futás, tárhely szempontjából használata előnyös (nem kell minden adatot megadni paraméterként). A globális adattagokat a rekurzió bármely szintjéről elérjük.
•
Bemenet biztosítása paramétereken lehetőséget nyújt számunkra a kód áttekinthetőségében. Hátránya, hogy minden külső paramétert meg kell adni (minden példány létrehoz egy saját paramétert belőle), ezért nagyobb tárhelyigényű, futás szempontjából lassabb. 45
Rekurzív hívási lánc során problémát jelenthet az eredmény visszaadása, mivel az eredeti hívó, illetve a végeredményt elérő függvény között számos függvényhívás állhat.
Kimeneti értékek: •
•
•
Eredmény visszaadása külső változókon keresztül. (a hívó külső adatból olvassa be) int valtozo; public void rekurziv_fv(int parameter){ [....] valtozo=[....]; } Eredmény visszaadása függvény visszatérési értékkel. (hagyományos függvény visszatérési érték, biztosítani, hogy az önmagától visszakapott értéket továbbítsa) public int rekurziv_fv(int parameter){ [....] return [...]; } Eredmény visszaadása paraméterekkel. (cím szerinti paraméterátadásnál mindegyik szinten egyszerre módosul) public void rekurziv_fv(ref int parameter){ [....] parameter=[....]; }
Rekurzív hívási lánc során problémát jelenthet az eredmény visszaadása, mivel az eredeti hívó, illetve a végeredményt elérő függvény között számos függvényhívás állhat.
Rekurzió előnyei: • •
áttekinthetőbb kód bizonyos feladatoknál egyszerűbb megoldás
Rekurzió hátrányai: • • • •
nehezen értelmezhető nyomkövetés nagyszámú újrahívás esetén nehézkes költséges művelet nehéz a hibajavítás
46
16. Visszalépéses keresés (általános formája, gyakorlati példák) A visszalépéses keresés olyan feladattípusoknál alkalmazható hatékonyan, amelyeknél egy tetszőleges szabállyal a várt eredmények egy részéről is meg lehet állapítani, hogy nem lehet egy jó megoldás része. Az algoritmus a feladatmegoldás során nem folytat olyan utakat, amelyek nem vezethetnek megoldáshoz. A feladattól függő szabályokat általában két függvény segítségével adjuk meg: • ft(i, r) – visszatérési értéke igaz, ha az i. részeredményként elfogadható az r érték (a mi példánkban ez mindig igaz lesz) //van olyan érték amit nem vehet fel. • fk(i, r, j, q) – visszatérési értéke igaz, ha az i. helyen található r érték és a j. helyen található q érték nem zárják ki egymást (a mi példánkban akkor igaz, ha r != q) Amennyiben az összes lehetséges megoldást szeretnénk megtalálni a vizsgálandó problémára, akkor a piros résszel egészítjük ki az algoritmusunk általános megoldását.
47
Optimális megoldáskeresést alkalmazhatunk amennyiben a megoldások eredményértéke eltérő. (minimum kiválasztás)
Feladatok, amik megoldhatók az algoritmussal: • Hogyan helyezzünk el úgy 8 királynőt a sakktáblán, hogy azok ne üssék egymást. •
A sakktábla bármelyik mezőjéről be lehet-e járni egy huszárral az egész táblát úgy, hogy minden mezőt pontosan egyszer érintünk? // ft – megadott helyre léphet-e a huszár (táblán belül marad?) //fk – az előző lépések nem zárják-e ki az új helyet? (járt már ott?)
•
Adott M darab Ti tömegű tárgy, illetve egy hátizsák,amibe legfeljebb MAX tömegű tárgy fér. Adjunk egy optimális megoldást arra, hogy minél jobban kihasználjuk a hátizsák kapacitását!
•
Adott M darab őstermelő, akik fejenként KIi mennyiségű répát termesztenek. Adott N darab áruház, akik BEi mennyiségű répát igényelnek. Egy áruház csak egy őstermelőtől szeretne vásárolni (fordítva nincs ilyen kikötés)(változtassuk a répa árát és optimalizáljuk)
48
17. Program átalakítások)
transzformációk
(rekurzív
–
iteratív
Programozási tételek rekurzív formája:
Függvény kiszámítása rekurzívan:
49
Függvény iteratív leírása jobb rekurzióval
Függvény iteratív leírása balrekurzióval
Ciklusok átírása rekurzív megoldásra:
• •
Számlálós ciklus egyszerűen átírható elöl tesztelőssé. Amennyiben a ciklus előtt vagy után további műveletek szerepelnek, azokat célszerű egy másik függvényben (a rekurzió „0. szintjén”) elvégezni
50
Sorozatszámítás rekurzívan: Eljárás Sorozatszámítás(S, A, K, N) Ha K Parosak(int[] tomb, int n){ if (n < 0) return new List(); if (tomb[n] % 2 == 0){ List eredmeny = new List(); eredmeny.AddRange(Parosak(tomb, n - 1)); eredmeny.Add(tomb[n]); return eredmeny; } return Parosak(tomb, n - 1); }
51
18. Adatszerkezetek, láncolt listák, egyszerű láncolt listák műveletei I. (új elem felvétele, bejárás, törlés) Adatszerkezet Adatszerkezet: Az adatelemek egy olyan véges halmaza, amelyben az adatelemek között szerkezeti összefüggések vannak. Adatszerkezetek megvalósításai: • • • • • • •
Tömb Láncolt lista Fa, kupac Gráf Hasító táblázat Sor Verem
Lista Fogalmak Lista: 0 vagy több elem véges sorozata. Lista hossza: Az elemek előfordulási számának az összege a listában, az ismétlődések figyelembevételével (a ténylegesen listában lévő elemek száma). Üres lista: Olyan lista, amely nem tartalmaz egyetlen elemet sem (lista hossza 0). Részsorozat: Az eredeti listából 0 vagy több elem elhagyásával sorrendiséget megőrző részlista. Előtag, utótag: Az előtag olyan részlista, ami az eredeti lista első elemével kezdődik, az utótag, ami az utolsó elemével végződik. Az üres lista minden listának előtagja és utótagja. Elem pozíciója: Az elem listában betöltött pontos helyét meghatározó index.
Láncolt Lista Láncolt lista: A láncolt lista olyan adatszerkezet, amelynek minden eleme tartalmaz egy hivatkozást egy másik, ugyanolyan típusú elemre és az elemek összefüggő láncot alkotnak. Típusai: • • • •
Egyszeresen láncolt lista Rendezett láncolt lista Láncolt lista strázsa elemekkel Speciális láncolt listák o Kétirányú o Többszörösen láncolt o Ciklikus 52
A láncolt lista eleme két részből áll: •
Tartalom: Az adott listaelem adata(i). Fajtái:
•
egyszerű típus összetett típus objektum referencia Hivatkozás(ok): Hivatkozás(ok) láncolt lista elem(ek)re. Fajtái:
tömb index mutató (pointer) objektum referencia
Lista előnyei: Az elemek sorrendjét nem a fizikai rendezettség határozza meg, ezért gyorsabban és egyszerűbben lehet elem(ek)et beszúrni, törölni, láncban elfoglalt helyet módosítani. Nem igényel összefüggő memória területet tároláshoz. Lista hátrányai: Csak lineáris keresés alkalmazható keresésnél (minden elem vizsgálat),mert nincs közvetlen indexelés. Hivatkozások miatt nagyobb az elemek tárigénye. Bonyolult a szervezése. Egyirányú láncolt lista (Egyszeresen láncolt lista) • • • • •
Minden eleme láncolt lista típusú elem (tartalom, hivatkozás) Minden elemnek csak egy hivatkozása lehet , ezért egyszeresen láncolt lista. A fej hivatkozás része a lista első elemére mutat, a fej tartalmi része üres. Az utolsó elem hivatkozása az üres halmaz (gyakorlatban többnyire a „null” kifejezés) jele:Ø (Üres lista esetén a fej rá hivatkozik.) Az elemek egymás utáni sorrendjét nem csak a fizikai sorrend szabhatja meg.
53
Bejárás Eljárás Bejárás(fej) p ← fej Ciklus amíg p ≠ ∅ Feldolgozás(p.tart) p ← p.köv Ciklus vége Eljárás vége
A bejárás metódussal végig lépkedünk a lista összes elemén. A „Feldolgozás(p.tart)” sorban van lehetőségünk a lista minden elemével műveletet végezni. (pl összegképzés , keresés, számtani átlag, maximum kiválasztás, stb.) A Bejárás metódus előtt meg kell vizsgálni a lista tartalmát. (üres lista)
Új elem felvétele Eljárás MegadottHelyreBeszúrás(fej, n, újérték) // n=1..listahossz ElemLétrehozás(uj) uj.tart ← újérték Ha (fej = ∅) vagy (n = 1) akkor // lista elejére való beszúrás uj.köv ← fej; fej ← uj különben p ← fej; i ← 2 // ha vége az elemeknek, vagy elértük a keresett helyet Ciklus amíg (p.köv ≠ ∅) és (i < n) p ← p.köv; i ← i + 1 Ciklus vége uj.köv ← p.köv p.köv ← uj Elágazás vége Eljárás vége
Törlés Eljárás Törlés(fej, törlendő) p ← fej; e ← ∅ Ciklus amíg (p ≠ ∅) és (p.tart ≠ törlendő) // amíg nem lista vége vagy keresett e←p p ← p.köv Ciklus vége Ha p ≠ ∅ akkor // ha van következő elem Ha e = ∅ akkor fej ← p.köv // ha az első elemet töröljük külöben e.köv ← p.köv // ha az a közepén van ElemFelszabadítás(p) különben Kiir(„Nincs ilyen elem”) // vissza adja, hogy nincs olyan elem amit törölni szeretnénk. Elágazás vége Eljárás vége
Teljes lista törlése Eljárás ListaTörlés(fej) Ciklus amíg (fej ≠ ∅) p ← fej fej ← fej.köv ElemFelszabadítás(p) Ciklus vége Eljárás vége
54
19. Adatszerkezetek, láncolt listák, speciális listák műveletei II. (rendezett láncolt lista, többirányú, többszörösen láncolt lista, strázsa) Rendezett láncolt lista Rendezett láncolt lista: A láncolt lista elemei tartalmuk szerint valamilyen előre definiált rendezési szempont szerint sorrendben helyezkednek el. Az elemeket a lista létrehozásától kezdve célszerű rendezni, mert a későbbi rendezés nehézkes. (célszerű beszúró rendezést használni) Az egyszeres egyirányú rendezett lista keresés és elem beszúrás metódusai a rendezettség fenntartásával egészülnek ki. (gyorsító hatás) Keresés Függvény KeresésRendezettben(fej, mitkeres) p ← fej Ciklus amíg (p ≠ ∅) és (p.tart < mitkeres) p ← p.köv Ciklus vége van ← (p ≠ ∅) és (p.tart = mitkeres) Ha van akkor Keresés ← p Függvény vége
// ha a keresettnél már nagyobb
// ha p.tart a keresett elem
Beszúrás Eljárás RendezettBeszúrás(fej, újérték) ElemLétrehozás(uj); uj.tart ← újérték p ← fej; e ← ∅ Ciklus amíg (p ≠ ∅) és (p.tart < újérték) e ← p; p ← p.köv Ciklus vége Ha e = ∅ akkor uj.köv ← fej fej ← uj különben uj.köv ← p e.köv ← uj Elágazás vége Eljárás vége
// beszúrandó hely keresése
// ha üres a lista vagy a lista végén vagyunk
// ha 2 elem közé
Strázsa Strázsa (sentinel) elemek: A lista elejére és a végére felvett kiegészítő elemek. Értékes adatot nem tárolnak, csak technikai szerepük van, hogy kiküszöböljék a kivételes eseteket. Előnyei: Egyszerűbb és gyorsabb beszúrás és törlés. Rendezett lista esetén az első strázsa célszerűen az adott implementációban legkisebb, az utolsó pedig a lehető legnagyobb értéket tartalmazza. (gyakorlatban +/- végtelen)
55
Listalétrehozáskor célszerű ezeket a technikai elemeket beszúrni. Eljárás StrázsaInicializálás(fej) ElemLétrehozás(st2) st2.tart ← +∝ st2.köv ← ∅ ElemLétrehozás(st1) st1.tart ← -∝ st1.köv ← st2 fej ← st1 Eljárás vége
Kétirányú láncolt lista Jellemzői: -
A lánc minden eleme tartalmaz egy hivatkozást a sorban rá következő, illetve a sorban őt megelőző elemre is.
-
Az első elem előtti elemre mutató hivatkozás és az utolsó elem utáni elemre mutató hivatkozás értéke a kitüntetett üres halmaz hivatkozása (∅)
-
Az első elem címét a fej változó az utolsó elemnek a címét a vége változó tartalmazza.
Alkalmazásának előnyei: -
gyorsabb keresési lehetőség nyílik, ha tudjuk, hogy az elem a lista melyik részében helyezkedhet el.
-
törlésnél és beszúrásnál az előző elem és a következő elem mutatók segítségével sokkal gyorsabban és egyszerűbben végezhető el.
Alkalmazásának hátrányai: -
Nagyobb a helyfoglalása az elemeknek mint egyszerű lista esetén.
-
Bonyolultabb a beszúrás az összes hivatkozás beállításának szükségessége miatt.
Többszörösen láncolt lista Jellemzői:
56
-
Minden eleme tartalmaz egy tartalom részt (elemenként csak egyszer szerepel) és n darab tetszőleges számú hivatkozást. Az n darab hivatkozás egyenként n darab független láncolt listát alkot, amelyekben az elemek sorrendje eltérő. Minden hivatkozás utolsó elemének következő mutatója az üres halmazra (∅) hivatkozik.
-
’n’ darab listafejet tartalmaz, melyek a láncolt listák kezdeti elemeire mutatnak.
-
A műveletek az egyszerű láncolt listánál tanultakkal egyeznek meg.
Hátránya: -
Bonyolultabb a listába való beszúrás és törlés a sok hivatkozás miatt.
-
Egy elem tartalmi módosítása során az egyes láncolt listák módosításai körülményesebbek. (több listában változhat a sorrend)
Ciklikusan láncolt lista Az utolsó elem következő elem mutatóját beállítjuk az első elem hivatkozásaként. Alkalmazásának előnyei: -
A fejmutató hivatkozhat a listán belül bármelyik elemre. (több belépési pont)
-
Megoldódik az első és az utolsó elemre figyelés problémája törlés és beszúrás metódusok esetén.
Alkalmazásának hátrányai: -
A bejárás megnehezedik, mert vizsgálnunk kell a körbeérés lehetőségét.
-
Csak speciális rendezést használhatunk, mert az utolsó elem az elsőre mutat. (pl. nagyság szerinti sorrendet nem használhatunk.)
-
Sok azonos elem esetén használata körülményes.
57
20-21 B-fa adatszerkezet, B-fába való beszúrás algoritmusa (B-fa jellemzői, előnyei, felépítése, új elem felvétele, törlés) Általánosan a B-fákról: A B-fa egy kiegyensúlyozott (jól súlyozott) keresőfa, vagyis az összes levél eleme azonos távolságra található a fa gyökerétől (minden levél eleme azonos mélységben van). Kiegyensúlyozottságából következik, hogy hatékonyan lehet alkalmazni háttértárolókon is. Futási idejét két dolog határozza meg, a lemez hozzáférések száma és a központi egység műveleteinek száma. A gyakorlatban például az NTFS fájlrendszernél is alkalmaznak B-fát, mert a mai háttértárolókon gyorsabban lehet adatot írni/olvasni blokkonként, mintha egy blokk mennyiségű adatot szeretnénk írni/olvasni elemi adatokként. (Elemi adatok írása/olvasása helyett blokkok írása/olvasása.) Az adatszerkezet meghatározó elemei: •
Csúcs (node): Az adatszerkezet építőköve elemeket tartalmaz. Kitüntetett csúcs a gyökér. A csúcsokban tárolt elemek száma alulról és felülről is korlátos. A korlátozást az adatszerkezet felépítésénél előre meg kell választani (jelen esetben t paramétert használunk rá). A nem gyökér csúcspontok elemszáma legfeljebb 2t-1lehet, és legalább t-1 elemet kell tartalmaznia. A levélelemek kivételével a csúcsban szereplő elemszám határozza meg, hány gyermekeleme lehet az adott csúcsnak. Mindig elemszám+1 gyermekelembe sorolja be a további elemeket. Amennyiben egy elem van a csúcsban, akkor két gyermekeleme (csúcsa) lehet, ha 2 elem van a csúcsban, akkor három gyermekeleme lehet, stb. (jelen esetben a B és a 2, 4 elemek a szülő csúcsok, az A, C, 1, 3,5, 6 elemek a gyermekelemek) A csúcsok bináris fa típusú szerkezetet biztosítanak a kulcsok segítségével. Számok esetén a mellékelt ábra példáján bemutatva: o Minden olyan elem, ami kisebb kettőnél, a kettestől balra lévő gyerekelemben helyezkedik el. o Azok az elemek, amelyek értéke kettőnél nagyobb, de kisebb mint négy, a kettes és a négyes közti gyermekelemben helyezkednek el. o Minden elem, ami nagyobb mint négy, a négytől jobbra lévő gyermekelemben helyezkedik el.
•
Elem : o „Kulcs” mező értéke alapján van rendezve a fa. (pl. ABC sorrend, számok számegyenesen betöltött helyzete) o „Levél” mező logikai érték alapján tudjuk megkülönböztetni az elemeket a fában lévő elhelyezkedésükről. (Levél vagy belső csúcs.) 58
o
„Tartalom” mező tetszőleges típusú változót tartalmazhat. Feltételezzük, hogy a kulcsokkal együtt mozog.
B-fák műveletei: Bejárás és keresés: Alkalmazhatók a bináris fák esetében megismert bejárások és keresés műveletek, amennyiben kezeljük a csúcsban található több elem lehetőségét. A csúcsban található elemszám biztosítja, hogy kevesebb csúcspontbetöltés szükséges. Ezek a műveletek nem változtatják meg a fa felépítését. Beszúrás, törlés és keresés ideje megközelítőleg O(log(n)). Beszúrás: Eljárás Insert(object k, Object e) //k jelöli a kulcsot, e jelöli a beszúrandó elemet. Gyökértől lefele haladunk a fán, megkeressük a beszúrandó kulcsú elem helyét. Ezt bináris fákra jellemző beszúrás módszerrel tesszük. (Az elemnél nagyobb érték esetén a jobb részfába, az elemnél kisebb elem esetén a bal részfába.) Ha az adott kulcs már szerepel a fában, akkor a kulcs baloldali részfájában haladunk tovább egészen addig, amíg a levélelemhez nem érünk el. Beszúrás csak levélelembe történhet. Kulcskeresés közben a gyökér elemtől lefelé haladva minden lépésben megvizsgáljuk, hogy át kell-e strukturálni a fát. Amennyiben megtaláltuk az elem helyét, és beszúrásához már nem kell strukturálni, akkor beszúrjuk az elemet a helyére. Eljárás vége
Beszúráshoz kapcsolódó átstrukturálás: Ha egy csúcspontban elértük a maximálisan benne tárolható elemszámot, és egy új elemet kellene beszúrni a részfájába vagy az adott csúcsba, akkor a kiegyensúlyozottság fenntartása miatt át kell strukturálni a fát. Szét kell bontani a vizsgált csúcsot, és középső elemét a szülő csúcsba kell helyeznünk. „F” –t szeretnénk beszúrni, a csúcsban tárolható maximális elemszám 7. (átstrukturálni nem kell)
59
„G” –t szeretnénk beszúrni, a csúcsban tárolható maximális elemszám 7. (átstrukturálás)
Amennyiben a gyökérelem telített, azt is szét kell vágni. Ilyenkor a középső elem lesz az új gyökér, a tőle jobbra lévő elemek a jobbgyermek csúcspontjába kerülnek, a baloldali elemek pedig a bal gyermekbe. A gyökérvágás az egyetlen folyamat, aminek hatására a fa magassága változik. „X” szúrunk, de a gyökér telített.
Átstrukturálásra két dolog miatt van szükség: • •
Helyet csináljunk az új elemnek. Helyet csináljunk a kiszakított elemnek.
Törlés Eljárás Remove (Object k) Megkeressük a törlendő elem kulcsát. Ha egy levélcsúcsban nem egyedüli elem a törlendő, akkor töröljük. Ha egy belső csúcsban található a törlendő elem, akkor kicseréljük a következő legnagyobb elemre. A következő legnagyobb elemet mindig egy levélelem csúcsa tartalmazza a fa alján. Egy elemet akkor lehet törölni, ha a fa kiegyensúlyozottsága fennmarad, ezért sok esetben át kell strukturálni. Ezesetben elindulunk a gyökérelemtől, és elkezdjük strukturálni. 60
Eljárás vége
Törléshez kapcsolódó átstrukturálás Lefelé haladásunk során megsemmisítjük az egy elemet tartalmazó csúcsokat a levélelemekig. Megvizsgáljuk, milyen elemszámmal rendelkeznek a közvetlen testvérek. Amennyiben a csúcs közvetlen testvérei között van több elemet tartalmazó csúcs, akkor elemet ragadunk el a több elemet tartalmazó közvetlen testvércsúcsból. Elragadni csak forgatás útján tudunk. A részfák struktúrája forgatás során nem változik, ezért egészben mozgathatóak egyik helyről a másikra (az ábrán „S” ként van feltüntetve). Részfák esetén a levélelemekig kell lehatolni.
Amennyiben nincs a közvetlen testvéreknek, csak egy eleme, akkor szülőktől ragadunk el elemet. A gyökérelem kivételével ebben az esetben mindig van a szülőnek legalább két eleme. A folyamatot egyesülésnek nevezzük.
Amennyiben a vizsgálandó elem szülője a gyökérelem, és minden testvércsúcsnak csak egy eleme van, akkor egyesítjük a csúcsokat, és új gyökérelemet hozunk létre, amely háromelemű lesz. Ebben az egy esetben csökken csak a fa magassága egy szintet.
61
Amennyiben a korlátozási tényező három, következőképpen történik a megvalósítás: //Ezesetben minden csúcsnak a gyökérelem kivételével legalább két elemet kell tartalmaznia. //Megkeressük a törlendő utáni legnagyobb elemet, és beszúrjuk a törlendő helyére, ügyelve a B-fa tulajdonság megőrzésére.
62
22. Fa adatszerkezetek, bináris fák alapműveletei (új elem felvétele, bejárások, törlés) Fa adatszerkezet A gráfelméletben fának vagy fa gráfnak nevezzük azokat a gráfokat, amelynek bármely két csúcsát pontosan egy út köti össze, azaz a fák körmentes összefüggő gráfok. A számítástechnikában fának nevezzük azon összefüggő csomópontok és élek összességét, amelyeknek bármely két csúcsát pontosan egy él köt össze, és egyetlen kitüntetett csomópontjától (gyökértől) különböző összes elemének legfeljebb egy szülő eleme van. A csomópontok és élek összefüggőek, bármely nem „gyökér” csomóponttól kiindulva a szülőkön keresztül a gyökérhez jutunk el.
Grafikus szemléltetés: Adott egy él halmaz (V) és adott egy csúcspont/csomópont-halmaz (E), amik egy fa gráfot(F) alkotnak(F=(V,E)). •
Az u csúcspont a gyökér elem.
•
v-t a w valódi szülőjének, w-t pedig a v valódi gyerekének nevezzük.
•
Ha w-ből vezet út u ba, akkor u őse w-nek.
•
A w,x,y,z csúcspontok nem rendelkeznek valódi leszármazottal, ezeket levél elemeknek nevezzük.
•
Bármely gyökérelemtől különböző csúcspont gyökér elemként való kiválasztásával az adott fa egy részfáját kapjuk.
Fa jellemzői: •
Csomópont mélysége: A gyökértől a vizsgált csúcspontig elvezető út hossza.
•
Fa magassága: a leghosszabb levelekig vezető út hossza.
•
Csomópont szintje: a fa magasságának és a csomópont mélységének a különbsége.
•
Láncolt lista szerkezetre vezethető vissza. A fa egy eleme elképzelhető, mint egy tartalom részből és egy további részfákkal rendelkező struktúrából (mutató) álló láncolt lista-elem. (TFa = Struktúra(tartalom, fák)) 63
Bináris Fa Bináris fa olyan speciális fa, amely minden elemének (csúcspontjának) legfeljebb két gyermek eleme lehet (balgyerek, jobbgyerek). //TBinárisFa = Struktúra (tartalom, balfa, jobbfa) Tartalom típusa lehet: •
egyszerű típusú
•
összetett típusú
•
objektum referencia
Jellemzői: •
Balgyerek, jobbgyerek: a csomópont baloldali illetve jobboldali részfák gyökér elemére hivatkozik.
•
Ha nincs valamilyen oldali gyermek eleme egy csúcspontnak, akkor üres halmazzal jelöljük az elemre mutató hivatkozást.
•
Láncolt listáknál megismert kezdeti érték mutató segítségével hivatkozunk a gyökér elemre. Esetünkben a gyökér kulcsszóval fogjuk jelezni.
•
Egyéb hivatkozásokat is tárolhatunk (pl. szülőre hivatkozást).
Bináris keresőfa (BST) A bináris keresőfa olyan bináris fa, amely valamilyen szempont (kulcs) alapján rendezett. //TBSTElem = Struktúra (kulcs, tartalom, balgyerek, jobbgyerek) A rendezésre szolgáló kulcs megvalósításai: •
különálló kulcs mező,
•
a kulcs a tartalom része,
•
a kulcs a tartalomból számítható érték.
A rendezés irányára vonatkozóan nincs megkötés, viszont a rendezésnek egyértelműen és egységesen az egész fára alkalmazhatónak kell lennie. Példa: Számok esetében a relációk felhasználásával alakíthatunk ki egy ilyen bináris keresőfát. Kulcs alapján rendezett: a fa minden r csomópontjára igaz, hogy r baloldali részfája legfeljebb r.kulcs nagyságú, r jobboldali részfája pedig legalább r.kulcs nagyságú kulcsokat tartalmaz.
64
Bejárás
Bejárás: az adatszerkezet valamennyi elemének egyszeri elérése (feldolgozása). Feldolgozásának sorrendje alapján három fő változat különböztethető meg: PreOrder
Gyakorlatban: Fa elmentésénél használjuk. InOrder
Gyakorlatban: Elemek elérése rendezés szerinti sorrendben (növekvő vagy csökkenő). PostOrder
Gyakorlatban: Fa felszabadítása. 65
Új elemfelvétel Új elembeszúrásnál (beláncolásánál) ügyelni kell a bináris keresőfa-tulajdonság fenntartására. Függvény Beszúrás(címszerint p, újkulcs) Ha p = ∅ akkor ElemLétrehozás(p) p.kulcs ← újkulcs; p.bal ← ∅; p.jobb ← ∅ Beszúrás ← p Különben Ha p.kulcs > újkulcs akkor Beszúrás ← Beszúrás(p.bal, újkulcs) Különben Ha p.kulcs < újkulcs akkor Beszúrás ← Beszúrás(p.jobb, újkulcs) Különben Beszúrás ← p Elágazás vége Elágazás vége Elágazás vége Függvény vége
Törlés Elem törlése (kiláncolása) során ügyelni kell a bináris keresőfa-tulajdonság fenntartására. Három törlési lehetőséget különböztetünk meg: 1. Levél elemet szeretnénk törölni. (kódban a második lehetőséggel egybe van vonva) 2. Olyan elemet szeretnénk törölni, aminek csak 1 gyermek eleme van. 3. Olyan elemet szeretnénk törölni, aminek 2 gyermek eleme van.(C eset)
Eljárás Törlés(címszerint p, törlendő) Ha p = ∅ akkor „Nincs ilyen elem” Különben Ha p.kulcs > törlendő akkor Törlés(p.bal, törlendő) Különben Ha p.kulcs < törlendő akkor Törlés(p.jobb, törlendő) Különben Ha p.bal = ∅ akkor q ← p; p ← p.jobb; ElemFelszabadítás(q) Különben Ha p.jobb = ∅ akkor q ← p; p ← p.bal; ElemFelszabadítás(q) Különben TörlésCEset(p, p.bal) Elágazás vége Elágazás vége Elágazás vége Elágazás vége Elágazás vége Eljárás vége
//ha nem a kívánt, akkor rekurzív hívás //ha nem a kívánt, akkor rekurzív hívás //ha nincs balgyermeke (2ik eset)
//ha nincs jobbgyermeke (2ik eset) //meghívjuk a bal gyerekre a C esetet
66
Eljárás TörlésCEset(p, címszerint r) Ha r.jobb ≠ ∅ akkor //rekurzívan lemegyünk a legjobboldalibb elemig TörlésCEEset(p, r.jobb) Különben //ha megvan a legjobboldalibb elem akkor p.kulcs ← r.kulcs //átírjuk a törlendő címére az összes értékét p.tart ← r.tart q←r r ← r.bal //töröljük a 2ik eset szerint az r-et (csak baloldali gyereket feltételezve) ElemFelszabadítás(q) //felszabadítjuk a q elemet a memóriából Elágazás vége Eljárás vége
Bináris fa előnyei: •
Rendezettségéből következik, hogy gyors a törlés és beszúrás.
•
Módosító műveletek során ritkán kell az egész fát átrendezni
Bináris fa hátrányai: •
A rekurzív műveletek költségesek.
•
Nincs közvetlen elérhetősége az elemeknek.
•
Gyors keresés csak kiegyensúlyozott fában lehetséges.
•
Két gyermek címének tárolása miatt nagyobb a helyfoglalás.
Felhasznált irodalom http://hu.wikipedia.org/wiki/Fa_(gr%C3%A1felm%C3%A9let) http://hu.wikipedia.org/wiki/Adatszerkezet http://hu.wikipedia.org/wiki/Gr%C3%A1felm%C3%A9leti_fogalomt%C3%A1r http://staff.kzs.hu/tamas/programozas/adatsz.html#fa
67
23. Fa adatszerkezetek, piros-fekete (forgatások, új elem felvétele, törlés)
fa
adatszerkezet
Piros fekete fa: A piros-fekete fa olyan bináris keresőfa, amely a következő tulajdonságokkal rendelkezik: • • • •
minden csúcsának színe piros vagy fekete minden levél elemének színe fekete minden piros csúcsú elemnek két fekete gyereke van minden tetszőlegesen kiválasztott csúcsra igaz, hogy a belőle induló részfa összes levélbe vezető útján ugyanannyi fekete csúcs van.
//A fenti felsorolás miatt, ha a fa levéleleme piros lenne, akkor beszúrunk két fekete null vagy nil típusú gyermeket. Alapfogalmak: • • • •
Egy fa kiegyensúlyozott, ha legfeljebb egy szintnyi (mélység) eltérés van az egyes (azonos szinten található) részfái között. Teljesen kiegyensúlyozott fa: minden csúcsából leágazó bal- és jobboldali részfa csúcsainak száma legfeljebb eggyel különbözik egymáshoz képest. Teljes fa: Minden csúcsból leágazó bal- és jobboldali részfa csúcsainak száma azonos. Megközelítőleg kiegyensúlyozott egy fa, ha biztosítható, hogy bármely, a gyökértől levélig vezető, út hossza nem nagyobb, mint a legrövidebb ilyen út hosszának a kétszerese.
A piros-fekete fa a bináris keresőfától abban tér el, hogy kiegyensúlyozott. A kiegyensúlyozottságot forgatás segítségével éri el.
68
Forgatás
Forgatás: olyan lokális művelet, amely megváltoztatja a fa szerkezetét, de megőrzi a rendezettséget. Megkülönböztetünk balra- illetve jobbra forgatás műveletet.
69
Balra forgatás forráskódja: Eljárás Balra-forgat(x) y ← x.jobb x.jobb ← y.bal Ha y.bal ≠ ∅ akkor y.bal.szülő ← x y.szülő ← x.szülő Ha x.szülő = ∅ akkor gyökér ← y Különben Ha x.szülő.bal = x akkor x.szülő.bal ← y különben x.szülő.jobb ← y Elágazás vége y.bal ← x x.szülő ← y Eljárás vége
Beszúrás
70
Egyéb műveletek Bejárás – –
azonos az egyszerű bináris keresőfánál megismerttel a piros-fekete tulajdonságnak nincs szerepe
Keresés – –
azonos az egyszerű bináris keresőfánál megismerttel a piros-fekete tulajdonságnak nincs szerepe
Törlés – –
alapja az egyszerű bináris keresőfánál megismert törléssel, kiegészítve egy piros-fekete tulajdonságot biztosító karbantartó eljárással a beszúráshoz hasonlóan ezt átszínezésekkel és forgatásokkal oldja meg
Felhasznált irodalom:
http://www.cs.bme.hu/~ildi/algel/pirosfekete.pdf http://www.ms.sapientia.ro/~kasa/adat9.pdf http://en.wikipedia.org/wiki/Red-black_tree http://en.wikipedia.org/wiki/Tree_rotation
71
24. Gráfok 1 (Labirintus & Dijkstra) Gráf elmélet: A gráf a matematikai gráfelmélet és a számítógép-tudomány egyik alapvető fogalma. A gráf véges sok dolog (csomópontok, csúcsok) és rajtuk értelmezett véges sok összeköttetés (élek) halmaza.
Egy gráfot megadhatunk csúcsainak és éleinek felsorolásával, vagy szemléletesebben egy diagram formájában, ahol a pontok felelnek meg a gráf csúcsainak, az őket összekötő ívek pedig az éleknek. A két megadási mód ekvivalens, azaz a gráf pusztán egy struktúra, semmilyen megjelenítési információt nem tartalmaz, így különböző diagramok is tartozhatnak ugyanahhoz a gráfhoz.
Gráf csoportosítások alakjuk és szerkezeti felépítésük szerint: •
Alapértelmezésben a gráf irányítatlan, azaz nem teszünk különbséget „A-ból B-be”, illetve „Bből A-ba” menő élek között. Ezzel szemben az irányított gráfokban (angolosan: digráf) a két pont között irányított élek vannak.
•
Azt a gráfot amelyben nincs hurok, sem többszörös él, egyszerű gráfnak nevezzük. (vagyis egy gráf lehet hurkot tartalmazó, lehet többszörös éllel rendelkező, lehet egyszerű)
•
Amennyiben a gráfokat összekötő éleket súly tényezőkkel(pl. költségekkel) látjuk el, a gráfot súlyozott gráfnak nevezzük. (vagyis van súlyozott és súlyozatlan gráf)
•
A gráf összefüggő, ha bármely pontjából bármely másik pontjába élek mentén el lehet jutni.(vagyis van összefüggő és nem összefüggő gráf)
A fenti csoportok önállóan , de keveredve, illetve együttesen is jellemezhetnek egy gráfot.
Gráf tulajdonságai: • • • •
A gráf két élét szomszédosnak nevezzük, ha van egy közös csúcspontjuk. Két csúcspont szomszédos, ha van egy közös élük. ( éllel vannak összekötve) Egy séta szomszédos csúcsok és élek váltakozó sorozata. Az önmagát nem metsző sétát útnak hívjuk, ha első és utolsó csúcsa különbözik, illetve körnek, ha ez a két csúcs megegyezik.
72
Labirintus Probléma ismertetése
Adott egy súlyozatlan és irányítatlan gráf. Milyen módszerrel tudunk tetszőlegesen kiválasztott két pontja között véges lépésszám alkalmazásával egy egyszerű utat találni.
Konkrét megvalósítás
A labirintust egy véges sok szobából (csúcspontból) álló rendszerként képzeljük el, amelyben a szobákat folyosók (élek) kötik össze. (nem feltétlenül összefüggő, nem üres, nem irányított gráf)
Minden folyosó két szobát köt össze. Szomszédos szobáknak nevezzük a folyosó két végén lévő szobákat. Önmagukba nyíló szobákat figyelmen kívül hagyva zsákutcának nevezzük azokat a szobákat amelyeknek csak egy szomszédos szobája van.
Geometriailag a labirintus egy pontrendszer, amely pontrendszerrel (szobákkal) és bizonyos pontpárokat összekötő szakaszokkal (folyosókkal) írható le.
Algoritmus alapja
•
Y szoba elérhető X szobából, ha van olyan út, amelyik folyosókon és szobákon át oda vezet.
•
Ha X-ből Y elérhető, akkor egyszerű úton is elérhető. (minden szobán csak egyszer haladunk át). A mi esetünkben színekkel fogjuk megkülönböztetni a folyosókat. Felhasznált folyosó típusok:
o
Zöld: Olyan folyosó, amin még egyszer sem haladtunk át
o
Sárga: Olyan folyosó, amin egyszer haladtunk át: 73
o
•
Piros: Olyan folyosó, melyen kétszer haladtunk át
Fonál felhasználása, hogy megkülönböztessük merre jártunk már.
o
fonal legombolyítása: Átmenni a következő szobába zöld út sárgává változtatása
o
fonal felgombolyítása: Visszamenni egy szobát a sárga folyosó pirossá változtatás
Két szobát különböztetünk meg a kiindulásit ezt A szobának nevezzük, itt van Ariadné, valamint a cél szobát az M-et itt van Minotaurusz. T vagyis Tézeusz feladata eljutni A szobából M szobába.
Döntési táblázat
Ha egy szobába érünk, sorra vesszük a lépéseket egytől ötig, amelyik először teljesül aszerint lépünk. Ezt addig ismételjük, amíg megálláshoz nem jutunk.
• • • • •
Minotaurusz: az adott szobában felfedezzük a Minotauruszt. (teendő: Megállás) Hurok: az adott szobából két sárga folyosó nyílik. (teendő: a fonal felgombolyítása és vissza egy szobát) Zöld út: az adott szobából legalább egy kijárat van, ami még zöld (teendő: elindul a zöld folyosón fonal legombolyítása) Ariadné: a szobában van Ariadné (ott van ahonnan indult) (teendő: Megállás) Egyéb: Az előzőek közül egyik sem áll fenn. (teendő: a fonal felgombolyítása és vissza egy szobát) (zsákutca)
74
Tételek Az algoritmus használhatósága a következő állításokból igazolható.
• • •
Tetszőleges A és M (A≠M) esetben véges sok lépés után T megáll A vagy M szobájában. Ha a megállás M-nél történik, akkor M elérhető. Ekkor a fonál A és M közötti egyszerű utat határoz meg. Ha a megállás A-nál történik, akkor M nem elérhető.
Tétel bizonyítások
Az első tételt lépések számára vonatkozó teljes indukcióval bizonyítjuk. A döntési táblázat használata biztosítja számunkra a tétel bizonyítását, vagyis az algoritmus bármelyik fázisában ez a két lehetséges állapot érvényesül. • Ha nincs sárga folyosó, akkor T a szobájában van. • Ha van sárga folyosó, akkor A-tól T-ig egyszerű út van és ez a sárga folyosó. (döntési tábla feltételek alapján magyarázható)
Második állítás bizonyítása Ha T, M szobájában áll meg akkor sárga út köti össze A-t és M -et, aminek létezését az előző bizonyítással igazoltuk (döntési tábla feltételek alapján magyarázható)
Harmadik állítás igazolása. T bármelyik folyosón vagy kétszer vagy egyszer se haladt át (nincs sárga folyosó, A –ból minden kivezető folyosó piros) (döntési tábla feltételek alapján magyarázható)
Gyakorlati megvalósítás Az algoritmus gyakorlatban való alkalmazásának egyik fontos kérdése, hogy miszerint válasszon a zöld utak közül. A véletlen zöld út választás kiküszöbölése esetén az algoritmus leprogramozása biztosan megadja az egyszerű utat A és M között amennyiben létezik ilyen út.
75
Dijkstra Probléma ismertetése Adott egy irányított (irányítatlan is lehet), súlyozott gráf. Ebben az irányított gráfban szeretnénk megkeresni a legrövidebb utakat egy adott csúcspontból kiindulva. A Dijkstra-algoritmus egy mohó algoritmus, amely helyi optimumok megvalósításával próbálja megtalálni a globális optimumot. Az algoritmus használható arra is, hogy adott pontból kiindulva a gráf összes többi pontjába vezető legrövidebb utakat megkeressük.
Bementi tényezői egy súlyozott irányított G gráf ,és a G gráfnak egy P csúcspontja. Az élekhez rendelt súlytényezőket tekinthetjük a két pont közötti távolság általánosításának ezt másnéven költségnek is nevezhetjük. A kiindulási pont és egy tetszőleges pont közötti út költsége az úton lévő élek költségének az összege.
Algoritmus - 1
1. Állítsuk be az összes csúcsba való eljutás kezdő értékét. Kiindulási csúcs legyen nulla a többi csúcs pedig legyen végtelen. 2. Állítsuk be az összes csúcsot eddig nem látogatottra és állítsuk be a kezdő csúcsot (jelen esetben az „a”) 3. Számítsd ki a szomszédos csúcspont távolságát az él súly értéke és az adott csúcs és kiinduló elem távolságából. (aktuális elemtől való távolság + aktuális kezdetitől számított távolság) Ha az így kapott távolság kisebb mint az adott csúcspont elérésének beállított távolsága akkor cseréljük le az elérést a kisebb értékre 4.Ha az összes körülötte lévő csúcsot megvizsgáltuk akkor meghatároztuk a legrövidebb utat abba a csúcsba így többet már nem kell vizsgálnunk az adott csúcsot. 5. Át állítod az aktuális csúcspontot a legkisebb súly értékkel rendelkező szomszédra majd ismételd a 3-as lépéstől addig amíg van nem felkeresett csúcs.
76
Algoritmus - 2
Kell: kiinduló csúcs (Kezdeti), innen számoljuk a legrövidebb utat az összes többi csúcshoz Inicializálás •
Minden I csúcs távolsága legyen az I és a „Kezdeti” csúcs távolságának negatív értéke (vagyis az őket összekötő él súly tényezője ezt egy Suly[] tömbben tároljuk). //A negatív távolság azt jelzi, hogy a csúcs még nincs kész. • • •
Kezdetivel nem szomszédos csúcsok távolság értéke legyen mínusz végtelen. Minden I csúcsnál tároljuk azt a csúcsot amin keresztül az I-be jutottunk(ezt egy Os tömbben tároljuk) A Kezdeti csúcs előtti csúcs legyen -1, ezzel jelezzük, hogy ez a Kezdeti a kiindulócsúcs ( Os[Kezdeti]= -1 )
Eljárás Dijkstra Ciklus, amíg van negatív súly (vagyis: amíg létezik nem-kész csúcs) • • •
Minimum=az abszolút értékben legkisebb negatív súly sorszáma; Suly[minimum] = -Suly[minimum]; Minden nem-kész (vagyis negatív) I súlyra megnézzük, hogy a jelenlegi Suly[I] súlynál abszolút értékben kisebb súlyt kapunk e, ha nem az Os[I] eddigi előző csúcson, hanem a Minimum-csúcson keresztül közelítjük meg. Ha igen, akkor ezzel frissítjük a Suly[I]-t, és Os[I]=Minimum;
Ciklus vége Eljárás vége
77
1 5 IDX
Os
S
Os
S
Os
S
Os
S
Os
S
1
-1
0
-1
0
-1
0
-1
0
-1
0
2
1
-10
4
-8
4
8
4
8
4
8
3
1
-V
4
-14
2
-9
2
9
2
9
4
1
-5
1
5
1
5
1
5
1
5
5
1
-V
4
-16
4
-16
3
-10
3
10
Felhasznált Irodalom Gráf
http://hu.wikipedia.org/wiki/Gr%C3%A1f
http://erettsegi.com/matematika/mit-nevezunk-grafnak-mi-az-n-pont-teljes-graf-mi-az-egyszerugraf-mi-az-osszefuggo-graf/ 78
Labirintus
http://nik.bmf.hu/csink/aao/labirintus.pdf
Dijkstra
http://hu.wikipedia.org/wiki/Dijkstra
http://hu.wikipedia.org/wiki/Dijkstra-algoritmus
http://hu.wikipedia.org/wiki/Moh%C3%B3_algoritmus
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
http://nik.bmf.hu/szabozs/SZIGO/04Varosok.zip //Docs könyvtárba van anyag hozzá.
79
25. Gráfok II. (Kruskal algoritmus és alkalmazásai) A gráf a matematikai gráfelmélet és a számítógép-tudomány egyik alapvető fogalma. A gráf véges sok dolog (csomópontok, csúcsok) és rajtuk értelmezett véges sok összeköttetés (élek) halmaza.
Egy gráfot megadhatunk csúcsainak és éleinek felsorolásával, vagy szemléletesebben egy diagram formájában, ahol a pontok felelnek meg a gráf csúcsainak, az őket összekötő ívek pedig az éleknek. A két megadási mód ekvivalens, azaz a gráf pusztán egy struktúra, semmilyen megjelenítési információt nem tartalmaz, így különböző diagramok is tartozhatnak ugyanahhoz a gráfhoz.
Gráf csoportosítások alakjuk és szerkezeti felépítésük szerint: •
Alapértelmezésben a gráf irányítatlan, azaz nem teszünk különbséget „A-ból B-be”, illetve „Bből A-ba” menő élek között. Ezzel szemben az irányított gráfokban (angolosan: digráf) a két pont között irányított élek vannak.
•
Azt a gráfot amelyben nincs hurok, sem többszörös él, egyszerű gráfnak nevezzük. (vagyis egy gráf lehet hurkot tartalmazó, lehet többszörös éllel rendelkező, lehet egyszerű)
•
Amennyiben a gráfokat összekötő éleket súly tényezőkkel(pl. költségekkel) látjuk el, a gráfot súlyozott gráfnak nevezzük. (vagyis van súlyozott és súlyozatlan gráf)
•
A gráf összefüggő, ha bármely pontjából bármely másik pontjába élek mentén el lehet jutni.(vagyis van összefüggő és nem összefüggő gráf)
A fenti csoportok önállóan , de keveredve, illetve együttesen is jellemezhetnek egy gráfot.
Gráf tulajdonságai: • • • •
A gráf két élét szomszédosnak nevezzük, ha van egy közös csúcspontjuk. Két csúcspont szomszédos, ha van egy közös élük. ( éllel vannak összekötve) Egy séta szomszédos csúcsok és élek váltakozó sorozata. Az önmagát nem metsző sétát útnak hívjuk, ha első és utolsó csúcsa különbözik, illetve körnek, ha ez a két csúcs megegyezik.
A minimális költségű feszítőfa vagy minimális feszítőfa (angolul minimum spanning tree) egy összefüggő, irányítatlan gráfban található legkisebb élsúlyú feszítőfa. A feszítőfa egy olyan fa, ami a gráf összes csúcsát tartalmazza, és élei az eredeti gráf élei közül valók. A minimális feszítőfa nem feltétlenül egyértelmű, de annak súlya igen.
80
Kruskál A Kruskál algoritmust irányítatlan összefüggő gráf minimális feszítőfájának meghatározásra használják. Az algoritmus egy mohó algoritmus, ami a lokális optimumok felhasználásával határozza meg a globális optimumot. Egyes megoldások színekkel különböztetik meg a már felkeresett csúcsokat és éleket.
// G gráf, benne N db csúccsal Eljárás Kruskal(G) 1.
Minden V csúcshoz hozzuk létre a C(V) komponenst(csoportot), amelyben csak a V csúcs van benne. 2. Inicializáljunk egy Q sort, amelyben G összes éle benne van. A sor legyen súly szerint rendezett. 3. Definiáljuk a T fát, ami kezdetben legyen üres. Ebben lesz a minimális feszítőfa (Minimum Spanning Tree, MST). 4. Ciklus, amíg T-ben kevesebb mint n-1 él van 5. (u,v) ← Q.removeMin() 6. //Q-ból kiszedjük a legkisebb súlyú élet, ami U és V csúcsokat köti össze. 7. //Ezután, körvizsgálat: az UV él csak akkor lehet része a minimális feszítőfának, ha U és V nem azonos komponensben van. Egyébként a fában kör jönne létre nem fa lenne ... C(V)=az a komponens, amelyben a V van, C(U)=az a komponens, amelyben az U van. 8. Ha C(U)!=C(V), akkor 9. T-hez hozzá lehet adni az UV élt 10. C(V)=C(V) és C(U) uniója 11. Ha Vége 12. Ciklus vége Eljárás vége
Az algoritmus akkor áll le, ha már nincs megvizsgálatlan él (leállhatna már akkor is, ha az előbb következne be, hogy felhasználtuk az összes csúcspontot). Mivel véges sok élünk van, és minden lépésben felhasználunk egyet, így |E| lépés után az algoritmus biztosan befejezi a működését.(az E jelen esetben az élek számát jelöli.)
81
Példa az algoritmus megvalósítására
82
26. Gráfok III. (topológiai rendezés és alkalmazásai) Minden irányított körmentes gráfnak van egy topológiai rendezése, ami a csúcsainak egy olyan sorozata, amelyben minden csúcs a belőle elérhető csúcsok előtt szerepel. Ez a rendezés általában nem egyértelmű. Az azonos részleges rendezéssel reprezentált irányított körmentes gráfhoz tartozó topológiai rendezések halmaza azonos. A topológia rendező algoritmus egy adott S csúcsból indul. Vagy ismerünk egy olyan S csúcsot , amiből minden csúcs elérhető, vagy az algoritmus létrehozza és beszúrja a csúcsok halmazába. Beszúrás esetén az S csúcshoz irányított éleket rendelünk, amelyek az irányított gráf kezdeti elemeire mutatnak. Az élek hozzárendelése egyben a gráf élei közé történő felvételt is jelenti. (Az ábrán a 7,5,3-as elemre mutatnának az S csúcs irányított élei.) A képen látható gráf topológiai rendezései lehetnek: • • • •
7,5,3,11,8,2,10,9 7,5,11,2,3,10,8,9 3,7,8,5,11,10,9,2 3,5,7,11,10,2,8,9
Az egyes csúcsokból az irányított élek mentén haladva vesszük az elemeket. Azokat az elemeket, amelyeket már az összes rámutató irányított éle szerint megvizsgáltunk, hozzáadjuk a topológiai listához, ha még nem szerepelne benne. Véges számú csúcs- és élhalmaz esetén az algoritmusunk véges számú lépés után leáll egy topológiai sorrendet visszaadva. Topológiai listához való adás magyarázata több az elemre mutató irányított él esetén. A 11-es elem csak a 7-es és 5-ös elem topológiai listában való szereplése után kerülhet be a topológiai listába. Vagyis ahhoz, hogy a 11-es elemet fel tudjuk dolgozni, először „rendelkezésre kell hogy álljon” / már „meg kellet vizsgálni” az összes rámutató csúcsot.
83
Topológiai sorrend meghatározásának egy lehetséges megoldása //bemeneti paraméterként egy körmentes irányított G gráfot adunk meg, és a G gráf csúcsainak számát (ez már tartalmazza az S-et, amit ha mi adtunk hozzá, el kell távolítani az eljárás lefutása után a listából) // több szabad él esetén a csúcsválasztásra több lehetőségünk van. Ez az eljárás feltételez egyfajta választást.
Eljárás TopológiaiRendezés(gráf G, darabszám) Topológiai lista ürítése Ciklus i 1 –tól darabszám-ig // az 1. elemtől az utolsóig Ha (a csúcsra csak egy irányított él mutat, vagy az összes rá mutató irányított élen jártam már) akkor ii+1 Ha (nem szerepel a listában) akkor Topológiai sorrendhez hozzáadjuk a csúcsot Különben Visszalépek egy csúcsot Elágazás vége Ha (van a csúcsból induló még fel nem használt irányított él) akkor Továbblépek az irányított élen a következő csúcsra Különben Visszalépek egy csúcsot Elágazás vége Ciklus vége Visszaad topológiai lista Eljárás vége
84
27. Hasító táblázatok (alapelvek, kulcsütközések feloldása)
hasító
függvények,
Hasító függvény: A hasító függvény egy olyan jól definiált metódus vagy matematikai függvény, melynek segítségével egy rendelkezésre álló adathalmaz minden értékét valamilyen szempont szerint csoportokra bontva és a csoportokhoz index értéket rendelve egy tömbbe képez le. A hasító függvény által végeredményként kapott elemeket hasított értéknek, hasított kódnak vagy egyszerűen hash-eknek nevezzük. A hasító függvény által kapott csoportokat és index értékeiket hasító táblának nevezzük. A kiindulási adathalmaz minden elemének rendelkeznie kell kulcs adattaggal, ami alapján egyértelműen leképezhetjük a hasító táblába. Kulcs kialakításnál figyelni kell, hogy ne legyenek azonos kulcsú elemek, ha mégis előfordulnak, akkor kezelni kell őket. Hasításhoz szükséges elemek: •
A tárolandó elem. Felépítése: THashElem = Struktúra(kulcs, tartalom)
•
Kulcshalmaz: Kulcshalmaz alatt azt a halmazt értjük, ami alapján szeretnénk majd csoportosítani az elemeket. (Jele: K, nevek halmaza). Minden elemnek rendelkeznie kulcs értékkel, amik elemei a kulcs halmaznak
•
Indexhalmaz: Azon csoportok halmaza, amelyekbe az elemeket le szeretnénk képezni. (Jele: I, abc sorrend). Mérete a felosztandó csoportok számával egyezik meg. Jellemzően mérete kisebb, mint az elemek száma.
•
Hasító függvény: Aminek segítségével az elem kulcs alapján besorolódik az index halmazba, és előáll a hasító tábla. (hasító függvény jele: h, hasító tábla jele: T, leképez név kezdőbetű abc sorrendben betöltött helyre)
85
Közvetlen címzés: Amennyiben az elemek kulcsai nem túl nagyok és nincs két azonos kulcsú elem, akkor egyben a T-beli index is lehet a kulcs. (gyakorlatban ritkán valósul meg) Hasító tábla előnye: •
Ha a szótárban valóban tárolt elemek darabszáma jelentősen kisebb, mint a lehetséges kulcsok K halmaza, akkor a hasító táblázat jóval kevesebb memóriát foglalhat.
Hasító tábla hátrányai: •
Fennáll a lehetőség, hogy két kulcs ugyanoda képződik le. (Ezt kezelni kell.)
Hasító függvényt mindig az adott feladathoz kell választani és megfogalmazni. Általános megoldás nem létezik. Hasító függvénnyel szemben támasztható követelmények: •
Egyenletesen ossza szét a kulcsokat
•
Véletlenszerűen ossza szét a hasonló kulcsokat
•
Kevés ütközést produkáljon
•
Egyszerűen kiszámolható legyen
Választható hasító függvény módszerek: •
Osztó módszer h(k) = k mod m Jellemzői: o 2,10 értéket nem célszerű „m”-nek adni
•
o
Prímszámot érdemes választani az egyenletes elosztás érdekében
o
k∈Z
Szorzó módszer h(k) = KözepeM(A*k) Jellemzői:
•
o
A közepe KözepeM(x) vissza adja a középső M darab helyiértéket.
o
Nevezetes megoldás A értékét k-ra választani. (így négyzetközép módszert kapunk)
o
Célszerű A-t prímszámnak választani.
o
k∈Z
Számjegyes módszer h(k) = ∑Helyiértéki(k) mod m 86
Jellemzői: o
érzéketlen a helyi értékek cseréjére.
o
Célszerű súlyértékkel megszorozni.
h(k) = ∑Súlyi * Helyiértéki(k) mod m •
Jel-kód módszer Ha nem csak számra szeretnénk leképezni az elemeket, hanem karakterre vagy szövegre is. (pl. személyigazolvány számok) Karakterre: h(k) = Karakterkód(k) // k ∈ Karakter szövegre: h(k) = ∑Karakterkód(ki) // k ∈ Szöveg
Univerzális hasítási technika: Alapja, hogy a paramétereket nem előre beállítva adjuk meg, hanem véletlenszerűen választjuk ki. Az esetek többségében ez a módszer kielégítő eredményt ad, és elkerüli a legrosszabb eseteit a paraméterválasztásnak. Összetett kulcsok: Együttesen szeretnénk a leképezésnél figyelembe venni az összes kulcsát az elemnek (pl. név és születési dátum együttesen). Nincs kialakított általános megoldás. Gyakorlatban gyakran használt módja, ha feldaraboljuk az összetett kulcsokat bizonyos méretekre vagy súlyozó függvény alapján és utána hajtjuk végre a leképezést. Kulcsütközések: Kulcsütközésnek tekintjük, ha a kulcs-transzformációs függvény két különböző kulcsú elemet azonos indexhalmazbeli elemre képez.
87
Kulcsütközés elkerülésének technikái: •
Túlcsordulási terület A beszúrandó új elemet egy új különálló területre, a túlcsordulási területre szúrjuk be . Keresésnél és törlésnél ezt a területet is vizsgálni kell.
•
Láncolt altáblák Láncolt listás megvalósítással történik az elem leképezés és módosítás.
•
Nyílt címzés Függvény leképezés után bizonyos lépésközzel megkeressük az első üres helyet, és oda beszúrjuk. Keresésnél, ha nem találjuk, akkor az első üres lépésközig keresünk a léptékkel. Törlésnél csak megjelöljük törlésre, de nem töröljük.
•
Másodlagos kulcs/ kettőshasítás Két hasító függvényt használunk. Ha az első függvény helyén van már elem, akkor használjuk a második függvényt. Keresésnél először az első hasító függvény leképzett helyén keressük az elemet, ha nem találjuk, a második helyén keressük.
•
Hierarchikus módszer Összetett kulcsok esetén először az egyik tényező szerint hasítunk, majd az így kapott csoportokat a következő kulcs szerint csoportonként tovább hasítjuk.(pl. születési dátum szerint először év szerint, majd hónap szerint, majd nap szerint)
•
Blokkolt altáblák A kulcstranszformációs-függvény nem egy elem címét, hanem több elemet tartalmazó blokkot határoz meg, amennyiben ez a blokk betelik, hozzáláncolható egy következő.
88
Felhasznált irodalom http://www.iit.unimiskolc.hu/iitweb/export/sites/default/users/vargae/Targyak/ProgAlapjaiC/KeresesiTechnikak.pdf http://74.125.77.132/search?q=cache:l_UkmV3DJwgJ:scape.extra.hu/downloads/BMFNIK/Programoz%25E1si%2520paradigm%25E1k%2520%25E9s%2520technik%25E1k/PPT%2520EA/H as%25EDt%25F3%2520t%25E1bl%25E1zatok.doc+has%C3%ADt%C3%B3+f%C3%BCggv%C3%A9ny&c d=4&hl=hu&ct=clnk&gl=hu http://74.125.77.132/search?q=cache:RHl30igHKEwJ:segedlet.nikhok.hu/download/Szoftvertechnolo gia.doc+has%C3%ADt%C3%B3+f%C3%BCggv%C3%A9ny&cd=3&hl=hu&ct=clnk&gl=hu http://docs.google.com/viewer?a=v&q=cache:aEdkbislLnoJ:www.ms.sapientia.ro/~kasa/adat12.pdf+ has%C3%ADt%C3%B3+f%C3%BCggv%C3%A9ny&hl=hu&gl=hu&pid=bl&srcid=ADGEESjKzWGMxADnzs DmDp-yPf0du_vkPMDRbF182LPPCsYtB_09BkwsgSYkjfXOKCPl_fiHdHJBkiNnIRDPO4870Btz33YQqfKiprk48n_bV35TXTglHBzclMU1WJHQrWMsawq1UpO&sig=AHIEtbSU2T uYzSO1XmgQuBvDxBxPLczdnw http://en.wikipedia.org/wiki/Hash_function
89
64. Hagyományos tesztelési és hibakeresési módszerek Tesztelés: Nagyobb programokat részegységekből rakunk össze. Az egyes részegységek külön-külön megfelelően működnek, de sok esetben az összeillesztés során felfedetlen hibák derülnek ki. A tesztelés célja a program tervezett működésétől eltérő működést eredményező hibák feltárása. A tesztelést tesztesetek lefuttatásával végezzük. Teszteset során olyan bemeneti paramétereket adunk meg, amelyeknek ismert kimeneti értéket kell produkálniuk. Teszteléssel szemben elvárt követelmények: • • •
Reprodukálhatónak kell lennie. Érvényes és érvénytelen működéseket egyaránt vizsgálni kell. A lehető legtöbb információt ki kell tudni nyerni belőle.
Tesztelés során három nagy csoportot különböztetünk meg: • • •
Moduláris tesztek: Minden függvényt, osztályt egymástól függetlenül ellenőrzünk le. Integrációs tesztek: Az egyes osztályok és modulokat közösen teszteljük. Eredmény-ellenőrző tesztek: A megadott paraméterek alapján az elvárt kimeneti érték eredményül adása.
Tesztelési módszerek: •
•
•
Statikus o Kódellenőrzés (implementált programforrás ellenőrzése; sok esetben más programozó végzi) o Formai ellenőrzés (szintaktikai hibák, nem létező változók, függvények; fordító program végzi - nem engedi a programot futtatni) o Tartalmi ellenőrzés (nem használt változó, változókhoz kapcsolódó értékadások; fordítóprogram engedi futni - figyelmeztetést ad) Dinamikus Fekete doboz módszer (csak bemeneti és kimeneti paraméterek alapján vizsgálunk mindent. Megadott paraméterre megadott érték.) o Ekvivalencia osztályok keresése (bemeneti paramétereket osztályozzuk. Paraméterosztályok tartományainak tesztelése) //Gyakran célszerű a kimenő paramétereket is osztályozni. o Határeset elemzés (határértékekre a kívánt megoldás) Dinamikus Fehér doboz módszer Tesztelést a program ismeretében végzünk. (ismert használati eset, implemetáció) • Kipróbálási stratégiák o Meghatározni mit szeretnénk tesztelni? utasításlefedés (minden utasítást elérjen a vezérlés) döntéslefedés (minden elágazás legyen tesztelve)
90
részfeltétel-lefedés (összetett elágazás esetén minden rész feltétel) Tesztesetek generálása kipróbálási stratégiák során meghatározott utakon végigvezető tesztesetek meghatározása Ekvivalencia osztályok keresése és meghatározása
•
• Speciális tesztek: • • • • •
Funkció teszt (minden szükséges funkcióval rendelkezik-e) Biztonsági teszt (bemeneti adatellenőrzés, hozzáférések ellenőrzése) Stressz teszt (nagy sebességgel érkező adatot feltud-e dolgozni, tud –e kezelni több irányból érkező adatokat párhuzamosan) Volumen teszt (nagy mennyiségű adatfeldolgozásra alkalmas-e, milyen teljesítményesés következik be) Modulteszt, integrációs teszt
Hibakeresés és javítás: A feltárt hibák helyének megállapítása, erre fejlett eszközöket nyújtanak a fejlesztői környezetek (pl. nyomkövetések). Tipikus hibák: • • • • •
szintaktikai hiba végrehajtás közben jelentkező hiba program nem áll meg program megáll, de nem ad eredményt program megáll, de hibás eredményt ad
A talált hibát javítani kell, majd ismét tesztelni a programot.
91
Módszerei: •
Indukciós (Megvizsgáljuk a kapott teszteseteket és kiválasszuk azokat a tényezőket, amik változtak.)
•
Dedukciós (Összegyűjtjük a lehetséges hiba okokat, és a minta tulajdonságai alapján kizárjuk a hibához nem kapcsolódó okokat.)
•
Visszalépéses technika (Végeredménytől lépésenként haladunk visszafele, és vezetjük vissza az adatokat.)
•
Teszteléssel segített hibakeresés (A tesztelés során mindig csak egy paramétert változtatva teszteljük a programot.)
•
Fejlesztői eszközök használata o szintaktikai ellenőrzés o program lépésenkénti futtatása o változók értékeinek nyomon-követése o töréspontok elhelyezése a programkódban o adatok értékeire vonatkozó töréspontok o hívási verem megtekintése o változók értékeinek menet közbeni megváltoztatása o vezérlés aktuális pontjának megváltoztatása o programkód futás közbeni módosítása o egyéb megoldások
•
Programozási nyelvek által nyújtott hibakezelés
92
65. Kivételkezelés (elvi háttere, gyakorlati megvalósítása) Hagyományos hibakezelés: Hagyományos hibakezelés esetén a programkódban nem használunk beépített kivétel és error osztályokat. A kivételeket felmerülési helyükön lokálisan kezeljük. Hagyományos hibakezelés hátrányai: • • • •
nehezen olvasható a kód (hosszú kód; nehezen áttekinthető, mert keveredik a tényleges kóddal; gyakran csak sok lépésben oldható meg) nehezen karban tartható (több előfordulási hely estén duplikálni kell; egymásba ágyazás esetén megoldani a legfelső szintre lépést) nehezen programozható (meg kell vizsgálni milyen bementekre ad hibás eredményt és azokat nem engedélyezni) függvényhívás esetén kitüntetett értékkel kell jelezni a hibát (Hibaok lekérdezéshez újabb függvény, visszatérési értéknek utalnia kell a hibára. A hiba sok esetben különböző típusú.)
Elterjedt használatának okai: • •
Régebben nem volt ilyen beépített lehetőség, ezért bizonyos szinten rögzült. Hatékonyabb bizonyos esetekben, mint a kivételkezelés
Kivételkezelés beépített osztályok használatával: Általában három különböző blokkot különböztetünk meg: •
•
•
try: Védett (próbára tett) szakasz. Ide helyezzük azokat az utasításokat, amelyek esetleg hibákat (vagy egyéb kivételt) okozhatnak. catch: Hibakezelő szakasz. Erre a blokkra kerül a végrehajtás, ha a megadott típusú kivétel keletkezett a védett szakaszon belül. Állhat több blokkból is. finally: Lezáró szakasz. Tartalmaz minden kritikus utasítást, aminek mindig le kell futni. Itt is keletkezhet hiba, de azt már nem lehet elkapni a catch blokkban. Csak ha külön try és catch blokkot alkalmazunk rá.
Használatának előnyei: • • • •
Könnyebben írható és rövidebb kód (nincs szükség műveletenkénti elemzésre) Programkód áttekinthetőbb (elválik a kivételkezelés és a tényleges program). Könnyebben karbantartható (kivételkezelő blokkok egymástól függetlenek). Más fejlesztők számára könnyebben értelmezhető.
Hibakezelés jellemzői:
93
•
• • •
Hibakezelés a hibakezelő blokkban történik. A különböző hibákra külön blokkokat tudunk létrehozni, amelyek függetlenek egymástól. Egy blokk több hibát is elkaphat, ezért nem kötelező mindet felsorolni. A védett részben több helyen keletkező azonos típusú hibákat egy blokkal tudjuk kezelni. A blokkok hierarchikusan épülnek egymásra, ezért rugalmasan lehet definiálni egy kivételkezelő blokkot. Több try blokk ágyazható egymásba, a try blokkba dobott hibákat a hozzájuk legközelebb eső catch blokk kapja el.
Hibakezelés előnyei: • •
•
• • •
Megfelelő alkalmazásával nem kell a függvény visszatérési értékét ellenőrizni. Amennyiben kivétel keletkezik, a program nem áll le, hanem lefuttatja a kivételkezelő blokkot és a védett rész után folytatja tovább a műveletvégzést. (kizárja a program hibás adatokkal való futását) Védett részben történő kivételdobás esetén a védett rész bármely beágyazott részéből a hibakezelő blokkba lép. (nem kell minden egymásba ágyazásból kilépni.). A hibakezelő blokkok veremben tárolódnak, ami nincs a veremben, azt a futtató környezet kapja el. Kivételkezelés és keletkezés helye elválik egymástól. A dobott kivétel lehetőséget biztosít a hibával kapcsolatosan egyéb információk átadására is. (mikor és miért váltódott ki) Csökkenti a nyomkövetéssel töltendő időt.
A kivételeket objektumoknak tekintjük, ezért rendelkeznek objektum tulajdonságokkal (öröklés, polimorfizmus, adatok). A kivételek hierarchiája programozási nyelvenként eltérő lehet. Kivételek csoportosítása: •
•
•
készítő alapján o keretrendszer o fejlesztő forrás alapján o szoftver kivétel o hardver kivétel ( erőforrás ) ellenőrzés alapján (csak bizonyos nyelvekben) o kötelezően ellenőrzött (pl. hálózati kapcsolat) o nem kötelezően ellenőrzött (pl. aritmetikai hibák)
Saját kivételek Saját kivételosztály definiálása általában nem különbözik egy általános osztály definíciótól. A saját kivételosztály őse célszerűen az adott környezet (programozási nyelv) megfelelő beépített kivételosztálya.
94
Egy kivétel általában az alábbi információkat tartalmazza: • • • • •
kivétel neve – célszerű már a kivétel nevét is beszédesen megválasztani, hogy az utaljon a kiváltás okára üzenet – szöveges mezőben tetszőleges üzenet továbbítása a kivétel kezelője felé hívási verem – a hívási verem állapota a kivétel létrejöttekor beágyazott kivétel – kivétel újradobása esetén tartalmazhatja az előző (már kezelt) kivételt tartalmazhat más nyelvi elemeket (metódus, statikus tagok)
Hibakezelés menete: •
•
Kivételt dobunk: Sajátkivétel-dobás esetén a kódot ki kell egészítenünk a hiba keletkezésének helyén a „throw new MyException(”…”)”- sorral. Elkapjuk a dobott kivételt: A catch blokk elkapják a hibákat és hierarchiájuk alapján lekezelik.
Gyakorlati megvalósítása: class EgyetNemOsztok : Exception { } static void Main() { string s,t; try { Console.WriteLine("Mit szeretnél elosztani?"); s = Console.ReadLine(); int osztandó = int.Parse(s); if (osztandó == 1) throw new EgyetNemOsztok(); Console.WriteLine("Mivel szeretnéd elosztani?"); t = Console.ReadLine(); int osztó = int.Parse(t); int szám = osztandó / osztó; Console.WriteLine("Erdmény = " + szám); } catch (DivideByZeroException DBZEx) { Console.WriteLine("Nullával nem osztunk"); } catch (FormatException FEx) { Console.WriteLine("Nem számot adtál meg!"); } catch (EgyetNemOsztok ENO) { Console.WriteLine("Egyet nem osztok el semmivel!"); } finally { Console.WriteLine("Erőforrás-felszabadítás."); Console.ReadLine(); } }
95
