A gyakorlatban előforduló fejlettebb adatszerkezetek felismerési bonyolultságának vizsgálatával kapcsolatban az utóbbi években fokozódó érdeklődés figyelhető meg, pl. I és mtársai 2014-ben, majd ezt javítva Starikovskaya és Vildhoj suffix fák felismerésére adtak lineáris időigényű algoritmust 2015-ben, border tömbök felismerésére Lu és mtársai 2002-ben, parametrizált border tömbök felismerésére I és mtársai O(n^1.5)-ös algoritmust 2010-ben. A felismerési problémát vizsgálták korábban KMP táblákra, prefix táblákra, cover tömbökre, irányított körmentes szógráfokra és részsorozatgráfokra is, egyes esetekben hatékony algoritmusokat sikerült adni, más esetekben pedig a vonatkozó probléma NP-nehézségét igazolni. A probléma motivációját általában az adatszerkezet matematikai struktúrájának megragadásán felül a vonatkozó adatszerkezet implementációjának futásidejű debugolása is adja. A kitűzött feladat ezen kutatásokba bekapcsolódás, elsősorban bonyolultságelméleti alsó korlátok eredmények igazolásával.
előírt nyelvtudás: angol további elvárások: matematikai érzék
Bejelentkezés
