Algoritmusok és adatszerkezetek II.

Tematika:

• Kiegyensúlyozott keresőfák. AVL fák. Piros-fekete fák Önszervező bináris keresőfák. B-fák.
• A Halmaz adattípus megvalósítása ugrólistával (Skiplist) Tördelőtáblák.
• Diszjunkt halmazok kezelése, az UnioHolvan adattípus. A binomiális kupac, egyesíthető prioritási sor.
• A Gráf adattípus, gráfok reprezentációi. Széltében keresés gráfokban. Mélységi keresés gráfokban. Topologikus rendezés. Gráf erősen összefüggő komponenseinek meghatározása. Minimális feszítőfa előállítása; a Kruskal algoritmus. Egy pontból induló legrövidebb utak meghatározása; a Dijkstra algoritmus. Legrövidebb utak meghatározása minden pontpárra; a Floyd-Warshall algoritmus. Mintaillesztés; a Knuth-Morris-Pratt és a Boyer-Moore algoritmusok.

Ajánlott irodalom:

• T. H. Cormen, C.E. Leiserson, R.L. Rivest: Algoritmusok, Műszaki Könyvkiadó, 1998.
• 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épprogramozás művészete, 3. Kötet, Műszaki Könyvkiadó, 1990.
• V. Aho, J. E. Hopcroft, J. D. Ullman: Számitógép-algoritmusok tervezése és analizise, 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.