16 tavaszi félév Előadó: Dr. Ásványi Tibor Készítették: Koruhely Gábor (Koru) Szalay Richárd (Whisperity)

Algoritmusok és adatszerkezetek 2 2015/16 tavaszi félév Előadó: Dr. Ásványi Tibor Készítették: Koruhely Gábor (Koru) Szalay Richárd (Whisperity) Lektorálta: Dr. Ásványi Tibor Frissítve: 2016. 06. 18.

12 EA első blokk: 10:15 - 11:00 szünet: 11:00 – 11:15 második blokk: 11:15 - 12:00

Rendezés lineáris időben Edényrendezés (bucket sort) Tételezzük fel, hogy a kulcsok: [0,1) intervallumba esnek és egyenletesen oszlanak el. Példa számok: 0,32; 0,81; 0,89; 0,17; 0,53 (n = 5) a „k” kulcsot ⌊k ∗ n⌋ edénybe tesszük 0.edény: 0,17 1.edény: 0,32 2.edény: 0,53 3.edény: 4.edény: 0,81; 0,89 az eredmény: 0,17; 0,32; 0,53; 0,81; 0,89 Bucket_sort(&S; n) E[0..n-1] létrehozása üresen nincs vége S-nek x:= S következő eleme Θ(n) i:= ⌊x. kulcs ∗ n⌋ x-et beszúrjuk E[i]-be i = 0..n – 1 mT(n) ∈ Θ(n) Pl.: beszúró rendezések E[i] rendezése MT(n) ∈ Θ(n2 ) S := <> i = 0..n – 1 Θ(n) S végéhez hozzáfűzzük E[i] tartalmát azonban hiába mehet n2 -ig a műveletigény, a legtöbb esetben (a legtöbb inputra) marad az átlagos n-es műveletigény

1

Leszámláló rendezés (Counting sort) Most tegyük fel, hogy a kulcsok [0..k]-ba esnek, k ∈ Ο(n) (azaz k legfeljebb n-nel lineáris) φ: kulcsfüggvény φ: T ⟶ [0;k]

A[1..n]: T C[0..k]: 0..n

négyes számrendszer-beli számok

Példa: (k = 3), a számok: 312, 213, 021, 222, 323, 331 (a 0. lépés az init) C[] adottodik elemkor h 0. 1. 2. 3. 4. 5. 6. végén 0 0 1 1 1 0 0 ennyi ilyen kulcsú 2 0 1 2 2 elem van φ szerint 3 0 1 2 3 3 Counting_sort(A[1..n], k, φ, B[1..n])

végén utána

C[0..k] létrehozása i:= 0..k C[i] := 0 i = 1..n C[φ(A[i])] := C[φ(A[i])] + 1 i = 1..k C[i] := C[i] + C[i – 1] i = n..1 (-1) j := φ(A[i]) B[C[j]] := A[i] C[j] := C[j] - 1

Θ(k) Θ(n) Θ(k) Θ(n)

most már a bal szélső számjegy szerint is rendezett a tömb; a többi számjegy szerinti, most már másodlagos rendezettséget megtartotta.

2

Radix (számjegypozíciós) rendezés Radix(n elem, d számjegy, (szjegyek 0..k)) i := 1..d rendezzük az elemeket stabil rendezéssel hátulról i-edik számjegyük szerint Stabil rendezés: amely az elemeknek, egyenlő kulcsok esetén, az egymáshoz viszonyított sorrendjét nem változtatja meg (pl Counting_sort ilyen).

Tradix ∈ Θ( d ∗ Tstabil (n))

TRadix rendezés tömbökre ∈ Θ(d ∗ (n + k)) = Θ(n)

Tcounting (n, k) ∈ Θ(n + k)

ha d konstans és 𝑘 ∈ Ο(𝑛) volt Szétfűz sorrendtartó módon

Radix rendezés láncolt listákra, stabil edényrendezéssel, jobbról az i.-edik számjegy szerint (i:= 1,..,d)

Szétfűz sorrendtartó módon összefűzés után sorban:

összefűzés után sorban: T𝑟𝑎𝑑𝑖𝑥/𝑒𝑑é𝑛𝑦𝑟𝑒𝑛𝑑𝑒𝑧é𝑠 (n, k) ∈ Θ(d ∗ (n + k)) = Θ(n) ha d konstans és 𝑘 ∈ Ο(𝑛)

3

102 EA tárgy követelményei:  Legalább elégséges gyakorlati jegy kell a vizsgázáshoz,  vizsga  3szor lehet maximum vizsgázni egy vizsgaidőszakban,  vizsga ugyanolyan felépítésű, mint előző félévben az algo 1 tematika:  A tárgy honlapján megtalálható a tárgy tematikája: http://aszt.inf.elte.hu/~asvanyi/ad/ad2programok.pdf  8tétel  nem összehasonlító rendezésekről lesz szó,  hasítótáblák  gráf algók o legrövidebb út o minimális feszítőfa  veszteségmentes tömörítés  mintaillesztés

Hasítótáblák (Hash tables) Hasonlóan a kiegyensúlyozott fákhoz cél lenne a 3 alapművelet (keresés, beszúrás, törlés) optimálisan fusson le.  átlagos esetben Θ(1), legrosszabb esetben Θ(n). Direkt – címzés (Direct addressing): a lehetséges kulcsok az U = {0,...,m-1} (m nem túl nagy pozitív egész) univerzumba esnek műveletei: beszúr; keres; töröl Beszúr, (T[0..m-1], p)

fv.Keres (T[0..m-1], k)

Töröl (T[0..m-1], p)

T[p->kulcs] := p

return(T[k])

T[p->kulcs] := ∅

A tárigény miatt problémás a módszer, pl. ha a személyi szám szerint így tárolnánk a magyarokat, akkor a <10millió embernek 75 millió hely kellene, nagyon sok az üres hely. (n a tárolt adatok száma)

h: kulcsuniverzumból résekre (slotokra) képez le. (|U| >> m /*>> := sokkal nagyobb*/), (m ∈ Ο(n))

h: U[0..m-1] h hasító függvény

A baj az, hogy hiába tesszük a hash szerinti helyre a kulcsokat, előbb, utóbb lesz két külön kulcs, aminél h(k) = h(k’). Ekkor kulcsütközés következik be, ez célszerűen láncolt listával elkerülhető. Láncolt listás esetben viszont MTkeres(n) ∈ Θ(n); mTkeres (n) ∈ Θ(1); ATkeres (n) ∈ Θ(1 + α), a törlés műveletigénye ugyanaz, mint a keres egyes eseteiben. a minimális akkor lehet, ha a réshez tartozó lista első elemét keressük, vagy a lista üres. a listák átlagos hossza a hashtábla kitöltöttségi hányadosa, α =

n m

Ha nem ellenőrizzük az esetleges duplikált kulcsokat, a beszúrás igénye Θ(1). Ha nem engedjük meg a duplikált kulcsokat, ugyanaz, mint a keresés-nél. Egyszerű egyenletes hasítás: minden slotra ugyanakkora a h leképezési valószínűsége. Ilyen hash-ek megadhatók, de elég komoly matematika van mögötte. Osztómódszer: h(k) = k mod m, ahol m olyan prím amely messze van a 2-hatványoktól Ha a kulcsok a [0,1) intervallumon egyenletesen oszlanak el, akkor a h(k) = ⌊k ∗ m⌋ is jó hashfüggvény Szorzómódszer:

