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époésszáma robbanásszerűen növekedne, ezért az utóbbi 4 évtizedben megnőtt az igény az olyan algoritmusok iránt, 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.
Login
