Diplomatémák

Babcsányi István: Csoport-típusú automaták

A kidolgozandó feladat részletezése: Az automatákhoz rendelt kísérő srtuktúrák közül a legfontosabb az u.n. karakterisztikus félcsoport. Abban az esetben, ha a karakterisztikus félcsoport csoport, az automaták vizsgálata csoporelméleti módszerek alkalmazását teszi lehetővé. A hallgató feladata az eddig elért eredmények rendszerezése, különös tekintettel az erősen összefüggő automaták esetében.
A diplomázóval szemben támasztott elvárások: A téma irodalmazása, az eredmények összefoglalása, esetleg új eredményekkel való kiegészítés, rendszerezés.

Ferenczi Miklós Algebrai logika és általános modellelmélet

Az algebraizáció fogalmának tárgyalása és bemutatása néhány nevezetes logikán keresztül. Logikai és univerzális algebrai fogalmak kapcsolatrendszerének leírása. Kompaktság, dedukció tétel, teljesség vizsgálata. Szemantika és bizonyításelmélet modellezése algebrai logikában. A programozás elmélettel való kapcsolatok elemzése.
A diplomázóval szemben támasztott elvárások: A kijelölt irodalom elsajátítása (szakszöveg olvasása angolul), egyszerű példák és alkalmazások kidolgozása.

Horváth Erzsébet: Karakterek nullahelyeinek vizsgálata GAP segítségével

A szakdolgozat célja a véges csoportok irreducibilis karaktereinek nullahelyeivel kapcsolatos eredmények összegyűjtése, valamint GAP programok irása karakterek nullahelyeinek vizsgálatára. Lehetőség szerint a meglévő eredmények továbbfejlesztése.
A diplomázóval szemben támasztott elvárások: a fenti témához kapcsolódó alapismeretek

Horváth Erzsébet: Blokkindukciók vizsgálata véges csoportokban

A moduláris reprezentacióelméletben több blokkindukció fogalmát is be lehet vezetni. A szakdolgozat célja ezek vizsgálata a szimmetrikus csoportok esetében. A vizsgálatokhoz a GAP programcsomag használata javasolt.
A diplomazóval szemben támasztott elvárások: a Moduláris reprezentációelmélet c. speciálelőadás felvétele v. egyéb forrásból a moduláris reprezentációelmélet alapvető tételeinek elsajátitása. A szimmetrikus csoportok reprezentációinak ismerete előnyös.

Ivanyos Gábor: Reverzibilis számítások (BSc)

Egy reverzibilis számítást végző Boole-hálózat olyan logikai kapukból áll, amelyek mindegyike egy-egy bijektív függvényt valósít meg a saját lehetséges bemeneti, illetve kimeneti bitsorozatai között. A feladat a modell különféle változatainak ismertetése és a témakör néhány klasszikus és újabb eredményének bemutatása.
Irodalom: E. Fredkin, T. Toffoli, Conservative logic, International Journal of Theoretical Physics, 21:219–253, 1982.

Ivanyos Gábor: Általánosított Reed-Muller-kódok (BSc)

A feladat az általánosított Reed-Muller-kódok főbb tulajdonságainak, fontosabb dekódolási módszereinek és néhány alkalmazásának áttekintése.
Irodalom: E. F.Assmus Jr., J.D. Key, Polynomial Codes and Finite Geometries, In: V. S. Pless and W. C. Huffman, (eds), Handbook of Coding Theory, Vol. 2, pp. 1269-1343, 1998.

Ivanyos Gábor: Lineáris polinom-elemű mátrixok rangja. (BSc)

Legyenek egy M mátrix elemei többváltozós valós polinomok. M rangja az M-ből a változókba történő behelyettesítéssel nyert mátrixok rangja közül a legnagyobb. Számos izgalmas elvi és algoritmikus kérdés kapcsolatos már olyan polinommátrixok rangjának meghatározásával is, amelynek elemei elsőfokúak. A feladat néhány ilyen probléma és ide vonatkozó eredmény bemutatása.
Irodalom:
M. D. Atkinson, S.Lloyd, Large spaces of matrices of bounded rank, Quarterly Journal of Mathematics 31, pp. 253-262.
L. Lovász, Singular spaces of matrices and their applications in combinatorics, Bol. Soc. Braz. Mat. 20 pp. 87-89, 1989.
J. F. Buss, G. S. Frandsen, J. Shallit, The computational complexity of some problems of linear algebra, J. Comput. Syst. Sci. 58, pp 572-596, 1999.
J. Draisma, Small maximal spaces of non-invertible matrices, Bull. London Math. Soc 38, pp. 764-776.