0 < A < 1 konstans h(k) = ⌊{k ∗ A} ∗ m⌋

({x} a törtrész fgv.)

(√5−1)

(különböző vizsgálatok szerint A = ≈ 0,618 …. jól szórja szét a kulcsokat. 2 Ezt a kiszámítást azonban nehéz elvégezni a lebegőpontos aritmetika miatt. 4

m = 2p a hashtábla mérete w = 32 k ∈ 0 … 2w − 1; legyen, 0 < p < w

bitjének kiválasztása

A kulcsütközések feloldására a láncolt lista helyett vannak más módszerek is. Nyílt címzés: h: U × [0 … m − 1] ⟶ [0 … m − 1] Most az egyszerűség kedvéért nem ellenőrizzük a duplikált kulcsokat. k kulcshoz m darab hash-érték fog tartozni:  próbasorozat A műveletek a próbasorozaton mennek végig: szabad

Pl: beszúrásnál ha h(k,0)-hoz van foglalt elem akkor h(k,1)-re szúr be, feltéve ha az már ⏞ üres vagy törölt fv.Beszúr(T[0..m-1],p) i := 0 i<m j := h(p.kulcs,i) T[j] ∈ {⊘, ⨂} T[j] := p i := i+1 return (j) return ∅ ahol:

fv.Töröl(T[0..m-1],k) j := Keres(T,k) j≠∅ T[j] := ⨂ return(j) (⨂ a törölt rés)

⊘: üres rés ⨂: törölt rés ∅ ∈ ℤ\[0. . 𝑚 − 1]

A próbasorozatnak a <0,1,… ,m-1> permutáltjának kell lennie A próbasorozatok egyik előállítási módja pl. a lineáris próbálás: h(k,i) = (h’(k) + i) mod m

fv.Keres(T[0..m-1],k) i :=0 l:= igaz l j:= h(k,i) T[j].kulcs = k return(j) i := i+1 l:= ( i < m ∧ T[j] ≠ ⊘) return ∅ Feltesszük, hogy ⊘.kulcs, ⨂.kulcs ∉ U

k∈U

5

112 EA Hasítótáblák Hasítótáblák tulajdonságai:  egy szótárt valósítanak meg  kulcs alapján lehet benne keresni  törölni is lehet benne  átlagos műveleti igény konstans a tábla (ism.): egy tömbnek lehet tekinteni; 0..m-1-ig indexelve van speciálisan a nyílt címzésnél az adatokat slot-okban tároljuk; megkülönböztetjük a törölt (⨂) illetve az üres (⊘) slotokat sikertelen a keresés, ha üres slothoz ér, vagy ha túl sokat próbálkozik (m db próba után megáll) valójában nem egy hash függvény van, hanem m db hash függvény van

Tipikusan foglalt rések hosszú összefüggő szakaszain alakulnak ki T[0..m-1]-ben elsődleges csomósodások.

feltehetjük, hogy van m db hash függvény h: ( . , i) : U  0..m-1 ( i ∈ 0..m-1) perm <0, … , m-1> lineáris próba: h(k,i) = (h’(k) + i) mod m négyzetes próba: h(k,i) = (h’(k) + c1 ∗ 𝑖 + c2 ∗ 𝑖 2 ) mod m /*ahol h’(k) = h(k,0)*/ 1 ahol jól bevált ajánlás, hogy m 2-hatvány, c1 , c2 pedig (m = 2𝑝 , 0 < 𝑝 ∈ ℤ) i∗(i+1)

j∗(j+1)

2

i ≠j: (h(k,i) – h(k,j)) mod m = [ – ] (mod m ) ≠ 0 ⟺ 2 2 2m ∤ i ∗ (i + 1) – j ∗ (j + 1) = i2 + i – j2 – j = i2 – j2 + (i – j) = (i – j)(i + j + 1) 2p+1 ∤ (i − j)(i + j + 1) ezek párossága különbözik a) 2 | (i – j) ⇒ 2 ∤ ( i + j + 1) de 2m ∤ (i – j) hiszen i - j < 2m-1 b) 2 | ( i + j + 1) ⇒ 2 ∤ (i – j) de 2m ∤ (i + j + 1)-nek, mivel (i + j + 1) < 2m – 1 azaz 2-hatvány tábla esetén a négyzetes próba szépen lefedi az egész táblát (i + 1) ∗ (i + 2) i ∗ (i + 1) (h(k, i + 1) − h(k, i)) mod m = [ − ] mod m = (i + 1) mod m 2 2 azaz: h(k, i + 1) = (h(k, i ) + (i + 1)) mod m és h(k,0) = h’(k) feltesszük: törölt(⨂) slot kulcsa és az üres(⊘) slot kulcsa nem eleme az U-nak fv.beszúr(T[0..m-1], k) j:= h’(k) i := 0 i<m T[j] ∈ {⊘,⨂} T[j] := k return(j) i := i + 1 j := ( j + i) mod m return -1 nyílt címzés, négyzetes próba és ⊘.kulcs és ⨂.kulcs ∉ kulcsuniverzum az általános négyzetes próbánál (ahol c1 és c2 tetszőleges) ha h(k1 , 0) = h(k 2 , 0), akkor ∀i − re h(k1 , i) = h(k 2 , i)

fv.keres(T[0..m-1], k) j:= h’(k); i := 0; b:= true b T[j].kulcs = k return j i := i + 1 b := T[j] ≠⊘ és i < m j:= (j + i) mod m return -1 Megjegyzés: ha T[j] NIL, akkor T[j].kulcs olyan extremális érték, amely bármilyen összehasonlításra hamisat ad

Másodlagos csomósodás Tehát csak m különböző próbasorozat van a lehetséges m! közül, így a (másodlagos) csomósodás fellép, de ez jobb, mint a lineáris próba elsődleges csomósodása, ahol a sorozatok menet közben gabalyodhatnak össze… 6

Kettős hasítás h(k, i) = [ h1 (k) + i ∗ h2 (k)] mod m a próbasorozatok száma itt már Θ(n2 ) szemben Θ(n)-nel. ez – tapasztalat alapján – már majdnem ideális tud lenni ha lnko(h2 (k), m) = 1 ⇒ perm <0, … , m-1>-nak hiszen i ≠ j ⇒ (h(k,i) – h(k,j) mod m ≠ 0 0 ≠ (h(k,i) – h(k,j)) mod m ⟺ (i – j) * h2 (k) mod m ≠ 0 ⟺ m ∤ (i – j) * h2 (k) mivel |i – j| < m, h2 (k) pedig relatív prím (ez feltétel volt, hogy lehet biztosítani, hogy a h2 (k) és az m relatív prímek legyenek). a) m legyen prím, akkor h1 (k) ∶= k mod m h2 (k)=1 + (k mod m’) ahol: m’= m- 1 v m’= m – 2 például, azaz m-nél picit kisebb p (k) b) m = 2 és 2 ∤ h2 Hashelés Ideális esete: Egyenletes hasítás ideális lenne, ha <0..m-1> összes permutáció azonos valószínűséggel fordulna elő 0 < α telítettségi együttható < 1 esetén 1  sikertelen keresés várható hossza ≤ 

