Jegyzet - Dr.Nagy Ferenc (2006)

Országok listájaHungaryMiskolci EgyetemGépészmérnöki és Informatikai KarMérnök informatikusAdatstruktúrák és AlgoritmusokJegyzet - Dr.Nagy Ferenc (2006)

Adatstruktúrák, algoritmusok

-1-

ADATSTRUKTÚRÁK, ALGORITMUSOK
BSc mérnök informatikus szak

Eladások vázlatai Írta: Nagy Ferenc

Miskolci Egyetem
2006 február-május

Adatstruktúrák, algoritmusok

-2-

Bevezet megjegyzések
A leírásban idnként használjuk a matematikai jelöléseket: Létezik ! Egyértelmen létezik Minden A bizonyítások végét a jel jelzi. A görög ábécé kis- és nagybeti alfa beta gamma delta epszilon dzeta eta teta µ iota kappa lambda m n kszi omikron pi , ro szigma tau üpszilon fi khi pszi omega O Nagy ordo o Kis ordo
N Természetes számok

Z Egész számok halmaza R Valós számok halmaza

Adatstruktúrák, algoritmusok

-3-

A tárgy helye. Egy informatikai alkalmazási rendszer kifejlesztése során három f szintet szokás megkülönböztetni., amit egy repülgép helyfoglalási rendszer példájával illusztrálunk. Szint neve Fels szint Középs szint Alsó szint Szint jellemzése Alkalmazói szint modellalkotás Modellezési szint algoritmizálás Csupasz gépszint Repüljegy helyfoglalási példa útvonalak, gépek, dátumok, helyfoglalások file-ok, táblázatok, listák, adatrekordok, stringek, fák objektumok, mveletek, gépi reprezentálásuk

Az adat fogalma az értelmez szótár szerint: Az adat valakinek vagy valaminek a megismeréséhez, jellemzéséhez hozzásegít (nyilvántartott) tény vagy részlet. Mi adatnak fogunk tekinteni minden olyan információt, amelynek segítségével leírunk egy jelenséget, tanulmányunk tárgyát, vagy annak egy részét. Az adat formai megjelenésére nem leszünk tekintettel. (Absztrakt adat.) Definíció: Az absztrakt adattípus Az absztrakt adattípus egy leírás, amely absztrakt adatok halmazát adja meg (definiálja) nem törödve azok konkrét (gépi) realizálásával. Absztrakt adattípusra példa lehet a logikai érték, egész szám, valós szám, komplex szám, tömb (vektor, mátrix), lista, verem, sor, kupac, elsbbségi (prioritásos sor), fa, gráf, hálózat, binomiális kupac, stb. Definíció: Az algoritmus (csak heurisztikus definíció, nem tudományos) Meghatározott számítási eljárás, a számítási probléma megoldási eszköze. Az algoritmus pontos elírás, amely megad egy tágan értelmezett számítási folyamatot. Az algoritmus valamely elre meghatározott adathalmaz valamely tetszleges kiinduló elemébl kezdve az ezen elem által meghatározott eredmény elérésére törekszik. Lehet, hogy a lépések sorozata azzal szakad meg, hogy nincs eredmény. Az algoritmus karakterizáló paraméterei: 1. 2. 3. 4. 5. 6. A kiinduló adatok lehetséges halmaza (D) A lehetséges eredmények halmaza A lehetséges közbüls eredmények halmaza A kezdési szabály A közvetlen átalakítási szabályok A befejezési szabály

Adatstruktúrák, algoritmusok

-4-

7. Az eredmény kiolvasási szabálya Amikor egy algoritmust keresünk egy feladat megoldására a következ két kérdés fel kell, hogy vetdjön: 1. Megoldható-e a probléma és ha igen, akkor egy vagy több megoldása van-e? (Egzisztencia és unicitás.) 2. Van-e a meglevnél hatékonyabb megoldási módszer (algoritmus)? Az algoritmus hatékonysági jellemzi. Legyen A egy algoritmus, x a bemen (input) adata. Legyen n=|x| az x (a probléma) mérete. Legyen D az input adatok halmaza. Két hatékonysági mutatót szokás általában használni algoritmusok hatékonyságának összehasonlítására, a TA(x) idigényt és az SA(x) tárigényt . Az algoritmus Az algoritmus idbonyolultsága tárkapacitás bonyolultsága
xD x n

TA (n) = sup TA (x )

S A (n) = sup S A ( x )
xD x n

Láthatóan a bonyolultságok a probléma méretének függvényei és a legrosszabb esettel jellemzik az algoritmust. Az egyes bonyolultságok összehasonlítása az egyes függvények növekedési ütemének, rendjének az összehasonlítását jelenti. (Igen gyakran a TA(n) idigényt használják az összehasonlításokban.) A növekedési rend leíró fogalma, az ordo szimbolika. Legyen f,g : N Z két növekedést leíró függvény. Definíció: Az ordo szimbolika szimbólumai 1. f(n)=O(g(n)): c>0 és n0 , hogy ha n>n0, akkor 0 < f(n) cg(n) 2. f(n)= (g(n)): c>0 és n0 , hogy ha n>n0, akkor 0 < cg(n) f(n) 3. f(n)=(g(n)): c1,c2>0 és n0 , hogy ha n>n0, akkor 0 < c1g(n) f(n) c2g(n) 4. f(n)=o(g(n)): c>0 n0 , hogy ha n>n0, akkor 0 < f(n) < cg(n) 5. f(n)= (g(n)): c>0 n0 , hogy ha n>n0, akkor 0 < cg(n) < f(n)

Adatstruktúrák, algoritmusok

-5-

A gyakorlatban gyakran elforduló jellemz növekedések Konstans Logaritmikus Lineáris Négyzetes Köbös Polinomiális Exponenciális f(n) = (1) f (n) = (log n) f (n) = (n) f (n) = (n2) f (n) = (n3) f (n) = (nk), k>0, kR f (n) = (an), a>1

A Fibonacci számok Az alábbi számsorozatot Fibonacci számsorozatnak nevezzük.
Számok Jelölés 0 F0 1 F1 1 F2 2 F3 3 F4 5 F5 13 F6 21 F7 34 F8 55 F9 89 144 233 377 610 F10 F11 F12 F13 F14 ... ...

A számsorozat rekurzív képzési szabálya: F0=0, F1=1, Fn+2=Fn+1+Fn, n=0,1,2,... A probléma, hogy az n index elemet nem tudjuk a megelzek nélkül kiszámítani a rekurziós formula alapján. Ennek a megoldását adja a Binet formula. Tétel: A Binet formula A Fibonacci számsorozat elemei felírhatók az index függvényében az alábbi módon:

Fn =

1 n - n , n = 0,1,2,... 5 1+ 5 1- 5 1.618..., = -0.618... 2 2

(

)

ahol =
Bizonyítás

Tekintsük a rekurzív definíciót a kezdfeltételek nélkül és keressük a megoldást Fn=zn alakban. Tehát a probléma: Fn+2=Fn+1+Fn, n=0,1,2,... A megoldások közül kizárjuk a z=0 esetet, mint érdektelent. Behelyettesítve: zn+2=zn+1+zn, n=0,1,2,... adódik, ahol zn-nel leosztva z2=z+1-re jutunk. Ennek a másodfokú egyenletnek két valós megoldása van: z1 = és z2 = . Ha

z1n megoldás, akkor

A1 z1n is az, amirl behelyettesítéssel

Adatstruktúrák, algoritmusok

-6-

n n meggyzdhetünk. Ugyanígy ha z2 megoldás, akkor A2 z2 is az. Vegyük

észre, hogy A1 z1 + A2 z2 is megoldás. Helyettesítsük be ezt az eredeti rekurzív definíciónkba n=0 és n=1-re. Az alábbi lineáris egyenletrendszert kapjuk A1-re és A2-re.
n n

A1 + A2 = 0

A1 + A2 = 1
Innen A1-et és A2-t kifejezve kapjuk, hogy

A1 =
Tétel:

1 1 , A2 = - 5 5



A Fibonacci számok elállítása kerekítéssel Az n index Fibonacci szám képezhet az alábbi módon a Binet formula felhasználásával:

1 n Fn = Round , n = 0,1,2,... 5
Itt a Round a legközelebbi egész számra történ kerekítést jelenti. Bizonyítás Belátjuk, hogy a kerekítend szám és Fn között kevesebb, mint fél az eltérés. Ez azt jelenti, hogy a kerekítend szám köré fel tudunk rajzolni egy szimmetrikus intervallumot, amelynek a szélessége kevesebb, mint egy. Ekkor azonban csak egyetlen egész szám lehet ebben az intervallumban, ami így éppen a Fibonacci szám lesz.

Fn - -

1 n 1 n 1 n 1 n 1 n < - F- =- 5 5 5 5 5

1 1 1- 5 5 - 5 1 = = < 2 10 2 5 5 1 n 1 1 n 1 - < Fn < + , amibl látszik, hogy Fn egybeesik Tehát 2 2 5 5
egyetlen egésszel, amely a megadott intervallumban van.

az

A Fibonacci számok sorozata exponenciálisan növekszik. Ez következik a

1 n Fn = Round , n = 0,1,2,... elállításból. Fn 0.447213595 1.618033989n . 5 n Írhatjuk, hogy Fn = . (Meg tudnánk adni a definíciójában szerepl c1, c2

( )

konstansokat és az n0 küszöbindexet?)

Adatstruktúrák, algoritmusok

-7-

A rekurzív egyenletekrl Az algoritmusok idbonyolultságának elemzésekor sok esetben nem rendelkezünk közvetlen explicit formulával, amely megadná, hogy a méret függvényében hogyan alakul az algoritmus idigénye a legrosszabb esetben. Sok esetben csak az egyes méretek idigényei közötti kapcsolatot ismerjük. Ebbl kellene felírni vagy az explicit kapcsolatot, vagy legalább az idigény aszimptotikus viselkedését. Rekurzív egyenletnek hívjuk azokat az alábbi alakú egyenleteket: T(n)=h(T(m1(n)),T(m2(n)),...,T(mk(n))) ahol h:NkZ függvény, mj:NN, j=1,...,k függvények. Az mj(n)1 konstansok, p=logba, f(n):NZ függvény. Legyen a rekurziós összefüggésünk: T(n)=a·T(n/b)+f(n). (Az n/b helyén n/b vagy n/b is állhat.) Készítünk egy teszt polinomot: np. Ezen feltételek esetén igazak az alábbi állítások:

Adatstruktúrák, algoritmusok

-8-

1. Ha >0, hogy f(n)=O(np-), azaz f(n) polinomiálisan lassabb növekedés, mint a tesztpolinom, akkor T(n)=(np) 2. Ha f(n)= (np), akkor T(n)= (nplog n) 3. Ha > 0, hogy f(n) = (np+), azaz f(n) polinomiálisan gyorsabb növekedés, mint a tesztpolinom, és teljesül az f fügvényre a regularitási feltétel, azaz c < 1 konstans és n0 küszöbméret, hogy n n0, esetén a·f(n/b) c ·f(n), akkor T(n) = (f(n)) Példa a mester tétel alkalmazására: T(n)=9T(n/3)+n A mester tétel szerintinek tnik az eset. Legyen a=9, b=3, f(n)=n, p=log39=2 ,a tesztpolinom n2. Ha 0<<1, akkor f(n)=O(n2-). Teljesülnek a mester tétel 1. pontjának a feltételei, tehát a tételt alkalmazva: T(n)=(n2). Példa a mester tétel alkalmazására: T(n)=T(2n/3)+1 A mester tétel szerintinek tnik az eset. Legyen a=1, b=3/2, f(n)=1, p=log3/21=0 ,a tesztpolinom n0=1. 1=f(n)=(n0) =(1). Teljesülnek a mester tétel 2. pontjának a feltételei, tehát a tételt alkalmazva: T(n)=(1·log n). Példa a mester tétel alkalmazására: T(n)=3T(n/4)+n·log n A mester tétel szerintinek tnik az eset. Legyen a=3, b=4, f(n)= n·log n, p=log43, 0
Adatstruktúrák, algoritmusok

-9-

