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,
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