BME MATEMATIKA MESTERSZAK (MSc)

Szakmai törzsanyag tárgyainak tárgyleírása

A hallgatónak összesen 30 kreditet kell e tárgyakból teljesítenie, ami hat tárgyat jelent e felkínált tizennégyből. A hallgató tárgyválasztásának megfelelően széles tematikus spektrumot kell lefednie. Ezen előírás pontos részletei a mintatanterv táblázatból olvasható ki.

Jelölés: Az egyes tárgyak leírásában megjelentetett e/g/l/t/k jelölés feloldása

e = előadások heti óraszáma,

g = gyakorlatok heti óraszáma,

l = laboratóriumi foglalkozások heti óraszáma,

t = teljesítés módja = v(izsga) vagy f(élévközi jegy),

k = kreditszám.

Globális optimalizálás 3/1/0/f/5

Tárgyfelelős: Tóth Boglárka

További oktatók: Mádi-Nagy Gergely

Globális optimalizálási feladatok különböző alakjai, ezek egymásba való átalakításai, redukálása egydimenziós feladatra.

A globális optimalizálási feladat műveletigényének viszonya a lineáris programozáséhoz.

A globális optimalizálási módszerek osztályozásai. Lagrange-függvény, Kuhn–Tucker tétel, konvex-, DC programozás.

Sztochasztikus programozás alapmodelljei, megoldó módszerek.

Sztochasztikus és multi-start eljárások globális optimalizálásra, konvergenciájuk, megállási feltételeik.

Lipschitz konstansra támaszkodó eljárások, konvergenciatételek.

Korlátozás és szétválasztás módszere, intervallum aritmetikán alapuló eljárások, automatikus differenciálás.

Több célfüggvényes optimalizálás.

Irodalom:

R. Horst and P. Pardalos: Handbook of Global Optimization, Kluwer, 1995

R. Horst, P.M. Pardalos, and N.V. Thoai: Introduction to Global Optimization, Kluwer, 1995

A. Törn and A. Zilinskas: Global Optimization, Springer, 1989

Lineáris programozás 3/1/0/v/5

Tárgyfelelős: Szántai Tamás

További oktatók: Hujter Mihály

Konvex poliéderek. Minkowski tétel, Farkas tétel, Weyl tétel, Motzkin felbontási tétele. A lineáris programozás feladata, példák lineáris programozási feladatra, grafikus szemléltetés. A lineáris programozási feladat megengedett megoldásának, bázismegoldásának fogalma, a szimplex módszer alap algoritmusa. A ciklizálás és annak kizárási lehetőségei: lexikografikus szimplex módszer, Bland szabály alkalmazása. Induló megengedett bázis keresése, a kétfázisú szimplex módszer. Az explicit bázisinverz és a módosított szimplex módszer. A lineáris programozás dualitás elmélete. Kiegészítő eltérések tételei. A játékelmélet. Kétszemélyes zéróösszegű játékok elmélete, Neumann János tétele. A duál szimplex módszer és a metszősík algoritmusok. A Gomory-féle metszősík algoritmus egészértékű programozási feladatok megoldására. Speciális lineáris programozási, illetve arra visszavezethető feladatok. Szállítási feladat, gráfelméleti alapfogalmak és azok alkalmazása a szállítási feladat szimplex módszerrel történő megoldására (‘stepping stone’ algoritmus). Duál változók módszere az optimalitás teszt gyors végrehajtására. Hozzárendelési feladat, Kőnig-Egerváry tétel és a magyar módszer. Hiperbolikus programozási feladat visszavezetése lineáris programozásra a Martos-féle módszerrel. Szeparábilis programozási feladat. Egyedi felső korlát technika. A Dantzig-Wolfe dekompozíciós eljárás, ellipszoid módszer és a belső pontos algoritmusok vázlata.

Irodalom:

Prékopa András: Lineáris programozás, I. Bolyai János Matematikai Társulat, 1968  

A. Schrijver: Theory of Linear and Integer Programming, John Wiley, New York, 1986

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

Elméleti számítástudomány 3/1/0/f/5

Tárgyfelelős: Ferenczi Miklós

