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.
Bejelentkezés
