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. Csima Judit, egyetemi docens, Számítástudományi és Információelméleti Tanszék

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/

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: hash lineáris próbával, gyorsrendezés randomizált változata, k. elem keresése, ennek randomizált és determinizált változata is, Karger algoritmusa minimális vágás keresésére.

4. Algoritmusok véletlen gráfon, pl. 3 színnel színezés O(1)-ben, különböző véletlen gráf modellek: Erdős-Rényi modell, Barabási féle modell, összehasonlításuk.

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. Binomiális kupac, Fibonacci-kupac. Amortizált elemzés módszere (bankár módszer és potenciált használó módszer), alkalmazás Fibonacci-kupacra.

8. Adatszerkezetek diszjunkt halmazokra (unió-holvan adatszerkezet útösszenyomással és ennek elemzése). Megmaradó (persistent) adatszerkezetek, lusta kiértékelés.

9. Homogén és nem homogén lineáris rekurziók megoldása, az Akra-Bazzi formula, mester tétel. Példák rekurzív algoritmusok lépésszámának becslésére.

10. Nehéz problémák egy kezelési módja: paraméteres bonyolultság alapvető technikái: a keresési fa korlátozása, kernel technika, néhány alapvető példa.

11. Triviálisnál jobb exponenciális algoritmusok nehéz problémákra, gyors mátrixszorzás, maximális független ponthalmaz, utazó ügynök probléma, kromatikus szám, részletösszeg probléma, lokális keresés.

12. Worst-case és average-case analízis közötti hibrid megoldások. Simított analízis, simított lokális keresés. A 2-OPT alapú lokális kereső algoritmus simított polinomiális futásidejének bizonyítása.

13. Tömörített érzékelés, alulhatározott lineáris egyenletrendszer ritka megoldásai, L_1-minimalizálás lineáris programozással. Alkalmazás: útban az egy pixeles fényképezőgép felé.

14. Házi feladat megbeszélés

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 szorgalmi időszakban: A kiadott házi feladatok beadása.

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. Csima Judit	egyetemi docens	Számítástudományi és Információelméleti Tanszék
Dr. Friedl Katalin	egyetemi docens	Számítástudományi és Információelméleti Tanszék
Hosszú Éva	PhD hallgató	Távközlési és Médiainformatikai Tanszék
Dr. Katona Gyula	egyetemi docens	Számítástudományi és Információelméleti Tanszék
Dr. Tapolcai János	egyetemi tanár	Távközlési és Médiainformatikai Tanszék