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
Péntek 12:00-13:30, Déli tömb 4.428.
Csak a hallgatóimnak / Only for my students
Hirdetmények
- A jegyzet
2.58. verziója.
- A jegyzet első három fejezetét mindenki önállóan tanulja meg.
- Vizsgára az alábbi jegyzet anyagát kell tudni, plusz az utolsó két óra
anyagát.
A jegyzet a félév során még frissülhet.
Az első órától feltételezem a jegyzet első 3 fejezetének ismeretét.
- Mindennemű hibajelentést a jegyzettel kapcsolatban NAGYON várok a
kiraly@cs.elte.hu címemre.
Ajánlott irodalom
- Letölthető segédanyagok
- [CLR] Cormen-Leiserson-Rivest-Stein: Új Algoritmusok
- [AHU] Aho-Hopcroft-Ullman: Számítógépalgoritmusok tervezése és analízise
- [T] Robert Endre Tarjan: Data Structures and Network Algorithms
- [RISz] Rónyai-Ivanyos-Szabó: Algoritmusok
- [K] D. E. Knuth: A számítógép-programozás művészete, III. kötet
- [L] Lovász: Algoritmusok bonyolultsága, ELTE jegyzet, 1992.
- [BKOS] Berg-Kreveld-Overmars-Schwarzkopf:
Computational Geometry: Algorithms and Applications, Springer-Verlag.
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.