beszúrás várható hossza ≤

1 1−α

1−α

Feltéve, hogy nincs a hasító táblában törölt rés (slot). 1 α

1 ∗ ln ( ) 1−α

 sikeres keresés várható hossza ≤ Ha sokat használjuk a hashtáblát, akkor feltöredezik, elfogynak az üres slotok, ekkor frissítést kell végrehajtani: beszúrásokkal új táblát létrehozni a mostani elemekből.

Gráf algoritmusok Szomszédosági mátrix (C) G= (V,E) E ⊆ V × V V = 1..n C[1..n,1..n] 1 ⟺ (i,j) ∈ E C[i,j] = 0 ⟺ (i,j) ∉ E ha számít az él költsége w(i,j) ⟺ (i,j) ∈ E C[i,j] = 0⟺i=j +∞ különben

w: E  ℝ (i ≠ j)

Azonban a mátrix tárolás miatt a műveletigény Θ(n2 ), ami az irányítatlan esetben a szimmetria kihasználásával javítható (majdnem felezhető), de Θ(n2 ) marad (csak alsó háromszög mátrixot tároljuk).

Szomszédsági éllistás reprezentáció: Memóriaigény n csúcs és e él esetén: Θ(n + e)

7

1002 EA Elemi gráf algoritmusok Szélességi keresés Meghatározzuk a start csúcsból a további csúcsokba a legkevesebb élet tartalmazó utat. d – hány élen keresztül jutunk a csúcsba π – melyik csúcsból jutunk a csúcsba Q = 1. lépés: Q= /*b szomszédai*/ 2. lépés: Q= /*c rákövetkezője e, de ott már voltunk*/ 3. lépés: Q= <e, a> /*„a” d szomszédjai*/ 4. lépés: Q= /*e szomszédja csak a d, de ott már voltunk*/ 5. lépés: Q=<> /*a sor kiürült, a bejárás véget ért

f-ből indítva, másik szemléltetési móddal:

d f c e d a b

a ∞

b ∞

c ∞ 1

d ∞

e ∞ 1

f 0

2 3 3

4 4

1

2

1

0

Q π <e> <>

a ∅

b ∅

c ∅ f

d ∅

e ∅ f

f ∅

f

∅

e d d

a a

f

e

Az irányított gráfon a „szomszédsági” kapcsolat nem szimmetrikus. A fenti gráfban pl.: a szomszédja b, de b-nek nem szomszédja a. Jelölés: Ha G = (V, E), E ⊆ V × V gráf, G.V a G csúcsainak halmaza G.E a G éleinek halmaza u ∈ G.V esetén G.Adj[u] ≝ { 𝑣 ∈ 𝐺. 𝑉 | (𝑢, 𝑣) ∈ 𝐺. 𝐸 } Feltesszük, hogy (𝑢, 𝑢) ∉ 𝐺. 𝐸, azaz nincs hurokél. Feltesszük, hogy nincsenek párhuzamos élek sem.

G egyszerű gráf

8

BFS(G,s) ∀ u ∈G.V u.d := ∞ u. π := ∅ u.szín := fehér s.d := 0 s.szín := szürke Q := <s> Q ≠<> u:= Q.sorból() ∀ v ∈ G.Adj[u] v.szín = fehér v.d := u.d + 1 v.π := u v.szín := szürke Q.sorba(v) u.szín := fekete BFS műveletigénye: T(n, e) ∈ Ο(n + e), ahol n = |V| és e=|E| mindent legfeljebb egyszer dolgozunk fel, de előfordulhat, hogy néhány csúcs kimarad (a start csúcsból nem elérhető csúcsok és élek maradnak ki.). DFS (Mélységi keresés) DFS(G) ∀ u ∈ G.V u. π := ∅ u.szín := fehér ido := 0 ∀ u ∈ G.V u.szín = fehér DFS_VISIT(u,G, ido) u.d = elérési idő (discovery time) u.f = befejezési idő (finishing time)

DFS_VISIT(&u,G, &ido)

ido := ido + 1 u.d := ido u.szín := szürke ∀ v ∈ G.Adj[u] v.szín = fehér v.π := u v.szín = szürke DFS_VISIT(v,G, ido) viszael(u,v) u.szín := fekete ido := ido + 1 u.f := ido

Mélységi bejárás példa:

Ha az él már fekete csúcsba mutat, keresztélet vagy előreélet találtunk. 9

Élek osztályozása Def: a ⟶ b faél: ez kerül a mélységi fába, e mentén járjuk be a gráfot f ⟵ g visszaél (f a g őse egy mélységi fában.) b ⟶ f előreél, az előreél két leszármazottat köt össze, ahol b-ből kettő vagy több faélből álló út vezet f-be. g ⟶ h keresztél, olyan két csúcs, amelyek más ágon vannak vagy másik mélységi fába mutat át

⊛

Példa: Azaz a keresés eredménye egy mélységi erdő

DFS műveletigénye: T(n,e) = Θ(n + e)

minden csúcsot néhányszor (3) és minden élet egyszer.

Tétel: Ha a ⊛ mélységi bejárás során egy (u,v) élet találunk: (u,v) faél ⟺ v.szín = fehér (u,v) visszaél ⟺ v.szín = szürke (u,v) előreél ⟺ v.szín = fekete ∧ u.d < v.d (u,v) keresztél ⟺ v.szín = fekete ∧ u.d > v.d

10

1012 EA Irányított gráfok csúcsainak topologikus rendezése Topologikus rendezés: A csúcsok olyan sorrendje, amelyben minden él egy-egy később jövő csúcsba (szemléletesen: balról jobbra) mutat.

Tétel: Pontosan akkor ∃ topologikus rendezés, ha nincs irányított kör a gráfban. Bizonyítás: a) Ha van irányított kör a gráfban, jelölje 〈𝑢1 , 𝑢2 , … , 𝑢𝑘 , 𝑢1 〉! Ekkor egy tetszőleges topologikus rendezésben 𝑢1 után jön valahol 𝑢2 , az után valahol 𝑢3 , és így tovább, végül is 𝑢1 után jön 𝑢𝑘 , és 𝑢𝑘 után 𝑢1 , ami ↯, tehát ekkor nincs topologikus rendezés (a gráf csúcsain). b) Ha nincs irányított kör a gráfban, akkor nyilván van olyan csúcs, aminek nincs megelőzője. Ha veszünk egy megelőzővel nem rendelkező csúcsot és töröljük a gráfból, akkor a maradék gráfban nem keletkezik irányított kör, lesz megint legalább egy olyan, amelyiknek nincs megelőzője. Sorban a törölt csúcsok adják a topologikus rendezést. G=(V,Adj[V])

Adj[u] = {v ∈ V |(u, v) ∈ E} ⊆ V

fv.TR(G, TR[1..n]) BEFOKOK(G,BE[1..n]) i := 0 H:= {v ∈ V | BE[v] = 0} H ≠ {} u ’from’ H i := i+1 TR[i] := u ∀ v ∈ G.Adj[u] BE[v] := BE[v] - 1 BE[v] = 0 H:=H ∪{v} return i TTR (n) ∈ Ο(n + e). Mélységi bejárás:

Θ(n + e) Θ(n) ’from’  kivesz H-ból egy elemet a kör csúcsai nem kerülnek H-ba, így az eredménybe (TR[1..n]) sem. Ο(n+e)

ha i=n, minden csúcsot feldolgoztunk

A sorrend: <óra, ing, nyakkendő, alsónadrág, zokni, nadrág, öv, kabát, cipő> Tetszőleges u csúcs, akkor kerül a TR-be, a hátulról első szabad helyre, amikor befejeztük. Ha a mélységi bejárás visszaélt talál ⟺ irányított kör van a gráfban ⟺ nincs topologikus rendezés. 11

Erősen összefüggő komponensek /*Minden csúcsból minden csúcsba vezet irányított út a komponensen belül*/ A gráf erősen összefüggő komponensei: 

