ÜTEMTERV

Adatstruktúrák és algoritmusok

c. tárgyhoz (GEMAK241B)

BSc programtervező informatikus alapszakok számára

Óraszám: heti 2+2, (aláírás+kollokvium, 5 kredit)
2014/15-es tanév II. félév. 

1. hét:  Adat, absztrakt adattípus, adatstruktúra. Az algoritmus. Számárzázolások.

2. hét: 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.

3. hét: 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.

4. hét: 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.

5. hét: 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.

6. hét:  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.

7. hét: 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. 

8. hét: Az elsőbbségi sor. Mohó algoritmusok. A Huffmann kód. Diszjunkt halmazok.

9. hét: Binomiális fák, binomiális kupac. Keresési technikák. Bináris keresőfák. Piros-fekete fák.

10. hét:  Gráfalgoritmusok. Szélességi keresés. Mélységi keresés. Topologikus rendezés. Erősen összefüggő komponensek.

11. hét: 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. 

12. hét: 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.

13. hét: 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

Az aláírás feltétele:

• Három zárthelyi dolgozat legalább elégséges szintű megírása.

A félév során két elméleti zárthelyi dolgozat lesz a 5. és 10. oktatási héten, valamint egy gyakorlati feladatokból álló zárthelyi dolgozat a 12. héten.

Elégtelen zárthelyi dolgozat javítására a félév végén, a 13. héten nyílik lehetőség pótzárthelyi dolgozat írásával, melynek anyaga megegyezik azzal, aminek a pótlására szolgál. Ha ez is elégtelen, akkor a vizsgaidőszakban az egész félév anyagából kell zárthelyi dolgozatot írni.

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.

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, 2015. február 8. 

(Dr. Házy Attila)

a tárgy jegyzője