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: 2011. január 25.

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

    Műszaki Informatika Szak

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

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Friedl Katalin

    Egy. Docens

    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

    Gráfelmélet

    6. Előtanulmányi rend
    Kötelező:
    (TárgyEredmény( "BMEVISZA110" , "aláírás" , _ ) = -1
    VAGY TárgyEredmény( "BMEVISZA031" , "jegy" , _ ) >= 2
    VAGY TárgyEredmény( ahol a TárgyKód = "BMEVIMA1236", ahol a Típus = "VIZSGA", ahol a Ciklus = tetszőleges, ahol a KépzésKód = tetszőleges) >=2
    VAGY Aláírás( ahol a TárgyKód = "BMEVIMA2603", ahol a Ciklus = tetszőleges)
    VAGY TárgyEredmény( "BMEVISZA071" , "jegy" , _ ) >= 2 )
    VAGY KépzésLétezik( ahol a KépzésKód = "9N-MM09")

    ÉS
    NEM ( TárgyEredmény( "BMEVISZAB01" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZAB01", "FELVETEL", AktualisFelev()) > 0)

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

    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:
    Bevezetés a Számításelméletbe II.-ből aláírás
    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

    Kereső algoritmusok. Alapvető adatszerkezetek: keresőfa, kiegyensúlyozott keresőfa (AVL-fa), B-fa, hash-tábla, kupac.

    Rendező algoritmusok: buborék rendezés, beszúrásos rendezés, összefésülés, kupacos rendezés, gyorsrendezés, láda- és radixrendezés.

    Alsó becslés az összehasonlitó rendezések lépésszámára.

    Alapvető gráfelméleti algoritmusok:

    Mélységi és szélességi bejárás, összefüggő és erősen összefüggő komponensek meghatározása, maximális párositás keresése páros gráfban.

    Legrövidebb utak keresése Dijkstra, Bellman-Ford és Ford algoritmussal.

    Minimális költségű feszitőfa keresése Prim módszerével, Kruskal algoritmusa és az unióüholvan adatszerkezet.

    Általános algoritmus-tervezési módszerek: mohó algoritmus, oszd meg és uralkodj, dinamikus programozás, elágazás és korlátozás.

    Közelitő algoritmus a ládapakolás és az euklideszi utazóügynök problémára.

    A bonyolultságelmélet alapjai: kiszámithatóság, NP, NP-teljesség

    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

    c. Elővizsga: nincs

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

     pótzárthelyi

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

    Igény szerint folyamatosan biztosítjuk.

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

    Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok, Typotex, Budapest, 1999.

    T. Cormen, C. Leiserson, R. Rivest, C. Stein: Új algoritmusok, Scolar Kiadó, 2003.

    Feladatgyűjtemény: http://cs.bme.hu/algel/fasor.pdf

    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka

    (a tantárgyhoz tartozó tanulmányi idő körülbelüli felosztása a tanórák, továbbá a házi feladatok és a zárthelyik között (a felkészülésre, ill. a kidolgozásra átlagosan fordítandó/elvárható idők félévi munkaórában, kredit x 30 óra, pl. 5 kredit esetén 150 óra)):

     

    Kontakt óra

    56

    Félévközi készülés órákra

    28

    Felkészülés zárthelyire

    10

    Házi feladat elkészítése

    Kijelölt írásos tananyag elsajátítása

    Zárthelyi megírása..

    2

    Vizsgafelkészülés

    54

    Összesen

    150

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

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Friedl Katalin

    egy. docens

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

    Visza213.rtf