További oktatók: Rónyai Lajos, Ivanyos Gábor, Friedl Katalin

A logikai programozás és gépi bizonyítas elméleti alapjai. Véges modellek és bonyolultság. Nem-klasszikus logikák a számítástudományban: temporális, dinamikus, program logikák. Rekurzív függvények és a lambda-kalkulus kapcsolata. Boole-algebrák, reláció algebrák és alkalmazásaik.

Fontosabb gépmodellek. Bonyolultságelméleti alapfogalmak, nevezetes idő és térosztályok. NP-teljesség. Randomizált számítások. Algoritmustervezési módszerek.

Fejlett adatszerkezetek, amortizációs elemzés. Mintaillesztés szövegben.

Adattömörítés.

Irodalom:

Carmen, T.H., Leiserson, C.E., Rivest: Algoritmusok, Műszaki Kiadó, 1999

Rónyai L., Ivanyos G., Szabó R.: Algoritmusok, Typotex, 2001

Ferenczi M.: Matematikai Logika, Műszaki Kiadó, 2002

Galton, A.: Logic for Information Technology, Wiley, 1990

Algebrai és általános kombinatorika 3/1/0/v/5

Tárgyfelelős: Friedl Katalin

További oktatók: Küronya Alex, Recski András, Szeszlér Dávid, Wiener Gábor

A Young-tablók kombinatorikája, tablógyűrűk, Pieri-formulák, Schur-polinomok, Kostka-számok. Robinson–Schensted–Knuth megfeleltetés. Littlewood–Richardson-számok és -tétel. Nevezetes szimmetrikus polinomok és generátorfüggvényeik, Cauchy–Littlewood formulák. A szimmetrikus polinomok alaptételének Garsia-féle általánosítása. Bázisok a szimmetrikus függvények gyűrűjében.

Fejezetek a kombinatorikus optimalizálás módszereiből: Mohó algoritmus, javító algoritmusok, matroid-elméleti alapfogalmak, matroid metszet algoritmus. Közelítő algoritmusok (pl. halmazfedés, Steiner-fák, utazó ügynök probléma). Ütemezési algoritmusok (egygépes ütemezés, ütemezés párhuzamos gépekre, ládapakolás).

irodalom:

William Fulton, Young Tableaux: With Applications to Representation Theory and Geometry (London Mathematical Society Student Texts) (Paperback), Cambridge University Press, 1996

Richard P. Stanley: Enumerative Combinatorics I.- II., Cambridge University Press, 2001

Dinamikai rendszerek 3/1/0/v/5

Tárgyfelelős: Garay Barnabás

További oktatók: Bálint Péter, Simon Károly

Folytonos és diszkrét idejű dinamikai rendszerek, folytonos versus diszkrét: követőfüggvény, diszkretizáció.
Egyensúlyi helyzetek lokális elmélete: Grobman–Hartman lemma, stabil-instabil-centrális sokaság, Poincaré normálforma.
Attraktorok, Ljapunov-függvények, LaSalle-elv, fázisportré.
Strukturális stabilitás, egyensúlyi helyzetek/fixpontok és periodikus megoldások elemi bifurkációi, bifurkációs görbék biológiai modellekben.
Sátor és logaritmikus függvények, Smale-patkó, szolenoid: topológiai, kombinatorikus, mértékelméleti tulajdonságok. Káosz a Lorenz-modellben.

Irodalom:

P. Glendinning: Stability, Instability and Chaos, Cambridge University Press, Cambridge, 1994
C. Robinson: Dynamical Systems, CRC Press, Boca Raton, 1995
S. Wiggins: Introduction to Applied Nonlinear Analysis and Chaos, Springer, Berlin, 1988

Fourier analízis és függvénysorok 3/1/0/v/5

Tárgyfelelős: Kroó András

További oktatók: Horváth Miklós, Járai Antal, G. Horváth Ákosné

A trigonometrikus rendszer teljessége. Fourier-sorok. A Parseval képlet és alkalmazásai. Ortogonális függvényrendszerek, Legendre polinomok, Haar- és Rademacher-féle rendszerek. Bevezetés a waveletekbe, wavelet ortonormált rendszerek és alkalmazásaik. Integrálható függvények Fourier-transzformaciója.

