Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

     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.

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.

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.

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.

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

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

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.