Programozás | Programozás-elmélet » Nagy Ferenc - Adatstruktúrák, algoritmusok előadásvázlat

Adatstruktúrák, algoritmusok -1- ADATSTRUKTÚRÁK, ALGORITMUSOK BSc mérnök informatikus szak Előadá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 időnként használjuk a matematikai jelöléseket: ∃ Létezik ∃! Egyértelműen létezik ∀ Minden O Nagy ordo o Kis ordo N Természetes számok Z Egész számok halmaza R Valós számok halmaza A bizonyítások végét a ■ jel jelzi. A görög ábécé kis- és nagybetűi α β γ δ ε ζ η θ Α Β Γ ∆ Ε Ζ Η Θ alfa beta gamma delta epszilon dzeta eta teta ι κ λ µ ν ξ ο π Ι Κ Λ Μ Ν Ξ Ο Π iota kappa lambda mű nű kszi omikron pi ρ ς, σ τ υ φ χ ψ ω Ρ Σ Τ Υ Φ Χ Ψ Ω ro szigma tau üpszilon fi khi pszi omega 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ülőgé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ülőjegy helyfoglalási példa útvonalak, gépek, dátumok, helyfoglalások file-ok, táblázatok, listák, adatrekordok, stringek, fák objektumok, műveletek, 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, elsőbbsé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 előre meghatározott adathalmaz valamely tetszőleges kiinduló eleméből 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 vetődjö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 meglevőnél hatékonyabb megoldási módszer (algoritmus)? Az algoritmus hatékonysági jellemzői. 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) időigényt és az SA(x) tárigényt . Az algoritmus Az algoritmus időbonyolultsága tárkapacitás bonyolultsága TA (n) = sup TA (x ) x∈D x ≤n S A (n) = sup S A ( x ) x∈D 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) időigé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) ≤ c⋅g(n) 2. f(n)=Ω (g(n)): ∃ c>0 és n0 , hogy ha n>n0, akkor 0 < c⋅g(n) ≤ f(n) 3. f(n)=Θ(g(n)): ∃ c1,c2>0 és n0 , hogy ha n>n0, akkor 0 < c1⋅g(n) ≤ f(n) ≤ c2⋅g(n) 4. f(n)=o(g(n)): ∀c>0 ∃ n0 , hogy ha n>n0, akkor 0 < f(n) < c⋅g(n) 5. f(n)= ω(g(n)): ∀c>0 ∃ n0 , hogy ha n>n0, akkor 0 < c⋅g(n) < f(n) Adatstruktúrák, algoritmusok -5- A gyakorlatban gyakran előforduló 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, k∈R 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 megelőzőek 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 ahol Φ = 1+ 5 1− 5 ≈ 1.618, Φ = ≈ −0.618 2 2 Bizonyítás Tekintsük a rekurzív definíciót a kezdőfelté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, amiről behelyettesítéssel Adatstruktúrák, algoritmusok -6- n n meggyőződhetü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 < Φ + , amiből látszik, hogy Fn egybeesik Tehát 2 2 5 5 ≤− az ■ egyetlen egésszel, amely a megadott intervallumban van. 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 ≈ 0447213595⋅ 1618033989n ⎝ 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 egyenletekről Az algoritmusok időbonyolultsá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 időigénye a legrosszabb esetben. Sok esetben csak az egyes méretek időigényei közötti kapcsolatot ismerjük. Ebből kellene felírni vagy az explicit kapcsolatot, vagy legalább az időigé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)<n feltétel teljesülését elvárjuk, mert különben logikai nehézségeink támadnak T(n) kiszámításakor. Példa: T(n)=T(n-1)+1, T(1)=1. Az ilyen időbonyolultságú algoritmus a méret egységnyi növekedésére az idő egységnyi növekedésével válaszol. Írhatjuk a visszavezetési módszert alkalmazva, hogy: T(2)=T(1)+1=1+1=2 T(3)=T(2)+1=2+1=3 Teljes