Számelméleti algoritmusok
Definíció: Az oszthatóság Azt mondjuk, hogy a d egész szám osztja az a egész számot, ha az osztásnak zérus a maradéka, azaz, ha létezik olyan k egész szám, hogy a=k·d. Jelölésben: d a . A d számot az a osztójának nevezzük.
Definíció: Prímszám Prímszámnak nevezzük azt az 1-nél nagyobb egész számot, amelynek csak az 1 és saját maga az osztója. Tétel: A maradékos osztás tétele Ha a egész szám, n pedig pozitív egész szám, akkor egyértelmen létezik olyan q és r egész szám, hogy a = q n + r , ahol 0 r < n . A q szám neve hányados, r neve maradék. q = a / n , r = a - q n = a mod n Definíció: Kongruencia Az a és b egész számokat kongruensnek mondjuk az n modulus szerint, ha az n szerinti osztás utáni maradékaik megegyeznek. Jelölésben:

a b mod n

Definíció: Közös osztó Azt mondjuk, hogy a d egész szám az a és b egészek közös osztója, ha d mindkét számot osztja. Definíció: Lineáris kombináció Az s egész számot az a és b egészek lineáris kombinációjának nevezzük, ha létezik x és y egész szám, hogy s = x a + y b . Az x és y számokat a lineáris kombináció együtthatóinak nevezzük. Az a és b számok összes lineáris kombinációjának halmazát L(a,b)-vel jelöljük. Speciálisan lineáris kombinációk az a+b és az a-b számok is. Példa: Legyen két szám a=36, b=60. Határozzuk meg az s=xa+yb értékeket az x=3...3, y=-3...3 együtthatókra s=xa+yb tábla -3 -2 -1 0 -3 -288 -252 -216 -180 -2 -228 -192 -156 -120 -1 -168 -132 -94 -60 y 0 -108 -72 -36 0 1 -48 -12 24 60 2 12 48 84 120 3 72 108 144 180

x

Adatstruktúrák, algoritmusok -

- 10

1 2 3 Tétel:

-144 -108 -72

-84 -48 -12

-24 12 48

36 72 108

96 132 168

156 192 228

216 252 288

A közös osztó tulajdonságai Legyen a d egész az a és b egészek közös osztója. Akkor fennállnak az alábbi állítások: 1. d a

vagy a = 0

2. Ha d a és a d , akkor d = ±a 3. A közös osztó osztója az a és b szám minden lineáris kombinációjának is. s L(a, b) - re d s .

Definíció: Legnagyobb közös osztó

ha a = 0 és b = 0 0 d = lnko(a, b) = max d egyébként a db d
*

Definíció: Relatív prímek Az a és b egész számokat relatív prímeknek nevezzük, ha lnko(a,b)=1. Tétel: Az lnko elemi tulajdonságai Legyen a d* egész az a és b egészek legnagyobb közös osztója. Akkor fennállnak az alábbi állítások:
* 1. 1 d min a , b

(

)

2. lnko(a, b) = lnko(b, a ) = lnko(- a, b ) = lnko a , b
3. lnko(a,0) = a
4. lnko(a, ka) = a ,

(

)

k Z

* 5. Ha d közös osztó, akkor d d

Tétel:

Az lnko reprezentációs tétele Ha az a és b egész számok nem mindegyike zérus, akkor a legnagyobb közös osztó megegyezik a két szám pozitív lineáris kombinációinak minimumával.

d * = lnko(a, b) = min s = a x* + b y * = s *
sL ( a ,b ) s >0

Adatstruktúrák, algoritmusok -

- 11

Bizonyítás
* * A bizonyítás menete az lesz, hogy megmutatjuk, hogy s d és d * s* , amibl következni fog az állítás.

s * d * megmutatása azzal történik, hogy megmutatjuk, hogy s* közös
osztó, ami nem lehet nagyobb, mint a legnagyobb közös osztó. Azt, hogy s* közös osztó azáltal látjuk be, hogy az osztási maradéka zérus. Csak az a számra látjuk ezt be, b-re ugyanígy megy a bizonyítás. Kiszámítjuk a * maradékot tehát a esetén. Az r maradékra igaz, hogy 0 r < s . Legyen q a hányados. Akkor

0 r < s* 0 a - qs* < s *

) 0 (1 - qx )a + (- qy )b < s
* *

0 a - q a x* + b y * < s *
*

(

Az egyenltlenség közepén álló maradék az a és b lineáris kombinációja. A baloldali egyenltlenség miatt nem lehet negatív, a jobboldali egyenltlenség miatt pedig kisebb, mint a pozitív lineáris kombinációk közül a legkisebb. Emiatt csak zérus lehet. Tehát az s* osztja az a számot.

d * s* abból következik, hogy a legnagyobb közös osztó osztja az
összes lineáris kombinációt, így s*-ot is. Ekkor azonban nem lehet nagyobb, mint s*, hiszen annak osztója. A tétel következményei: 1. A közös osztó osztja a legnagyobb közös osztót, ugyanis a legnagyobb közös osztó az a és b egészek lineáris kombinációja a tétel szerint, amit a közös osztó oszt. 2. Tetszleges n nemnegatív egészre lnko(n a, n b) = n lnko(a, b) Ugyanis zérusra az állítás triviális, pozitív n-re pedig

lnko(n a, n b) = nax* + nby* = n ax* + nby* = n lnko(a, b)

(

)

(Lássuk be, hogy az utolsó egyenlségjel valóban igaz, azaz a lineáris kominációkban mindkét számpár esetén ugyanaz az x*,y* megfelel választás.) Tétel: A lineáris kombinációk halmazának jellemzése Az L(a,b) halmaz és d*=lnko(a,b) egész többszöröseinek a halmaza azonos, azaz L(a,b) minden eleme d* egész többszöröse és ha egy s szám d* egész többszöröse, akkor az a és b lineáris kombinációja is.

Adatstruktúrák, algoritmusok -

- 12

Bizonyítás

Legyen M a d* egész többszöröseinek a halmaza. Megmutatjuk, hogy L M és M L, amibl következik az állítás. L M esete:. d*|a, d*|b a=kad, b=kbd, ka,kbZ L s=ax+by=kad*x+kbd*y=d*(kax+kby)=kd* M, mert kZ M L esete:. d*=lnko(a,b)=ax*+by* M s= ksd*=ks(ax*+by*)=kax*a+kby*b) L

Tétel:

Az lnko redukciós tétele

lnko(a, b) = lnko(a - b, b)

Bizonyítás

* * Legyen d1 = lnko(a, b) és d 2 = lnko(a - b, b ) .A bizonyítás menete az lesz,

* * * * hogy megmutatjuk, hogy d1 d 2 és d 2 d1 , amibl következni fog az állítás.

Világos, hogy fennállnak az alábbi tulajdonságok
* d1* d2 * d1* L(a, b) d 2 L(a - b, b) * d1* L(a, b) d 2 L(a - b, b)

* * Megmutatjuk, hogy d1 L(a - b, b) és d 2 L(a, b ) is fennáll. amibl a kölcsönös oszthatóság már következik.

d1* L(a - b, b) megmutatása: * * * * * * * d1* = x1 a + y1 b = x1 (a - b + b) + y1 b = x1 (a - b) + x1 + y1 b L(a - b, b)

(

)

* * * * * * * d 2 L(a, b) megmutatása: d 2 = x2 (a - b) + y2b = x2 a + y2 - x2 b L(a, b)

(

)

Az eddigiek alapján algoritmus konstruálható a legnagyobb közös osztó meghatározására. Az algoritmus neve: Bináris lnko algoritmus. Az algoritmus a két nemnegatív egész bináris felírásának alakjából indul ki. Az utolsó bit alapján a kiinduló problémát egyszerbbé redukálja, amíg csak az egyik szám zérussá nem válik. Ekkor a másik redukált szám egy szorzóval korrigáltja lesz az lnko. Munka közben az algoritmus csak egyszer, hatékony gépi mveleteket egész kivonás és jobbra shiftelés (eltolás) ­ használ. Legyen a két szám a és b és a ne legyen kisebb b-nél.

Adatstruktúrák, algoritmusok -

- 13

Lnko(a,b) ekkor az alábbiak szerint redukálódik az utolsó bit szerint egyszerbb feladattá: Utolsó bit b 0 1 a 0 2·lnko(a/2,b/2) lnko(a/2,b) 1 lnko(a,b/2) lnko((a-b)/2,b) A bináris lnko algoritmus pszeudokódja:

SZE_01

Bináris lnko algoritmus

Bináris_lnko (a, b) c1 WHILE a 0 és b 0 DO
,,a és b paritásértékei pa és pb. 0 = páros, 1 = páratlan"

IF

pa = a mod 2 pb = b mod 2 CASE pa=0, pb=0: c2c aa/2 bb/2 pa=0, pb=1: aa/2 pa=1, pb=0: bb/2 pa=1, pb=1: a(a-b)/2 IF a < b THEN a b csere a=0 THEN RETURN (c·b) ELSE RETURN (c·a)

Példa az algoritmusra: Lnko(3604,3332)=22·17=68 Lépésszám a 0 3604 1 1802 2 901 3 34 b Korrekció 3332 2 1666 2 833 833

Adatstruktúrák, algoritmusok -

- 14

4 5 6 7 8 9 10 11 Tétel: Az lnko rekurziós tétele

833 833 408 204 102 51 17 0

34 17 17 17 17 17 17 17

lnko(a, b) = lnko(b, a mod b)

Bizonyítás Az a mod b az a-ból b ismételt kivonásaival megkapható és így a redukciós tétel értelmében az állításunk igaz. A rekurziós tétel révén készíthet el az euklideszi algoritmus lnko meghatározására. Az algoritmus pszeudokódja:

SZE_02

Euklideszi algoritmus

Euklidesz (a, b) IF b=0 THEN RETURN (a) ELSE RETURN ( Euklidesz (b, a mod b))
Példa: Lnko(3604,3332)=68

q = a / n , r = a - q n = a mod n
Lépésszám a b q 0 3604 3332 1 1 3332 272 12 2 272 68 4 3 68 0 r 272 68 0 68

Tétel:

Lamé tétele Ha az euklideszi algoritmusban a > b 0 és b < Fk +1 valamely k > 0 ra, akkor a rekurziós hívások száma kevesebb, mint k.

A tételt nem bizonyítjuk.

Adatstruktúrák, algoritmusok -

- 15

Következmény a tételbl: Ha Fk b < Fk +1 , akkor a rekurziós hívások száma kevesebb, mint k, valamint becslést tudunk adni erre a k-ra közvetlenül a b-bl. A k értékére jól memorizálható becslés az, hogy k vehet a b tízes számrendszerbeli jegyei ötszörösének. (Valójában megmutatható, hogy itt a kisebb reláció is igaz.) A meggondolás az alábbi:

Fk

1 k 1 , 1.618, log10 0.2089, 4.78 5 log10 5

log10 Fk k log10 - log10 5 k log 5 1 log10 Fk + 10 5 log10 Fk 5 log10 b log10 log10

Bizonyítható, hogy az euklideszi algoritmusnak a legrosszabb bemen adatai a szomszédos Fibonacci számok. Az euklideszi algoritmus idigénye O(log b) A kibvített euklideszi algoritmus Tekintsük az euklideszi táblát. Lépésszám a b 0 a0 b0 1 a1 b1 ... ... ... k ak bk k+1 a k+1 b k+1 ... ... ... n d* 0 q q0 q1 ... qk q k+1 ... r r0 r1 ... rk rk+1 ... d*

* * * A tábla k. sorában sorában (k=0,1,...,n) érvényes a d = xk ak + yk bk összefüggés,

ahol továbbá ak +1 = bk , bk +1 = rk , qk = ak / bk , rk = ak - qk bk . A kapcsolat a sorok között:
* * d * = xk ak + yk bk = * * = xk (qk bk + rk ) + yk bk = * * * = ( xk qk bk + xk rk ) + yk bk = * * * = ( xk qk + yk ) bk + xk rk = * * = xk +1 ak +1 + yk +1 bk +1

Adatstruktúrák, algoritmusok -

- 16

Kaptunk egy összefüggést az x és y együtthatók között az egymást követ sorokra, ha fentrl lefelé haladunk a táblában.
* * * xk +1 = xk qk + yk * * yk +1 = xk * * Haladjunk lentrl felfelé. Akkor ebbl az egyenletrendszerbl xk és yk kifejezve: * * xk = yk +1 * * * yk = xk +1 - qk yk +1

* * * * Az utolsó sor esetén viszont d = 1 d + 0 0 , azaz xn = 1 és yn = 0 . Az utolsó * * sorból indulva így visszafelé sorról-sorra haladva az xk és yk értékek kiszámíthatók.

