Ü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)
2015/16-os 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: Oktatási szünet
9. 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.
10. 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.
11. hét: Gráfalgoritmusok. Szélességi
keresés. Mélységi keresés. Topologikus rendezés.
Erősen összefüggő komponensek.
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.
14. 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:
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, 2016.
február 8.
(Dr. Házy Attila)
a tárgy jegyzője