BME VIK - Haladó adatszerkezetek és algoritmuselemzési technikák

A tantárgy angol neve: Advanced Datastructures and Techniques for Analysis of Algorithms

3. A tantárgyfelelős személy és tanszék Dr. Katona Gyula,

A tantárgy tanszéki weboldala http://cs.bme.hu/haladoadat/

4. A tantárgy előadója

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

5. A tantárgy az alábbi témakörök ismeretére épít

Alapvető adatszerkezetek és algoritmusok

További részletek a tárgy weboldalán: http://cs.bme.hu/haladoadat/

6. Előtanulmányi rend

Ajánlott:

7. A tantárgy célkitűzése A tantárgy keretében a hallgatók megismerkednek néhány modern, jól használható adatszerkezettel. Az algoritmusoknak a legrosszabb esetre koncentráló elemzése nem mindig ad elég támpontot a gyakorlati használhatóságról. A kurzus célja, hogy bemutassa és szemléltesse a véletlen (átlagos) esetekre vonatkozó becslések néhány módszerét, és más manapság sokszor alkalmazott technikát (pl. simított vagy paraméteres bonyolultsági elemzés).

8. A tantárgy részletes tematikája

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.

9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) Heti 4 óra előadás.

10. Követelmények

A vizsgaidőszakban: szóbeli vizsga

Elővizsga: lehetséges

12. Konzultációs lehetőségek Fogadóórákon, illetve személyes egyeztetés alapján

13. Jegyzet, tankönyv, felhasználható irodalom

Cormen, Leiserson, Rivest, Stein: Új algoritmusok (Scolar, 2003)

Motwani, Raghavan: Randomized Algorithms (Cambridge, 2000)

Hromkovic: Algorithmics for hard Problems (Springer, 2004)

Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh: Parameterized Algorithms (Springer 2015)

internetes források

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka

Kontakt óra	56
Félévközi készülés órákra	28
Felkészülés zárthelyire
Házi feladat elkészítése	28
Kijelölt írásos tananyag elsajátítása	14
Vizsgafelkészülés	24
Összesen	150

15. A tantárgy tematikáját kidolgozta

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