PhD szigorlat Diszkrét matematika számítástudomány tárgyai

Főtárgy:
Diszkrét matematika: 1+2+7.
Számítógéptudomány: 1+3+4.
Operációkutatás: 5+6+7.
Melléktárgy: Bármely kettő a fenti témák közül.

1. Kombinatorika és gráfelmélet: Kombinatorikus analízis, leszámlálások, permutációk, variációk, kombinációk, rekurziók, generátorfüggvények, Fibonacci sorozat, első- és másodfajú Stirling számok, számelméleti partíciók, Catalan számok. Gráfelmélet, gráfelméleti algoritmusok, gráfelméleti alapfogalmak, szélességi és mélységi keresés alkalmazásai, legrövidebb utak, párosítások, folyamok, színezések, Euler- és Hamilton- tételsor, síkbarajzolhatóság, extremalis gráfelmélet, Ramsey típusú tételek.

Irodalom:
Katona Gy. Y. - Recski A. - Szabó Cs.: A számítástudomány alapjai, Typotex, 2002. 1. és 7. fejezetek
N. J. Vilenkin: Kombinatorika, Műszaki Könyvkiadó, 1971.
Hajnal Péter: Összeszámlálási problémák, Polygon, Szeged, 1997.
(*) Lovász L. Combinatorial Problems and Exercises, North-Holland és Akadémiai Kiadó, 1979 és 1993; magyar fordítás: Kombinatorikai problémák és feladatok, Typotex, 1999.
J. A. Bondy - U. S. R. Murty: Graph Theory with Applications, Macmillan Press, 1976.
Katona Gy. Y. - Recski A. - Szabó Cs.: A számítástudomány alapjai, Typotex, 2002. 2. és 3. fejezetek
Diestel: Graph Theory, Springer, 1997 és 2000.
Rónyai L. - Ivanyos G. - Szabó R.: Algoritmusok, Typotex, 1999. 6. fejezet
Hajnal Péter: Gráfelmélet, Polygon, Szeged, 1997.
(*) Lovász L. Combinatorial Problems and Exercises, North-Holland és Akadémiai Kiadó, 1979 és 1993; magyar fordítás: Kombinatorikai problémák és feladatok, Typotex, 1999.

2. Matroidelmélet: Alapfogalmak, ekvivalens jellemzések, algebrai és geometriai reprezentációk, grafikus, kografikus, reguláris és bináris matroidok, matroid particios, metszet és párosítási problémák.

Irodalom:
D. J. A. Welsh: Matroid Theory, Academic Press, 1976. (legalább az 1., 2., 4., 6., 9., 10. és 19. fejezetek)
A. Recski: Matroid Theory and its Applications, Springer, 1989. (legalább a 7., 9., 11. és 13. fejezetek)
(*) J. Oxley: Matroid Theory, Oxford University Press, 1992.

3. Adatstruktúrák: Adatstruktúrák, keresési és rendezési algoritmusok, gráfalgoritmusok listák, tömbök, keresőfák, AVL-fa, 2-3-fa, B-fa, kupacok, hashelés,bináriskeresés, összehasonlítás alapú rendezések, kulcsmanipulációs rendezések, legrövidebb utak, szélességi és mélységi bejárás, minimális költségű feszítőfák, maximális párosítás keresése, maximális folyam keresése)

Irodalom:

A.V. Aho - J. E. Hopcroft - J. D. Ullman: The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974. 2., 3. és 4. fejezetek

M. R. Garey - D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP- Completeness, W. H. Freeman, 1979.

Rónyai L. - Ivanyos G. - Szabó R.: Algoritmusok, Typotex, 1999. (1.,2., 3., 4. és 6. fejezetek)

T. H. Cormen - C. E. Leiserson - R. L. Rivest: Algoritmusok, Műszaki Könyvkiadó, 1997. (II. - V. részek)

(*) D. E. Knuth: The Art of Computer Programming Vol. 3. (Sorting and searching), Addison-Wesley, 1973; magyar fordítás: A számitógép-programozás művészete 3. Keresés és rendezés, Műszaki Könyvkiadó, 1988.

4. Számítási modellek: Számítási modellek, formális nyelvek, számítások bonyolultsága, véges automata, determinizálás, minimalizálás, reguláris kifejezések, veremautomata,Turing gép, RAM gép,Chomsky fele nyelvosztályok, kapcsolatuk a különféle automatákkal, rekurziv ésrekurzivan felsorolható nyelvek, algoritmikusan eldönthetetelen problémák, idő- és tarbonyolultságok, P, PSPACE, NP, NP-teljes nyelvek, véletlent használó Turing-gép randomizált algoritmusok, RP nyelvosztály, Kolmogorov bonyolultság, közelitő módszerek.

