Thesis supervisor: Katalin Friedl
Location of studies (in Hungarian): Számítástudományi és Információelméleti Tanszék Abbreviation of location of studies: SZIT
Description of the research topic:
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.
Number of students who can be accepted: 1
Deadline for application: 2015-01-05
2024. IV. 17. ODT ülés Az ODT következő ülésére 2024. június 14-én, pénteken 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).
Login
