A kurzus teljesítésének feltételei Évközi teljesítés • Két gyakorlaton megírt ZH, az elérhet˝o 100 pontból 50 pontot kell elérni. • Aki nem teljesíti a feltételt a vizsgaid˝oszak els˝o hetében a vizsgára engedésért írhat dolgozatot. • Az I404 kódú kurzus teljesítéséhez meg kell oldani egy otthoni feladatot, határid˝o április 30. Vizsga • Kiskérdések, amelyekb˝ol 63 pontot lehet szerezni, a minimumkövetelmény 35. • Egy tétel 37 pont, minimumkövetelmény nincs. Érdemjegy • 175-200 jeles • 150-174 jó • 125-149 közepes • 100-124 elégséges • 0-99 elégtelen Oktatási segédanyag • El˝oadás anyag www.inf.u-szeged.hu/∼cimreh/algo2.htm • Régebbi el˝oadások anyaga: /pub/alg/II • T. H. Cormen, C. E. Leiserson, R.L. Rivest: Algoritmusok, M˝uszaki Könyvkiadó, 2003. • T. H. Cormen, C. E. Leiserson, R.L. Rivest, C. Stein: Új algoritmusok, Scolar Informatika Könyvkiadó, 2003 A félév során el˝okerül˝o témakörök • hasítótáblák • piros fekete fák • AVL fák • B-fák • geometriai algoritmusok • amortizációs elemzés • binomiális kupac 1
• Fibonacci kupac • mintaillesztési algoritmusok • számelméleti algoritmusok, RSA • visszalépéses algoritmus • korlátozás és szétválasztás elve • közelít˝o algoritmusok Halmaz Értékhalmaz: E, Halmaz= H ⊆ E M˝uveletek: H : Halmaz, x : E, I : Iterator / • {Igaz} Letesit(H) {H = 0} • {H = H} Megszuntet(H) {Igaz} / • {H = H} Uresit(H) {H = 0} • {H = {a1 , . . . , an }} Elemszam(H) {Elemszam = n} • {H = H} Eleme(H,x) {Eleme = (x ∈ Pre(H))} • {H = H} Bovit(H,x) {H = Pre(H) ∪ {x}} • {H = H} Torol(H,x) {H = Pre(H) \ {x}} • {H = H} IterKezd(H, I) {} • {I = I} IterAd(I,x) {} • {I = I} IterVege(I) {} Megvalósítás: bitvektor, tömb, lánc, hasítótábla. Hasítótáblák Adott egy nagyméret˝u U univerzum amelyhez a kulcsuk által azonosított elemeket tartoznak. Ezek közül szeretnénk elemeket tárolni egy m méret˝u T tömbben úgy, hogy az elemek a kulcs alapján hatékonyan megtalálhatóak legyenek. A továbbiakban feltesszük, hogy az elemek maguk a kulcsok, de a valódi alkalmazásokban a kulcsok csak azonosításra szolgálnak, és az elemek további adatokat tartalmaznak. Választunk egy h : U → {0, . . . , m − 1} hasítófüggvényt, amely minden a halmazelemre megadja azt a tömbindexet, ahol az elemet tárolni szeretnénk T [h(a)] := a. Abban az esetben van probléma, ha két különböz˝o elemet ugyanott szeretnénk tárolni azaz, ha a 6= b és h(a) = h(b). Az ilyen esetekben ütközésr˝ol beszélünk. Az ütközések feloldására két elterjedt módszer a láncolás és a nyílt címzés. Ütközésfeloldás láncolással Ebben az esetben az ütközést úgy oldjuk fel, hogy ugyanarra a helyre rakjuk az elemeket. Tehát a T tömb elemei láncok, minden láncelem egy adatból és egy csat mutatóból áll, amely a következ˝o láncelemre mutat. 2
Keres(x) i:=h(x) p:=T[i] while (p!=Nil and x!=p.adat) p:=p.csat if (p!=Nil) then return p.adat else return Nil Bovit(x) i:=h(x) Letesit(E:Lancelem) E.adat:=x E.csat:=T[i] T[i]:=E Eszam:=Eszam+1 Id˝oigény O(1). Torol(x) i:=h(x) p:=T[i] pp:=p while (p!=Nil and x!=p.adat) pp:=p p:=p.csat if (p!=Nil) Then if (pp=p) Then T[i]=p.csat else pp.csat=p.csat Eszam:=Eszam-1 return true else return false A Keres (Töröl) muvelet ˝ id˝oigénye Legjobb eset O(1). Legrosszabb eset O(n), ahol n a táblában szerepl˝o elemek száma. Átlagos eset Az elemzés során feltesszük, hogy h gyorsan, konstans id˝oben számolható. A tábla telítettsége α = n/m A hasítófüggvényre feltesszük az egyenletességi feltételt. Ez azt jelenti, hogy ha ∀k ∈ U esetén pk annak a valószín˝usége, hogy k-t választjuk, akkor minden j = 0, . . . , m − 1 esetén:
∑
pk =
k:h(k)= j
1 . m
A keresés, így a törlés id˝oigénye is lineárisan függ az adott láncban megvizsgált elemek számától, így ezen elemek számának várható értékét kell elemezni. 3
Sikertelen keresés Tétel Az egyenletességi feltétel mellett a láncolásos ütközésfeloldás esetén a sikertelen keresés átlagos ideje Θ(1 + α). Biz: - Az egyenletességi feltétel miatt bármely k elemre, egyforma valószín˝uséggel adódik bármely j = h(k) tömbindex. - Így egy k elem sikertelen keresésének átlagos ideje megegyezik annak átlagos idejével, hogy a T[h(k)] láncot végigkeressük. - Másrészt ennek a láncnak az átlagos hossza α, így h(k) kiszámításával együtt az átlagos futási id˝o Θ(1 + α). Sikeres keresés Tétel Az egyenletességi feltétel mellett a láncolásos ütközésfeloldás esetén a sikeres keresés átlagos ideje Θ(1 + α). Biz: - Az x elem sikeres keresése esetén megvizsgált elemek várható száma eggyel nagyobb, mint azoknak az elemeknek a várható száma, amelyek megel˝ozik x-et az x-et tartalmazó láncban. - Az x-et megel˝oz˝o elemeket x beszúrása után szúrtuk be, mivel az új elemet mindig a lánc elejére szúrjuk be. - Legyen ki a táblázatba i-edikként beszúrt elem, az egyenletességi feltétel miatt Pr(h(ki ) = h(x)) = 1/m. - Tehát ha az x elemet i-ediknek szúrtuk be, akkor a megvizsgálandó elemek várható száma 1 + ∑nj=i+1 1/m. Következésképpen a megvizsgálandó elemek várható száma n n−1 1 n = Θ(1 + α). (1 + ∑ 1/m) = 1 + ∑ n i=1 2m j=i+1
Hasítófüggvények Osztásos módszer Tegyük fel, hogy a k kulcs egész számérték. Az osztás módszere: h(k) = k mod m Szorzásos módszer h(k) = bm(k · A mod 1)c ahol k · A mod 1 k · A törtrésze, A pedig egy 0 < A < 1 többnyire irracionális szám. Ütközésfeloldás nyílt címzéssel
Nyílt címzés esetén, egy helyre csak egy elemet teszünk, és az ütközést úgy oldjuk fel, hogy nem csak egy hasítófüggvényünk van, hanem minden elemhez tartozik egy próbasorozat. Az elemet a próbasorozatból az els˝o üres helyre tesszük. Tehát ebben az esetben h az U ×{0, . . . , m−1} halmazból képez a {0, . . . , m−1} halmazba, úgy, hogy (h(k, 0), . . . , h(k, m 1)) sorozat minden k esetén a {0, . . . , m − 1} elemek egy permutációja. A k elem helye a táblázatban az a j = h(k, i), amelyre i a minimális olyan érték, ahol T [h(k, i)] hely nem foglalt. Példa m=7, h(k, i) = (k + i) mod 7 beszúr 7,2,16,4,23,30 T = [7, −, 2, 16, 4, 23, 30] Ha törlünk egy elemet nem állíthatjuk üresre a helyét, a fenti példában törölve 4-et, utána keresve 23-at, megállnánk a 16 utáni üres helyen. Tehát törlés után a felszabaduló helyet a törölt címkével látjuk el. Muveletek ˝ Keres(x) i:=0 repeat j:=h(x,i) If T[j]=x 4
return j i:=i+1 until(i=m or T[j]=Nil) return -1 Bovit(x) i:=0 repeat j:=h(x,i) If (T[j]=Nil or T[j]=Torolt) Then T[j]:=x Eszam:=Eszam+1 return i:=i+1 until(i=m) print "megtelt a tabla" return -1 Torol(x) j:=Keres(x) If j>=0 Then T[j]:=Torolt Eszam:=Eszam-1 return True Else return False Futási id˝o elemzése Legjobb eset O(1) Legrosszabb eset: Θ(n) Átlagos eset 1 . tétel Nyílt címzés esetén a sikertelen keresés során a próbák számának várható értéke legfeljebb 1−α Biz: Legyen pi annak a valószín˝usége, hogy a keresés során pontosan i nem üres tömbelemet vizsgálunk meg. Ekkor a próbák számának várható értéke: 1 + ∑m i=0 i · pi . m Legyen qi annak valószín˝usége, hogy legalább i sikertelen próbát kell végezni. Ekkor ∑m i=0 i · pi = ∑i=1 qi . n−1 n−i+1 Másrészt qi = mn · m−1 · · · m−i+1 ≤ (n/m)i = αi . Tehát a próbák számára a következ˝o fels˝o korlátot kaptuk m
∞
i
1 + ∑ α ≤ 1 + ∑ αi = i=1
i=1
1 . 1−α
következmény Egy α telítettség˝u hasítótábla esetén a beszúrás várható költsége 1 + 1/(1 − α). Biz: Els˝oként egy sikertelen keresést hajtunk végre, majd a megtalált üres helyre berakjuk az elemet. Sikeres keresés 1 tétel Nyílt címzés esetén a sikeres keresés során a próbák számának várható értéke legfeljebb α1 ln 1−α . Biz Sikeres keresés ugyanazon próbasorozatot hajtja végre, mint amikor az elemet beraktuk a táblázatba. 1 Ha a k kulcsú elem i+1-edikként került a táblázatba, akkor a próbák száma az el˝oz˝o következmény alapján 1−i/m = m m−i . A hasítótáblában lev˝o n elemre kiszámolva a keresés várható próbaszámát a következ˝o korlátot kapjuk:
5
1 n−1 m m n−1 1 1 = = (Hm − Hm−n ), ∑ ∑ n i=0 m − i n i=0 m − i α ahol Hi = ∑ij=1 1/ j a j-edik harmonikus szám. Továbbá m
Hm − Hm−n =
1/k ≤
∑ k=m−n+1
Z n
(1/x)dx = ln m−n
m 1 = ln . m−n 1−α
Megjegyzés: Félig telített táblánál a fenti érték 1,387 és 90 százalékos telítettségnél is csak 2,559. Példák próbasorozatokra • Lineáris pótvizsgálat h(k, i) = (h0 (k) + i) mod m, ahol h0 U → {0, . . . , m − 1} egy hasítófüggvény. • Négyzetes pótvizsgálat h(k, i) = (h0 (k) + c1 · i + c2 · i2 ) mod m, ahol h0 U → {0, . . . , m − 1} egy hasítófüggvény. • Dupla tördelés h(k, i) = (h1 (k) + i · h2 (k)) mod m, ahol h1 , h2 U → {0, . . . , m − 1} hasítófüggvények. A h2 (k) értékeknek relatív prímnek kell lenni a táblázat m méretéhez.
6
