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: 2018. július 24.

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

    Műszaki Informatika szak, BSc képzés

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZAB03   2/2/0/v 5  
    3. A tantárgyfelelős személy és tanszék Dr. Friedl Katalin,
    A tantárgy tanszéki weboldala http://cs.bme.hu/algel
    4. A tantárgy előadója

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Csima Judit

    egyetemi docens

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

    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

    6. Előtanulmányi rend
    Kötelező:
    (TárgyEredmény( "BMEVISZAA01" , "aláírás" , _ ) = -1
    VAGY TárgyEredmény( "BMEVISZAA04" , "aláírás" , _ ) = -1)

    ÉS
    NEM ( TárgyEredmény( "BMEVISZA213" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZA213", "FELVETEL", AktualisFelev()) > 0
    VAGY
    TárgyEredmény( "BMEVISZAB01" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZAB01", "FELVETEL", AktualisFelev()) > 0
    VAGY
    TárgyEredmény( "BMEVISZAB01" , "aláírás" , _ ) = -1)

    ÉS (Training.Code=("5N-A8") VAGY Training.Code=("5NAA8"))

    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

    A tantárgy célkitűzése a műszaki informatika tanulmányokhoz szükséges és a mérnöki alapműveltséghez tartozó egyes alapvető matematikai ismeretek elsajátítása, azok szemléletmódjának kialakítása. Ezen belül a tantárgy az automaták és formális nyelvek elméletének, adatstruktúrák és algoritmusok elemzésének egyes területeire nyújt bevezetést.

    A tantárgyat sikeresen teljesítő hallgató képes lesz:

    • (K3)  érteni és alkalmazni a tárgyban előkerülő fogalmakat és ismereteket;

    • (K3)  önállóan megoldani az anyaghoz kapcsolódó gyakorlati feladatokat;

    • (K2)  alkalmazni a tárgyban szereplő algoritmusokat;

    • (K3)  a későbbi tanulmányok során felismerni azokat a helyzeteket, ahol a tárgyban tanult ismeretek szerephez jutnak és sikerrel alkalmazni a tanultakat.



    8. A tantárgy részletes tematikája
    1. Mintaillesztés. Naív algoritmus, Rabin-Karp (ujjlenyomatos) algoritmus. A véges automatás megoldás.

    2. Determinisztikus és nemdeterminisztikus véges automaták, ezek ekvivalenciája. A reguláris kifejezés fogalma, kapcsolata a reguláris nyelvekkel, véges automatákkal (az automatából reguláris kifejezés irány legfeljebb vázlatosan).

      A véges automata mint lexikális elemző.
    1. Környezetfüggetlen nyelvtanok. Levezetési fák, bal- és jobboldali levezetés. Az egyértelműen levezethető szó, egyértelmű nyelvtan, nyelv fogalma, algoritmikus jelentősége.

    2. A (nemdeterminisztikus) veremautomata.

      A veremautomaták és a környezetfüggetlen nyelvek kapcsolata (részletesen a nyelvtanból automata irány). Az elemzés feladata (parser).
    1. A Turing-gép, mint a legáltalánosabb automata. Church-Turing-tézis. A P, NP, coNP osztályok, kapcsolatuk. A Karp-redukció fogalma, NP-teljesség.

    2. Cook-Levin-tétel (vázlatosan), a SAT, 3SAT, 3SZÍN NP-teljessége

    3. További NP-teljes nyelvek:MAXFTL, H, H-út, Utazóügynök, 3DH, RH, Partíció, Hátizsák, Részgráfizo (nagyrészt csak az NP-beliség bizonyításával)

      Nyitott kérdés: a Gráfizo bonyolultsága.
    1. A lineáris és az egészértékű programozás feladata. LP polinom idejű (biz. nélkül),

      IP NP- teljes. Korábbi problémák átfogalmazása egészértékű programozássá.Elágazás és korlátozás (pl. független pontok, színezés)
    1. Dinamikus programozás (pl. Hátizsák, leghosszabb közös részsorozat)

    2. Közelítő algoritmusok: utazóügynök probléma így is nehéz, az euklideszi változatára 2-közelítő algoritmus, Ládapakolásra a FirstFit algoritmus 2-közelítésének bizonyítása, Ibarra-Kim-tétel (tetszőlegesen jól lehet közelíteni) kimondva.

    3. Ö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.

    1. Lineáris és bináris keresés, az utóbbi optimalitása.

      Keresőfa fogalma, tulajdonságai, hatékonysága. A piros-fekete fa.
    1. : 2-3 fa, illetve a B-fa fogalma, tulajdonságai, előnyei. Hash

    2. Ismétlés, összefoglalá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 heti 2 órás gyakorlat.

    10. Követelmények

    A szorgalmi időszakban: A félév folyamán egy nagyzárthelyit íratunk. Az aláírás feltétele a zárthelyi dolgozat sikeres teljesítése.

    A vizsgaidőszakban: A vizsgajegyet a zárthelyi eredményéből és az írásbeli vizsgán kapott pontszámból alakítjuk ki olyan módon, hogy abba a zárthelyi 40 százalék erejéig, a vizsgán kapott pontszám 60 százalék erejéig számít bele.

    Elővizsga: nincs

    11. Pótlási lehetőségek

    A félév során az arra kijelölt időpontban pótzárthelyi, valamint a pótlási héten pótpótzárthelyi írására van lehetőség.

    12. Konzultációs lehetőségek

    Igény szerint.

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

    A tantárgy weboldalán  található leírások,

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

    Csima Judit, Friedl Katalin: Nyelvek és automaták, elektronikus jegyzet

    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 28
    Felkészülés zárthelyire 18
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása 0
    Vizsgafelkészülés 48
    Összesen 150
    15. A tantárgy tematikáját kidolgozta

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Friedl Katalin

    egyetemi docens

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

    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.


    Egyéb megjegyzések

    A zh-n és a vizsgán is 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 zh-n és a vizsgán is 0-19 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.