Belépés címtáras azonosítással
magyar nyelvű adatlap
angol nyelvű adatlap
Haladó adatszerkezetek és algoritmuselemzési technikák
A tantárgy angol neve: Advanced Datastructures and Techniques for Analysis of Algorithms
Adatlap utolsó módosítása: 2024. október 25.
PhD képzés
szabadon választható tárgy
Dr. Friedl Katalin, egyetemi docens, Számítástudományi és Információelméleti Tanszék
Dr. Katona Gyula, egyetemi docens, Számítástudományi és Információelméleti Tanszék
Alapvető adatszerkezetek és algoritmusok
További részletek a tárgy weboldalán: http://cs.bme.hu/haladoadat/
1. Hashelés haladóknak:
az univerzális hash fogalma, univerzális hash-függvények konstrukciója és
a k-szoros függetlenség, a tökéletes hash.
2. Biztosan konstans keresési idő:
kakukk hash. Keresés randomizáltan kis hibával: Bloom-filter.
3. Átlagos futási idő elemzése:
a munkaerő felvételi probléma gyorsrendezés randomizált változata,
4. Véletlen sorozatból generált bináris keresőfa magassága,
gráf színezési algoritmus várható ideje véletlen gráf esetén.
5-6. Haladó adatszerkezetek és elemzésük: skip list, treap, S-fa (splay tree), szófa,
szuffix-fa (ennek alkalmazásai bioinformatikai problémákra: átfedések keresése,
leghosszabb közös részszó), trie
7. Hálózati folyamok:
Edmonds-Karp algoritmus, Dinitz algoritmus, általánosítások, alkalmazások
8. Adatszerkezetek diszjunkt halmazokra
(unió-holvan adatszerkezet útösszenyomással és ennek elemzése).
Megmaradó (persistent) adatszerkezetek, lusta kiértékelés.
9. Maximális párosítás keresése nem páros gráfokban, Edmonds algoritmusa.
10. Gyors mátrixszorzás, Karatsuba algoritmusa.
11. Paraméteres bonyolultság: Kernel technika, dinamikus programozás
12. Paraméteres bonyolultság: Iteratív összenyomási technika, randomizált algoritmusok
13. Véletlen gráf modellek:
Erdős-Rényi, Barabási. Közösségek keresése szociális hálózatokban.
A vizsgaidőszakban: szóbeli vizsga