Végül az x0 és y0 is kiadódik. Ez a módosítás vezet az euklideszi algoritmus kibvítésére, melynek pszeudokódját alább közöljük.

*

*

SZE_03

Kibvített euklideszi algoritmus

Kibvített_Euklidesz (a, b) IF b=0 THEN RETURN (a, 1, 0) (d*,x*,y*) Kibvített_Euklidesz (b, a mod b) (d*,x*,y*) (d*,y*,x* - a/b y*) RETURN (d*,x*,y*)
Példa a kibvített euklideszi algoritmusra: Lépésszám a b q 0 3604 3332 1 1 3332 272 12 2 272 68 4 3 68 0 *

r 272 68 0 68

d* 68 68 68 68
*

x* y* -12 1-1(-12)=13 1 0-121=-12 0 1-40=1 1 0

Az algoritmus eredményeképpen x0 = -12 és y0 = 13 adódott. Ellenrzésképpen 68=(-12)3604+133332=-43248+43316, ami valóban megfelel az elvárásoknak. A lineáris kongruencia egyenlet. Definíció: A lineáris kongruencia egyenlet Az axb mod n a,bZ, nZ+ egyenletet, melyben x az ismeretlen lineáris

Adatstruktúrák, algoritmusok -

- 17

kongruencia egyenletnek nevezzük. Tétel: A lineáris kongruencia egyenlet megoldhatósági tétele A lineáris kongruencia egyenletnek akkor és csak akkor van megoldása, ha d * b ahol d*=lnko(a,n)=ax*+ny* Ha van megoldás, akkor végtelen sok van, de ezeket egy d* számú megoldást tartalmazó alaprendszerbl megkaphatjuk az n egész számú többszöröseinek a hozzáadásával. Az alaprendszer elemeit a 0x ax b

Bizonyítás Legyen q1 = , q 2 = , q = q 2 - q1 Akkor a lineáris kongruencia n n egyenlet ax-q1n=b-q2n alakra, amibl ax+qn=b egyenlet adódik, vagyis hogy a b az a és az n lineáris kombinációja. Ha azt akarjuk, hogy legyen megoldás, akkor bL(a,n) fenn kell álljon, ahol L(a.n) az a és n lineáris kombinációinak a halmaza. Ha ez nem áll fenn, akkor nincs megoldás. A lineáris kombinációban lév elemeket viszont az lnko osztja (és csak azokat osztja).Teljesüljön most d*|b. Akkor van olyan k egész szám, hogy b=kd*. A d*=ax*+ny* egyenérték az ax*d* mod n egyenlettel, ha az n szerinti maradékokat nézzük. Szorozzunk itt be k-val ax*kd*k mod n x0=x*k=x*(b/d*) mod n megoldás. További megoldásokat kapunk, hogyha képezzük az xi=x0+i(n/d*) mod n, i=1,2,...,d*-1 számokat, ugyanis a lineáris kongruencia egyenletbe történ behelyettesítés után az ax0+ai(n/d*), i=1,...,d*-1 jelenik meg a baloldalon, ahol a második tag osztható osztható n-nel, mert a d* az a-t osztja, így az n megmarad, tehát ez a tag nem módosítja az els tag általi maradékot. Nyílvánvaló, hogy ha n egész többszörösét hozzáadom az alapmegoldásokhoz, akkor újra megoldást kapok, csak az már nem lesz alapmegoldás (nem viselkedik maradékként.) A lineáris kongruencia egyenlet megoldására algoritmus konstruálható, ugyanis a kívánt x* a kibvített euklideszi algoritmusból megkapható.

SZE_04

Lineáris kongruencia megoldó algoritmus

Lineáris_kongruencia_megoldó (a, b, n) (d*,x*,y*) Kibvített_Euklidesz (a, n) IF d*|b

Adatstruktúrák, algoritmusok -

- 18

THEN

