Ü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)
2021/22-es tanév II. félév. 

1. hét Adat, absztrakt adattípus, adatstruktúra. Az algoritmus. Számábrá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 Oktatási szünet

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

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

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

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 Oktatási szünet.

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

13. 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. Feladatok algoritmikus megoldhatósága. P és NP feladatosztályok kapcsolata. P és NP feladatok.

14. hét Pótzárthelyi dolgozat megírása

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

Az aláírás feltétele:

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

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

Elégtelen zárthelyi dolgozat javítására a félév végén, a 14. 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, 2022. február 3. 

(Dr. Házy Attila)

 a tárgy jegyzője