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