Laplace-transzformáció és alkalmazásai. Fourier-sorok konvergenciája, Dirichlet-féle formula, Dini és Lipschitz konvergencia kritériumok. Fejér példája divergens Fourier sorra. Fourier-sorok összegezése, Fejér tétele, az Abel–Poisson-féle módszer.

Weierstrass approximációs tétele, Stone tétele és annak alkalmazásai. Legjobb megközelítés Hilbert-terekben, Müntz tétele a hézagos polinomok sűrűségéről.

Lineáris operátorokkal való közelités, Lagrange interpoláció, Lozinski–Harshiladze-tétel. A legjobb polinomapproximáció hibabecslése, Jackson tételei. Pozitív lineáris operátorok approximációs tulajdonságai, Korovkin tétele, Bernstein polinomok, Hermite–Fejér operátor. Bevezetés a spline-approximációba, B-spline-ok, spline-ok konvergencia-tulajdonságai.

Irodalom:

N.I. Ahijezer: Előadások az approximáció elméletéről, Akadémiai Kiadó, Budapest, 1951
Szökefalvi-Nagy Béla: Valós függvények és függvénysorok, Tankönyvkiadó, Budapest, 1975
G. Lorentz, M.V. Makovoz: Constructive Approximation, Springer, 1996
M.J.D. Powell: Approximation Theory and methods, Cambridge University Press, 1981

Parciális differenciálegyenletek 2 3/1/0/f/5

Tárgyfelelős: Fritz József

További oktatók: Garay Barnabás, Járai Antal

A Laplace-operator Szoboljev térben (ismétlés a BSc anyag alapján).
Másodrendű lineáris parabolikus egyenletek gyenge és erős megoldásai. Ritz–Galerkin approximáció. Lineáris operátorfélcsoportok (Evans és Robinson szerint).
Reakció-diffúzió (kvázilineáris parabolikus) egyenletek gyenge és erős megoldásai. Ritz–Galerkin approximáció. Nemlineáris operátorfélcsoportok (Evans és Robinson szerint).
Csak példákban: monotonitás, maximum-elvek, invariáns tartományok, egyensúlyi helyzet stabilitásának vizsgálata linearizálással, utazó hullámok (Smoller szerint).
Globális attraktor. Inerciális sokaság (Robinson szerint).

Irodalom:

L.C. Evans: Partial Differential Equations, American Mathematical Society, Providence, 2002
J. Smoller: Shock Waves and Reaction-Diffusion Equations, Springer, Berlin, 1983
J.C. Robinson: Infinite-dimensional Dynamical Systems, Cambridge University Press, 2001

Sztochasztikus analízis és alkalmazásai 3/1/0/v/5

Tárgyfelelős: Simon Károly

További oktatók: Székely Balázs, Tóth Bálint, Fritz József

Bevezetés, ismétlés: Markov-folyamat, sztochasztikus félcsoport, infinitezimális generátor, martingál, megállási idő.

Brown-mozgás: Brown-mozgás fenomenologikus leírása, véges dimenziós peremeloszlások, és folytonosság. Wiener-folyamat konstrukciója, erős Markov tulajdonság. Rekurrencia, skálázás, idő megfordítás. Tükrözési elv és alkalmazásai. Trajektóriák majdnem biztos analitikus tulajdonságai: folytonosság, Hölder-tulajdonság, nem differenciálhatóság, kvadratikus variáció, szinthalmazok.

Folytonos martingálok: Definíció és jellemzés. Schwartz–Dubbins tétel. Exponenciális martingál.

Lévy-folyamatok: Független és stacionárius növekmények, Lévy–Hincsin formula és a folyamatok felbontása. Konstrukció Poisson pont folyamat segítségével. Szubordinátor folyamatok. Stabilis folyamatok. Példák és alkalmazások.

