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ó    

    Algoritmuselmélet

    A tantárgy angol neve: Theory of Algorithms

    Adatlap utolsó módosítása: 2022. augusztus 24.

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

    Mérnökinformatikus BSC

    kötelező tárgy 
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZAA08 2 2/2/0/f 5  
    3. A tantárgyfelelős személy és tanszék Dr. Katona Gyula,
    A tantárgy tanszéki weboldala http://www.cs.bme.hu/algel
    4. A tantárgy előadója
    dr. Csima Judit egyetemi docens SZIT 
    dr. Friedl Katalin egyetemi docens 
    dr. Katona Gyula egyetemi docens SZIT  
    dr. Kaszanitzky Viktória, egyetemi docens SZIT
    dr. Sali Attila, egyetemi docens SZIT 

     
    5. A tantárgy az alábbi témakörök ismeretére épít gráfelmélet, középiskolai matematika 
    6. Előtanulmányi rend
    Kötelező:

    (TárgyTeljesítve_Képzésen("BMEVISZAA04") VAGY
    TárgyTeljesítve_Képzésen("BMEVISZAA01") VAGY
    Felvetel("BMEVISZAA04") )


    ÉS

    NEM ( TárgyTeljesítve_Képzésen("BMEVISZAB03") )

    ÉS

    ( Kepzes("5N-A8") VAGY
    Kepzes("5NAA8"))

    VAGY EgyenCsoportTagja("Kreditpótlás_2023/24/2")

    VAGY
    (Kepzes("9N-AM06")ÉS
    TargyEredmeny("BMEVISZA025" , "jegy" , _ ) >= 2 ÉS
    TargyEredmeny("BMETE91AM43" , "jegy" , _ ) >= 2 ÉS
    (TargyEredmeny("BMETE91AM57" , "jegy" , _ ) >= 2 VAGY
    TargyEredmeny("BMETE91AM57", "FELVETEL", AktualisFelev()) > 0))

    VAGY

    (Kepzes("9NAAM17")ÉS
    TargyEredmeny("BMEVISZA025" , "jegy" , _ ) >= 2 ÉS
    TargyEredmeny("BMETE91AM43" , "jegy" , _ ) >= 2 ÉS
    (TargyEredmeny("BMETE91AM57" , "jegy" , _ ) >= 2 VAGY
    TargyEredmeny("BMETE91AM57", "FELVETEL", AktualisFelev()) > 0))

    A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

    A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

    7. A tantárgy célkitűzése
    (K1) Ismeret szint: 
    a témakör fogalmainak felidézése, felsorolása, felületes bemutatása. 

    (K2) Megértés szint: 
    magyarázatok, összefüggések ismerete, esetek felismerése, besorolása. 

    (K3) Alkalmazás szint: 
    problémamegoldás ismeretek alkalmazásával, példák, feladatok önálló megoldása. 

    (K4) Konstrukciós szint: 
    problémaelemzés, megoldási alternatívák felállítása, összevetése, választás, indoklás. 
    8. A tantárgy részletes tematikája
    1. Minimum, maximum keresés n-1 lépésben, kiválasztásos rendezés, függvények nagyságrendje, Ordo jelölés, egyszerű rekurziós egyenletek megoldása, összefésüléses rendezés. 
     
    2. Összehasonlítás alapú rendezések és elemzésük (buborék, beszúrásos, összefésüléses, gyorsrendezés). Alsó becslés a szükséges összehasonlítások számára.  Nem összehasonlítás alapú rendezések és elemzésük: ládarendezés, radix rendezés. 
     
    3. Gráfok megadása mátrixszal, illetve éllistával, alapműveletek lépésszáma gráfokban, mélységi keresés, irányított-körmentes gráfok (DAG), ezek felismerése, 
     
    4. Topologikus sorrend meghatározása, legrövidebb és leghosszabb út DAGban 
     
    5. Dinamikus programozás, hátizsák feladat, maximális összegű intervallum 
     
    6. A Dijkstra-algoritmus és helyességének bizonyítása 
     
    7. Adatszerkezetek: bináris fa és bejárásai, kupac, Dijsktra algoritmus kupaccal 

    8. Bináris keresőfa, piros-fekete fa, 2-3-fa, B-fa 
     
    9. Vödrös hashelés, hashelés nyitott címzéssel 
     
    10. Kruskal implementációs részletei, lépésszáma, Prim-algoritmus 
     
    11. Eldöntési problémák, hatékony tanúsítvány, a P, NP, coNP problémaosztályok definíciói és kapcsolatuk 

    12.A Karp-redukció és tulajdonságai, NP-teljesség, példák NP-teljes problémákra 
     
    13. Közelítő algoritmusok, epszilon közelítés, ládapakolás, FirstFit algoritmus, FirstFitDecreasing algoritmus, utazóügynök probléma: általában és az euklideszi változat, elágazás-és-korlátozás  
     
    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) A tárgyból heti 2 óra előadást és heti 2 óra gyakorlatot tartunk.
    10. Követelmények
    A félév során 2 zárthelyit iratunk. A félév teljesítésének feltétele: mindkét zárthelyin legalább 40 %-os teljesítmény. A végső jegy (teljesítés esetén) a  zárthelyik átlagából adódik. 

    11. Pótlási lehetőségek
    A szorgalmi időszak során minden zárthelyi dolgozathoz lesz pótlási (javítási) lehetőség. 
     
    A pótlási héten egyetlen alkalom lesz, amikor egy tetszőleges zh dolgozat pótolható.  
    12. Konzultációs lehetőségek Igény 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 óra56
    Félévközi készülés órákra28
    Felkészülés zárthelyire24
    Házi feladat elkészítése28
    Kijelölt írásos tananyag elsajátítása14
    Vizsgafelkészülés
    Ö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 

    IMSc tematika és módszer
    A gyakorlatokon más feladatokat dolgozunk fel, mint a többi kurzuson. Kevesebb bevezető, rutin, gyakorló feladat szerepel és több összetettebb, nehezebb, gondolkodtatóbb feladat lesz. 

     

     
    IMSc pontozás
    A 2 zárthelyin lesz egy-egy plusz, nehezebb feladat. A jegyek ponthatárát e nélkül határozzuk meg. A (plusz feladat nélkül is elérhető) jeles feletti teljesítményt a zárthelyiken plusz ponttal értékeljük. Ezeknek a plusz pontoknak az összege, de maximum 25 adja az IMSC pontot. 
     
    A tantárgy témájához csatlakozó, de annál lényegesen összetettebb feladatokkal foglalkozó Algoritmus szakkörön való aktív részvétellel is lehet IMSC pontot szerezni (max 10-et, úgy, hogy az összeg ne menjen 25 fölé). 
     
    Az IMSC-pontok megszerzése a programban nem résztvevő hallgatók számára is biztosított.