indukcióval kihozható, hogy T(n)=n. Aszimptotikusan T(n)=Θ(n) Az algoritmus lineáris idejű. Példa: T(n)=T(n-1)+n, T(1)=1. A visszavezetési módszerrel: T(2)=T(1)+2=1+2=3 T(3)=T(2)+3=3+3=6 Teljes indukcióval belátható, hogy T(n)=1+2+3++n=n·(n+1)/2= Θ(n2). Az algoritmus kvadratikus idejű. Példa: T(n)=T(n/2)+1, T(1)=1. A visszavezetést alkalmazva (csak az n=2m alakú nre) azt írhatjuk, hogy T(2m)=T(2m-1)+1. Bevezetve az U(m)=T(2m) jelölést azt kapjuk, hogy U(m)=U(m1)+1 Ezt a feladatot az első példában megoldottuk és onnan a megoldás U(m)=m Akkor T(2m)=m. Figyelembe véve, hogy m=log2n a végeredmény T(n)= log2n= Θ(log2n). Az algoritmus logaritmikus idejű Speciális, de a gyakorlat szempontjából sok fontos esetben a rekurzív egyenletekre a mester tétel ad megoldást (sok esetben pedig nem ad). A tételt nem bizonyítjuk Tétel: A mester tétel Legyenek a≥1, b>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)= Θ(np⋅log 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 tűnik 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 tűnik 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 tűnik az eset. Legyen a=3, b=4, f(n)= n·log n, p=log43, 0<p<1, a tesztpolinom np. Ha 0<ε<1-p, akkor f(n)=Ω(np+ε), ugyanis (n·log n)/np+ε limesze ha n a végtelenbe tart, végtelen. A mester tétel 3 pontjának a feltételei fognak teljesülni, ha még kimutatjuk az f regularitását. 3·f(n/4) = 3·(n/4)·log(n/4) = (3/4)· n·log n - (3/4)·n·log 4 ≤ (3/4)·n·log n =(3/4)·f(n). Azaz minden pozitív n-re teljesül a regularitás c=3/4<1-gyel. A tételt alkalmazva: T(n)=Θ(f(n))= Θ(n·log n) 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értelműen 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=33, y=-33 együtthatókra s=xa+yb tábla x y -3 -2 -1 0 -3 -288 -252 -216 -180 -2 -228 -192 -156 -120 -1 -168 -132 -94 -60 0 -108 -72 -36 0 1 -48 -12 24 60 2 12 48 84 120 3 72 108 144 180 Adatstruktúrák, algoritmusok - -144 -108 -72 1 2 3 Tétel: - 10 -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 ⎪ dd ba ⎩ * 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 s∈L ( 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 , amiből 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 egyenlőtlenség közepén álló maradék az a és b lineáris kombinációja. A baloldali egyenlőtlenség miatt nem lehet negatív, a jobboldali egyenlőtlensé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. Tetszőleges 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ó egyenlősé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 - Bizonyítás - 12 Legyen M a d* egész többszöröseinek a halmaza. Megmutatjuk, hogy L ⊂ M és M ⊂ L, amiből következik az állítás. L ⊂ M esete:. d*|a, d|b ⇒ a=kad, b=kbd, ka,kb∈Z L ∋ s=ax+by=kad*x+kbdy=d(kax+kby)=kd ∈ M, mert k∈Z M ⊂ L esete:. d*=lnko(a,b)=ax+by M ∋ s= ksd*=ks(ax+by)=kaxa+kbyb) ∈ L Tétel: Bizonyítás ■ Az lnko redukciós tétele lnko(a, b) = lnko(a − b, b) * * 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 , amiből következni fog az állítás. Világos, hogy fennállnak az alábbi tulajdonságok d1* d 2* 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. amiből a kölcsönös oszthatóság már következik. d1* ∈ L(a − b, b) megmutatása: d1* = x1a + y1b = x1 (a − b + b) + y1b =

x1 (a − b) + x1 + y1 b ∈ L(a − b, b) ( ) ( ) d 2* ∈ L(a, b) megmutatása: d 2 = x2 (a − b) + y2b = x2a + 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 egyszerűbbé 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 műveleteket 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 egyszerűbb 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) c←1 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: c←2c a←a/2 b←b/2 pa=0, pb=1: a←a/2 pa=1, pb=0: b←b/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 b Korrekció 0 3604 3332 2 1 1802 1666 2 2 901 833 3 34 ↔ 833 Adatstruktúrák, algoritmusok - - 14 4 5 6 7 8 9 10 11 833 833 408 204 102 51 17 0 34 17 17 17 17 17 17 17 Az lnko rekurziós tétele Tétel: 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 - Tétel: r 272 68 0 68 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ételből: 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-ből. 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 Φ ≈ 02089, ≈ 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 időigénye O(log b) A kibőví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 fentről lefelé