Sztochasztikus integrálás I.: Diszkrét sztochasztikus integrálás bolyongás szerint és diszkrét idejű martingál szerint. Alkalmazások, diszkrét Black–Scholes. Sztochasztikus integrálás Poisson-folyamat szerint. Diszkrét állapotterű Markov-folyamat martingáljai. Kvadratikus variáció, Doob–Meyer felbontás.

Sztochasztikus integrálás II.: Jósolható folyamatok és az Itô-integrál Wiener-folyamat szerint kvardatikus variáció folyamat. Doob–Meyer-felbontás. Itô-formula és alkalmazásai.

Irodalom:

K.L. Chung, R. Williams: Introduction to stochastic integration. Second edition. Birkauser, 1989

R. Durrett: Probability: theory and examples. Second edition. Duxbury, 1996

B. Oksendal: Stochastic Differential equations. Sixth edition. Springer, 2003

D. Revuz, M. Yor: Continuous martingales and Brownian motion. Third edition. Springer, 1999

G. Samorodnitsky & M. S. Taqqu: Stable Non-Gaussian Random Processes: Stochastic

Models with Infinite Variance. Chapman and Hall, New York, 1994

válogatott cikkek, előadó jegyzetei

Statisztika és információelmélet 3/1/0/f/5

Tárgyfelelős: Bolla Marianna

További oktatók: Györfi László

Becslések és hipotézisvizsgálat többdimenziós paramétertérben: Fisher-információs-mátrix, likelihood-hányados-próba. Hipotézisvizsgálat többdimenziós Gauss-modellben: Mahalanobis-távolság, Wishart-, Hotelling-, Wilks-eloszlások. Lineáris becslések, Gauss–Markov-tétel. Regresszióanalízis, egy- és többszempontos varianciaanalízis, mint lineáris modell. ANOVA-táblázatok, Fisher–Cochran-tétel. Főkomponens- és faktoranalízis. Faktorok becslése és forgatása, hipotézisvizsgálatok a faktorok számára.

Hipotézisvizsgálat és I-divergencia (diszkrét eset).

I-vetületek, exponenciális eloszláscsalád esetén a maximum likelihood becslés, mint I-vetület. A megfelelő I-divergencia-statisztika határeloszlása. Kontingenciatáblázatok analízise információelméleti módszerrel, loglineáris modellek. Információelméleti alapú statisztikai algoritmusok: iteratív arányos illesztés, EM-algoritmus. Maximális entrópia módszere.

Irodalom:

M. Bolla, A. Krámli: Statisztikai következtetések elmélete, Typotex, Budapest, 2005

I. Csiszár, P. C. Shields: Információelmélet és statisztika. Oktatási segédanyag (angolul).

Alapok és trendek a kommunikáció- és információelméletben c. kiadványnak 420-525. oldala, Now Publ. Inc., Hollandia, 2004. (Szintén elérhető a Rényi Intézet www.renyi.hu honlapján, Csiszár Imre oktatási segédanyagainál.)

Kommutatív algebra és algebrai geometria 3/1/0/f/5

Tárgyfelelős: Küronya Alex

További oktatók: Horváth Erzsébet, Rónyai Lajos

Zárt algebrai halmazok és koordinátagyűrűik, morfizmusok, irreducibilitás, dimenzió, Hilbert-féle Nullstellensatz, radikálideálok és részvarietások közti megfeleltetés.

Monomiális rendezések, Gröbner-bázisok, Buchberger-algoritmus, számítások polinomgyűrűkben.

Reguláris függvényektől a racionális leképezésekig, lokális gyűrű, kévék alapfogalmai, gyűrűzött terek.

Projektív tér és részvarietásai, homogén koordinátagyűrű, morfizmusok, projektív varietás képe zárt.

Geometriai konstrukciók: Segre- és Veronese-leképezések, Grassmann-varietások, pontból történő vetítés, felfújás.

Affin és projektív varietások dimenziója, hiperfelületek.

Sima varietások, Zariski-érintőtér, Jacobi-feltétel.

Hilbert-polinom és Hilbert-függvény, példák, számítógépes kísérletek.

Gyűrűk és modulusok alapfogalmai, láncfeltételek, szabad modulusok.

Végesen generált modulusok, Cayley–Hamilton-tétel, Nakayama-lemma.

