Algoritmusok és adatszerkezetek I.
- 2 óra előadás (kollokvium), 1 óra gyakorlat (Gyakorlati jegy)
- 3+1 kredit, őszi félév
Tantárgyleírás
A kurzus célja olyan ismeretek elsajátítása, készségek és képességek kifejlesztése, amelyek birtokában a hallgató képes alapvető számítási problémák megoldására korrekt és hatékony algoritmust tervezni, helyességét bizonyítani, hatékonyságát elemezni és képes az algoritmust hatékonyan megvalósítani. A képzési cél eléréséhez a hallgató
Ismerje meg, hogyan lehet számítási probléma helyességét kifejezni, és a helyességet bizonyítani.
Ismerje meg a legfontosabb módszereket algoritmusok futási idejének és tárigényének kifejezésére és elemzésére.
Ismerje meg a legfontosabb absztrakt adattípusokat, és képes legyen azokat felhasználni hatékony algoritmusok készítésére.
Ismerje meg az alapvető adatszerkezeteket, képes legyen adott probléma hatékony megoldásához szükséges adatszerkezeteket megtervezni és megvalósítani.
Ismerje meg az alapvető számítási problémák hatékony megoldását adó algoritmusokat.
Sajátítsa el a legfontosabb probléma-megoldási módszereket (stratégiákat).
Tematika
Bevezető példák. Algoritmus - számítási probléma - specifikáció - programhelyesség - programhelyesség bizonyítása. Beszúró rendezés.
Algoritmusok futási ideje (legjobb, legrosszabb, átlagos). Függvények növekedése, O, ?, ? jelölések. Rekurzió, példák rekurzióra (partíciószám).
Rendezési algoritmusok: kiválasztó, beszúró, kupacrendezés, gyorsrendezés. Műveletigények Absztrakt adatszerkezetek. Elemi adatszerkezetek. Fabejáró algoritmusok. Verem, sor, prioritási sor, absztrakt adattípus
Dinamikus programozás: partíciószám, szerelőszalag ütemezése, mátrixok szorzása, leghosszabb közös részsorozat, hátizsák feladat. Dinamikus programozás alapjai.
Mohó algoritmusok: esemény kiválasztása. Töredékes hátizsák probléma. Huffman kódolás. Mohó algoritmusok tervezése Oszd meg és uralkodj: bináris keresés, rendezés, euklideszi algoritmus.
Gráfok ábrázolása. Gráf adattipus. Utak, szélességi, mélységi keresés. Topologikus rendezés, erősen összefüggő komponensek Minimális feszítőfák: Kruskal és Prim eljárása. Legrövidebb utak Dijkstra módszere. Floyd és Warshall módszere Lineáris elsőfokú homogén, inhomogén egyenletek, megoldásuk Alsó korlát általános rendezési algoritmus legrosszabb esetére. Lineáris rendezések: leszámláló, radix, vödrös. Mediánok és rendezett minták.
Absztrakt adattípusok: verem, sor, prioritás sor, lista, kétirányú lista, tömb, sorozat, halmaz, rhalmaz, függvény, reláció. Megvalósítások. Bináris keresőfa.
Ajánlott irodalom
Adonyi Róbert: Adatstruktúrák és algoritmusok, Typotex Kiadó, 2011.
Jegyzet letöltése PDF formátumban.
Heckl István: Adatstuktúrák és algoritmusok példatár, Typotex Kiadó, 2011.
Jegyzet letöltése PDF formátumban.
T. H. Cormen, C. E. Leiserson, R.L. Rivest, C. Stein: Új algoritmusok, Scolar Informatika Könyvkiadó, 2003.
T. H. Cormen, C. E. Leiserson, R.L. Rivest: Algoritmusok, Műszaki Könyvkiadó, 2003.
D. E. Knuth: A számitógépprogramozás művészete, 1. Kötet, Műszaki Könyvkiadó, 1988. D. E. Knuth: A számitógép-programozás művészete, 3. Kötet, Műszaki Könyvkiadó, 1990.
V. Aho, J. E. Hopcroft, J. D. Ullman: Számítógép-algoritmusok tervezése és analízise, Műszaki Könyvkiadó, 1982.
G. Gonnet, R. Baeza-Yates: Handbook of algorithms and data structures. In Pascal and C. , Addison-Wesley. 1991.
R. Sedgewick: Algoritms in C++, Addison-Wesley. 1991.
E. Horowitz, S. Shani: Fundamentals of Computer Algorithms, Computer Science Press, 1998.
Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok, Tipotex, 1998.
A pub könyvtárban elérhető anyagok:
Nyomtatható változat: ni.pdf (i = 1, . . .) állományokban.
Vetíthető változat: vi.pdf (i = 1, . . .) állományokban.
Gyakorló feladatok gyűjteménye: feladgyujt.pdf
Programok:
/pub/alg/java/*
/pub/alg/I/prog/*.pas
/pub/alg/I/prog/*.c
állományokban.
