Tárgyfelelős: Dr. Dósa György és Dr. Tuza Zsolt
Vizsgaanyag: szabadon választott 6 témakör a tematikából, amelyet a vizsgázó előzetesen egyeztet a vizsgáztatóval.
Irodalom: a vizsgáztató jelöli ki a vizsgázó által választott témakörök alapján
1. Algoritmikus problémák kiszámítási komplexitása: Problématípusok (eldöntési stb.), determinisztikus és nemdeterminisztikus Turing gép, Church-Turing hipotézis. P, NP, co-NP, PTAS, APX osztályok, eldönthetetlenség. NP- és APX-teljesség, alapvető problémák komplexitása, redukciós elvek.
2. Adatszerkezetek, rendező és kereső algoritmusok: Elemi adatstruktúrák, összehasonlításon alapuló rendezések, információelméleti alsó korlát, kupac, összefésülő rendezés, keresőfák. Rendezés lineáris időben, medián keresés és rendezési statisztikák. Hash-tábla, gyorsrendezés, véletlen bináris keresőfa, (2,3)-fák.
3. Gráfok és fák bejárásai, alkalmazások: Euler-vonal, Hamilton-kör, szélességi és mélységi keresés, összefüggő és erősen összefüggő komponensek, pre-, in-, postorder bejárás, utazó ügynök probléma, kínai postás probléma.
4. Gráf- és hálózatoptimalizálási algoritmusok: Legrövidebb utak, minimális súlyú feszítőfák. Maximális párosítások, „magyar módszer”, hálózati folyamok, Menger-útrendszerek. Lineáris idejű algoritmusok korlátos favastagságú gráfokon, kapcsolat a monadikus másodrendű logikával.
5. Gráfszínezések: Általános becslések kromatikus számra és -indexre, kapcsolat irányíthatósággal. Síkgráfok színezhetősége. Approximálhatóság és online színezés. Perfekt gráfok, speciális osztályaik (komplementer-redukálható gráfok, merevkörű ill. páros gráfokból származtatott perfekt osztályok), karakterizáció, algoritmusok. Perfekt gráf tétel.
6. Approximációs algoritmusok: A ládapakolás klasszikus algoritmusai, mint Next Fit, First Fit, First Fit Decreasing, Best Fit, Any Fit, Worst Fit. Ezek aszimptotikus és abszolút approximációs arányai. A súlyfüggvény technika (FF klasszikus súlyfüggvénye, és annak Sgall-féle felbontása, az amortizációs lemma).
7. Az ütemezéselmélet klasszikus eredményei: Párhuzamos gépek ütemezése, teljes átfutási idő minimalizálás. A Graham-féle List Scheduling algoritmus, és annak rendezett változata, a Longest Processing Time algoritmus. Ezek hatékonyságbecslése, az élességet bizonyító inputok. A Multifit algoritmus. Approximációs séma a Pm | | Cmax feladatra. Online ütemezés: A Pm | | Cmax feladat online algoritmusai (LS, és annál jobb hatékonysággal rendelkező algoritmusok).
8. Az LP feladatok általános alakja, a primál szimplex módszer, optimalitási feltételek, több-szempontú optimalizálás, cél programozás.
9. Dualitás a lineáris programozásban. Gyenge és erős dualitási tételek. Duál megengedettség és a primál optimalitás kapcsolata, a duál szimplex algoritmus.
10. Többváltozós nem-korlátozott problémák megoldási módszerei. Meredek irány módszerek, Newton módszere, konjugáltság, konjugált irányok módszere.
11. Feltételes optimalizálási problémák. Általános alak, egyenlőség és egyenlőtlenség feltételek, elsőrendű szükséges optimalitási feltételek, másodrendű optimalitási feltételek, Lagrange függvény, Kuhn-Tucker tétel.
12. Egészértékű programozás, a feladat formalizálása, relaxált feladat, egészértékű feladatok, megoldási módszerek, legfontosabb modellek, korlátozás és szétválasztás alapú algoritmusok.
13. Heurisztikák alkalmazása egészértékű feladatok megoldására (becslések, genetikus algoritmusok, tabu keresés, szimulált hűtés). Utazóügynök probléma. Heurisztikák utazó ügynök probléma megoldására. Halmazlefedési probléma: matematikai modellek és heurisztikák.
14. Intervallum aritmetika, intervallum felosztási módszerek, gyorsító eszközök, intervallumos Newton eljárás, konvergencia sebessége.