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: 2024. október 25.

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