Ivanyos Gábor: Számítógépes algebrai módszerek kvantum-, illetve reverzibilis kapukészletek vizsgálatára. (MSc)

Egyik lehetséges feladat a két modell univerzális kapuival kapcsolatos algoritmikus eredmények és módszerek áttekintése, összehasonlítása és továbbfejlesztése. Másik lehetséges feladat a két modell univerzális kapuival kapcsolatos legfontosabb ismert tények áttekintése után néhány nyitott kérdés vizsgálata számítógép segítségével.

Ivanyos Gábor: Az LLL-rácsredukció alkalmazásai. (MSc)

A feladat az LLL-bázisredukciós algoritmus és az eljárás néhány újabb keletű alkalmazásának bemutatása.
Irodalom: P. Q. Nguyen, B. Vallée (eds.), The LLL Algorithm Springer 2010.

Ivanyos Gábor: Algebrai számelméleti algoritmusok. (MSc)

A feladat az algebrai számelmélet néhány algoritmikus kérdésével kapcsolatos eredmény bemutatása, különös tekintettel az utóbbi években sikerrel alkalmazott módszerekre.
Irodalom: S. Hallgen, Fast quantum algorithms for computing the unit group and class group of a number field, Proc. STOC 2005.

Ivanyos Gábor: Kvadratikus alakokkal kapcsolatos algoritmikus problémák bonyolultsága. (MSc)

A feladat a címben szereplő témakör néhány fontosabb eredményének áttekintése.

Ivanyos Gábor: Polinom-mátrixok rang-optimális behelyettesítése (MSc)

A feladat a maximális rangot adó behelyettesítés megkeresésének algoritmikus bonyolultsága néhány fontos speciális esetben.
Irodalom:
L. Lovász, Singular spaces of matrices and their applications in combinatorics, Bol. Soc. Braz. Mat. 20 pp. 87-89, 1989.
J. F. Buss, G. S. Frandsen, J. Shallit, The computational complexity of some problems of linear algebra, J. Comput. Syst. Sci. 58, pp 572-596, 1999.
L. Gurvits, Classical complexity and quantum entanglement, Journal of Computer and System Sciences 69, pp 448-484, 2004.

Lukács Erzsébet: A Mathieu-csoportok konstrukciói

A sporadikus egyszerű csoportok első, nevezetes családjára, a Mathieu-csoportokra hosszú évek során számos különböző konstrukció született, összekapcsolva ezeket a kombinatorikus struktúrák, a kódelmélet területével. A diplomázó feladata lehetne ezeknek az eredényeknek az ismertetése, valamint az egyes előállítások használhatóságának az összehasonlítása.

Lukács Erzsébet: Részcsoporthálók

Más kísérőstruktúrákhoz hasonlóan a részcsoporthálókra is vizsgálják, hogy milyen mértékben, milyen feltételek mellett határozza meg a csoportot részcsoporthálójának ismerete. Bár magának a csoportnak a részcsoporthálója viszonylag kevés információt ad a csoportról, a direkt négyzet részcsoporthálója sok osztályban már elegendő a csoport felismeréséhez (noha általánosan ez még mindig nem igaz). Nyitott kérdés, hogy a nagyobb hatványok (akár az összes véges hatvány) részcsoporthálója meghatározza-e a csoportot, illetve a kisebb hatványok részcsoporthálóját (speciálisan a direkt négyzet részcsoporthálójából visszakapható-e magának a csoportnak a részcsoporthálója). A vizsgázónak ebben az irányban kellene új eredményt elérnie.

Nagy Attila: Szubdirekt irreducibilis félcsoportok speciális félcsoport-varietásokban

A kidolgozandó feladat részletezése: Mivel minden félcsoport felbontható szubdirekt irreducibilis félcsoportok szubdirekt szorzatára, ezért fontos, hogy ismerjük a szubdirekt irreducibilis félcsoportokat speciális félcsoport-varietásokban. E feladat az, hogy speciális félcsoport-varietásokra eddig ismert eredmények összefoglalása, rendszerezése, az eredmények esetleges teljessé tétele.

Rónyai Lajos: Elliptikus görbék kriptográfiai alkalmazásai

Az elliptikus görbéket alkalmazó titkosító eljárások fontos szerepet játszanak a kriptográfiában. A feladat az elméleti háttér és az alapvető módszerek áttekintése, esetleg - a hallgatóval való megegyezés szerint - egy részfeladat számítógépes implementációja.

Rónyai Lajos: Algebrai-geometriai gráfkonstrukciók