a,b,e



f,g



c,d



h

Előállítás: mélységi bejárással mintha topologikus rendezés lenne, de nem kezeljük a visszaéleket. A sorozat: a csúcsok befejezés szerinti sorrendben. Transzponáljuk a gráfot, ezen mélységi bejárás a sorrend szerint, az így talált mélységi fák a komponensek.

Minimális feszítőfák Kössünk össze minden várost, hogy minden pontba eljusson az áram, de a lehető legolcsóbban (és még sok más megfogalmazású feladat) A lényeg minimális feszítőfa keresése.

G=(V,E) E⊆VxV (u,v) ∈ E ⟺ (v,u) ∈ E /*u ≠ v, a hurokéleknek nincs értelme*/ w: E ℝ élsúlyok w(u,v) = w(v,u) GEN_MST(G) A:={} s :=0 s < n−1 (u,v) legyen olyan él a G.E \ A-ból, azaz A ∪ {(u,v)} minimális feszítőfa része marad ami A-hoz biztonságosan hozzávehető P invariáns = ∃ T = (V, TE ) MST, hogy 𝐴 ⊆ 𝑇𝐸 A:= A ∪ {(u,v)} s := s + 1 Def1: G=(V,E), ∅ ⊊ S ⊊ V esetben (S, V\S) vágás a G gráfban Def2: A ⊆ E és (S, V\S) vágás esetén a vágás elkerüli az A-t ⟺ A egyetlen éle sem keresztezi a vágást Def3: (u,v) él keresztezi az (S, V\S) vágást ⟺ az u ∈ S és v ∈ V\S (vagy fordítva u ∈ V\S és v ∈ S )

12

Tétel: G = (V,E) irányítatlan w: E  ℝ-rel élsúlyozott gráf (S, V\S) vágás a gráfban elkerüli A− t, ahol ∃𝑇 = (𝑉, 𝑇𝐸 ) 𝑀𝑆𝑇, ℎ𝑜𝑔𝑦 𝐴 ⊆ TE (u, v) ∈ E egy könnyű él (legkisebb költségű) a vágásban Ekkor (u,v) biztonságos A-ra nézve Bizonyítás: a) (u, v) ∈ TE  b) (u,v) ∉ TE⇒ (p, q) ∈ TE , ami keresztezi az (S, V\S) vágást, ui: T feszítőfa, tehát T-ben el lehet jutni u-ból v-be. ⇒ w(p,q) ≥ w(u,v) (p,q) törlésével az MST szétesik, de ha ehhez (u,v)-t hozzávesszük, akkor újra feszítőfa lesz. T’ = T \ {(p,q)} ⋃ {(u,v)} w(T’) = w(T) – w(p,q) + w(u,v) ≤ w(T) viszont mivel T MST volt, w(T’) ≥ w(T) ⟹ azaz w(T’) = w(T) és T’ is MST kell, hogy legyen…

13

1102 EA Minimális feszítőfa ismétlése példán keresztül G=(V,E) w: E  ℝ egy vágás: S V\S {a,b,d} {c,e,f} egy vágást keresztező él az E ∩ (S × (V \ S)) egy eleme, ennek a halmaznak a legkisebb súlyú tagja a könnyű él A ∅ d-e d-e

c | f

a-b d–e

S {a, b, d} {a, b, d, e, f} {a}

V\S {c, e, f} {c}

{a, b, d, e}

{c, f}

{b, c, d, e, f}

Az új vágás a két élt kerülje el, ne menjen keresztül rajtuk, majd mindig választjuk a könnyű élt. Az eddig kiszámolt feszítőfa-részlet (A) élhalmaza diszjunk kell, hogy legyen a vágás éleivel.

c | f

a-b

{a, b}

{c, d, e, f}

d–e-f | c

Kruskal algoritmus  

0. lépés

a b c d e f

Elsőként súly szerint sorba rendezzük a csúcsokat! Minden csúcs egy egyelemű fát képezzen! Majd minden lépésben hozzávesszük a minimális élt, ha külön komponenseket kötnek össze (ha nem, kihagyjuk) 1 d1e

a b c d1 e f

2 a2 b

2

a b c d1 e f

3 e2f

2

a b c d1 e2 f

4 b |3 e a2b c |3 d1 e2 f

5 a |4 d a2 b c |4 |3

d

1

e

2

f

kihagyjuk

6

7 c

8 b6c

9

végeredmény:

|5

f a2b c |3 |5 d1 e 2f

a2b6c |3 |5 d1 e2 f kihagyjuk

14

0

1 (d-e)

a b c d e f

a b c d f ↑ e

A komponensek nyilvántartásához menetközben egy másik fát is kezelünk: 2 (a-b) 3 (f-d) 4 (b-e) 5 6 7 (c-f) a d c ↑ ↑ b e f

a d c ↑ ↑ ↖ b e f

ad c ↑ ↑ ↖ b e f

MST_Kruskal(G,w) G.E mon. növ. rend. w szerint ∀ u ∈ G.V Make_Set(u) A := {} ∀ (u,v) ∈ G.E (w szerint mon. növ.) x := HOL_VAN(u) y := HOL_VAN(v) x≠y A := A ∪ {(u,v)} Unió(x,y) return(A)

(kihagyjuk)

(kihagyjuk)

8

9

(kihagyjuk)

(kihagyjuk)

n-1 ≤ e = |G.E| < n2 Ο(e*log e) = Ο(e*log n) Θ(n) Θ(1)

Ο(e*log n)

Ο(log n) e-szer Ο(n) (n-1-szer néhány konstans)

A HOL_VAN() megállapítja, a csúcs melyik ilyen köztes fában van, ennek megfelelően az unió később a fákat köti össze. (Mindegyik fát a gyökércsúcsa azonosítja.) Az új élt úgy vesszük a köztes fához, hogy a fák magassága ne változzon, de a komponenshez tartozás jelezve maradjon. (Az alacsonyabb fa gyökerét a nagyobb fa gyökere alá kötjük be.) A fák magassága legfeljebb log 2 n (n = |G. V|) Közös magasság esetén az uniózott fa magassága h+1 lesz (h közös magasság volt)

Prim algoritmus   

Kiindulva egy csúcsból és a (csúcs, maradék) vágás közé választja a minimális élt Ezt hozzáveszi az eredményhez és az (eddigi eredmény, maradék) vágásban keresi a könnyű élt addig folytatva az előző két lépést, míg Minimális feszítőfát nem kapunk.