Irodalom:
V. Aho - J. E. Hopcroft - J. D. Ullman: The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974. (1., 5., 10. és 11. fejezetek)
J. E. Hopcroft - J. D. Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.
M. R. Garey - D. S. Johnson: Computers and Intractability: Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
Rónyai L. - Ivanyos G. - Szabó R.: Algoritmusok, Typotex, 1999. (1.,6., 7., 8. és 9. fejezetek)
Bach I.: Formális nyelvek, Typotex, 2001.
Lovász L.: Algoritmusok bonyolultsága, ELTE Kiadó
C. H. Papadimitriou: Computational complexity, Addison-Wesley, 1994; magyar fordítás Számítási bonyolultság, Novadat, 1999.

5. Lineáris programozás: A lineáris programozás feladata. Szimplex módszer és különböző variánsai. Degeneráció. A szimplex módszer hatékonysága. Érzékenység vizsgálat, parametrikus analízis. Számítógépes implementációk. A konvex analízis alaptételei. Belső pontos módszerek. Út-követő eljárások. Az affin skálázás módszere. A homogén onduális eljárás.

Irodalom

V. Chvatal: Linear programming, Freeman, 1983.

(*) A. Schrijver: Theory of Linear and Integer Programming, Wiley, 1986.

R. J. Vanderbei: Linear Programming: Foundations and Extensions, Kluwer, 1997.

Prékopa A.: Lineáris programozás I., Bolyai J. Mat. Tars. kiadványa, Budapest, 1968.

6. Sztochasztikus programozás: Statisztikai döntési elvek. Konvexitási tételek.A logkonkáv mértékek elmélete. Általános konvexitási tételek. Statikus sztochasztikus programozási modellek. Valószínűség maximalizálás. Egyedi, illetve együttes valószínűségi korlátokat tartalmazó sztochasztikus programozási feladatok elmélete és megoldási módszerei. Feltételes várható értéket tartalmazó modellek. Véletlen célfüggvényes modellek. Büntetéses sztochasztikus programozás elmélete. Dinamikus sztochasztikus programozási modellek.Kétlépcsős sztochasztikus programozási feladat és matematikai tulajdonságai. Diszkrét valószínűségi vektorváltozóra vonatkozó kétlépcsős sztochasztikus programozási feladat megoldása bázis dekompozíciós módszerrel. A Wets-féle , ‘L-shaped’ megoldási módszer. A sztochasztikus dekompozíció és a feltételes sztochasztikus dekompozíció módszere. Sztochasztikus kvázi-gradiens módszerek. Többlépcsős sztochasztikus programozási feladatok. Bázis dekompozíció és ‘L-shaped’ megoldó módszer a többlépcsős sztochasztikus programozási feladatok esetében. A sztochasztikus programozás néhány alkalmazása. Elektromos energia véletlen hatások melletti termelése és kapacitás bővítése. Erőművi megbízhatósági elemzések. Tó vízkészlet szabályozása. Tározók optimális irányítása. A PERT probléma. Pénzügyi modellek.

Irodalom

(*) Prékopa A.: Stochastic programming, Kluwer és Akadémiai Kiadó, 1995.

Kall, P. Stein Wallace, Stochastic programming, Springer, 1996.

M. S. Bazaraa, H. D. Sherali, C. M. Shetty: Nonlinear Programming, Theory and Algorithms, Wiley, 1994.

7. Kombinatorikus optimalizálás: Legrövidebb út, párosítás és folyamalgoritmusok, matroidos és poliederes módszerek.

Irodalom

W. J. Cook - W. H. Cunningham - W. R. Pulleyblank - A. Schrijver: Combinatorial Optimization, Wiley, 1998. (első 5 fejezet nagy része)

T. H. Cormen - C. E. Leiserson - R. L. Rivest: Algoritmusok, Műszaki Könyvkiadó, 1997. VI. rész.

A. Recski: Matroid Theory and its Applications, Springer, 1989. (legalább a 11., 13. és 17. fejezetek)

M e g j e g y z é s: A (*)-gal jelölt művek nagylélegzetű monográfiák, példatárak, melyeket "háttéranyagként" adtunk meg, de nem kell tartalmukat elsajátítani .