Login
 Forum
 
 
Thesis topic proposal
 
Szabolcs Iván
Adatszerkezetek felismerési bonyolultsága

THESIS TOPIC PROPOSAL

Institute: University of Szeged
computer sciences
PhD School in Computer Science

Thesis supervisor: Szabolcs Iván
Location of studies: SZTE
Abbreviation of location of studies: SZTE


Description of the research topic:

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.

Required language skills: angol
Further requirements: 
matematikai érzék

Number of students who can be accepted: 1

Deadline for application: 2017-03-31

 
All rights reserved © 2007, Hungarian Doctoral Council. Doctoral Council registration number at commissioner for data protection: 02003/0001. Program version: 1.2318 ( 2016. XI. 26. )