meg kell adni, hogy hol kezdi (s), de mindegy, hogy hol kezdi MST_PRIM(G, s, w) ∀ u ∈ G.V Θ(n) u.kulcs := ∞ u.π := ∅ Lehet, hogy az u hozzávétele után v s.kulcs := 0 Θ(1) közelebb kerül a részleges feszítőfához. Q : PrSor(G.V, kulcs alapján) Θ(n) Q ≠ <> Θ(n) u := Q.MIN_KIVESZ() n*Ο(lg(n) ) Θ(n+e) ∀ v ∈ G.Adj[u] v∈Q∧ Θ(e) v.kulcs > w(u,v) v.kulcs := w(u, v) Ο(e) + Ο((e)*lg(n)) a kupac v. π := u adminisztrációja, a kulcs váltás miatt Az egész algoritmus műveletigénye: Ο((n+e)*lg(n)), de a gráf összefüggő (e ≥ n-1), azaz Ο(e*lg(n))

15

kezdő csúcs: a lépés

a 0

b ∞ 2

kulcs c d ∞ ∞ 4 6 1

π e ∞

f ∞

a ∅

b ∅ a

c ∅

d e f start ∅ ∅ ∅ a a b 3 b b e 2 e e d f 5 f c nincs már több lehetséges szomszédja vége: 0 2 5 1 3 2 f e b e ∅ a -: a szomszéd már korábban belekerült a fába 1: új, jobb távolság prim optimalizációja: Fibonacci kupacokkal le lehet csökkenteni a műveleti igényt: Ο(e+n*lg(n))

Az MST, amit kaptunk, irányított faként reprezentált IRÁNYÍTATLAN FA

16

1112 EA Legrövidebb út probléma Adott egy tetszőleges hálózat, amiben az utaknak költségeik vannak, ezt a hálózatot egyszerű gráffal ábrázoljuk. G=(V,E) w: E  ℝ

Negatív költség is lehetséges. Adott pontból az összes többi csúcsba meg szeretnénk határozni a legrövidebb utat a költségekkel, nem biztos, hogy a legkevesebb élből álló út a legrövidebb. Mikor értelmes a kérdés:  ha létezik a start csúcsból elérhető negatív kör, nincs legrövidebb út egyetlen a körből elérhető csúcsba sem. Ha a startcsúcsból csak nem negatív kör érhető el, az az útból elhagyható. Optimális útnak tetszőleges részútja is optimális út. Általános algoritmus: (Robert Endre Tarjan: Data Structures and Network Algorithms könyvben: "Breadth-first Scanning" algoritmus) ,,Queue-based BELLMAN-FORD” (Sor alapú Bellman-Ford algo) d init a b c d b d

a 0

b ∞ 3

c ∞ 1

d ∞ 1

0 -2 0

0

1

Q <>

-2

π

a ∅

c ∅ a

d ∅ b

c b

menet ∅ 0. 1. 2. 3.

∅

SZÉLESSÉGI_BELLMAN_FORD(G,s) GKI(G,s) Q := <s> Q ≠ <> u := Q.sorból() ∀v: (u,v) ∈ G.E u.d + w(u,v) < v.d v.d := u.d + w(u,v) v. π := u v∉Q Q.sorba(v)

b ∅ a

c

a

b GKI(G,s) ∀u ∈ G.V u.d := ∞ u. π := ∅ s.d := 0

a sorban levés ellenőrizhető pl. egy adattaggal, mindig bejárni a sort nem lenne hatékony.

Tulajdonság: ∀u ∈ G.V, hogy ha az u csúcsba vezet k élből álló s  u optimális út ⇒ a k. menet elején már u.d = w(s  u) és (s, …, u.π.π, u.π, u) egy optimális út Lemma: s-ből nem érhető el negatív kör (amely összköltsége negatív) ⇒ tetszőleges u elérhető csúcsra létezik s  u optimális út, ami legfeljebb n-1 élből áll. T( Lemma és Tulajdonság következménye): Ha s-ből nem érhető el negatív kör ⇒ tetszőleges u elérhető (s-ből) csúcsra létezik s  u optimális út, és egy optimális út az n-1. menet elején már rendelkezésünkre áll (ki van számolva). ⇒ az n-1. menet végére kiürül a sor, az algoritmus Ο(n*e) időben megáll. 17

Következmény: Ha az (n-1). menet végén van a Q sorban elem ⟺ van s-ből elérhető negatív kör. Megjegyzés: vegyünk egy ilyen w elemet. Ebből a π pointereken visszafele haladva megtalálható egy ismétlődő v elem, amire ∃ k ∈ 1..n πk (v) = v, és (v, πk−1 (v), πk−2 (v), … , π(v), v) egy negatív kör.

Legrövidebb utak egy forrásból, körmentes irányított gráfokon feltétel: nincs irányított kör, ekkor lehet topologikus rendezéssel optimális utakat keresni.

topologikus rendezés:

d a b c d e f ∞ 0 ∞ ∞ ∞ ∞ --------------------------------1 -1 2 0 1

init a b e f d c vége: ∞ 0 1 „a” nem volt elérhető

0

-1

1

π a b c d e f ∅ ∅ ∅ ∅ ∅ ∅ --------------------------------b b b e e

∅

∅

b

e

b

nem történik semmi, el kell jutni a start csúcsba

e

Műveletigény: Θ(n+e) műveletigény (topologikus rendezés) ∀ csúcs kiterjesztése (Θ(n+e)) Teljes műveletigénye: Θ(n+e)

18

10002 EA Legyen G=(V,E) akár irányított, akár irányítatlan, w: E  ℝ0 nem negatív valós számok

DIJKSTRA algoritmus d init:

vége:

a 0

0

b ∞ 2

c ∞ 4 3 2

d ∞ 1

e ∞

2

2

1

∞

kiterjesztés π

a ∅

b ∅ a

c d e ∅ ∅ ∅ a a d b

∅

a

b

a d b c e

a

∅

Dijkstra(G,w,s) ∀u ∈ G.V u.d := ∞ u. π := ∅ s.d := 0 Q := G.V Q ≠ <> u:= Q.MINKIVESZd () ∀v: (u,v) ∈ G.E v.d > u.d + w(u,v) v.d := u.d + w(u,v) v. π := u Q.HELYREÁLLÍTd(v)

Θ(n) T(n) ∈ Θ(𝑛2 ) ha a Q rendezetlen

Θ(1) Θ(n) d szerint

n-szer Θ(n) e < 𝑛2 e*Ο(1)

alsó index d azt jelenti, hogy a minkivesz a d értékei szerinti szomszédsági éllista + bináris kupac esetén T(n,e) ∈ Ο((n+e)*log n)

Q.MINKIVESZd (): n* Ο(lg n) Q. HELYREÁLLÍT𝑑 (v): Ο(e * lg n)

Áll: Amikor a csúcsot kivesszük a sorból, oda már optimális út vezet. Bizonyítás: start csúcsra , a költség optimális. Tegyük fel, hogy nem igaz az Állítás! Legyen u az első ilyen csúcs, t pedig az su optimális út első csúcsa amely ∈ Q sornak. u-ra nem igaz, u-t válasszuk kiterjesztésre, ekkor nincs talált optimális út (de attól még létezik) opt

u.d > w(s→ u), mivel egyébként megtaláltuk volna az optimális utat. opt