haladunk a táblában. xk*+1 = xk ⋅ qk + yk yk*+1 = xk * * Haladjunk lentről felfelé. Akkor ebből az egyenletrendszerből 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 kibővítésére, melynek pszeudokódját alább közöljük. SZE 03 Kibővített euklideszi algoritmus Kibővített Euklidesz (a, b) IF b=0 THEN RETURN (a, 1, 0) (d*,x,y) ← Kibővített Euklidesz (b, a mod b) (d*,x,y) ← (d,y,x - ⎣a/b⎦ y) RETURN (d*,x,y) Példa a kibőví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-12⋅1=-12 0 1-4⋅0=1 1 0 Az algoritmus eredményeképpen x0 = −12 és y0 = 13

adódott. Ellenőrzésképpen 68=(-12)⋅3604+13⋅3332=-43248+43316, ami valóban megfelel az elvárásoknak. * * A lineáris kongruencia egyenlet. Definíció: A lineáris kongruencia egyenlet Az ax≡b mod n a,b∈Z, n∈Z+ 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ó alaprendszerből megkaphatjuk az n egész számú többszöröseinek a hozzáadásával. Az alaprendszer elemeit a 0≤x<n intervallumból választjuk ki. Az alaprendszer megoldásai az alábbi módon írhatók fel: x0=x*(b/d ) mod n, xi=x0+i⋅(n/d*) mod n, i=1,2,,d-1 Bizonyítás ⎢ ax ⎥ ⎢b ⎥ Legyen q1 = ⎢ ⎥, q 2 = ⎢ ⎥, q = q 2 − q1 Akkor a lineáris

