Bejelentkezés
 Fórum
 
 
Témakiírás
 
Iván Szabolcs
Adatszerkezetek felismerési bonyolultsága

TÉMAKIÍRÁS

Intézmény: Szegedi Tudományegyetem
informatikai tudományok
Informatika Doktori Iskola

témavezető: Iván Szabolcs
helyszín: SZTE
helyszín rövidítés: SZTE


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

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

felvehető hallgatók száma: 1

Jelentkezési határidő: 2017-03-31

 
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.2318 ( 2016. XI. 26. )