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ó    

    Theorie der Algorithmen

    A tantárgy angol neve: Theory of Algorithms (In German)

    Adatlap utolsó módosítása: 2006. november 27.

    Tantárgy lejárati dátuma: 2015. január 31.

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

    Műszaki informatika

    2.

    Tantárgy kódjaSzemeszterKövetelményKreditNyelvTárgyfélév
     VIMA22074.3+1+0v5magyar1/1
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VIMA2607   3/1/0/v 5  
    4. A tantárgy előadója
    Név:Beosztás:Tanszék, Int.:
    Dr. Friedl KatalinEgy. DocensSzámítástudományi és Információelméleti Tanszék
     Dr. Recski András Egy.tanár 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 Diszkrét matematika elemei, alapvetõ programozási ismeretek.
    6. Előtanulmányi rend
    Ajánlott:

    BSZ II. kredit

    Programozás alapjai     I. kredit

    7. A tantárgy célkitűzése Az algoritmusok tervezésével, elemzésével kapcsolatos alapvetõ módszerek, készségek elsajátítása. 
    8. A tantárgy részletes tematikája

    Turing gépek (TG): definíció; egyszerû példák; idõ- és tárkorlátos TG; univerzális TG; többszalagos TG szimulációja 1 szalagossal, TG-k konstrukciója.            

    A kiszámíthatóság elméletének alapjai: Rekurzíve felsorolható és rekurzív nyelvek, parciális rekurzív és rekurzív függvények, kapcsolatuk egymással; R a RE és coRE osztályok metszete; RE-n kívüli nyelvek létezése; a megállási feladat eldönthetetlensége, nyelv-tulajdonságok eldönthetetlensége; Hilbert 10. problémája; dominóprobléma; Post feladat; Church-Turing tézis.            

    A RAM gép: definíció; logaritmikus költség és uniform költség            

    RAM-TG és TG-RAM szimulációk.           

    Kolgomorov bonyolultság: invariancia tétel: összenyomhatatlan szavak létezése, alkalmazások; a Kolgomorov bonyolultság kiszámíthatatlansága.           

    Nevezetes bonyolultsági osztályok: idõ és tár kapcsolata; lineáris idõ, P, FP, PSPACE, EXPTIME példákkal.          

       Az NP nyelvosztály: Nemdeterminisztikus Turing gépek (NTG); NP definíciója NTG-vel illetve tanúkkal; példák NP-beli nyelvekre (gráftulajdonságok: összefüggõség, színezhetõség, független ponthalmazok, Hamilton-kör stb.; lieáris egyenlõtlenség-rendszerek, összetett illetve prímszámok); jó karakterizáció (NP és coNP metszete), Pratt, Kuratowski.             NP-teljesség: Karp redukció, NP-teljesség, Cook-Levin tétel; nevezetes NP-teljes nyelvek (3-SAT, 3-színezés, független ponthalmaz, 3DM, hátizsák probléma, ládapakolás stb.).                       

    Algoritmus-tervezési technikák: mohó módszer (pl. minimális költségû feszítõfa), oszd meg és uralkodj, dinamikus programozás (pl. hátizsák), korlátozás és elágazás (pl. maximális független ponthalmaz gráfban), közelítõ módszerek (pl. ládapakolási heurisztikák).           

     Adatrendezési módszerek: rendezés összehasonlításokkal (beszúrásos, összefésülõ, gyorsrendezés); kupac fogalma, kupacos rendezés; kulcsmanipulációs rendezések (láda- és radixrendezés); külsõ tárak tartalmának rendezése.            Alapvetõ adatszerkezetek: tömb, lista, verem, sor; keresõ fák (bináris keresõfák, 2-3 fák, B-fák, AVL fák, szófák); hashelés (cél, alkalmazhatóság, kezelendõ problémák), ütközések feloldása (láncolás, nyitott címzés), jó hash-függvények; szekvenciális keresés. Információ tömörítés.           

    Alapvetõ gráf-algoritmusok: gráfok tárolására szolgáló adatszerkezetek; legrövidebb utak keresése (Dijkstra, Floyd, Warshall módszerei); mélységi keresés és aklkalmazásai (DAG tulajdonság tesztelése, erõs komponensek); topologikus rendezés; szélességi keresés; minimális költségû feszítõfa keresése (piros-kék algoritmus, Boruvka, Prim és Kruskal módszerei); az UNIÓ-HOLVAN adatszerkezet; maximális párosítás kétrészes gráfokban, folyamok hálózatokban.             Alapvetõ aritmetikai algoritmusok: euklideszi algoritmus, gyors hatványozás.

    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) Elõadás, gyakorlat
    10. Követelmények

    a.         A szorgalmi időszakban:

    - a félév lezárásának módja: aláírás

    - a félév lezárásához szükséges követelmény: sikeres zárthelyi

    b.       A vizsgaidőszakban:

    - írásbeli vizsga

    11. Pótlási lehetőségek 1 pótzárthelyi lehetőséget biztosítunk
    12. Konzultációs lehetőségek Igény szerint
    13. Jegyzet, tankönyv, felhasználható irodalom

    Tankönyv: Ivanyos, Rónyai, Szabó: Algoritmusok, Typotex Kiadó, 1998

     

    Az anyaghoz részben használható további szakkönyvek:

     Cormen Leiserson, Rivest: Algoritmusok, Mûszaki Könyvkiadó, 1997

    Feladatgyûjtemény elérhetõ: http://www.cs.bme.hu/~friedl/alg

    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra 56
    Félévközi készülés órákra 35
    Felkészülés zárthelyire 10
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása 
    Vizsgafelkészülés 49
    Összesen 150
    15. A tantárgy tematikáját kidolgozta
    Név:Beosztás:Tanszék, Int.:
    Dr. Friedl Katalinegy. docensSzámítástudományi és Információelméleti Tanszék