t.d = w(s→ t) ≤ w(su) < u.d az s t optimális út, mivel optimális út részútja. = : hiszen „t”-t megelőző csúcs kiterjesztésekor beállítottuk, de mivel t.d < u.d, ezért a következő 1épés „t”-t választja kiterjesztésre ↯ Minden csúcsból minden csúcsba legrövidebb út minden csúcsra futtatott Dijkstrával:  ritka gráfra Ο(n*(n+e)*log n) = Ο(n2 *log n)  sűrű gráfra Ο(n3 *log n), nem jó választás… o ehelyett a vektorpáros Dijkstra stabil Ο(n3 )-öt (n * Ο(n2 )) fut. 19

Floyd–Warshall - algoritmus Engedjük meg a negatív élsúlyt, de ne lehessen negatív kör. G=(V, E) G: V = 1..n csúcsmátrixos ábrázolás Dij := i j optimális út költsége (végtelen, ha nincs optimális út) πij := i j optimális úton j szülője (k)

Dij

= az i j úton az [1..k] indexű csúcsok lehetnek csak közbenső csúcsok. k ∨|

(k) πij (0) Dij

min{w(i→ j)} = egy ilyen [1..k] közbensős úton a j csúcsok szülője (közvetlen út szülője)

0, ha i = j w(i,j), ha (i,j) ∈ G.E ∧ i ≠ j ∞, ha i ≠ j ∧ (i,j) ∉ G.E

=

∅ i ∅

(0)

πij =

, ha i = j , ha i ≠ j és (i,j) ∈ G.E , különben

(n)

Dij = Dij (n)

πij = πij

(k−1)

ha Dij

(k−1)

> Dik

(k−1)

+ Dkj

(k)

, akkor Dij (k)

különben: Dij

(k−1)

= Dik

(k−1)

+ Dkj

(k−1)

= Dij

(k)

(k−1)

hasonlóan πij is ha nem tudtuk az utat javítani = πij (k−1)

ha tudtuk = πkj (k)

(k−1)

(k)

(k−1)

Dik = Dik Dkj = Dkj

Az algoritmus lépésenként előállítja mátrixpárok sorozatát. (k)

D(k) = (Dij )

𝑛

i,j=1

k = 0,.., n-ig, n+1 db mátrix.

D és π k-adik sora és oszlopa a (k-1) és k. lépésben egyenlő: D i.-edik sora: i. csúcsból optimális utak hossza.

20

Floyd-Warshall(G,D[1..n, 1..n], w, π[1..n, 1..n]) ∀(i,j) ∈ 1..n × 1..n D[i,j] := 0 π [i,j] := ∅

i=j (i,j) ∈ G.E D[i,j] := w(i,j) D[i,j] := ∞ π [i,j] := i π [i,j] := ∅

k = 1.. n ∀(i,j) ∈ 1..n × 1..n D[i,j] > D[i,k] + D[k,j] D[i,j] := D[i,k] + D[k,j] π [i,j] := π [k,j]

Θ(n2 )

Θ(n3 )

TFW ∈ Θ(n3 ) Sűrű gráfokon az aszimptotikus műveletigény, mint a Dijkstra, de ritka gráfokon a Dijkstra aszimptotikusan jobb (feltéve hogy ∄ negatív él, és így a Dijkstra is alkalmazható). Megjegyzés: A negatív körök a D főátlójában negatív számként jelennek meg. Tranzitív lezárt algoritmus (Warshall algoritmus) Tij: van-e út i-ből j-be (megállapítja, hogy van-e a két csúcs között út (csak az számít, hogy van-e, hogy milyen költségű az nem számít)) (k) Tij

k ∨|

j megint csak legfeljebb az 1..k csúcsokat érintő út. , ha i = j ∨ (i,j) ∈ G.E (0) Tij TRANZ_LEZ(G, T[1..n, 1..n]) , különben ∀(i,j) ∈ 1..n × 1..n (k) (k−1) (k−1) (k−1) Tij = Tij ∨ (Tik ∧ Tkj ) T[i,j] := (i = j ∨ (i,j) ∈ G.E) k = 1 .. n (n) Tij = Tij ∀(i,j) ∈ 1..n × 1..n (k) (k−1) T[i,j] := T[i,j] ∨ (𝑇[𝑖, 𝑘] ∧ 𝑇[𝑘, 𝑗]) Tik = Tik (k)

⟺ i → ↑ = ↓

Θ(𝑛2 ) Θ(𝑛3 ) Θ(𝑛3 )

(k−1)

Tkj = Tkj

Sűrű gráfokra sokkal jobb, mint n db szélességi bejárás. Ritka gráfokra (e ∈ Ο(n)) viszont n darab szélességi bejárás műveletigénye:Ο[n ∗ (n + e)] = Ο(𝑛2 ) aszimptotikusan kisebb, mint a Θ(𝑛3 ) Warshall algo-nál. 𝑒 ∈ Ο(𝑛) Sűrű gráfokra 𝑇𝑛∗𝐵𝐹𝑆 (𝑛) ∈ Ο(𝑛 ∗ (𝑛 + 𝑒)) = Ο(𝑛3 ). Ez hasonló a Warshall-hoz, de annak kisebb a konstans szorzója.

𝑒 ∈ Θ(𝑛2 )

21

10012 EA Mintaillesztési feladat 1 2 3 4 5 6 7 8 9 10 11

T[1..11] = A B A B B A B A B A B B AB A B AB A B AB A B AB A B AB A B AB A B AB A B AB A

P[1..4] = BABA piros betű: annál a betűnél található az első nem egyező karakter zöld betű: egyező karakter zöld szó: a keresett minta megtalálható a szóban s = 4 eltolás két találat s = 6 eltolás

Fa: T[1..n]: Σ; P[1..m]: Σ 0< m ≤ n S := { s ∈ 0..n-m | T[s+1..s+m] = P[1..m]} programozása Egyszerű_mintaillesztő_alg(T[1..n], P[1..m], S)

T[s+1..s+m] = P[1..m] j := 1 j ≤ m és T[s+j] = P[j] j := j+1 return (j > m)

S := {} s := 0..n-m T[s+1..s+m] = P[1..m] S := S ∪ {s}

Ο(m) MT(m) ∈ Θ(m) mT(m) ∈ Θ(1)

Az egész eljárás műveletigénye: MT(n,m) ∈ Θ((n-m+1)*m) = Θ((n-m)*m) mT(n,m) ∈ Θ(n-m+1) = Θ(n-m)

n > m esetén

Megjegyzés: Gyakran feltehető: n ≫ m Ekkor: MT(n,m) ∈ Θ(n*m) mT(n) ∈ Θ(n) Elég jónak tűnhet, de nagy inputra hamar elszáll, kell ennél jobb algoritmus.

22

QUICK SEARCH Alapfilozófiája példán illusztrálva: Pl: Σ = {A, B, C, D} T = A D A B A D C A D A B C A B A D A C A D AD A C A DA C AD A C AD A C A DA C A DA C AD A C AD A C AD A C AD A ABCD shift: 1 5 4 2

P = CADA piros betű: a keresett minta nem található zöld szó: a keresett minta megtalálható a szóban

⊛

eltoljuk annyival, hogy a szövegnek a mintán túli első karaktere (jel.X) illeszkedjen a mintában az (X) karakter jobb szélső előfordulására. ha mintánkon nem szereplő input karakter jön, teljes hosszon átugorjuk, hiszen úgysem illeszkedne

