Thesis supervisor: András Recski
Location of studies (in Hungarian): BME VIK SZIT Abbreviation of location of studies: BME
Description of the research topic:
A többszáz éves diszkrét matematikán (kombinatorikán) belül a számítógépek elterjedésével megnőtt az igény az algoritmikus kérdések vizsgálata iránt. A nagyméretű feladatok esetén az összes esetet gépiesen vizsgáló algoritmusok lépésszáma robbanásszerűen növekedne, ezért az utóbbi 4 évtizedben elsősorban az olyan algoritmusok iránt érdeklődnek, amelyek lépésszáma felülről becsülhető a bemenet méretének polinomiális (és nem exponenciális) függvényével. Ehhez persze a szóbanforgó matematikai probléma struktúráját, speciális tulajdonságait is fel kell használni.
Az ilyenfajta struktúrális kérdésekkel foglalkozik a kombinatorikus optimalizálás; fontos eszközei a gráfok és hipergráfok elmélete, a matroidelmélet, a totálisan unimoduláris mátrixokat alkalmazó speciális lineáris programozás stb. Ezeknek az eszközöknek a segítségével gyakran polinomiális rendű algoritmusok adhatóak korábban reménytelennek tartott feladatokra (vagy legalábbis azok bizonyos speciális eseteire).
A kutatási munka célja részben a fenti eszközök (elsősorban a matroidelmélet), részben pedig ezek műszaki alkalmazásainak a kutatása. A kutatási munkának a Számítástudományi és Információelméleti Tanszéken eddig művelt konkrét alkalmazási területei közül kiemelem a nagybonyolultságú integrált áramkörök (VLSI) huzalozásávaal kapcsolatos vizsgálatokat, a villamos hálózatok klasszikus elméletének aktív és/vagy nonreciprok elemeket is tartalmazó hálózatokra való kiterjesztésével kapcsolatos kutatásokat, valamint a rúdszerkezetek (és általában az ún. tensegrity szerkezetek) merevségével kapcsolatos kvalitatív vizsgálatokat.
Required language skills: angol Number of students who can be accepted: 1
Deadline for application: 2015-12-31
2024. IV. 17. ODT ülés Az ODT következő ülésére 2024. június 14-én, pénteken 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).
Login
