ÜTEMTERV

Adatstruktúrák és algoritmusok

c. tárgyhoz (GEMAK241BL)

BSc programtervező informatikus alapszak, levelező tagozat számára

Óraszám: 20

2016/17-es tanév II. félév. 

Adat, absztrakt adattípus, adatstruktúra. Az algoritmus. Számárzázolások. Pszeudokód és folyamatábra. Az algoritmus minőségi jellemzői. Függvények növekedésének jellemzése, az ordo szimbolika. A Fibonacci számok, Binet formula. Rekurrens egyenletek, mester tétel. Számelméleti algoritmusok. Legnagyobb közös osztó, euklideszi és kibővített euklideszi algoritmus, lineáris kongruencia egyenletek. Multiplikatív inverz, moduláris hatványozás, Fermat prímteszt. RSA. Az absztrakt adatszerkezetek ábrázolásának módszerei. Dinamikus halmazok. Tömb, láncolt lista, verem, sor és tipikus alkalmazásaik. Keresés egyszerű struktúrákban: lineáris, logaritmikus keresés. Hasító táblák. Kiválasztási problémák. Minimum és maximum keresése. Kiválasztás lineáris idő alatt. Beszúró rendezés. Az oszd meg és uralkodj elv. Összefésülő rendezés, gyors rendezés. Időelemzéseik. Az összehasonlító rendezések időtétele. A Batcher-féle összefésülés és tétele. Buborék rendezés, Shell rendezés, minimum kiválasztásos rendezés, négyzetes rendezés. Lineáris idejű rendezések: leszámláló, radix, edényrendezés. Külső tárak rendezése és a gyorsítás. Elemi gráfelméleti bevezető. A fa szerkezet, a nyílt fák tulajdonságainak tétele, műveletek. Gyökeres fák és ábrázolásuk, bináris fák, kupac. Kupacrendezés. Az elsőbbségi sor. Mohó algoritmusok. A Huffmann kód. Diszjunkt halmazok. Binomiális fák, binomiális kupac. Keresési technikák. Bináris keresőfák. Piros-fekete fák. Gráfalgoritmusok. Szélességi keresés. Mélységi keresés. Topologikus rendezés. Erősen összefüggő komponensek. Optimumfeladatok fákon. Minimális feszítőfák. Kruskal és Prim algoritmus. Adott csúcsból induló legrövidebb utak. a fokozatos közelítés. Dijkstra algoritmus. Bellman-Ford algoritmus. Körmentes irányított gráfban legrövidebb utak. Legrövidebb utak minden csúcspárra. Floyd-Warshall algoritmus. Gráfok tranzitív lezártja, a Warshall algoritmus. A dinamikus programozás elve. Alkalmazás mátrixok véges szorzatainak optimalizálására. Feladatok algoritmikus megoldhatósága. P és NP feladatosztályok kapcsolata. P és NP feladatok.

A tárgy lezárásának módja: aláírás, kollokvium

A vizsga írásbeli. Meg nem engedett eszközök használata esetén a vizsga elégtelen és további vizsga abban a vizsgaidőszakban csak szóban, bizottság előtt, a tanszék által megadott időpontban lehetséges. Az írásbeli vizsga nyolc elméleti kérdést és négy gyakorlati feladatot tartalmaz. Mindkét rész jeggyel zárul és 50-50%-ban kerül be a végleges vizsgajegybe, ha egyikük sem elégtelen, egyébként a vizsgajegy elégtelen.

Ajánlott irodalom:

1.  Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Algoritmusok Műszaki Könyvkiadó 2001, Budapest ISBN 963 16 3029 3

2. Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok TypoTEX Kft. Elektronikus Kiadó, 1999 ISBN 963 9132 16 0

3. Házy Attila, Nagy Ferenc: Adatstruktúrák és algoritmusok, 
Miskolci Egyetem, 2011 elektronikus jegyzet TÁMOP-4.1.2-08-/1/A-2009-004

Miskolc, 2017. jauár 31. 

(Dr. Házy Attila)

 a tárgy jegyzője