x0 x* (b/d*) mod n FOR i 1 TO d*-1 DO xi x0 + i(n/d*) mod n RETURN (x0,...,xd*-1) ELSE RETURN (,,nincs megoldás")

Példa: 3604x136 mod 3332 Láttuk, hogy lnko(3604,3332)=68=-123604+133332. 136 osztható 68-cal, így az egyenletnek van megoldása. Az alaprendszer 68 különböz elemet tartalmaz. Most b/d*=136/68=2, n/d*=3332/68=49, x*=-12+68=56. A megoldások: x0=562=112, x1=112+49=161, x2=112+249=210,.., x67=112+6749=339563 mod 3332. Definíció: A multiplikatív inverz Legyen a lineáris kongruencia egyenlet ax1 mod n aZ, nZ+, lnko(a,n)=1 alakú (azaz a és n legyenek relatív prímek). Az egyenlet egyetlen alapmegoldását az a szám n szerinti multiplikatív inverzének nevezzük. Jelölése: x=a-1 mod n. A multiplikatív inverz meghatározása történhet a lineáris kongruencia megoldó algoritmus segítségével. Természetesen a FOR ciklus alkalmazására az eljárásban nem lesz szükség. Példa: 5-1=? mod 8 5x1 mod 8 megoldását keressük. Lépésszám 0 1 2 3 4 n 8 5 3 2 1 a 5 3 2 1 0 q 1 1 1 2 r 3 2 1 0 1 d* 1 1 1 1 1 x* y* 2 -1-12=-3 -1 1-1(-1)=2 1 0-11=-1 0 1-20=1 1 0

Láthatóan lnko(5,8)=1, tehát van multiplikatív inverz. 1=28+(-3)5=16-15. Az a együtthatója ­3, aminek a 8 szerinti maradéka ­3+8=5. Tehát az 5 multiplikatív inverze 8-ra nézve éppen saját maga. Ellenrzés: 55=25=38+1. A moduláris hatványozás

Adatstruktúrák, algoritmusok -

- 19

Sok esetben ­ többek között a majd ismertetésre kerül RSA algoritmusban ­ szükség van egészek hatványa valamely modulus szerinti maradékának meghatározására. Legyen a,b,nZ+. A feladat c=ab mod n meghatározása lehetleg elfogadható id alatt. Az ötlet a b szám bináris felírásából jön. legyenek a b bitjei: bk,bk-1,...,b1,b0. A legmagasabb helyiérték bit 1-es. Ha b-nek ki akarjuk számítani az értékét, akkor ezt megtehetjük a 2 hatványaival történ számítással, b= bk2k+bk-12k-1+...+b121+b020 Ugyanezt az eredményt megkaphatjuk a gazdaságosabb Horner séma szerint: b=((...(( bk)2+bk-1)2+...+b1)2+b0) Itt láthatóan csak kettvel való szorzást és egy nulla vagy egy hozzáadását kell végezni, melyek számítástechnikailag hatékony mveletek. A b szám a kitevben van, ezért a hatványozás során a kettvel való szorzásnak a négyzetreemelés az egy hozzáadásának pedig az alappal történ szorzás felel meg. Minden lépés után vehet a modulo n szerinti maradék, így a használt számtartomány mérete mérsékelt marad. A megfelel algoritmus pszeudokódja:

SZE_05

Moduláris hatványozó algoritmus

Moduláris_hatványozó (a, b, n) p0 c1 FOR i k DOWNTO 0 DO p 2p c c2 mod n IF bi = 1 THEN p p + 1 c ( c a ) mod n RETURN (c)
Az algoritmusban ténylegesen a p értékét nem kell kiszámítani, mert az végül a b értékét adja majd. Példa: 1182005 mod 137 b = (111 1101 0101 ) 10 9 8 7 6 5 1 1 1 1 1 0 12 1182 1282 1052 1352 612 = = = = = = 1 13924 16384 11025 18225 3721 1 87 81 65 4 22 1 ·118 87 ·118 81 ·118 65 ·118 4 ·118 = 118 118 = 10266 128 = 9558 105 = 7670 135 = 472 61

Adatstruktúrák, algoritmusok -

- 20

4 3 2 1 0

1 0 1 0 1

222 1202 152 1092 992

= 484 73 = 14400 15 = 225 88 = 11881 99 = 9801 74

73 ·118 = 8614 120 88 ·118 = 10384 109 74 ·118 = 8732 101

Az RSA algoritmus fel fogja tételezni, hogy nagy prímszámaink vannak. Ilyenek keresésére egy eszköz lehet (nem a leghatékonyabb és nem abszolút biztos) az alábbi tételen alapuló algoritmus. Tétel: A Fermat tétel Ha p prím, akkor ap-11 mod p, a=1,2,...,p-1

A tételt nem bizonyítjuk.

SZE_06

Fermat féle álprímteszt algoritmus

Fermat_teszt (n) IF Moduláris_hatványozó (2, n-1, n) 1 THEN RETURN (,,összetett szám") ELSE RETURN (,,lehet prímszám")
Ha az algoritmus azt mondja, hogy a szám összetett, akkor biztosan nem lesz prím. Ha azt mondja, hogy lehet, hogy prím, akkor nagy eséllyel valóban prímet vizsgált, ugyanis 10000-ig terjeden a számok között csak 22 olyan van, amely nem prím és a teszt esetleges prímnek minsíti. Ilyenek a 341, 561, 645, 1105, ... . Ötven bites számok esetén már csak a számok egy milliomod része lehet ilyen, 100 biteseknél pedig ez az arány 1:1013. Ezen hibák egy része kiszrhet azzal, hogy a 2 helyett más alapot veszünk be a moduláris hatványozásba, például 3-at, stb. Sajnos vannak olyan számok, amelyek azonban mindegyik alap esetén prímnek maszkírozzák magukat ennél az agoritmusnál. Ezek az úgynevezett Carmichael számok. Ezek nagyon kevesen vannak. (561, 1105, 1729,... . Az els egy milliárd szám között csak 255 ilyen van.) Példa: Döntsük el, hogy a 11 és a 12 prímek-e? 10 = (1010), 11=(1011) 210=? mod 11 3 1 12 = 1 1·2 = 2

Adatstruktúrák, algoritmusok -

- 21

2 0 1 1 0 0

22 = 4 42 = 16 5 102 = 100 1

5·2 = 10

2101 mod 11 Tehát a 11 nagy eséllyel prím. 211=? mod 12 3 2 1 0 1 0 1 1 12 22 42 82 = = = = 1 4 16 4 64 4 1·2 = 2 4·2 = 8 4·2 = 8

2118 mod 12 Tehát a 12 teljes bizonyossággal nem prím. A nyilvános kulcsú titkosítások A titkosítás alapja az eredeti szöveg átalakítása, kódolása. A nyívános kulcsok használata azt jelenti, hogy minden résztvevnek van egy nyílvános kulcsa (P) és egy titkos kulcsa (S). Legyen M az üzenet. Legyen a két résztvev A és B. A küldi B-nek az M üzenetet titkosítva. Az elküldött titkosított szöveg C=PB(M), B megkapja a C üzenetet és a titkos kulcsával dekódolja M=SB(C). A kulcsok egymás inverzei, és úgy vannak kialakítva, hogy a P kulcs révén könny legyen titkosítani, de a kulcs ismeretében nagyon nehezen lehessen csak (praktikusan lehetetlen) az S kulcsot meghatározni. A digitális aláírás ilyenkor történhet úgy, hogy a küld a titkosított C szüveg mellé akár nyítan odaírja a saját Q azonosítóját, majd annak az R=SA(Q) titkosítottját. Ezután B a Q alapján tudva, hogy kit nevez meg az aláírás, annak privát kulcsával dekódolja R-et. Q*=PA(R). Ha Q*=Q, akkor nem történt átviteli hiba, vagy hamisítás, egyébként igen. Persze Q az M-mel együtt is kódolható. Ez annak felel meg, mintha az els esetben nyílt levelezlapon lenne az aláírásunk, a másodikban pedig mintha borítékba tettük volna. Alább közöljük az RSA (Rivest ­ Shamir - Adleman) nyílvános kulcsú titkosítás algoritmusát. Az algoritmus feltételez két nagy prímszámot. (A gyakorlatban legalább 100-200 jegyekre van szükség, hogy praktikusan feltörhetetlen legyen.) A P kulcs felépítése P=(e,n), ahol n a két prím szorzata, e pedig egy kis páratlan szám. Az S kulcs P=(d,n).

SZE_07

RSA kulcsokat meghatározó algoritmus

RSA_kulcsok_meghatározása (p, q, e)

Adatstruktúrák, algoritmusok -

- 22

IF

npq f(p-1)(q-1) IF lnko(e,f) 1 THEN RETURN (,,Nincs kulcs") -1 de mod f RETURN (P=(e,n), S=(d,n)))
A szöveg titkosítása a C=P(M)=Me mod n alapján történik. Dekódolása pedig az M=S(C)=Cd mod n alapján. A szöveg darabolásának bitméretét az n szabja meg. Az eljárás helyességét nem bizonyítjuk. Számpélda RSA algoritmusra (nem életszer, mivel a prímek kicsik) Legyen a titkos választás: p=11, q=29, n=p ·q=11 ·29=319, e=3, f = ( p ­ 1 ) · ( q ­ 1 )=10 ·28=280 A kibvített euklideszi algoritmust alkalmazzuk. f e f / e f mod e d* x 93 3 y

p vagy q nem prím vagy e<3 vagy e páros THEN RETURN (,,Nincs kulcs")

280 3 3 1 1 0

1 1 1 - 93 1 1 0 1 1 1 1 0

Láthatóan Lnko(f,e)=1 és e multiplikatív inverze d = e-1 = - 93. Ez utóbbi helyett 280-at hozzáadva vesszük a 187-et. Ezek után akkor P = ( 3, 319 ) közölhet kulcs P( M ) = M3 mod 319 S = ( 187, 319 ) titkos kulcs S( C ) = C187 mod 319 Legyen az üzenetünk 100. Egy darabban titkosítható, mivel ez kisebb, mint 319. Titkosítsuk, majd fejtsük meg az üzenetet. Titkosítás: C= 1003 mod 319 310=112 1 1 12 = 1 1 1 ·100 = 100 100 0 1 1002 = 10000 111 111 ·100 = 11100 254 Megfejtés: M= 254
187

mod 319

18710=101110112

Adatstruktúrák, algoritmusok -

- 23

7 6 5 4 3 2 1 0

1 0 1 1 1 0 1 1

12 2542 782 1002 1222 672 232 672

= = = = = = = =

1 64516 6084 10000 14884 4489 529 4489

1 1 ·254 = 78 23 23 ·254 = 111 111 ·254 = 210 210 ·254 = 23 210 210 ·254 = 23 23 ·254 =

254 254 5842 100 28194 122 53340 67 53340 67 5842 100

Adatstruktúrák, algoritmusok -

- 24

Elemi dinamikus halmazok Definíció: Dinamikus halmaz Az olyan halmazt, amely az t felhasználó algoritmus során változik (bvül, szkül, módosul) dinamikus halmaznak nevezzük. A dinamikus halmazok elemei tartalmazhatnak - kulcsmezt, - mutatókat (pointereket), amelyek más elemekre mutatnak. (pl: a következ elemre) Dinamikus halmazon értelmezett mveletek Lekérdez KERES(S,k) adott k kulcsú elem x mutatóját adja vissza, vagy NIL, ha nincs. MINIMUM(S) a legkisebb kulcsú elem mutatóját adja vissza MAXIMUM(S) a legnagyobb kulcsú elem mutatóját adja vissza KÖVETKEZ(S,x) az x elem kulcsa utáni kulcsú elem mutatóját adja vissza, nil, ha x után nincs elem ELZ(S,x) az x elem kulcsa eltti kulcsú elem mutatóját adja vissza, nil, ha x eltt nincs elem Módosító BESZÚR(S,x) az S bvítése az x mutatójú elemmel TÖRÖL(S,x) az x mutatójú elemet eltávolítja S-bl Definíció: A verem adatstruktúra A verem (stack) olyan dinamikus halmaz, amelyben elre meghatározott az az elem, melyet a TÖRÖL eljárással eltávolítunk. Ez az elem mindig a legutoljára a struktúrába elhelyezett elem lesz. Az ilyen törlési eljárást Last In ­ First Out (LIFO) eljárásnak nevezzük. Verem attributum: tet[S] ­ mutató mely a legutóbb betett elemre mutat. (Tömbös realizációnál az elem index mely kezdetben zérus. A tömbelemek indexelése eggyel kezddik.) Tet 1 2 3 4 5 6 342 416 112 234

Adatstruktúrák, algoritmusok -

- 25

A verem mveletek pszeudokódjai tömbös realizáció esetére. S a vermet tároló tömb. DIN_01 Verem üres-e

ÜRES_VEREM(S) ,,Tömbös realizáció T= (1)" IF tet[S]=0 THEN RETURN(IGAZ) ELSE RETURN(HAMIS) DIN_02 Verembe beszúrás (~push) T= (1)"

VEREMBE(S,x) ,,Tömbös realizáció tet[S] tet[S]+1 S[tet[S]] x

DIN_03

Verembl törlés (~pop)

VEREMBL(S) ,,Tömbös realizáció T= (1)" IF ÜRES_VEREM(S) THEN hibajelzés ,,alulcsordulás" ELSE x tet[S] tet[S] tet[S] ­ 1 RETURN(x)

Definíció: A sor adatstruktúra A sor (queue) olyan dinamikus halmaz, amelyben elre meghatározott az az elem, melyet a TÖRÖL eljárással eltávolítunk vagy amelyet BESZÚR eljárással a halmazba beteszünk. Törlésre mindig a legrégebbi elem kerül, A beszúrt elem lesz a legfrissebb elem. A sor First In ­ First Out (elsnek érkezett ­ elsnek távozik - eljárást valósít meg. Törlésre mindig az els helyen álló elem kerül, a beszúrás az utolsó elemet követ helyre kerül. (Tömbös realizáció esetén a tömb a méreténél eggyel kevesebb elemet képes csak tárolni. Hossz[Q]=n, de csak n-1 elem kezelésére alkalmas.) Sor attributumok: fej[Q] ­ az els elem indexe

Adatstruktúrák, algoritmusok -

- 26

vége[Q] ­ annak a helynek az indexe, ahová az új érkez kerül A sor elemei: fej[Q], fej[Q]+1, fej[Q]+2,...,vége[Q]-1 ciklikus elrendezésben, n után 1 jön. Üres sor: fej[Q]=vége[Q]. (Kezdetben fej[Q]=vége[Q]=1.) Ha üres sorból veszünk ki elemet, az hiba (alulcsordulás). Tele sor: fej[Q]=vége[Q]+1 Beszúrás tele sorba hiba (túlcsordulás). DIN_04 Sorba beszúrás T= (1)"

SORBA(Q,x) ,,Tömbös realizáció Q[vége[Q]] x IF vége[Q] = hossz[Q] THEN vége[Q] 1 ELSE vége[Q] vége[Q]+1

DIN_05

Sorból eltávolítás T= (1)"

SORBÓL(Q) ,,Tömbös realizáció x Q[fej[Q]] IF fej[Q]=hossz[Q] THEN fej[Q] 1 ELSE fej[Q] fej[Q]+1 RETURN(x)

Definíció: A láncolt lista adatstruktúra A láncolt lista (linked list) olyan dinamikus halmaz, melyben az objektumok, elemek lineáris sorrendben követik egymást. A lista minden eleme mutatót tartalmaz a következ elemre. A lista lehet: egyszeresen láncolt vagy kétszeresen láncolt. rendezett vagy nem rendezett.

Adatstruktúrák, algoritmusok -

- 27

ciklikus vagy nem ciklikus. A fenti három tulajdonság nem zárja ki egymást. A lista attributuma: fej[L] ­ mutató, a lista els elemére mutat Ha fej[L] = NIL, akkor a lista üres. A listaelemek attributumai: kulcs[x] ­ az elem kulcsa el[x] ­ az elz elemre mutat köv[x] ­ a következ elemre mutat Ha el[x] = NIL, akkor x a lista eleje. Ha köv[x] = NIL, akkor x a lista vége DIN_06 Láncolt listában keresés

LISTÁBAN_KERES(L,k) ,,Lineárisan keresi a k kulcsot. T= (n)" ,,Visszaadja annak pointerét, ha van ilyen elem" ,,és NIL-t, ha nincs" x fej[L] WHILE x NIL és kulcs[x] k DO x köv[x] RETURN(x) DIN_07 Láncolt listába beszúrás T= (1)"

LISTÁBA_BESZÚR(L,x) ,,Az x mutatójú elemet a lista elejére teszi. köv[x] fej[L] el[x] NIL IF fej[L] NIL THEN el[fej[L]] x fej[L] x DIN_08 Láncolt listából törlés

LISTÁBÓL_TÖRÖL(L,x) ,,Az x mutatójú elemet törli a listából. T= (1)" ,,Ha a kulcs van megadva, akkor elbb meg kell keresni x-et" ,,ekkor az idigény T= (n)" IF el[x] NIL THEN köv[el[x]] köv[x]

Adatstruktúrák, algoritmusok -

- 28

IF

ELSE fej[L] köv[x] köv[x] NIL THEN el[köv[x]]] el[x] ELSE köv[el[x]] NIL Szentinel alkalmazása listában

Szentinel =rszem, strázsa Legyen nil[L] egy mutató, amely az alábbi szerkezet elemre mutat: köv Kulcs el lista elejére mutat lista végére mutat Speciális, ,,érvénytelen szerkezet" Ez testesíti meg a nem létez NIL elemet. Eszerint: köv[nil[L]] az els elemre mutat el[nil[L]] az utolsó elemre mutat Az utolsó elem esetében: köv[x] = nil[L] Az els elem esetében : el[x] = nil[L] A fej[L] attributumra nincs szükség!!! DIN_09 Szentineles listában keresés T= (n)"

SZENTINELES_LISTÁBAN_KERES(L,k) ,,Lineárisan keresi a k kulcsot. ,,Visszaadja annak pointerét, ha van ilyen elem" ,,és nil[L]-t, ha nincs" x köv[nil[L]] WHILE x nil[L] és kulcs[x] k DO x köv[x] RETURN(x) DIN_10 Szentineles listába beszúrás

SZENTINELES_ LISTÁBA_BESZÚR(L,x) ,,Az x mutatójú elemet a lista elejére teszi köv[x] köv[nil[L]] el[köv[nil[L]]] x köv[nil[L]] x el[x] nil[L]

T= (1)"

Adatstruktúrák, algoritmusok -

- 29

DIN_11 Szentineles listából törlés SZENTINELES_LISTÁBÓL_TÖRÖL(L,x) ,,Az x mutatójú elemet törli a listából T= (1)" ,,Ha a kulcs van megadva, akkor elbb meg kell keresni x-et" ,,ekkor az idigény T= (n)" köv[el[x]] köv[x] el[köv[x]] el[x] Alkalmazás: memória lefoglalása és felszabadítása Legyen m helyünk az adatok tárolására. Legyen n < m elem (hely) lefoglalva listás szerkezettel. Az m - n hely a szabad elemeké. Ezeket is listában (egyszeresen láncolt) tartjuk nyilván. A szabad globális mutató mutat az els szabad helyre. Mindig az els szabad helyet foglaljuk le, vagy a felszabadult hely a szabadok közé az els helyre kerül. (Verem listás reprezentációja.) DIN_12 Objektum lefoglalás OBJEKTUMOT_LEFOGLAL ( ) ,,T= (1)" IF szabad = NIL THEN hibajelzés ,,nincs szabad hely" ELSE x szabad szabad köv[x] RETURN(x) DIN_13 Objektum felszabadítás OBJEKTUMOT_FELSZABADÍT(x) ,,T= (1)" köv[x] szabad szabad x

Adatstruktúrák, algoritmusok -

- 30

Rendezések REN_01 Beszúró rendezés BESZÚRÓ_RENDEZÉS ( A ) ,,T= (n2)"

FOR j 2 TO hossz [ A ] DO kulcs A [ j ] ,,Beszúrás az A [ 1 .. j ­ 1 ] rendezett sorozatba" i j­1 WHILE i > 0 és A[i] > kulcs DO A[i+1] A[i] i i­1 A [ i + 1 ] kulcs Két rendezett tömb összefésülése egyetlen rendezett tömbbé Mindkettnek megvizsgáljuk az els elemét. A kett közül a kisebbiket beírjuk az eredménytömb els szabad eleme helyére. A felszabaduló helyre újabb elemet veszünk abból a tömbbl, ahonnan elzleg a kisebbik elem jött. Ezt a tevékenységet folytatjuk mindaddig, míg valamelyik kiinduló tömbünk ki nem ürül. Ezután a még vizsgálat alatt lév elemet, valamint a megmaradt másik tömb további elemeit sorba az eredménytömbhöz hozzáírjuk a végén. Legyen ÖSSZEFÉSÜL ( A, p, q, r ) az az eljárás, amely összefésüli az A [ p .. q ] és az A [ q + 1 .. r ] résztömböket az eredeti A [ p .. r ] helyen. Az összefésülés idigénye (n), ha összesen n elemünk van. (Egy menetben elvégezhet és az kell is hozzá.) Definíció: Az oszd meg és uralkodj elv Az oszd meg és uralkodj elv egy algoritmus tervezési stratégia A problémát olyan kisebb részekre osztjuk föl, amelyek rekurzívan megoldhatók. Ezután egyesítjük a megoldásokat. Az összefésül rendezés (oszd meg és uralkodj típusú algoritmus) Felosztás: A tömböt két n / 2 elem részre osztjuk Uralkodás: Rekurzív összefésüléses módon mindkettt rendezzük. (Az 1 elem már rendezett) Egyesítés: A két részsorozatot összefésüljük. Pszeudokód az A [ p .. r ] résztömb rendezésére a saját helyén.

Adatstruktúrák, algoritmusok -

- 31

REN_02 Összefésül rendezés (Merge Sort) ÖSSZEFÉSÜL_RENDEZÉS ( A, p, r ) ,,T= (n log n)" IF p < r THEN q ( p + r ) / 2 ÖSSZEFÉSÜL_RENDEZÉS ( A, p, q ) ÖSSZEFÉSÜL_RENDEZÉS ( A, q + 1, r ) ÖSSZEFÉSÜL ( A, p, r )

A teljes tömb rendezése megoldható az alábbi utasítással: ÖSSZEFÉSÜL_RENDEZÉS(A,1,hossz[A]) Az összefésül rendezés idigénye

(1) n Uralkodás: 2 T 2 Egyesítés: (n) Felosztás:

ha n = 1 (1), T (n) = n 2 T + (n), ha n > 1 2

Az algoritmus idigénye megkapható a mester tétel 2. pontja alapján: T(n) = (n log n) Gyorsrendezés (oszd meg és uralkodj típusú algoritmus) Felosztás: Az A [ p .. r ] tömböt két nemüres A [ p .. q ] és A [ q + 1 .. r] részre osztjuk úgy, hogy A [ p .. q ] minden eleme kisebb egyenl legyen, mint A [ q + 1 .. r ] bármely eleme. (A megfelel q meghatározandó) Uralkodás: Az A [ p .. q ] és A [ q + 1 .. r ] résztömböket rekurzív gyorsrendezéssel rendezzük. Egyesítés: Nincs rá szükség, mivel a tömb már rendezett. (A saját helyén rendeztük)

REN_03 Gyorsrendezés (Quick Sort) GYORSRENDEZÉS(A,p,r) IF ,,T= (n2), T(n)= (n log n)"

p
Adatstruktúrák, algoritmusok -

- 32

GYORSRENDEZÉS ( A, p, q ) GYORSRENDEZÉS ( A, q+1, r ) REN_04 Felosztás a gyorsrendezésben ,,T= (n)" xA[p] i p­1 j r+1 WHILE

FELOSZT ( A, p, r )

IGAZ DO REPEAT j j ­ 1 UNTIL A [ j ] x REPEAT i i + 1 UNTIL A [ i ] x IF i < j THEN csere A [ i ] A [ j ] ELSE RETURN ( j )

A gyorsrendezés idigénye A legrosszabb eset: a felosztás minden lépésben n - 1, 1 elem T ( 1 ) = ( 1 ), T(n)=T(n­1)+(n) T(n)=T(n­1)+ (n)=T(n­2)+ (n­1)+ (n)=...= = T ( 1 ) + ( 1 ) + ( 2 ) + ... + ( n ) = ( k ) = ( n2 ) A legjobb eset: n / 2, n / 2 a felosztás, ekkor T ( 1 ) = ( 1 ), T ( n ) = 2 T ( n / 2 ) + ( n ), ha n > 1 Ez megegyezik az összefésül módszer formulájával, tehát T ( n ) = ( n log n ) Megjegyzés: ha a felosztás aránya állandó pl. 9 / 10, 1 / 10, akkor a rekurziös formula: T ( n ) = T ( 9 n / 10 ) + T ( n / 10 ) + n). Bizonyíthatö, hogy ekkor is T ( n ) = ( n log n ). Ezen túlmenen az átlagos értékre is T ( n ) = ( n log n ) adódik. A Stirling formula Igaz az összefüggés az n!-ra: nn / en < n! < (n+1)n+1 / en

Adatstruktúrák, algoritmusok -

- 33

ln(n!) = 1 ln 2 + 1 ln 3 + 1 ln 4 + K + 1 ln n
n n n

ln(n!) > ln x dx = 1 ln x dx = [x ln x]1 - x
n

ln(n!) = 1 ln 1 + 1 ln 2 + 1 ln 3 + 1 ln 4 + K + 1 ln n
n+1 n n+1

1 dx = 1 1 1 x n = n ln n - [x]1 = n ln n - (n - 1) = n ln n - n + 1 > n ln n - n
n+1

ln(n!) < ln x dx = 1 ln x dx = [x ln x]1 - [x]1 =
1 1

= (n + 1) ln (n + 1) - (n + 1 - 1) = (n + 1) ln (n + 1) - n
Az összehasonlító módszerek döntési fája a1 a2 ? igen a2 a3 ? igen nem a1 a3 ? igen 1, 3, 2 nem 2, 3, 1 nem a1 a3 ? igen 2, 1, 3 nem a2 a3 ? igen 3, 1, 2 nem 3, 2, 1

1, 2, 3

Tétel:

Alsó korlát összehasonlító rendezésre Bármely n elemet rendez döntési fa magassága (n log n)

Adatstruktúrák, algoritmusok -

- 34

Bizonyítás Egy h magasságú döntési fa leveleinek száma legfeljebb 2h . Mivel minden permutációt rendezni kell tudnia az algoritmusnak, és összesen n! permutáció lehetséges, ezért a döntései fának legalább n! levele kell legyen. Tehát n! 2h fennáll. Logaritmálva: h log(n!). A Stirling formula szerint n! > ( n / e )n. Behelyettesítve: h log (( n / e )n) = n log n - n log e Tehát: h = ( n log n ) A Batcher-féle páros-páratlan összefésülés Az eljárás csak az összefésülést teszi hatékonyabbá. Nem önálló rendez módszer. Nagy elnye, hogy párhuzamosíthatók a lépései. Legyen két rendezett sorozatunk: A = {a1,...,al} B = {b1,...,bm} A két sorozat összefésülése adja a C = {c1,...,cl+m} sorozatot. Az összefésülés módja a következ: Mindkét kiinduló sorozatból kettt képezünk, a páratlan index és a páros index elemek sorozatait: A1 = {a1,a3,a5,...} B1 = {b1,b3,b5,...} A2 = {a2,a4,a6,...} B2 = {b2,b4,b6,...} Összefésüljük az A1,B2 sorozatokat, eredménye az U sorozat. Összefésüljük az A2,B1 sorozatokat, eredménye a V sorozat. Összefésüljük az U és V sorozatokat, eredmény a C sorozat. Tétel: A Batcher-féle összefésülés tétele A Batcher összefésülés során c2i-1 = min { ui , vi } és c2i = max { ui , vi }, 1 i ( l + m ) / 2 Fogadjuk el kiindulásként igaznak azt a feltevést, hogy C elejébl páros számú elemet véve azok között azonos számú U és V elem van. Ekkor {c1,...,c2(i-1)}= {u1,...,ui-1} {v1,...,vi-1} és {c1,...,c2i}= {u1,...,ui} {v1,...,vi} Ebbl viszont {c2i-1,c2i}={ui,vi}, ahonnan c2i-1< c2i miatt adódik a tétel állítása. A feltételezésünk bizonyítása: Legyen {c1,...,c2k}={a1,...,as} {b1,...,b2k-s}. Ezek közül U-ba kerül s/2 elem az A-ból (az A páratlan index elemei) és (2k-s)/2 elem a B-bl (a B páros index elemei), Valamint V-be kerül s/2 elem az A-ból (az A páros index elemei)

Bizonyítás

Adatstruktúrák, algoritmusok -

- 35

és (2k-s)/2 elem a B-bl (a B páratlan index elemei). Innen az U-beliek száma s/2 + (2k-s)/2 = k és a V-beliek száma s/2 + (2k-s)/2 = k A buborék rendezés A buborékrendezésnél az egymás mellett álló elemeket hasonlítjuk össze, és szükség esetén sorrendjüket felcseréljük. Ezt mindaddig folytatjuk, míg szükség van cserére. Idigény a legrosszabb esetben: n(n-1)/2,azaz T(n)=O(n2) Sok a csere, az elem lassan kerül a helyére. REN_05 Buborék rendezés (Bubble Sort) ,,T= (n2)"



BUBORÉK_RENDEZÉS(A)

j 2 REPEAT c 0 FOR i hossz[A] DOWNTO j DO IF A[i] < A[i - 1] THEN csere A[i] « A[i - 1] c 1 j j+1 UNTIL c = 0 A Shell rendezés (rendezés fogyó növekménnyel) A Shell rendezés a buborékrendezésnél tapasztalt lassú helyrekerülést igyekszik felgyorsítani azáltal, hogy egymástól távol álló elemeket hasonlít és cserél fel. A távolságot fokozatosan csökkenti, míg az 1 nem lesz. Minden növekmény esetén beszúrásos rendezést végez az adott növekménynek megfelel távolságra álló elemekre. Mire a növekmény 1 lesz, sok elem már majdnem a helyére kerül. A növekmények felépítése. Használjunk t számú növekményt. Legyenek ezek h[1..t]. A követelmény: h[t] = 1, és h[i + 1] < h[i], i=1,..., t - 1 Irodalmi javasolt növekményadatok: ..., 32, 16, 8, 4, 2, 1 t = log n - 1 h[i-1]=2h[i] ...121, 40, 13, 4, 1 h[i-1]=3h[i]+1 ...31, 15, 7, 3, 1 h[i-1]=2h[i]+1 A Shell rendezés pszeudokódja (strázsa alkalmazásával)

Adatstruktúrák, algoritmusok -

- 36

Megjegyzés: A hossz[A] a rendezend elemek számát jelöli. Az A tömböt az elején még kiegészítjük t darab rekesszel, amelyekbe menet közben a strázsa elemek kerülnek. Idigény: alkalmas növekmény választással leszorítható O(n1.2)-re. REN_06 Shell rendezés (Shell Sort) ,,T= (n1.2)"

SHELL_RENDEZÉS(A) FOR

m 1 TO t DO k h[m] s -k FOR i k + 1 TO hossz[A] DO x A[i] j i­k IF s = 0 THEN s - k s s+1 A[s] x WHILE x < A[j] DO A[j + k] A[j] j j­k A[j + k] x

Minimum kiválsztásos rendezés Hossz[A]-1 -szer végigmegyünk a tömbön. Minden alkalommal eggyel késbbi elemtl indulunk. Megkeressük a minimális elemet, és azt az aktuális menet els elemével felcseréljük. Idigény: összehasonlításszám ( n2 ). REN_07 Minimum kiválasztásos rendezés

MINIMUM_KIVÁLASZTÁSOS_RENDEZÉS(A) ,,T= (n2)" FOR i 1 TO hossz[A]-1 DO ,,minimumkeresés" k i x A[i] FOR j i + 1 TO hossz[A] DO IF A[j] < x THEN k j x A[j]

Adatstruktúrák, algoritmusok -

- 37

,,az i. elem és a minimum felcserélése" A[k] A[i] A[i] x Négyzetes rendezés Felosztjuk az A tömböt n számú n elemet tartalmazó részre (alcsoportra). Mindegyikbl kiemeljük (eltávolítjuk) a legkisebbet. (Ez lesz a fcsoport.) Kiválasztjuk a legkisebbek legkisebbikét (a legkisebbet a fcsoportból) és azt az eredmény tömbbe írjuk, a fcsoportból eltávolítjuk. Helyére abból az alcsoportból ahonnan jött újabb legkisebbiket emelünk be a fcsoportba. Az eljárást folytatjuk, míg az elemek el nem fogynak. Idigény: összehasonlításszám O(n · n)=O(n1.5). Továbbfejlesztett változat, amikor ³n számú elem van egy f-fcsoportban, ³n számú fcsoport van mindegyikben ³n számú elemmel, melyek mindegyikéhez egy ³n elemszámú alcsoport tartozik. A rendezés elve a fentihez hasonló. Idigény: O ( n · ³n ) Lineáris idej rendezk A leszámláló rendezés A lineáris idej rendezk nem használják az összehasonlítást. A leszámláló rendezés ( = binsort, ládarendezés) bemenete 1 és k közötti egész szám. Idigény: O(n+k). Ha k=O(n), akkor a rendezési id is T(n) = O(n), ahol n=hossz[A]. Az elemeket az A[1..n] tömbben helyezzük el. Szükséges továbbá két tömb: B[1..n] az eredmény tárolására, és C[1..k] segédtömb. A rendezés lényege, hogy minden elemre meghatározza a nála kisebb elemek számát. Ez alapján tudja az elemet a kimeneti tömb megfelel helyére tenni. Definíció: Stabil rendez eljárás Azt a rendez eljárást, melynek végén az azonos érték kulcsok sorrendje megegyezik az eredetivel. stabil eljárásnak nevezzük. Stabil eljárás: az azonos értékek sorrendje megegyezik az eredetivel. A leszámláló rendezés pszeudokódja REN_08 Leszámláló rendezés (Bin Sort)

LESZÁMLÁLÓ_RENDEZÉS (A, B, k)

Adatstruktúrák, algoritmusok -

- 38

,,T= (n)" FOR FOR FOR i 1 TO k DO C[i] 0 j 1 TO hossz[A] DO C[ A[ j ] ] C[ A[ j ] ] + 1 ,,C[i] azt mutatja, hogy hány i érték számunk van" i 2 TO k DO C[i] C[i] + C[i - 1] ,,C[i] most azt mutatja, hogy hány i-tl nem nagyobb számunk van" j hossz[A] DOWNTO 1 DO B[ C[ A[ j ] ] ] A[j] C[ A[j] ] C[ A[j] ] ­ 1 A számjegyes rendezés (radix rendezés) Azonos hosszúságú szavak, stringek rendezésére használhatjuk. (Dátumok, számjegyekbl álló számok, kártyák, stb.) Legyen d a szó hossza, k pedig az egy karakteren, mezben elforduló jegyek, jelek lehetséges száma, n pedig az adatok száma. Idigény: (d(n+k)) REN_09 Számjegyes (radix) rendezés ,,T= (n)" FOR i d DOWNTO 1 DO ,,Stabil módszerrel rendezzük az A tömböt az i. számjegyre" Edényrendezés Feltételezzük, hogy a bemenet a [0, 1) intervallumon egyenletes eloszlású számok sorozata. Felosztjuk a [0, 1) intervallumot n egyenl részre (edények). A bemenetet szétosztjuk az edények között, minden edényben egy listát kezelve. Az azonos edénybe esket beszúrásos módon rendezzük. A végén a listákat egybefzzük az elsvel kezdve. Várható idigény: (n) REN_10 Edényrendezés

FOR

SZÁMJEGYES_RENDEZÉS(A)

Adatstruktúrák, algoritmusok -

- 39

EDÉNYRENDEZÉS(A) ,,T= (n)" n hossz[A] FOR i 1 TO n DO ,,Beszúrjuk az A[i] elemet a B[ n · A[i] ] listába" FOR i 0 TO n - 1 DO ,,Rendezzük a B[i] listát beszúrásos rendezéssel" ,,Sorban összefzzük a B[0], B[1],..., B[n - 1] listákat." Küls tárak rendezése Küls tárak rendezésénél az elérési és a mozgatási id szerepe drasztikusan megn. Az összefésüléses módszerek jönnek elssorban számításba. Definíció: Futam küls táras rendezésnél Egy file k szomszédos rekordjából álló részét k hosszúságú futamnak nevezzük, ha benne a rekordkulcsok rendezettek. (pl.: növeked sorrendek). Elször alkalmas k-val (k=1 mindig megfelel) a rendezend file-t két másik file-ba átmásoljuk úgy, hogy ott k hosszúságú futamok jöjjenek létre. Ezután a két file-t összefésüljük egy-egy elemet véve mindkét file-ból. Az eredményfile-ban már 2k lesz a futamhossz.(esetleg a legutolsó rövidebb lehet). Ezt ismételgetjük a teljes rendezettségig mindig duplázva k értékét. Legyen a rekordok száma n. Egy menetben n rekordmozgás van a szétdobásnál és n az összefésülésnél. A menetek száma legfeljebb log n. Az idigény: (n log n). Küls tárak rendezésének gyorsítása Az n log n nem javítható az összehasonlítások miatt. A szorzó konstansokat lehet csökkenteni. Változó futamhosszak: a file-ban meglév természetes módon kialakult futamhosszakat vesszük figyelembe. A futamhatárok figyelésének adminisztrálása bejön, mint további költség. Több részfile használata esetén a szétdobás nem két, hanem több részre történik. Külön adminisztráció összefésülésnél a kiürült file-ok figyelése. Polifázisú összefésülés alkalmazásakor nem folytatjuk végig minden menetben az összefésüléseket, hanem a célfile szerepét mindig a kiürült file veszi át és ide kezdjük összefésülni a többit.

Adatstruktúrák, algoritmusok -

- 40

menet és futamszám File 1 2 3 4 5 6 1 1(1) 0 1(3) 0 1(5) 0 2 5(1) 4(1) 3(1) 2(1) 1(1) 0 0 1(2) 0 1(4) 0 1(6) 3 menet és futamszám Fibonacci eset File 1 2 3 4 5 6 0 1 8(1) 3(1) 0 2(5) 1(5) 2 5(1) 0 3(3) 1(3) 0 1(13) 0 5(2) 2(2) 0 1(8) 0 3 A kiválasztási probléma Bemenet: Az A halmaz (n különböz szám), és egy i index 1 i n. Kimenet: x A, melyre pontosan i ­ 1 darab nála kisebb elem van A-ban. Ha rendezzük az adatsort, akkor O(n log n) lépésben a feladat mindig megoldható. Speciális eset: i=1. (minimumkeresés) n ­ 1 összehasonlítással megoldható és ennyi kell is. KUP_01 MINIMUMKERESÉS(A) ,,T= (n)" min A[1] FOR i 2 TO hossz[A] DO IF min>A[i] THEN min A[i] RETURN(min) Minimum és maximumkeresés n-1 összehasonlítással a minimumot és ezután n-2-vel a maximumot megkereshetjük, ami összesen 2n-3 összehasonlítás. Egy gyorsabb módszer: Elször az els két elemet hasonlítjuk össze (1 összehasonlítás), a kisebbet minimumként, a nagyobbat a maximumként tároljuk. Ezután már csak elempárokkal Minimumkeresés

Adatstruktúrák, algoritmusok -

- 41

dolgozunk ((n-2)/2 van). Összehasonlítjuk az elempár elemeit egymással (1 összehasonlítás), majd a kisebbet a minimummal, a nagyobbat a maximummal (2 összehasonlítás). Ha az addigi minimumot, vagy maximumot változtatni kell, akkor megtesszük. Összesen az összehasonlítások száma: 3 ×((n-2)/2)+1 = 3n/2-3 ×2/2+1 = 3n/2-2<2n-3 A medián Mediánnak nevezzük az adatsor azon elemét, amely a rendezett sorban a középs helyet foglalja el. Ha páratlan számú elem van az adatsorban, akkor n=2k-1 és így a medián indexe a rendezés után k. Ha páros számú elem van az adatsorban, akkor n=2k, és ekkor két középs elem van a k és a k+1 index a rendezés után. (Alsó medián, fels medián.) Ha nem említjük, akkor az alsó mediánról beszélünk. 123, 234, 345, 444, 566, 777, 890 Medián 123, 234, 345, 444, 566, 777, 890, 975 Alsó medián Kiválasztás lineáris idben (algoritmus) KUP_02 KIVÁLASZT(A,i) ,,T= (n)" 0. Ha n=1, akkor x maga az A[1] elem 1. Ha n >1, akkor Osszuk fel a tömböt n/5 darab 5-elem csoportra. (Esetleg a legutolsó csoportban lesz 5-nél kevesebb elem.) 2. Az összes n/5 csoportban megkeressük a mediánt beszúrásos rendezéssel. 3. A KIVÁLASZT algoritmus rekurzív alkalmazásával megkeressük az n/5 darab medián mediánját 4. A FELOSZT algoritmus segítségével a mediánok mediánja körül felosztjuk a bemeneti tömböt két részre. (A FELOSZT algoritmust ezen célból módosítani kell) Legyen k elem az alsó és n-k a fels részben. 5. A KIVÁLASZT algoritmus rekurziójával keressük az i-dik elemet az felosztás alsó részében, ha i k, vagy pedig az i-k-adikat a fels részben egyébként. Lineáris id bizonyítása Kiválasztás lineáris idben Fels medián

Adatstruktúrák, algoritmusok -

- 42

n / 5 csoport alakult ki. Mindegyikben meghatároztuk a mediánt. Ezen mediánok mediánját is meghatározzuk. Az adatok között a mediánok mediánjánál nagyobb elemek számát meg tudjuk becsülni az alábbi meggondolással. Mivel a medián középen lév elem, így az a mediánok mediánja, amely n / 5 medián közül kerül ki. Ezen mediánok fele biztosan nagyobb, mint a mediánok mediánja, azaz legalább n / 5 /2 - 1 ilyen elem van (saját magát nem számítjuk bele). Minden ilyen medián csoportjában akkor legalább három elem nagyobb a medánok mediánjánál, kivéve az esetleg 5-nél kevesebb elem utolsó csoportot, amit szintén elhagyunk. Ezek alapján legalább 3 * ( n / 5 / 2 ­2 ) 3 n / 10 - 6 elem biztosan nagyobb, mint a mediánok mediánja. (Ugyanennyi adódik a kisebb elemek számára is.) Az 5. lépésben a KIVÁLASZT algoritmus a fentiek szerint a felosztás másik részében legfeljebb n ­ ( 3 n / 10 ­ 6 ) = 7 n / 10 + 6 elemmel dolgozhat. A KIVÁLASZT algoritmus egyes lépéseinek az idigénye: 1.O(n) 2.O(n) 3.T(n/5 ) 4.O(n) 5.T(7n/10+6 ) Összegezve érvényes: T(n) T(n/5 )+T(7n/10+6 )+O(n) O(n) konstansa legyen a. Feltételezzük, hogy a megoldás T(n) c×n egy bizonyos n küszöbtl kezdve, és behelyettesítve bizonyítjuk. T(n) c × n / 5 + c × ( 7 n / 10 + 6 )+O ( n ) c × n / 5 + c + 7 c n / 10 + 6 c + a × n 9 c n / 10 + 7 c + a × n = c × n ­ ( c × n / 10 ­ 7 c ­ a × n ) Válasszuk n-et úgy, hogy a zárójel nem negatív legyen. Akkor c 10 a×n / (n-70) Ha ezen felül n 140, akkor a c 20a választás megfelel a kiinduló feltételezésünk teljesüléséhez. Elemi gráfelméleti bevezet Definíció: Irányított gráf (digráf) G=(V,E) rendezett pár, ahol V véges halmaz, a G-beli csúcsok halmaza. E bináris reláció a V halmazon, az élek halmaza E={(u,v) rendezett pár | uV,vV}V×V (Hurkok megengedettek) Az u csúcsból kiinduló és a v csúcsba mutató él jele: (u,v) Definíció: Irányítatlan gráf G=(V,E) rendezett pár, ahol V véges halmaz, a G-beli csúcsok halmaza. E bináris reláció a V halmazon, az élek halmaza

Adatstruktúrák, algoritmusok -

- 43

E={(u,v) rendezettlen pár | uV,vV}V×V (Hurok nem megengedett) Az u és v csúcsból kiinduló él jele: (u,v) Definíció: Az u csúcs szomszédja Legyen (u,v) él egy G=(V,E) gráfban. Ekkor a v csúcsot az u csúcs szomszédjának nevezzük (A szomszédság reláció irányítatlan gráfban szimmetrikus, digráfban nem.) G=(V,E) gráf ábrázolása Szomszédsági lista (E <
Csúcsmátrix (szomszédsági, vagy adjacencia mátrix): Incidencia mátrix:

Definíció: Csúcs fokszáma irányítatlan gráfban A csúcs fokszáma a belle kiinduló élek száma. Definíció: Csúcs fokszáma digráfban Kimen fokszám (kifok): a csúcsból kimen élek száma Bemen fokszám (befok): a csúcsba bemen élek száma Csúcs fokszáma: kifok+befok Definíció: Ionizált csúcs Csúcs, melynek fokszáma zérus. Definíció: Az u csúcsot az u' csúccsal összeköt k hosszúságú út Csúcsok véges sorozata: v0,v1,v2,...,vk, ahol u=v0, u'=vk és (vi-1,vi)E, i=1,...,k Definíció: Az u' csúcs elérhet az u csúcsból (u pu') ha van olyan út, amely az u csúcsot az u' csúccsal összeköti.

Adatstruktúrák, algoritmusok -

- 44

Definíció: Egyszer út A benne szerepl csúcsok páronként különbözek Definíció: Út része Legyen v0,v1,v2,...,vk út. Az út része vi,vi+1,...,vj, ahol 0 i j k . Definíció: Kör digráfban Út, melyre v0=vk és az út tartalmaz legalább egy élt. Definíció: Egyszer kör Kör, melynek csúcsai mind különbözek Definíció: Hurok 1 hosszúságú kör. Definíció: Egyszer gráf Hurok nélküli digráf Definíció: Kör gráfban Egyszer kör és k 3, v0=vk. Definíció: Körmentes gráf Gráf, amely nem tartalmaz kört. Definíció: Összefügg gráf Ha bármely két csúcsa összeköthet úttal. Definíció: Összefügg komponens Csúcsok alkotta ekvivalencia-osztály, ahol az ekvivalencia reláció a csúcsok közötti elérhetség. Definíció: Digráf ersen összefügg Tetszleges két csúcs esetén mindegyik elérhet a másikból. Definíció: Izomorf gráfok A G=(V,E) és a G'=(V',E') gráfok izomorfak, ha létezik olyan f:VV' bijekció, hogy (u,v) E (f(u),f(v)) E'. Definíció: A G=(V,E) gráf részgráfja G'=(V',E') gráf, melyre V' V és E' E. Definíció: A G gráf V' által meghatározott részgráfja

Adatstruktúrák, algoritmusok -

- 45

G'=(V',E'), ahol E'={(u,v) E: u,v V'}. Definíció: A G=(V,E) gráfhoz tartozó digráf Az a G'=(V',E') digráf, melyre (u,v) E' (u,v) E (azaz az éleket két irányított éllel helyettesítjük). Definíció: A G=(V,E) digráfhoz tartozó irányítatlan gráf G'=(V',E') gráf, melyre (u,v) E' uv, (u,v) E (azaz elhagyjuk a hurkokat és az irányítást). Definíció: Teljes gráf Irányítatlan gráf, melyben bármely két csúcs szomszédos. (Minden lehetséges él benne van.) Definíció: Páros gráf Irányítatlan gráf, melynél V felbontható V1, V2 diszjunkt unióra úgy, hogy (u,v) E esetén vagy u V1 és v V2, vagy pedig u V2 és v V1. (Azaz V1-ben és V2-ben nincs bels él.) Definíció: Erd Körmentes, irányítatlan gráf. Definíció: (Nyílt) fagráf Összefügg, körmentes, irányítatlan gráf. Tétel: A nyílt fák tulajdonságai Legyen G=(V,E) irányítatlan gráf. Az alábbiak ekvivalensek. 1. G nyílt fa 2. G bármely két csúcsához egyértelmen létezik egy ket összeköt egyszer út. 3. G összefügg, de tetszleges élének elhagyása után a visszamaradó gráf már nem összefügg 4. G összefügg és E= V - 1 5. G körmentes és E= V - 1 6. G körmentes, de akár egyetlen éllel is bvítve E-t a kapott gráf már tartalmaz kört. Bizonyítás 1. G nyílt fa 2. G bármely két csúcsához egyértelmen létezik egy ket összeköt egyszer út. G fa G összefügg G bármely csúcspárja között van út. Be kell

Adatstruktúrák, algoritmusok -

- 46

látni, hogy csak egy van. Ha több lenne, akkor kettbl már kör alakítható ki, ami ellentmondás. 2. G bármely két csúcsához egyértelmen létezik egy ket összeköt egyszer út. 3. G összefügg, de tetszleges élének elhagyása után a visszamaradó gráf már nem összefügg G bármely két csúcsa egyértelmen köthet össze úttal. G összefügg. Tetszleges (u,v) élt választva az él az u és v csúcsokat köti össze egyelem útként. az egyetlen út u és v között. Ha elhagyom, akkor nem lesz ott út, tehát a gráf nem lesz összefügg. 3. G összefügg, de tetszleges élének elhagyása után a visszamaradó gráf már nem összefügg 4.G összefügg és E= V ­ 1 G (3) miatt összefügg, tehát ezt nem kell bizonyítani. Másrészt ebbl adódóan automatikusan EV - 1. Teljes indukcióval látjuk be, hogy EV - 1.Legyen n= V. Ha n = 1 vagy 2, akkor ez igaz, mert a gráfnak n-1 éle van. Legyen most n3 és minden kevesebb csúcsú gráfra teljesüljön (3). Hagyjuk el tetszleges élét. Ezáltal k darab összefügg komponens keletkezik, ahol k2. Minden komponens (3) tulajdonságú. Az élek száma legfeljebb n-kn-2. Az elvett élt is hozzávéve az élek száma legfeljebb n ­ 1. 4. G összefügg és E= V - 1 5.G körmentes és E= V - 1 Indirekt módon bizonyítunk. Tegyük fel, hogy van kör. Erre a körre, mint részgráfra igaz, hogy éleinek és csúcsainak száma megegyezik. Legyen ez k. Ha k< V, akkor van még csúcs a körön kívül, mely szomszédos a kör valamely csúcsával G összefüggsége miatt. Vegyük hozzá a körhöz ezt a csúcsot és az élt. Az így kapott részgráfban is a csúcsok száma és az élek száma azonos (k+1). Újabb és újabb csúcsok és élek hozzávételével az összes csúcspontot felhasználjuk. Ekkor G-re azt kapjuk, hogy E V, ami ellentmondás. 5.G körmentes és E= V - 1 6. G körmentes, de akár egyetlen éllel is bvítve E-t a kapott gráf már tartalmaz kört. Legyen G összefügg komponenseinek száma k. Minden komponens fa és (1) (5). Ezért G komponenseiben V - k él van. E = V - 1 miatt k=1 és így G fa. Ekkor viszont bármely két G-beli csúcs összeköthet egyszer úttal. Hozzávéve egy új élt a két csúcs között, az az úttal együtt kört alkot

Adatstruktúrák, algoritmusok -

- 47

6. G körmentes, de akár egyetlen éllel is bvítve E-t a kapott gráf már tartalmaz kört. 1. G nyílt fa Azt kell belátni, hogy G összefügg. Legyen u,v két tetszleges csúcs. Ha szomszédosak, akkor van közöttük út.Ha nem szomszédosak, akkor vegyük fel az u,v élt. Ekkor kör keletkezik (6) miatt, A kör élei az (u,v) él kivételével G-hez tartoznak.és így utat alkotnak u és v között. Tehát G összefügg, tehát fa. Definíció: Gyökeres fa T fagráf, amely egyik csúcsának kitüntetett a szerepe a többihez képest. Ez a csúcs a gyökér vagy gyökércsúcs (r). Definíció: Az x csúcs megelzje A gyökérbl x-be vezet úton fekv bármely csúcs. (x is a saját megelzje.) Definíció: y valódi megelzje x-nek ha megelzje x-nek, de y x. Definíció: x az y rákövetkezje ha y x-nek megelzje. (x is a saját rákövetkezje.) Definíció: x valódi rákövetkezje y-nak ha megelzje y-nak, de y x. Definíció: x-ben gyökerez részfa Az x és a rákövetkezibl álló részgráf (fa). Definíció: x szülje y ha az r p x úton (y,x) az utolsó él. (A gyökérnek nincs szülje T-ben.) Definíció: x az y gyereke ha y az x szülje. Definíció: Testvérek azok a csúcsok, amelyeknek ugyanaz a csúcs a szülje. Definíció: Küls csúcs vagy levél az a csúcs, amelynek nincs gyereke. Definíció: Bels csúcs az a csúcs, amely nem levél.

Adatstruktúrák, algoritmusok -

- 48

Definíció: x fokszáma gyökeres fában az x gyerekeinek száma. (A szül nem számít bele a fokszámba!) Definíció: x szintje az r p x út hossza. Definíció: T magassága a T-beli csúcsok szintjei közül a legnagyobb. Definíció: Rendezett gyökeres fa minden csúcs gyerekei rendezettek. (Azaz van els, második,..., k-adik) Definíció: Bináris fa Rendezett fa, melyben minden csúcs fokszáma legfeljebb kett. (Beszélhetünk bal gyerekrl és jobb gyerekrl.) Definíció: Null fa Üres bináris fa. Definíció: Teljes bináris fa Bináris fa, melyben a csúcsok fokszáma kett, kivéve a leveleket, melyeké 0. Definíció: Súlyozott fa A csúcsok gyerekeit különböz pozitív, egész számmal indexeljük. (1,2,3,...) Definíció: csúcs i-dik gyereke hiányzó nincs i index gyereke. Definíció: k-adrend fa Súlyozott fa, ahol minden csúcsnál a k-nál nagyobb index gyerekek hiányoznak. (A bináris fa másodrend.) Definíció: k-adrend teljes fa k-adrend fa, melyben a levelek ugyanazon szintek és az összes bels csúcs fokszáma k. A h magasságú teljes k-adrend fának kh számú levele van. Ha a levelek száma n, akkor a teljes k-adrend fa magassága logkn. A h magasságú teljes k-adrend fa bels csúcsainak a száma:

Adatstruktúrák, algoritmusok 1+ k + k +K+ k
2 h -1

- 49
k h -1 = k = k -1 i =1
h -1 i

Teljes bináris fa bels csúcsainak száma: 2h-1. A gyökeres fa adatstruktúra. A fa minden csúcsa egy objektum. Az objektumok tartalmaznak kulcs mezt és mutatókat. A T fa attribútuma: gyökér[T] Ha gyökér[T]=NIL, akkor a fa üres. Bináris fa esetén az x csúcs ábrázolható az alábbi sémával: Szül mutató Kulcs Bal gyerek mutató Jobb gyerek mutató Csúcsattribútumok: szül[x], kulcs[x], bal[x], jobb[x] Ha szül[x]=NIL, akkor x gyökér. Ha bal[x]=NIL, vagy jobb[x]=NIL, akkor az a gyerek nincs. Ha mindkett NIL, akkor x levél. k-adrend fák ábrázolása (Memória pazarló) Szül mutató Kulcs 1. gyerek mutató 2. gyerek mutató ... k. gyerek mutató k-adrend fák reprezentálása binárissal (Memóriaigény O(n)) Szül mutató Kulcs Bal gyerek mutató Jobb testvér mutató NIL *** NIL

*** ***

*** ***

NIL NIL

NIL ***

NIL ***

NIL NIL

NIL ***

NIL NIL

Adatstruktúrák, algoritmusok -

- 50

Definíció: A (bináris) kupac adatstruktúra A bináris kupac (heap) egy bináris gyökeres fa, amely minden szintjén kitöltött, kivéve esetleg az utolsó szintet, ahol balról jobbra haladva vannak a levelek kihagyás nélkül továbbá teljesül a kupac tulajdonság. Kupac tulajdonság: minden x r csúcsra Kulcs[Szül[x]] Kulcs[x] (max kupac esetén) minden x r csúcsra Kulcs[Szül[x]] Kulcs[x] (min kupac esetén) Kupac magasság = a fa magassága = (log n) Példa kupacra és tömbös realizációjára: 16

14

10

8

7

9

3

2

4

1

16 14 10
1 2 3

8
4

7
5

9
6

3
7

2
8

4
9

1
10

Kupac attribútumok (feltételezve, hogy a reprezentálás egy egyindexes A tömbbel történik, amelyben a kupacot tároljuk.) hossz[A] = a tömb fizikai maximális mérete (elemszám a tömbben). kupac_méret[A] = a kupacelemek (csúcsok) száma A fa gyökere A[1] ( = gyökér [ T ] )

Adatstruktúrák, algoritmusok -

- 51

Az i index elem esetén az attribútumok: Szül(i), Bal(i), Jobb(i) Mindegyik idigénye: (1) KUP_03 KUP_04 KUP_05 Szül ( i ) Bal ( i ) Jobb ( i ) RETURN ( i / 2 ) RETURN ( 2i ) RETURN( 2i + 1 ) KUP_06 KUPACOL

KUPACOL ( A, i ) ,,Eljárás a kupac tulajdonság fenntartására (log n)" ,,Akkor használjuk, ha az i baloldali és jobboldali részfái ugyan kupacok," ,,de i-ben sérülhet a kupac tulajdonság" b Bal ( i ) j Jobb ( i ) IF b Kupac_méret [ A ] és A [ b ] > A [ i ] THEN legnagyobb b ELSE legnagyobb i IF j Kupac_méret [ A ] és A [ j ] > A [ legnagyobb ] THEN legnagyobb j IF legnagyobb i THEN csere A [ i ] A [ legnagyobb ] KUPACOL ( A, legnagyobb )

KUP_07

KUPACOT_ÉPÍT (n)"

KUPACOT_ÉPÍT ( A ) ,,Eljárás, mely tetszleges adatokból kupacot épít ,,Most hossz[A] legyen azonos az elemek számával (n)" Kupac_méret [ A ] hossz [ A ] FOR i hossz [ A ] / 2 DOWNTO 1 DO KUPACOL ( A, i ) KUP_08 KUPACRENDEZÉS ( A ) ,,Eljárás, mely helyben rendez KUPACOT_ÉPÍT ( A ) FOR i hossz [ A ] DOWNTO 2 DO

KUPACRENDEZÉS (n log n)"

Adatstruktúrák, algoritmusok -

- 52

csere A [ 1 ] A [ i ] Kupac_méret [ A ] Kupac_méret [ A ] ­ 1 KUPACOL ( A, 1 ) KUP_09 KUPACBA_BESZÚR (log n)"

KUPACBA_BESZÚR ( A, kulcs ) ,, INC ( Kupac_méret [ A ] ) i Kupac_méret [ A ] WHILE i > 1 és A [ Szül ( i ) ] < kulcs DO A [ i ] A [ Szül ( i ) ] i Szül ( i ) A [ i ] kulcs KUP_10 KUPACBAN_MAX ( A ) ,, RETURN( A[1] ) KUP_11

KUPACBAN_MAX (1)"

KUPACBÓL_KIVESZ_MAX (log n)"

KUPACBÓL_KIVESZ_MAX ( A ) ,, IF Kupac_méret [ A ] < 1 THEN hiba ,,kupac alulcsordulás" max A [ 1 ] A [ 1 ] A [ Kupac_méret [ A ] ] DEC ( Kupac_méret [ A ] ) KUPACOL ( A, 1 ) RETURN ( max ) Elsbbségi sor

Definíció: Elsbbségi sor adatstruktúra Az elsbbségi sor (priority queue) olyan S halmaz, amelynek minden eleméhez egy kulcs értéket (prioritás) rendelünk. Az elsbbségi sorban a maximális (minimális) kulcs megkeresése konstans id.

Adatstruktúrák, algoritmusok -

- 53

Az elsbbségi sor gyakori és hatékony mveletei: BESZÚR(S,x): egy elemet hozzáadunk S-hez. S ¬S È {x} MAXIMUM(S): S legnagyobb kulcsú elemének meghatározása KIVESZ_MAX(S): megadja és törli a maximális kulcsú elemet. Az elsbbségi sor célszer realizációja a kupac. Definíció: Mohó algoritmus A mohó algoritmus egy algoritmus tervezési stratégia, mely esetében egy globális optimalizálási problémát lokális optimalizálások során keresztül próbálunk megoldani. A mohó stratégia elemei: Az adott pillanatban mindig az ott legjobbnak tn lehetséget választjuk a részprobléma megoldására. Ez függhet az elz választásoktól, de nem függ a késbbiektl. A mohó stratégia nem mindig vezet optimumra. A Huffman kód A Huffman kódolás adattömörítési célokat szolgáló eljárás. A probléma: Legyen adott egy adatfile, amelyben ismert az egyes adatelemek (pl.: byte-ok) gyakorisága. A feladat olyan kódot találni az adatelemekre, amely révén a kódolt file hossza rövidebb lesz (a lehet legrövidebb), mint az eredeti hossz volt. Az egyszerség kedvéért a kódoláshoz használjunk két jelet, a 0 és az 1 jeleket. Az adatelemek kódja lehet fix hosszúságú és változó hosszúságú. A kódot egy kódfával ábrázolhatjuk, amely egy bináris fa, levelei a kódszavak és a kódszó a gyökértl levélhez vezet útból olvasható ki. Ha balra lépünk, akkor 0, ha jobbra lépünk, akkor 1 íródik a kódszóhoz. A kódnak dekódolhatónak kell lennie, ami azt jelenti, hogy minden kódolt szöveg egyértelmen bontható kódszavakra. Definíció: Prefix kód Prefix kódnak nevezzük a kódot, ha egyik kódszó sem eleje semelyik másik kódszónak. (Semelyik kódszót sem lehet valamely másikból kódjelek hozzáírásával megkapni.) A prefix kód dekódolható kód. Két dekódolható kód ekvivalens, ha a megfelel kódszavaik hossza megegyezik. Bizonyítható, hogy minden dekódolható kódhoz létezik vele ekvivalens prefix kód.

Adatstruktúrák, algoritmusok -

- 54

Bet Gyakoriság Kódszó
f(c)

Kódszó 0 101 100 111 1101 1100

Fix hossz Változó hossz

A B C D E F

45 13 12 16 9 5

000 001 010 011 100 101

100
0 1

86
0 1 0

14

58
0 1 0

28
1 0

14
1

A:45

B:13

C:12

D:16

E: 9

F: 5

100
0 1

A:45 0

55
1

25

30

Adatstruktúrák, algoritmusok 0 C:12 1 0 1 D:16

- 55

B:13 0

14
1

F: 5

E: 9

Definíció: Kódfa költsége Legyen C a forrásábécé betinek halmaza. Jelölje f(c) a c bet gyakoriságát, d(c) a kódszó hosszát (a bet mélységét a fában). Az alábbi számot a kódfa (kód) költségének (átlagos kódszóhossznak) nevezzük.

B(T ) = f (c )d (c )
cC

Definíció: Optimális kód Optimálisnak nevezzük a kódot, ha a fa költsége minimális Tétel: A Huffman kód optimalitása A Huffman kód optimális. A Huffman kód szerkesztése Jelölje a kódolandó ábécé betinek halmazát C és legyen a betk száma n. A pszeudokód kiindul egy prioritási sorból, amelyben a betk a gyakoriságaik szerint vannak kulcsolva. Ezután n-1 lépésben a két legkisebb gyakoriságú elemet összevonva felépít egy optimális kódfát. Az optimum nem egyértelm, mert az optimális fában bármely csúcs bal és jobb gyerekét felcserélve újra optimális fát kapunk. Az algoritmus mohó algoritmus, mivel minden lépésben úgy von össze, hogy a költség a legkisebb mértékben növekedjen. A teljes fa költsége megegyezik az összevonási lépések költségének összegével. KUP_12 HUFFMANN( C ) ,, n C QC HUFFMAN KÓD ( n log n )"

Adatstruktúrák, algoritmusok -

- 56

i 1 TO n-1 DO z PONTOT_LÉTESÍT() x Bal[z] KIVESZ_MIN(Q) y Jobb[z] KIVESZ_MIN(Q) f[z] f[x]+f[y] BESZÚR(Q,z) RETURN( KIVESZ_MIN(Q) ) FOR Definíció: Diszjunkt halmazok adatszerkezet A diszjunkt halmazok adatszerkezet dinamikus halmazok S = ( S1, S2, ..., Sk ) együttese. Mindegyik halmazt egy képviselje azonosít, mely eleme a halmaznak. Általában lényegtelen, hogy melyik ez az elem. A halmazok elemei objektumok. Mveletek: HALMAZT_KÉSZÍT(x): Egy új halmazt hoz létre, melynek ez az egy x eleme lesz, amely egyúttal képviselje is. EGYESÍT(x,y): Az x-et tartalmazó Sx és az y-t tartalmazó Sy halmazokat egyesíti a két halmaz uniójává. Az eredmény az eredeti két halmaz helyére lép, azok megsemmisülnek. A közös képvisel az unió tetszleges eleme lehet HALMAZT_KERES(x): visszaad egy mutatót, amely x halmazának a képviseljére mutat. Diszjunkt halmazok alkalmazása Megkeressük egy gráf összefügg komponenseit KUP_13 ÖSSZEFÜGG_KOMPONENSEK(G)

ÖSSZEFÜGG_KOMPONENSEK(G) ,, " FOR v V [ G ] csúcsra DO HALMAZT_KÉSZÍT ( v ) FOR ( u, v ) E [ G ] élre DO IF HALMAZT_KERES ( u ) HALMAZT_KERES ( v ) THEN EGYESÍT(u,v) KUP_14 UGYANAZ_A_KOMPONENS

UGYANAZ_A_KOMPONENS ( u, v ) ,, " IF HALMAZT_KERES ( u ) = HALMAZT_KERES ( v )

Adatstruktúrák, algoritmusok -

- 57

THEN RETURN ( IGAZ ) ELSE RETURN ( HAMIS ) Diszjunkt halmazok realizálása: 1. Láncolt listás realizálás 2. Diszjunkt halmaz erd (gyökeres fákkal) KUP_15 HALMAZT_KÉSZÍT ( x ) ,, Szül [ x ] x Rang [ x ] 0 KUP_16 ÖSSZEKAPCSOL ( x, y ) ,, " IF Rang [ x ] > Rang [ y ] THEN Szül [ x ] x ELSE Szül [ x ] y IF Rang [ x ] = Rang [ y ] THEN Rang [ y ] Rang [ y ] + 1 KUP_17 HALMAZT_KERES HALMAZT_KÉSZÍT "

ÖSSZEKAPCSOL

HALMAZT_KERES ( x ) ,, " IF x Szül [ x ] THEN Szül [ x ] HALMAZT_KERES ( Szül [ x ] ) KUP_18 EGYESÍT

EGYESÍT ( x, y ) ,, " ÖSSZEKAPCSOL ( HALMAZT_KERES ( x ), HALMAZT_KERES ( y ) )



Hasonló témájú dokumentumok

Összefoglaló

- 2008-03-10 20:58:44

2007-es vizsgák az 5 éves képzésből

- 2007-12-27 13:26:05

A mások által feltöltött dokumentumokat értékelheted. Ha úgy ítéled meg, hogy a vizsgára való felkészülés szempontjából hasznos volt egy dokumentum, akkor adj rá sokcsillagos értékelést.
Ha hibákat tartalmaz, vagy egyéb probléma van vele, akkor keveset.
A dokumentumok sorrendje az értékelések alapján adódik. Ami fentebb van a listában, azt hasznosabbnak ítélték társaid. Az új dokumentumok pedig (értékelések hiányában) szintén a lista tetején kezdenek.

Hozzászólások

Ha észrevételed van egy dokumentummal kapcsolatban (például hibát találtál benne), akkor a Hozzászólások részben jelezheted. Az olyan jellegű kérdéseket mint pl.: A 2. feladat 4. sorából milyen átalakítással jutottunk az 5. sorban szereplő képlethez? - szintén ide érdemes írni

Egy tipp az oldalhoz! - Online ZH, vizsga kidolgozás! Mi is ez? Ha feltöltesz egy régi ZH-t/vizsgát, a dokumentum oldalán Hozzászólást lehet írni. Megírhatod például, hogy "szerintem a 3-as feladat megoldása ez: "... Ha hiba van benne, más hallgató egy új hozzászólásban ezt jelezheti.

1.óra 11 2009. május 21. 3. előadás ábris alapvizsga architekturak barokk bodlaki tamás deklaratív programozás épszerk v etika eu agrárpolitikája fémek földrajz inverz függvény kidolgozott kiskérdések kik kisebbség közgazdaság közigazgatási jog közjog közpolitika lévi-strauss malinowski matek ii. zh metafora minőségügy munka nonverbális kommunikáció növénytan oscar niemeyer oszlop őskor pénzügyek political science reklámelmélet reklámjog rugó setting prices stendhal stilisztika tájékoztató tűzvédelem vér vergilius vezgazd virológia vizes éh. kez. vizsga feladatsor