INFORMATIKAI KAR DOKTORI PROGRAM
SZIGORLATI TEMATIKA

Algoritmusok tervezése és elemzése


Az alapvetõ számítási modellek (rekurzív függvények, Turing-gépek, RAM -gépek), a három számítási modell egyenértékûsége. Algoritmikusan nem megoldható problémák.
A számítógépes algoritmusok elemzésének alapelemei. Idõ- és tárbonyolultság, függvények aszimptotikus viselkedése, függvények rekurzív definiciója és a rekurzió felodásának módszerei (helyettesítõ módszer, a rekurziós fa módszer, mester módszer, a mester tétel biszonyítása), valószíûségi elemzés.
A gyakolat szempontjából legfontosabb feladatosztályok: P, NP, NPC. A legfontosabb NPC feladatok.
A rendezési feladat. Összehasonlításos rendezõk, az összehasonlítások számára vonatkozó elméleti korlátok. A legfontosabb összehasonlításos rendezõk és elemzésük ( buborék, egyszerû beillesztés, gyors-rendezõ, heap-rendezõ, Shell-rendezõ, összefuttatásos rendezõ, rendezõ-fa).
A rendezési feladat. Hasító függvényeket használó rendezõk (edény rendezés, számjegy-pozíciós rendezés, leszámláló rendezés).
A rendezési feladat. Külsõ rendezõk. (több fázisú összefuttatatás, kiegyensúlyozott és Fibonacci változat, a futamok hosszának növelése helyettesítéses kiválasztással).
Rendezõ hálózatok.
Kiválasztások (maximum, párhuzamos maximum-minimum, k. elem és medián). Elméleti alsó korlátok és optimális algoritmusok.
Keresési feladat. Hasító táblázatok ( közvetlen címzésû táblázatok, hasító táblázatok, a kulcsütközések feloldásának módszerei, a nyílt címzés, a hasító függvények konsturkciós módszerei).
Keresési feladat. Lineáris keresés rendezetlen és rendezett sorozatban. Keresésõ fák (egyszerû keresõ fa, optimális keresõ fa, AVL-fák, piros-fekete fák, 2-3 fák, B-fák, S-fák, szó-fák).
Mûveletek szövegeken. Mintaillesztõ algoritmusok (brute force, Knuth-Morris-Pratt, Boyer-Moore, Karp-Rabin, Dömölky-szûrõ, automatákon alapuló módszerek). A leghosszabb közös részsorozat megkeresése.
Elemi gráfos algoritmusok (szélességi bejárás, mélységi bejárás, topológikus rendezés, összefüggõ komponenesek, erõsen összefüggõ komponensek, legrövidebb utak).
Fejlettebb gráfos algoritmusok (minimális feszítõfák, adott csúcsból induló legrövidebb utak, legrövidebb utak minden csúcspárra).
Geometriai algoritmusok (algoritmusok szakaszokra, ponthalmaz konvex burka, az egymáshoz legközelebbi két pont megkeresése).


Irodalom:

N. Wirth, Algoritmuslok + Adatstruktúrák = Programok, M?szaki Könyvkiadó, 1982.
A. Aho, J. Hopcroft, J. Ullman, Számítógép-algoritmusok tervezése és analízise, M?szaki Könyvkiadó, 1982.
D.E. Knuth, A számítógépprogramozás m?vészete, I. és III., M?szaki Könyvkiadó, 1987.
Sara Baase, Computer algorithms, Addison-Wesley, 1988.
Ivanyos Gábor, Rónyai Lajos, Szabó Réka, Algoritmusok elmélete, Typotext, Budapest, 1994.
C. H. Papadimitriu, Computational Complexity, Addison-Wesley Publishing Company, Inc., 1994. (magyar fordítása megjelent 1999-ben a Novodat kiadásában, fordító-szerkesztõ Ésik Zoltán)
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C Stein, Új algoritmusok, Scolar Informatika, 2003.