Algoritmusok és adatstruktúrák tervezése, elemzése és implementálása II

Adatstruktúrák

Előadás doktoranduszoknak, matematikusoknak és alkalmazott matematikusoknak, illetve informatikusoknak

2015 Tavasz

Előadó: Király Zoltán

Péntek 12:00-13:30, Déli tömb 4.428.


Csak a hallgatóimnak / Only for my students


Hirdetmények


Ajánlott irodalom


TEMATIKA


1. előadás (II. 13.)

Kruskal algoritmusa, jósága.
Kruskal megvalósítás tömbbel, illetve tömb + láncolt listával.
Fastruktúra a D.Unió-Holvan feladatra, útrövidítés és útfelezés. A rang tulajdonságai. Útfelezésnél lépésszám elemzése [CLR, AHU, T].


2. előadás (II. 20.)

Az elemzés bejezése.
Prim algoritmusa: megvalósítás, lépésszám [CLR]. Dijkstra algoritmusa. Jóság, megvalósítás, lépésszám [CLR]. d-edfokú kupacok, Dijkstra és Prim lépésszáma ilyennel [T]. SZÁMLÁLÓ.
Potenciál és amortizációs idő [AHU, CLR].
Konvex burok keresése [L].


3. előadás (II. 27.)

Fibonacci kupac, megvalósítás, BESZÚRÁS, MINTÖRLÉS, KULCS-CSÖK. Fibonacci kupacban kaszkádvágás, elemzése, alkalmazása Dijkstra és Prim algoritmusra. Mese a leggyorsabb MST-keresésről. [CLR, FT-cikk ].

4. előadás (III. 6.)

Mese a szigorú Fibonacci kupacról [BLT-cikk].

Párosítós kupacok definíciója, Fibonacci kupac tárolása bináris faként.
Műveletek párosítós kupacokban: az eredeti és a lusta változat [SV-cikk ].
A párosítós kupac változata, ahol a KULCS-CSÖKK amortizációs ideje log log n: [ E-cikk].
A párosítós kupac legújabb változata: [ HST-cikk].
Radix kupacok (r-kupacok). [ AMOT-cikk].


5. előadás (III. 13.)

Word RAM modell, mese a legjobb kupacról [ T-cikk].
Szótárak. Bináris keresőfák, keresés, beszúrás. Törlés bináris fában [T, RISz, CLR].
2-3 fák. B-fák [RISz, CLR].


6. előadás (III. 20.)

Piros-fekete fák [T, RISz, CLR].
AVL fák [T, RISz].
Sleator és Tarjan önkiegyensúlyozó fája (S-tree) [T, RISz].


7. előadás (III. 27.)

S-fa elemzés vége.
Hash-elés: jó hash függvény, születésnap paradoxon, ütközések [K, RISz].
Vödrös (láncolt) hash-elés [K, RISz].
Nyílt címzések: lineáris hash-elés [K, RISz].


8. előadás (IV. 10.)

Törlés lineáris hash-eléskor [K].
Dupla hash-elés [K, RISz].
Univerzális hash-elés.
Tökéletes (perfect) hashelés.
Kakukk hashelés.


9. előadás (IV. 17.)

A van Emde Boas adatstruktúra.
Szófa, x-fast trie, y-fast trie.

Az LCA és az RMQ feladat.


10. előadás (IV. 24.)

LCA visszavezetése a +-1 RMQ feladatra.
Megoldás a +-1 RMQ feladatra.

Descartes-fa, segítségével RMQ visszavezetése LCA-ra.
Kitekintés a geometriai adatstruktúrákra: egy intervallumba eső pontok lekérdezése, és egy pontot tartalmazzó intervallumok lekérdezése (intervallum-fák).


11. előadás (V. 7. Csütörtök! 10:15 D.3.???.)

Egy téglalapba eső pontok lekérdezése tartomány-fával (range tree). d dimenziós tartományfa [BKOS].

Range tree javítása kaszkád-tárolással [BKOS].
Egy függőleges szakaszt metsző vízszintes szakaszok lekérdezése [BKOS].
Egy irányba végtelen téglalapba eső pontok lekérdezése: kupacos keresőfák.
Szakasz fák, egy téglalapot metsző ferde szakaszok lekérdezése [BKOS].


12. előadás (V. 15.)

Dinamikus utak.
Dinamikus irányítatlan fák megvalósítása.
Dinic algoritmusa dinamikus fákkal.
Dinamikus fák, visszavezetés utakra (exponálás), ennek elemzése.