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ó    

    Théorie d'algorithme

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

    Adatlap utolsó módosítása: 2006. július 1.

    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 Szak
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VIMAF509 3. 3/1/0/v 5 1/1
    3. A tantárgyfelelős személy és tanszék Dr. Katona Gyula,
    4. A tantárgy előadója

    Név:

    Beosztás:

    Tanszék, Int.:

    Csima Judit

    egy.tanársegéd

    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
    Kötelező:
    TárgyEredmény( "BMEVIFOF013" , "jegy" , _ ) >= 2 ÉS TárgyEredmény( "BMEVIMAF503" , "jegy" , _ ) >= 2

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

    Ajánlott:

    Diszkrét matematika I. kredit

    Programozás alapjai I, II. kredit

    Számítógép labor I, II. 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.).

    Randomizált algoritmusok: plinomazonosság tesztelés (Schwartz lemmája); Rabin-Miller prímteszt, véletlen prímszám generálása, a nyilvános kulcsú kriptográfia elemei; az RP és Las Vegas nyelvosztályok.

    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 vagy beszámoló a gyak.vezetőnél.

    b. A vizsgaidőszakban:

    - írásbeli vizsga

    c. Elővizsga: Igény esetén biztosítunk lehetőséget.

    13. Jegyzet, tankönyv, felhasználható irodalom

    Tankönyv: Ivanyos, Rónyai, Szabó: Algoritmusok, Typotex Kiadó, 1998, ISBN 963 9132 16 0

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

    Aho, Hopcroft, Ullman: Számítógép-algoritmusok tervezése és elemzése;

    Műszaki Könyvkiadó 1982.

    Demetrovics, Denev, Pavlov: A számítástudomány matematikai alapjai;

    Tankönyvkiadó 1987.

    Lovász: Algoritmusok bonyolultsága; ELTE TTK jegyzet,

    Tankönvkiadó 1989.

    Knuth: A számítógép-programozás művészete, I-II-III. kötet;

    Műszaki Könyvkiadó 1985.

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

    Feladatgyűjtemény elérhető: http://www.math.bme.hu/~ig/algel

    15. A tantárgy tematikáját kidolgozta

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Rónyai Lajos

    egy. tanár

    Számítástudományi és Információelméleti Tanszék

    vimaF509.doc