Algoritmusok és adatszerkezetek I.

Tematika:

• Alapfogalmak: számítási probléma, specifikáció, algoritmus, algoritmus helyessége, a problémamegoldás fázisai.
• Adatmodellek. Rekurzió (particiószám, Hanoi tornyai, postfix konverzió). Aszimptotikus jelölések.
• Egyszerű rendezési algoritmusok: kiválasztó rendezés, beszúró rendezés.
• A kupacrendezés. A gyorsrendezés. Lineáris idejű rendezési algoritmusok (számláló, radix, vödrös). Mediánok és rendezett minták; k-adik legkisebb elemet kiválasztó algoritmusok. Külső rendezési algoritmusok; összefésülő és partícionáló rendezések.
• Dinamikus programozás (particiószám, pénzváltás, optimális bináris keresőfa).
• A mohó stratégia (egységnyi végr. munkák ütemezése, Huffman kód). Megoldás szisztemetikus keresése visszalépéssel (pénzváltás).
• Megoldás szisztemetikus keresése elágazás-korlátozással (ütemezés).
• A Verem, Sor, Lista, és Prioritási sor absztrakt adattípusok és megvalósításuk. A Halmaz és a Függvény adattípusok és megvalósításaik. Fák, bináris keresőfák.

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