Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással
    vissza a tantárgylistához   nyomtatható verzió    

    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: 2020. augusztus 10.

    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,
    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 ó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