Bejelentkezés
 Fórum
 
 
Témakiírás
 
Recski András
Kombinatorikus optimalizálás és műszaki alkalmazásai

TÉMAKIÍRÁS

Intézmény: Budapesti Műszaki és Gazdaságtudományi Egyetem
informatikai tudományok
Informatikai Tudományok Doktori Iskola

témavezető: Recski András


A kutatási téma leírása:

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.

felvehető hallgatók száma: 1

Jelentkezési határidő: 2008-05-20

 
Minden jog fenntartva © 2007, Országos Doktori Tanács - a doktori adatbázis nyilvántartási száma az adatvédelmi biztosnál: 02003/0001. Program verzió: 2.2358 ( 2017. X. 31. )