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: 2016. augusztus 26.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

PhD képzés

szabadon választható tárgy 

Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZDV05   4/0/0/v 5  
3. A tantárgyfelelős személy és tanszék Dr. Katona Gyula, Számítástudományi és Információelméleti Tanszék
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
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 óra56
Félévközi készülés órákra28
Felkészülés zárthelyire
Házi feladat elkészítése28
Kijelölt írásos tananyag elsajátítása14
Vizsgafelkészülés24
Összesen150
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