Lokalizáció és tenzorszorzat.

Modulusok szabad feloldásai, modulusok Gröbner-elmélete, számítások modulusokkal, a Hilbert-féle kapcsolat-tétel.

Irodalom:

Andreas Gathmann: A. Gathmann, Algebraic geometry, notes for a one-year course taught in the Mathematics International program at the University of Kaiserslautern (2003) , http://www.mathematik.uni-kl.de/~gathmann/en/pub.html

I.R. Shafarevich: Basic Algebraic Geometry I.-II., Springer Verlag (1995)

Miles Reid: Undergraduate Commutative Algebra, Cambridge University Press (1996)

Robin Hartshorne: Algebraic Geometry, Springer Verlag (1977)

M.F. Atiyah, I.G. Macdonald: Introduction to commutative algebra, Addison Wesley Publishing (1994)

Reprezentációelmélet 3/1/0/f/5

Tárgyfelelős: Küronya Alex

További oktatók: Szenes András

Differenciálható sokaságok, atlasz, sokaságok közti leképezések, immerzió, szubmerzió, részsokaság, érintő; tér, vektormező, Lie-derivált (szükség esetén topológiai hézagpótlás: kompaktság, összefüggőség, homotópia, fundamentális csoport).

Vektornyalábok, alternáló formák vektortereken, differenciálformák és integrálásuk, Stokes-tétel (bizonyítás nélkül).

Multilineáris algebrai konstrukciók (tenzorszorzat, szimmetrikus és alternáló szorzat, összehúzás) és alkalmazásuk vektornyalábokra.

Lie-csoportok definíciója és alapvető tulajdonságaik, exponenciális leképezés, invariáns vektormezők, Lie-csoport Lie-algebrája.

Mátrix Lie-csoportok és Lie-algebráik, fontos példák.

Csoportok reprezentációelmélete általában, karakterek, lineáris algebrai konstrukciók, Lie-csoportok folytonos reprezentációi, összefüggés Lie-csoportok és a hozzájuk tartozó Lie-algebrák reprezentációi között.

Lie-algebrák alapjai, derivációk, nilpotens és feloldható Lie-algebrák, Engel és Lie tételei, Jordan-Chevalley felbontás, Cartan-féle és maximális torális részalgebrák.

Féligegyszerű Lie-algebrák, Killing-forma, reprezentációk teljes felbonthatósága.

Az sl_2 Lie-algebra reprezentációelmélete, gyökrendszerek, Cartan-mátrix, Dynkin-diagram, gyökrendszerek osztályozása, féligegyszerű Lie-algebrák.

Mátrix Lie-csoportok reprezentációi, Weyl-kamrák, Borel-részalgebra.

Peter-Weyl tétel.

Irodalom:

Glen Bredon: Topology and Geometry, Springer Verlag (1997)

Jürgen Jost: Riemannian Geometry and Geometric Analysis, 4. kiadás, Springer Verlag (2005)

William Fulton, Joseph Harris: Representation Theory: a First Course, Springer Verlag (1999)

Daniel Bump: Lie Groups, Springer Verlag (2004)

James E. Humphreys: Introduction to Lie Algebras and Representation Theory, Springer Verlag (1997)

Differenciálgeometria és topológia 3/1/0/v/5

Tárgyfelelős: Szenes András

További oktatók: Szabó Szilárd

Sima sokaságok, differenciál-formák, külső deriválás, Lie-deriválás. Stokes tétele,

de Rham-kohomológia, Poincaré-lemma, Mayer–Vietoris egzakt sorozat, Poincaré-dualitás. Riemann-sokaságok, Levi–Civitá konnexió, görbületi tenzor, állandó görbületű terek. Geodetikusok, exponenciális leképezés, geodetikus teljesség, a Hopf–Rinow tétel, Jacobi-mezők, a Cartan–Hadamard-tétel, Bonnet tétele.

Irodalom:

J. M. Lee: Riemannian Manifolds: an Introduction to Curvature, Graduate Texts in Mathematics 176, Springer Verlag

P. Petersen: Riemannian Geometry, Graduate Texts in Mathematics 171, Springer Verlag

