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ó    

    Adatszerkezetek és algoritmusok

    A tantárgy angol neve: Data Structures and Algorithms 

    Adatlap utolsó módosítása: 2023. január 3.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar
    Mérnökinformatikus MSc képzés
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZMB02   2/1/0/v 5  
    3. A tantárgyfelelős személy és tanszék Dr. Csima Judit,
    4. A tantárgy előadója

    Dr. Csima Judit,      egyetemi docens, SZIT  

    Dr. Friedl Katalin,   egyetemi docens, SZIT 

    Dr. Katona Gyula,   egyetemi docens, SZIT  

    5. A tantárgy az alábbi témakörök ismeretére épít Alapvető adatszerkezetek és algoritmusok (BSc Algoritmuselmélet tantárgy anyaga) 
    7. A tantárgy célkitűzése

    A tantárgy célja a BSc képzésből kimaradt legfontosabb, sok helyen használt adatszerkezetek és algoritmusok megismertetése. 

    A tantárgy követelményeit eredményesen teljesítő hallgatóktól elvárható, hogy:  

     (1) ismerjék az előadáson elhangzó módszereket,  

     (2) megértsék a módszerek helyességének és hatékonyságának bizonyítását, 

     (3) képesek legyenek a tanultak alkalmazásával feladatokat megoldani, 

     (4) képesek legyenek felismerni az alkalmazási lehetőségeket, fel tudják fedezni,  milyen kisebb módosításokra van esetleg szükség az alkalmazásokhoz és ezt átgondolt módon meg is tudják valósítani.  

    8. A tantárgy részletes tematikája
      1. 1. k. elem keresés várhatóan lineáris időben és determinisztikus lineáris időben. A dinamikus eset – bináris keresőfa kibővítése 


      1. 2. Bináris keresőfák további alkalmazásai:  legkisebb közös ős keresése, intervallumba eső minimum keresése. Intervallumfák.

      2.  

      1. 3. Alapvető síkgeometriai algoritmusok (metsző szakaszpár, legközelebbi pontpár keresése, konvex burok) 


      1. 4. Hash-elés elméleti és gyakorlati változatai:  lineáris próba, dupla hash módosítása. Univerzális hash, hosszabbítható hash. 


      1. 5. Folyamalgoritmusok: Ford-Fulkerson-algoritmus, és ennek javítása az Edmonds-Karp-algoritmus. 


      1. 6. Hatékonyabb folyamalgortimusok: mohó javítás. Előfolyam módszer, előreemelő algoritmus. 


      1. 7. Mintaillesztés: egyszerű algoritmus, gyorskeresés.  A lineáris idejű Knuth-Morris-Pratt-algoritmus 


      1. 8. A dinamikus programozás néhány alkalmazása: közelítő mintaillesztés, szerkesztési távolság, leghosszabb közös részsorozat, egy egyszerű bioinformatikai alkalmazás. 


      1. 9. Az algoritmusok hatékonyságának egy, a tapasztalatokhoz sokszor közelebbi eredményt adó elemzési módszere:  amortizált elemzés és ennek néhány alkalmazása. 


      1. 10. Gráfok minimális feszítőfájának keresése: az általános piros-kék algoritmus, Prim, Boruvka, Kruskal algoritmusa, mint ennek alkalmazásai. 


      1. 11. A Kruskal algoritmushoz is szükséges unió-holvan adatszerkezet különböző megvalósításai, ezek (amortizált) elemzése. 


      1. 12. Nagy számok gyorsabb szorzása Karacuba módszerével. Nagy mátrixok gyorsabb szorzása. A gyors-Fourier transzformáció és alkalmazásai. 


      1. 13. Ismétlés, tartalék. 

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

    Heti 2 óra előadás és 1 óra gyakorlat. Az anyag egy részét önálló munkával, kiadott anyagokból kell elsajátítani.   

    A gyakorlatokon az előadáson tárgyalt anyagrésszel kapcsolatos feladatokat oldanak meg a hallgatók. 

     

    10. Követelmények

    Szorgalmi időszakban: 3 kiszárthelyi, egy kiszárthelyi akkor sikeres, ha legalább 50%-os. Az aláírás feltétele 2 sikeres kiszárthelyi. 

    Vizsgaidőszakban: szóbeli vizsga

    11. Pótlási lehetőségek A kiszárthelyik nem pótolhatóak. 
    12. Konzultációs lehetőségek Az előadóval való egyeztetés szerint. 
    13. Jegyzet, tankönyv, felhasználható irodalom

    Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok, TypoTeX Kiadó  

    Thomas H. Cormen,  Charles E. Leiserson , Ronald L. Rivest,  Clifford Stein: Új algoritmusok Scolar Kiadó, 2003  

    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra42
    Félévközi készülés órákra28
    Felkészülés zárthelyire9
    Házi feladat elkészítése
    Kijelölt írásos tananyag elsajátítása28
    Vizsgafelkészülés43
    Összesen150
    15. A tantárgy tematikáját kidolgozta

    dr. Csima Judit egyetemi docens SZIT  

    dr. Friedl Katalin egyetemi docens SZIT 

    dr. Katona Gyula egyetemi docens SZIT