kongruencia ⎣n⎦ ⎣n⎦ egyenlet ax-q1n=b-q2n alakra, amiből 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 b∈L(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*k≡dk 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+a⋅i(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 kibővített euklideszi algoritmusból megkapható. SZE 04 Lineáris kongruencia megoldó algoritmus Lineáris kongruencia megoldó (a, b, n) (d*,x,y) ← Kibővített Euklidesz (a, n) IF d*|b Adatstruktúrák, algoritmusok - - 18 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”) THEN Példa: 3604x≡136 mod 3332 Láttuk, hogy lnko(3604,3332)=68=-12⋅3604+13⋅3332. 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=56⋅2=112, x1=112+49=161,

x2=112+2⋅49=210,., x67=112+67⋅49=3395≡63 mod 3332. Definíció: A multiplikatív inverz Legyen a lineáris kongruencia egyenlet ax≡1 mod n a∈Z, n∈Z+, 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 5x≡1 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-1⋅2=-3 -1 1-1⋅(-1)=2 1 0-1⋅1=-1 0 1-2⋅0=1 1 0 Láthatóan lnko(5,8)=1, tehát van multiplikatív inverz. 1=2⋅8+(-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. Ellenőrzés: 5⋅5=25=3⋅8+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,n∈Z+. A feladat c=ab mod n meghatározása lehetőleg 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 kettővel való szorzást és egy nulla vagy egy hozzáadását kell végezni, melyek számítástechnikailag hatékony műveletek. A b szám a kitevőben van, ezért a hatványozás során a kettővel 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) p←0 c←1 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 - 4 3 2 1 0 1 0 1 0 1 222 1202 152 1092 992 - 20 = 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-1≡1 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 terjedően a számok között csak 22 olyan van, amely nem prím és a teszt esetleges prímnek minősí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 kiszűrhető 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 - 2 0 1 1 0 0 - 21 22 = 4 42 = 16 ≡ 5 102 = 100 ≡ 1 5·2 = 10 210≡1 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 211≡8 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észtvevőnek 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 levelezőlapon 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 jegyűekre 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 - IF - 22 p vagy q nem prím vagy e<3 vagy e páros THEN RETURN („Nincs kulcs”) n←p⋅q f←(p-1)⋅(q-1) IF lnko(e,f) ≠ 1 THEN RETURN („Nincs kulcs”) -1 d←e 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 kibővített euklideszi algoritmust alkalmazzuk. e ⎣f / e⎦ f mod e d* x f 280 3 93 3 1 1 0 3 - y 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 - 7 6 5 4 3 2 1 0 1 0 1 1 1 0 1 1 12 2542 782 1002 1222 672 232 672 - 23 = = = = = = = = 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 (bővül, szűkül, módosul) dinamikus halmaznak nevezzük. A dinamikus halmazok elemei tartalmazhatnak - kulcsmezőt, - mutatókat (pointereket), amelyek más elemekre mutatnak. (pl: a következő elemre) Dinamikus halmazon értelmezett műveletek 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 ELŐZŐ(S,x) az x elem

kulcsa előtti kulcsú elem mutatóját adja vissza, nil, ha x előtt nincs elem Módosító BESZÚR(S,x) az S bővítése az x mutatójú elemmel TÖRÖL(S,x) az x mutatójú elemet eltávolítja S-ből Definíció: A verem adatstruktúra A verem (stack) olyan dinamikus halmaz, amelyben előre 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 kezdődik.) Tető 1 2 3 4 5 6 342 416 112 234 Adatstruktúrák, algoritmusok - - 25 A verem műveletek 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) VEREMBE(S,x) „Tömbös realizáció tető[S] ← tető[S]+1 S[tető[S]] ← x DIN 03 T=Θ (1)” Veremből törlés (~pop) VEREMBŐL(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 előre 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 (elsőnek érkezett – elsőnek 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 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 T=Θ (1)” Sorból eltávolítás 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) T=Θ (1)” 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 előző 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 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 T=Θ (1)” 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 előbb meg kell keresni x-et” „ekkor az időigény T=Θ (n)” IF elő[x] ≠ NIL THEN köv[elő[x]] ← köv[x] Adatstruktúrák, algoritmusok - IF - 28 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

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 T=Θ (n)” 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 előbb meg kell keresni x-et” „ekkor az időigé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é Mindkettőnek 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ömbből, ahonnan előzőleg 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 időigé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 mindkettőt 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 időigé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 időigé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) „T=Θ (n2), T(n)=Θ (n log n)” IF p<r THEN q ← FELOSZT ( A, p, r ) Adatstruktúrák, algoritmusok - - 32 GYORSRENDEZÉS ( A, p, q ) GYORSRENDEZÉS ( A, q+1, r ) REN 04 Felosztás a gyorsrendezésben FELOSZT ( A, p, r ) „T=Θ (n)” x←A[p] i ←p–1 j ←r+1 WHILE 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

időigé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úlmenően 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 ln(n!) > ∫ ln x dx = ∫ 1 ⋅ ln x dx = [x ⋅ ln x]1 − ∫ x ⋅ 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 n n n ln(n!) = 1 ⋅ ln 1 + 1 ⋅ ln 2 + 1 ⋅ ln 3 + 1 ⋅ ln 4 + K + 1 ⋅ ln n ln(n!) < ∫ ln x dx = ∫ 1 ⋅ ln x dx = [x ⋅ ln x]1 − [x]1 = n+1 n 1 n+1 n+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 nem a2 ≤ a3 ? igen nem igen a1 ≤ a3 ? 1, 2, 3 igen 1, 3, 2 Tétel: a1 ≤ a3 ? nem a2 ≤ a3 ? 2, 1, 3 nem 2, 3, 1 igen 3, 1, 2 Alsó korlát összehasonlító rendezésre Bármely n elemet rendező döntési fa magassága Ω(n log n) nem 3, 2, 1 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 előnye, 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 kettőt 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 Bizonyítás Fogadjuk el kiindulásként igaznak azt a feltevést, hogy C elejéből 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} Ebből 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-ből (a B páros indexű elemei), Valamint V-be kerül ⎣ s/2⎦ elem az A-ból (az A páros indexű elemei) Adatstruktúrák, algoritmusok - - 35 és ⎡(2k-s)/2 ⎤ elem a B-ből (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. Időigé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) BUBORÉK RENDEZÉS(A) „T=Θ (n2)” 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[1t] 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] h[i-1]=3h[i]+1 121, 40, 13, 4, 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. Időigény: alkalmas növekmény választással leszorítható O(n12)-re REN 06 Shell rendezés (Shell Sort) SHELL RENDEZÉS(A) „T=Θ (n1.2)” 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ésőbbi elemtől

