Bejelentkezés
 Fórum
 
 
Témakiírás
 
Friedl Katalin
Hatékony algoritmusok

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ő: Friedl Katalin
helyszín (magyar oldal): Számítástudományi és Információelméleti Tanszék
helyszín rövidítés: SZIT


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

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

Az algoritmikus problémák nagy része NP-nehéz, de a polinom időben megoldhatók esetében is felmerül a kérdés, hogy bizonyos megkötésekkel nem lehet-e a szokásos eljárásoknál gyorsabbat találni. A cél elsősorban gráfokkal kapcsolatos feladatok, algoritmusok ilyen értelemben vett vizsgálata. Például a ma sokat vizsgált óriási gráfokon egy köbös vagy akár csak négyzetes algoritmus is nagyon sokáig tarthat, azonban több módszer is esélyt ad arra, hogy a feladatnak valamilyen hatékonyan megoldható változatához jussunk.

Egyik lehetőség, hogy olyan speciális eseteket keresünk, amelyek még érdekesek és hasznosak lehetnek, de van rájuk az általánosnál lényegesen gyorsabb algoritmus. Azt is kitűzhetjük célul, hogy az algoritmus az átlagos esetekben (véletlenszerű bemenetre) legyen hatékony. Egy másik megközelítési mód, hogy az optimum meghatározása helyett beérjük közelítő eredménnyel (pl. a minimum egy konstansszorosával), vagy nagy valószínűséggel helyes eredménnyel, ha ez által nyerünk a sebességen. További, mostanában sokat vizsgált eszköz a feladat paraméteres bonyolultságának vizsgálata, amikor is olyan újabb paramétert vezetünk be a feladatba (pl. maximális fokszám, vagy egyéb gráfparaméter), hogy a feladat hatékonyan megoldható lesz, amennyiben a paraméter értéke kicsi.

A kutatás célja a hallgató érdeklődésének megfelelő algoritmikus problémáknak a felsoroltak, vagy ezekhez hasonló módszerek segítségével való vizsgálata, hatékony eljárások találása.

felvehető hallgatók száma: 1

Jelentkezési határidő: 2012-01-06

 
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ó: 1.2357 ( 2017. V. 15. )