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ó    

    Algoritmusok és gráfok

    A tantárgy angol neve: Algorithms and Graphs

    Adatlap utolsó módosítása: 2018. június 29.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar
    Üzemmérnök-informatikus szak, BProf képzés
    közös tárgy
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZBA01   2/2/0/v 5  
    3. A tantárgyfelelős személy és tanszék Dr. Csima Judit, Számítástudományi és Információelméleti Tanszék
    4. A tantárgy előadója

    Név

    Beosztás

    Tanszék

    Dr. Csima Judit

    egyetemi docens

    Számítástudományi és

    Információelméleti Tanszék

    Dr. Fleiner Tamás

    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. Pach Péter Pál

    egyetemi docens

    Számítástudományi és

    Információelméleti Tanszék

    Dr. Recski András

    Professzor Emeritus

    Számítástudományi és

    Információelméleti Tanszék

    Dr. Szeszlér Dávid

    egyetemi docens

    Számítástudományi és

    Információelméleti Tanszék

    Dr. Wiener Gábor

    egyetemi docens

    Számítástudományi és

    Információelméleti Tanszék

    6. Előtanulmányi rend
    Kötelező:
    Training.Code=("5N-A9")

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

    A kötelező előtanulmányi rendek grafikus formában itt láthatók.

    7. A tantárgy célkitűzése

         Diszkrét matematika alapelemeinek elsajátítása, a problémamegoldó, algoritmikus gondolkodás készségének fejlesztése, alapvető feladattípusok és algoritmusaik elméleti hátterének megismerése. Gráfelmélet alapjainak áttekintése.

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

    ·      (K2)  érteni a gráfelmélet alapfogalmait;

    ·      (K2) felismerni a különböző algoritmus-tervezési technikákat;

    ·      (K3)  érteni és alkalmazni a tanult adatszerkezeteket;

    ·      (K3)  alkalmazni a tárgyban szereplő algoritmusokat gyakorlati feladatok megoldására;

    ·      (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

    Előadás

    Előadás anyaga

    1.

    Algoritmus fogalma, példák: minimális elem kiválasztása, kiválasztásos rendezés. Algoritmus leírása, helyességének belátása, lépésszám becslése   Buborék rendezés.

    2.

    Lineáris keresés. Bináris keresés, az oszd meg és uralkodj elv bemutatása. A nagy ordó jelölés bevezetése. Alsó becslés a keresés lépésszámára.  Beszúrásos rendezés. Összefésüléses rendezés.

    3.

    Alsó becslés az összehasonlítás alapú rendezések lépésszámára (bizonyítás nélkül). Láda és radix rendezés. Bináris fák, fabejárások.

    4.

    Bináris  keresőfák, műveletek ebben, ezek lépésszáma.  Piros-fekete fa említés szintjén. 2-3 fa, B-fa

    5.

    Hash (vödrös és a nyílt címzésűből lineáris és kvadratikus próba)

    6.

    Gráfelméleti alapfogalmak, gráfok megadása, BFS elve, lépésszáma

    7.

    BFS a legrövidebb utakra. DFS elve. Mélységi számozás

    8.

    Topologikus sorrend, DAG, példák ennek alkalmazására ütemzésben, adatbáziskezelésben.  Legrövidebb és leghosszabb utak DAG-ban.

    9.

    Dinamikus programozás elve, példák:  Fibonacci számok kiszámolása, további egyszerű példák

    10.

    Legrüvidebb út keresés általában: Bellman-Ford, Floyd algoritmus

    11.

    Mohó algoritmus elve, példák arra, hogy ez általában nem jó stratégia. Dijkstra algoritmusa

    12.

    Minimális feszítőfa algoritmusok: Kruskal és Prim

    13.

    Bonyolultságelmélet alapjai, informálisan, sok gyakorlati példával

    14.

    Tartalék

     A gyakorlatok anyaga megegyezik az azonos heti előadás anyagával.


    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

    A tárgyból heti 2 óra előadás és heti 2 órás kiscsoportos gyakorlat van.

    Az előadásokon az elmélet kerül bemutatásra,  oly módon, hogy az egyes témák egy-egy gyakorlatban felmerülő problémával indulnak, majd az ennek megoldására használható eszközök, adatszerkezetek, algoritmusok kerülnek bemutatásra. Az előadás közben egyszerű példákon szemléltetjük a tanultakat.

    A tanult fogalmak gyakorlása és feladatokban való alkalmazása az előadáshoz kapcsolódó  kiscsoportos gyakorlatokon zajlik, ahol a hallgatók feladatokat oldanak meg önállóan, igény szerint gyakorlatvezetői támogatással.

    10. Követelmények

    A szorgalmi időszakban: 

    A félév folyamán egy zárthelyit íratunk. A félévvégi aláírás megszerzésének (vagyis a vizsgára bocsátásnak) a feltétele a zárthelyin legalább 40%-os teljesítmény elérése.

    A félév végi aláírás feltételei:

     

    A zárthelyi sikeres megírása.

    A vizsgaidőszakban: 

    Vizsgára az jelentkezhet, aki érvényes aláírással rendelkezik.  A vizsga írásbeli, a vizsga 40%-tól sikeres.

    Az osztályzat megállapításának módja:  A vizsgajegyet a zárthelyi eredményéből és a vizsgán nyújtott teljesítményből alakítjuk ki olyan módon, hogy abba a zárthelyi eredménye 40 százalék, az írásbeli  vizsga eredménye pedig  60 százalék erejéig számít bele.

    A végső jegy az összesen elérhető 100%-ból az elért százalék alapján: 40%-tól elégséges, 55%-tól  közepes, 70%-tól jó, 85%-tól jeles.

    Ha az írásbeli vizsga elégtelen , akkor a vizsgajegy is elégtelen (függetlenül a zárthelyi eredményétől). Ismétlő vizsga esetén a zárthelyiből származó eredmény változatlanul érvényes.

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

    A félév során az arra kijelölt időpontban pótzárthelyi írására van lehetőség. A pótzárthelyin a korábban megírt, eredményes zárthelyi javítása is megkísérelhető, de csak azzal a feltétellel, hogy ilyenkor mindenképpen az új pontszám lesz érvényes, akkor is, ha az rosszabb, mint az eredeti. Ez alól egy kivétel van: ha egy hallgató a normál zárthelyin legalább 40%-os teljesítményt ért el és így az aláírás feltételeit már teljesítette, de a javítónak szánt pótzárthelyin 40% alatti teljesítményt ér el, akkor a hallgató az aláírást megkapja, de a zárthelyiből származó pontszáma a 40%-os eredménynek megfelelő, minimális pontszám lesz.

    Amennyiben a zárthelyi és a pótzárthelyi segítségével sem sikerül az aláírás feltételeit teljesíteni,  lehetőség nyílik a zárthelyi újbóli pótlására.  Ekkor a korábban megírt, sikeres (vagyis a 40%-os teljesítményt elérő) zárthelyi vagy pótzárthelyi eredménye már nem javítható.

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

    A vizsgák előtt konzultációs lehetőséget biztosítunk.

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

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

    Katona Y. Gyula - Recski András - Szabó Csaba: A számítástudomány alapjai, TypoTeX Kiadó, 2003.

    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra56
    Készülés előadásra14
    Készülés gyakorlatra24
    Készülés zárthelyire16
    Vizsgafelkészülés40
    Összesen150
    15. A tantárgy tematikáját kidolgozta

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Csima Judit

    egyetmi docens

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