indulunk. Megkeressük a minimális elemet, és azt az aktuális menet első elemével felcseréljük. Időigé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). Mindegyikből kiemeljük (eltávolítjuk) a legkisebbet. (Ez lesz a főcsoport) Kiválasztjuk a legkisebbek legkisebbikét (a legkisebbet a főcsoportból) és azt az eredmény tömbbe írjuk, a főcsoportból eltávolítjuk. Helyére abból az alcsoportból ahonnan ő jött újabb legkisebbiket emelünk be a főcsoportba. Az eljárást folytatjuk, míg az elemek el nem fogynak. Időigény:

összehasonlításszám O(n · √n)=O(n1.5) Továbbfejlesztett változat, amikor ³√n számú elem van egy fő-főcsoportban, ³√n számú főcsoport van mindegyikben ³√n számú elemmel, melyek mindegyikéhez egy ³√n elemszámú alcsoport tartozik. A rendezés elve a fentihez hasonló Időigény: O ( n · ³√n ) Lineáris idejű rendezők A leszámláló rendezés A lineáris idejű rendezők 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. Időigé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[1k] 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ékűek 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 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-től 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ámjegyekből álló számok, kártyák, stb.) Legyen d a szó hossza, k pedig az egy karakteren, mezőben előforduló jegyek, jelek lehetséges száma, n

pedig az adatok száma. Időigény: Θ (d(n+k)) REN 09 Számjegyes (radix) rendezés SZÁMJEGYES RENDEZÉS(A) „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 esőket beszúrásos módon rendezzük. A végén a listákat egybefűzzük az elsővel kezdve. Várható időigény: Θ (n) REN 10 Edényrendezés 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 összefűzzü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 elsősorban 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ő sorrendűek). Előszö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 időigé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 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: Előszö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 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 Felső medián Kiválasztás lineáris időben (algoritmus) KUP 02 Kiválasztás lineáris időben 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 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 időigé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öbtől 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 | u∈V,v∈V}⊂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 | u∈V,v∈V}⊂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⏐ <<⏐V⏐): Csúcsmátrix (szomszédsági, vagy adjacencia mátrix): Incidencia mátrix: minden u ∈V csúcshoz az Adj[u] tartalmazza az összes olyan v csúcsot, melyre létezik az (u,v) ∈E él. Listák hosszának összege: digráfban: ⏐E⏐ irányítatlan gráfban 2 ⏐E⏐ A=(aij) mérete ⏐V⏐× ⏐V⏐, aij értéke 1, ha (i,j) ∈E és 0 egyébként. Szimmetrikus esetben elég a főátló és a fölötte lévő elemeket tárolni. B=(bij) mérete ⏐V⏐ × ⏐E ⏐, (bij) értéke –1, ha a j él i-ből kivezet, 1 ha a j él i-be bevezet és 0 egyébként. Definíció: Csúcs

