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 (magyar oldal): 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


Jelentkezési határidő: 2018-01-31


2017. XI. 23.
ODT ülés
Az ODT következő ülésére 2017. december 8-án 10.00 órakor kerül sor a Semmelweis Egyetem II. Belgyógyászati Klinika tetőterében levő MSD teremben (Bp. Szentkirályi u. 46., a rektori épület mellett).

 
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ó: 2.2358 ( 2017. X. 31. )