J. Cheeger, D. Ebin: Comparison Theorems in Riemannian Geometry, North-Holland Publishing Company, Vol. 9, 1975

Szőkefalvi-Nagy Gy., Gehér L., Nagy P.: Differenciálgeometria, Műszaki Könyvkiadó, Budapest, 1979

Csoportelmélet 3/1/0/f/5

Tárgyfelelős: Horváth Erzsébet
További oktatók: Lukács Erzsébet, Héthelyi László, Rónyai Lajos

Permutáciocsoportok, csoporthatások.
Konjugáltság, normalizátor, cetralizátor, centrum, osztályegyenlet, Cauchy tetele.
Csoport automorfizmusai, szemidirekt szorzat,
koszorúszorzat. Csoportbõvítések. Sylow-tetelek. Véges p-csoportok. Nilpotens, ill. feloldható
csoportok. Véges nilpotens csoportok jellemzese.  Transzfer, normál komplementumtételek. Szabad csoportok,
definiáló reláciok. Szabad Abel-csoportok. Végesen generált Abel-csoportok
alaptétele, alkalmazások. Lineáris csoportok, klasszikus csoportok.
A reprezentációelmélet elemei.

Irodalom:
P.J. Cameron, Permutation groups, LMS Student Texts 45, CUP 1999.
B. Huppert, Endliche Gruppen I. Springer 1967.
D. Gorenstein, Finite groups, Chelsea Publishing Company, 1980.
M. Aschbacher, Finite group theory, Cambridge Studies in Advanced Mathematics 10, CUP 2000.
D.J.S. Robinson, A course in the theory of groups, GTM 80, Springer 1996.
J.J. Rotman, An introduction to the theory of groups, GTM 148, Springer 1995.
B. Szendrei Mária, Czédli Gábor, Szendrei Ágnes, Absztrakt algebrai feladatok, JATE TTK, JATEPress 1993.

Kombinatorikus optimalizálás 3/1/0/v/5

Tárgyfelelős: Recski András

További oktatók: Hujter Mihály

Gráfelméleti algoritmuscsaládok (legrövidebb út, párosítás, hálózati folyamok, a PERT-módszer) átismétlése, nevezetes NP-teljes feladatok a gráfelméletben (pontszínezés, független pontok maximális száma, maximális klikk-méret, Hamilton-kör és -út létezése, az utazó ügynök problémája, irányított köröket lefogó maximális halmazok) és rokon területeken (az egészértékű programozás alapfeladata, a többtermékes folyamprobléma). A lineáris programozás dualitás tételének alkalmazásai, egészértékű programozás, kombinatorikus optimalizálási feladatok, totális unimodularitás: maximális összsúlyú teljes párosítás (optimal assignment), minimálköltségű folyamprobléma egytermékes hálózatban. Matroidok definíciója, bázis, kör, rang, dualitás, minorok. Grafikus és koordinátázható matroidok, Tutte és Seymour tételei. Orákulumok, mohó algoritmus, k-partíció és 2-metszet algoritmus, a 3-metszet probléma, polimatroidok. Polinomrendű algoritmusokkal megoldható nevezetes műszaki problémák: a) a villamos hálózatok klasszikus elméletében (ellenálláshálózatok egyértelmű megoldhatósága, gráfok kör- és vágásmátrixainak tulajdonságai, általánosítás passzív és/vagy nonreciprok hálózatokra), b) a nagybonyolultságú áramkörök tervezésében (egyetlen pontsor huzalozása a Manhattan-modellben, csatornahuzalozás a különféle modellekben, az éldiszjunkt modell alkalmazása) és c) a rúdszerkezetek merevségével kapcsolatos kérdésekben (merevség, infinitezimális merevség, genetikus merevség, Laman tétele, Lovász és Yemini algoritmusa, a síkbeli rúdszerkezetek minimális számú csuklóval való lefogásának problémája, négyzetrácsok merevítésének kombinatorikus kérdései).

Irodalom:

Jordán Tibor, Recski András és Szeszlér Dávid: Kombinatorikus optimalizálás, Typotex Kiadó, Budapest, 2004