adott betű esetén annyit kell lépni, hogy a minta illeszkedhessen, ezek a mintához specifikusak

Init(shift[Σ] : 1..n+1, P[1..m] : Σ) ∀δ ∈ Σ shift[δ] :=m + 1 j = 1 .. m shift[P[j]] := m+1 - j j 1 2 3

Θ(d)

először feltesszük, hogy Σ ábécé összes betűjét át kell ugrani.

Θ(m)

shift[P[j]] m m-1 m-2 …

⊛ hogy a P[1] kerüljön X=T[s+m+1] alá, a mintát a teljes hosszával el kell tolni, hogy P[2] kerüljön az X alá, csak egyel, kevesebbet kell tolni, stb… QuickSearch(T[1..n]: Σ; P[1..n]: Σ; S)

d konstans 𝑑

Init(shift[Σ], P[1..m])

⏞ ) = θ(m+d) = Θ(m) Θ(m+ |𝛴|

s := 0 S := {} s+m≤n T[s+1..s+m] = P[1..m] S :=S ∪ {s} s+m < n s := s+shift[T[s+m+1]] s := s + 1

Θ(1)

n

mT(n, m) ∈ Θ ( )  pl: T és P diszjunkt m+1 MT(n,m) ∈ Θ((n-m+1)*m)  pl: T= A…A és p= A…A

RABIN-KARP Σ = {σ1 , … , σd } φ: Σ  0..d-1 φ(σi ) = i-1

𝑃0

m−j : d számrendszerbeli szám, Horner elrendezéssel: Θ(m) időben számítható. ∑m P[1..m] ~ ⏞ j=1 φ(P[j])d m−j : Horner elrendezéssel: Θ(m) időben számítható. T[s+1..s+m] ~ Ts = ∑m j=1 φ(T[s + j])d

23

A keresett eltolásokat S ∶= {s ∈ 0. . n − m | Ts = P0 } alakban oldjuk meg, a d-számrendszerű számok egyenlőségét vizsgáljuk. A számítás a Horner mellett tovább egyszerűsödik: m

Ts+1 = ∑ φ(T[s + 1 + j])dm−1 = (Ts − φ(T[s + 1])dm−j)d + φ(T[s + m + 1]) : Θ(1) időben, j=1

Ts= 1 2 8 25 Ts+1 = 2 8 2514 T0 és P0 számítása Θ(m) és Θ(m) idejű a rekurzió Θ(1) idejű. A teljes műveletigény így Θ(m) + (n − m) ∗ Θ(1), ami Θ(n) igényű. ha a rekurzió tényleg Θ(1) és a Ti , P0 számokat a gép tudja hatékonyan ábrázolni.

ha 𝑑 𝑚−1 -et előre kiszámoltuk.

Mi lesz a nagy mintákkal? p := P0 mod q (q „nagy” prím) t s := Ts mod q h:= dm−1 mod q t s+1 = (t s − φ (T[s + 1])h)d + φ(T[s + m + 1]) mod q a különbség átcsaphat negatívba… t s+1 = (((t ⏟s + dq − φ (T[s + 1])h) mod q) ∗ d + φ(T[s + m + 1])) mod q <(d+1)∗q

⟹ t s = (((t s−1 + dq − φ (T[s])h) mod q) ∗ d + φ(T[s + m])) mod q = : ∆ hogy jól működjön (d+1)q ≤ legnagyobb ábrázolható szám kell legyen (size_t, Integer’Last’…) Lehet hamis találat (fals pozitív), ekkor ellenőrizni kell, hogy valódi találat-e, eredeti karakterekkel.

24

10102 EA RABIN-KARP folytatása q=

maxℕ d+1

legnagyobb ábrázolható ℕ szám, prímszám használatával a mod q számítások nem fognak túlcsordulni

p ≠ t s ⇒ P0 ≠ Ts p = t s ⇏ P0 = Ts így potenciális találat esetén a valódi találatot ellenőrizni kell. a modulo számítás miatt elveszik az információ RABIN_KARP(T[1..n], P[1..m], S) t 0 := φ(T[1]) p := φ(P[1]) h := 1 j = 2..m t 0 ∶= ( t 0 ∗ d + φ(T[j])) mod q p ∶= ( p ∗ d + φ(P[j])) mod q h ∶= (h ∗ d) mod q p = t 0 ∧ T[1..n] = P[1..m] S := {0} S := {} s := 1.. n - m ∆ t s = p ∧ P[1..m] = T[s+1..s+m] S := S ∪{s}

Θ(m)

Θ(1) mT(n, m) ∈ Θ(n − m) ha t s = p sosem teljesül MT(n, m) ∈ Θ((n − m) ∗ m) ← pl: T = AA … A p = A … A ha a minta mindig megtalálható

teljes algoritmus: mTRK ∈ Θ(n) MTRK ∈ Θ((n − m + 1) ∗ m) A gyakorlatban nincs túl sok valódi találat, nagy q esetén a hamis találatok száma se túl sok. Így ATRK ~ mTRK (nem biz)

Mintaillesztés lineáris időben Példa: P[1..8] = BABABBAB T[1..18]= A B A B A B A B B A B A B A B B A B B eltoljuk a mintát annyival, hogy a minta illeszkedő része az eltolás után illeszkedjen B AB AB B részben a szövegre B AB AB B A B B AB AB B B A B A B B AB B A B …(vége a szövegnek) Keressük a legnagyobb olyan h-t, hogy P[1..h] suffixe T[1..i] és h < j

T[1. . i]j hosszú suffixe = P[1. . j] ⇒ T[1. . i]h hosszú suffixe = P[1. . j]h hosszú suffixe = P[1. . h] ilyen feltételt kielégítő h-t keresünk. 25

Ez az információ csak a minta ismeretében megkapható. Def: next(j) = max{h ∈ [0..j-1] | P[1..h] ⊐ P[1..j]} next[1..m] := next(1..m) Ezt kiszámolva úgy toljuk el a mintát, hogy p[1..next(j)] legyen a T[1..i] hosszú suffixe alatt, mivel korábban biztos nem lehet illeszkedés. KMP(T[1..n], P[1..m], S) init(next[1..m], P[1..m]) i := 0 j := 0 S := {} i
θ(m)

0≤ i ≤ n ∧ 0 ≤ j<m ∧ i≥j ∧ P[1..j] ⊐ T[1..i] ∧ S = {s ∈ 0..i-m | P[1..m] = T[s+1..s+m]}

θ(1)

θ(n)

next k(j)= P[1..j] k-adik leghosszabb illeszkedő prefixe

A fő ciklus T∈ Ω(n), mivel i növekedni egyesével tud, és n-ig nő ⟹ biztos van n lefutás t(i,j) = 2i – j ∈ [0..2n] szig mon növő mind a négy ágon, de így a főciklus legfeljebb 2n-szer fut le ⟹ T ∈ Ο(n) 0≤j≤i≤n ⇓ Tfő ∈ θ(n) init(next[1..m], P[1..m]) P[1..i] ⊐ P[1..j] next[1] := 0; i := 0; j := 1 j<m P[i+1] = P[j+1] i := i+1 i=0 j := j+1 j := j + 1 i := next[i] next[j] := i next[j] := 0 most is a 2j-i ∈ [0..2n], az ágakon szigorúan monoton növő mindig így legfeljebb 2m, legalább m-szer fut le ⇒ Θ(m)

26

10112 EA Folytatás init stuki: Def: next: [1..m]  [0..m-1]

(m ∈ ℕ+ )

next(j) = max{h ∈ [0..j-1] | P[1..h] ⊐ P[1..j]}

x ⊏y ⟺ xz = y (∃ z) x ⊐ y ⟺ zx = y (∃ z) x ps-párosa y-nak ⟺ x ≠ y ∧ x ⊏y ∧ x ⊐ y /*ps: prefix-suffix*/

Tulajdonságok: 1. P[1. . h] ps − párosa P[1. . j] − nek ⟺ 0 ≤ h < j ∧ P[1. . h] ⊐ P[1. . j] 2. P[1. . i + 1] ⊐ P[1. . j + 1] ⟺ P[1. . i] ⊐ P[1. . j] ∧ P[i + 1] = P[j + 1] 3. 0 ≤ next(j) < j

Köv: j > next(j) > next2 (j) > ⋯ > next k(j) = 0

4. 0 ≤ next(j+1) ≤ next(j) + 1

valamely k > 0-ra

5. a. next k(j) értelmezve van ⟺ ∃ a P[1..j]-nek a k. leghosszabb ps-párosa b. next k(j) értelmezve van ⇒ P[1.. next k(j)] a P[1..j] k. leghosszabb ps-párosa Q: m > 0 /*előfeltétel*/ R: next[1..m] = next(1..m) /*utófeltétel*/ Inv: 0 ≤ i < j ≤ m ∧ next[1..j] = next(1..j) ∧ P[1..i] ⊐ P[1..j] ∧ (a P[1..j] tetszőleges i-nél hosszabb P[1..l] pspárosára: P[l+1] ≠ P[j+1] (0≤ i < j)) 2j-i ∈ 2..2m 2-ről indul, szig. mon. nő

a ciklus legfeljebb (2n-2)-szer hajtódik végre ⟹ a ciklus legalább (n-1)-szer végrehajtódik

Példa: j 1 2 3 4 5 6 7 8 P[j] A B A B B A B A next[j] 0 0 1 2 0 1 2 3 Az algoritmus működése lépésről-lépésre: 12345678 i j next[j] A B A B B AB A 0 1 0 A 0 2 0 A 1 3 1 AB 2 4 2 AB A 0 4 üres mező A 0 5 0 A 1 6 1 AB 2 7 2 AB A 3 8 3

Tömörítés Naiv módszer: T[1..n]: Σ Σ = {σ1 , … , σd } ⌈ ⌉ n * lg d bittel kódolható a szöveg

⌈lg d⌉ bittel kódolható a karakter

Huffman kód: egyfajra prefix kód a szöveg: ABRAKADABRA jel előfordulás kód A 5 0 B 2 100 R 2 101 K 1 110 D 1 111

Megjegyzés: A kerekterenként kódoló tömörítések között a Huffman kód hossza minimális. Tömörített kód:

⏟ 0 100 ⏟ 101 ⏟⏟ 0 110 ⏟⏟ 0 111 ⏟⏟ 0 100 ⏟ 101 ⏟⏟ 0 𝐴

𝐵

𝑅

𝐴

𝐾

𝐴

𝐷

𝐴

𝐵

Kitömörítés kódfa : alapján 27

𝑅

𝐴

LEMPEZ-ZIV-WELCH (LZW) IN: a b ab c ba bab a aa aaa a OUT 1 2 4 3 5 8 1 10 11 1 szó a b c ab ba abc cb bab baba aa aaa aaaa

kód 1 2 3 4 5 6 7 8 9 10 11 12

Σ = {a, b, c}

Rekonstruálás: IN’ 1 2 4 3 5 8 1 10 11 1 OUT’ a b ab c ba bab a aa aaa a 8-as kód nincs a szótárban! generáláskor a 8-as kód a ba… szövegből jött létre 𝑏𝑎 ⏟ 𝑏ab  𝑏𝑎𝑏 ⏟ a..? 5

8

(hasonlóan járunk el a 10-es, 11-es esetben is)

LZW_COMPRESS (In, Out, Σ) D := {σ1 : 1, σ2 : 2, … , σd : d} kód := d + 1 s := get_char(In) ¬eof(In) c := get_char(In) (sc ̂ :_) ∈ D write(Out, kód(D,s)) s := sc ̂ D := D ∪{sc ̂ :kód} ⨀ s := c kód := kód + 1 write(Out, kód(D, s))

szó a b c ab ba abc cb bab baba aa aaa aaaa

kód 1 2 3 4 5 6 7 8 9 10 11 12

az utolsó sor dekódoláskor legtöbbször felesleges már Σ = {σ1 , … , σd } ábécé s: string c: char D: szótár, „string: kód” alakú rendezett párosok halmaza sc ̂ : az s string és a c char konkatenáltja σi : a σi betűből álló string (egybetűs string) kód(D,s) = a D szótárban az s string kódja eof(In) ⟺ az In inputról ∀ karaktert beolvastunk „s:_” olyan rendezett páros, aminek az első komponense s ⨀ Az így jelzett utasítások csak akkor hajtandók végre, ha még kód ≤ MAXKÓD, ahol MAXKÓD a kódok előre rögzített hosszától függ. Pl: ha ez 12bit, akkor MAXKÓD = 212 -1 = 4095.

LZW_DECOMPRESS(In, Out, Σ) D := {σ1 : 1, σ2 : 2, … , σd : d} kód := d + 1 k := get_code(In) s := string(D, k) write(Out, s) ¬eof(In) k := get_code(In) (_:k) ∈ D t := string(D, k) t := ss ̂1 write(Out, t) write(Out, t) ̂1 :kód}⨀ D := D ∪ {t:kód}⊗ D := D ∪ {st s := t kód := kód + 1

s,t: string k, kód: kódok t1 : a t string első betűje string(D,k)= a D szótárban k kódnak megfelelő string eof(In) ⟺ az In inputról ∀ kódot beolvastunk „_:k” olyan rendezett páros, aminek a 2. komponense k ⊗: Itt k = kód teljesül

Megjegyzés: Balra, az elágazásban az „(_:k) ∈ D” feltétel helyén „k < kód” is állhatna (így egy kicsit gyorsabb lenne az algoritmus)

28

Felhasznált segédanyagok:  Az előadáson készített jegyzetem (Koru),  Whisperity előadás jegyzete (a jegyzetben található összes kép és néhány szöveges kiegészítés).  http://aszt.inf.elte.hu/~asvanyi/ad/sor%20alapu%20Bellman-Ford%20alg.pdf  http://aszt.inf.elte.hu/~asvanyi/ad/Lempel-Ziv-Welch%20alg.pdf Külön köszönet Dr. Ásványi Tibor tanár úrnak a jegyzet alapos átolvasásáért, a talált hibák jelzéséért és az anyag megértését segítő megjegyzéseiért. A jegyzetet átolvasták és a talált hibákat jelezték, amiért köszönet:  Bán Róbert  Fekete Anett  László Tamás  Nagy Vendel  Szabó Gergő  Szécsi Péter  Tőkés Anna

29