fokszáma irányítatlan gráfban A csúcs fokszáma a belőle 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özőek 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özőek 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érhetőség. Definíció: Digráf erősen összefüggő Tetszőleges 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’ ⇔ u≠v, (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értelműen létezik egy őket összekötő egyszerű út. 3. G összefüggő, de tetszőleges é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 bőví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értelműen 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 kettőből már kör alakítható ki, ami ellentmondás. 2. G bármely két csúcsához egyértelműen létezik egy őket összekötő egyszerű út. 3. G összefüggő, de tetszőleges élének elhagyása után a visszamaradó gráf már nem összefüggő G bármely két csúcsa egyértelműen köthető össze úttal. ⇒ G összefüggő

⇒Tetszőleges (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 tetszőleges é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 ebből adódóan automatikusan ⏐E⏐≥⏐V⏐ - 1. Teljes indukcióval látjuk be, hogy ⏐E⏐≤⏐V⏐ - 1.Legyen n= ⏐V⏐ Ha n = 1 vagy 2, akkor ez igaz, mert a gráfnak n-1 éle van. Legyen most n≥3 és minden kevesebb csúcsú gráfra teljesüljön (3). Hagyjuk el tetszőleges élét Ezáltal k darab összefüggő komponens keletkezik, ahol k≥2. Minden komponens (3) tulajdonságú Az élek száma legfeljebb n-k≤n-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üggősé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 bőví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 bőví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 tetszőleges 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 megelőzője A gyökérből x-be vezető úton fekvő bármely csúcs. (x is a saját megelőzője.) Definíció: y valódi megelőzője x-nek ha megelőzője x-nek, de y ≠ x. Definíció: x az y rákövetkezője ha y x-nek

megelőzője. (x is a saját rákövetkezője) Definíció: x valódi rákövetkezője y-nak ha megelőzője y-nak, de y ≠ x. Definíció: x-ben gyökerező részfa Az x és a rákövetkezőiből álló részgráf (fa). Definíció: x szülője y ha az r p x úton (y,x) az utolsó él. (A gyökérnek nincs szülője T-ben) Definíció: x az y gyereke ha y az x szülője. Definíció: Testvérek azok a csúcsok, amelyeknek ugyanaz a csúcs a szülője. 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 gyerekről és jobb gyerekről.) 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 szintűek é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 - - 49 1+ k + k +K+ k 2 h −1 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 mezőt é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 2 7 4 9 3 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 időigé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 KUPACOT ÉPÍT ( A ) „Eljárás, mely tetszőleges 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 Θ (n)” 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 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 KUPACBAN MAX ( A ) „ RETURN( A[1] ) KUP 11 Θ (log n)” Θ (1)” KUPACBÓL KIVESZ MAX 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 ) Θ (log n)” Elsőbbségi sor Definíció: Elsőbbségi sor adatstruktúra Az elsőbbségi sor (priority queue) olyan S halmaz, amelynek minden eleméhez egy kulcs értéket (prioritás) rendelünk. Az

elsőbbségi sorban a maximális (minimális) kulcs megkeresése konstans idő. Adatstruktúrák, algoritmusok - - 53 Az elsőbbségi sor gyakori és hatékony műveletei: 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 elsőbbsé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 tűnő lehetőséget választjuk a részprobléma megoldására. Ez függhet az előző választásoktól, de nem függ a későbbiektől. 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 egyszerűsé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értől 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értelműen 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ó A B C D E F Kódszó Fix hossz Változó hossz f(c) 45 13 12 16 9 5 000 001 010 011 100 101 0 101 100 111 1101 1100 100 0 1 86 14 0 1 58 0 A:45 0 28 1 14 0 B:13 C:12 1 0 D:16 E: 9 F: 5 100 0 1 A:45 55 0 25 1 1 30 Adatstruktúrák, algoritmusok - - 55 1 0 C:12 0 B:13 1 D:16 14 0 F: 5 1 E: 9 Definíció: Kódfa költsége Legyen C a forrásábécé betűinek 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 ) c∈C 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é betűinek halmazát C és legyen a betűk száma n. A pszeudokód kiindul egy prioritási sorból, amelyben a betűk 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⏐ Q←C 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épviselője azonosít, mely eleme a halmaznak. Általában lényegtelen, hogy melyik ez az elem A halmazok elemei objektumok. Műveletek: HALMAZT KÉSZÍT(x): Egy új halmazt hoz létre, melynek ez az egy x eleme lesz, amely egyúttal képviselője 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ó tetszőleges eleme lehet HALMAZT KERES(x): visszaad egy mutatót, amely x halmazának a képviselőjé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 HALMAZT KÉSZÍT ” KUP 16 ÖSSZEKAPCSOL Ö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 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 ) )