A cél néhány, algebrai sokaságok metszéseinek segítségével definiált gráfkonstrukció vizsgálata, beleértve az algebrai/geometriai hátteret, és a gráfok extremális kombinatorikai tulajdonságait is.

Sági Gábor: A Vaught-sejtés változatainak vizsgálata

Legyen T egy elsőrendű formulahalmaz. A Vaught-sejtés szerint, ha T-nek megszáml álhatónál több, páronként nem izomorf megszámlálható modellje van, akkor kontinuum sok ilyen modellje van. E sejtés - teljes általánosságában - máig megoldatlan. A szakdolgozatban a Vaught-sejtés gyengítéseinek, variánsainak vizsgálatát tűzzük ki célul. E vizsgálatok során a hallgatónak el kell sajátítania bizonyos ismert algebrai logikai techinkákat, majd ezek alkalmazásával megpróbálunk új eredményeket nyerni a szokásos elsőrendű logika egyes módosításaira (például az egyenlőségmentes esetre) vonatkozó Vaught-sejtéssel kapcsolatban.

Schmidt Tamás: Geometriai terek hálóelméleti jellemzése

A különféle geometriai terek jellemezhetők az altereik részben rendezett halmazával (hálójával). A híres Desargues tétel egy hálóazonosság képében jelenik meg. E témáról a megadott irodalom segítségével egy áttekintő összefoglalót kell elkészíteni. Kiindulásul Bjarni Jonsson egy régebbi cikke szolgál. Kitekintés a Neuman-féle folytonos geometiára és annak kvantummechanikában való alkalmazására.

Schmidt Tamás: Általános Galois-kapcsolat relációk és műveletek között

Egy adott A algebrai struktúrán tekintsük relációknak egy R halmazát. Ekkor R meghatározza az A műveleteinek egy halmazát, amely az R-beli relációkkal felcserélhető műveletekből áll. Megfotdíva, műveletek egy halmaza meghatározza azon R-beli relációkat, amelyekkel felcserélhetők. Ily módon egy Galois megfeleltetést definiáltunk. E témáról G. Pöschel irt egy kis könyvet. A feladat e könyv ismertetése, az újabb irodalom felkutatása, és esetleg önálló eredmények bizonyítása.

Serény György: Természetes aritmetikai függetlenségi eredmények

Gödelnek a Peano aritmetika (és rekurziv konzisztens bővítései) nemteljességére vonatkozó tételét a matematikusok többsége ezoterikus, csak a logikusok számára érdekes eredményként könyveli el, hisz a tétel olyan állítások függetlenségét mutatja meg, melyek matematikailag egyszerűen nem érdekesek. A természetes függetlenségi eredmények bizonyos értelemben erre adott vélaszul születtek. Ezek valódi véges kombinatorikai állitásoknak a Peano aritmetikától (és annak bizonyos bővítéseitől) való függetlensegére vonatkoznak, bizonyitva ezzel, hogy a matematika alapjainak tisztázására irányuló kutatások eredményei relevánsak lehetnek a tiszta matematikával foglalkozó kutatók számára is.
Magukon az eredményeken kí vül a bizonyí tásukra szolgáló technikai eszközök is igen érdekesek: olyan (ún. gyorsan növő) függvények konstrukcióján alapszanak, melyek gyorsabban nőnek annál, hogysem a teljes indukció „követni tudná” őket.
Irodalom:
W. Buchholz and S. Wainer, Provably computable functions and the fast growing hierarchy, Contemp. Math. 65 (1987), 179-198.
Kirby, L. and Paris, J. Accessible Independence Results for Peano Arithmetic, Bull. London Math. Soc. 14, 285-293, 1982.
Smorynski, C., Some Rapidly Growing Functions, Math. Intell. 2, 149-154, 1980.
Smorynski, C., The Varieties of Arboreal Experience, Math. Intell. 4, 182-188, 1982.
Smorynski, C., ‘Big’ News from Archimedes to Friedman, Not. Amer. Math. Soc. 30, 251-256, 1983.
Spencer, J. ”Large Numbers and Unprovable Theorems.” Amer. Math. Monthly 90, 669-675, 1983.

Wettl Ferenc: Számelméleti és kombinatorikai konstrukciók kriptográfiai protokolokban

A modern kriptográfiai protokolok legtöbbje számelméleti és kombinatorikai konstrukciókra épül. A diplomázó tekintse át ezek valamely közösen kiválasztott részét.
A kiválasztott protokol(ok) különböző megvalósításait hasonlítsa össze matematikai eszközökkel, és a protokol jellegétől függően esetleg számítógéppel végzett kísérletekkel is.