|
|
Structural and Algorithmic Properties of Permutation Classes
Opler, Michal ; Jelínek, Vít (vedoucí práce) ; Kozma, László (oponent) ; Bouvel, Mathilde (oponent)
V této práci studujeme vztah mezi strukturou dědičných permutačních tříd a výpo- četní složitostí různých rozhodovacích problémů. Nejdříve zkoumáme strukturu permu- tačních tříd z pohledu několika různých parametrů, zejména stromové šířky. Definujeme nové vlastnosti obecné permutační třídy C, z nichž nejdůležitější je vlastnost dlouhé cesty. Z těchto vlastností pak odvodíme různé dolní odhady na to jakou největší stromovou šířku může mít permutace délky n z třídy C. Například dokážeme, že libovolná třída s vlastností dlouhé cesty má stromovou šířku neomezenou. Hlavní rozhodovací problém, kterým se zabýváme, je znám jako Permutation Pat- tern Matching (PPM). Vstupem pro problém PPM je dvojice permutací τ (text) a π (vzor), a cílem je rozhodnout jestli τ obsahuje π jako podpermutaci. Nejdříve zběžně uvažujeme problém PPM ve své obecné verzi, a poté se zaměříme na jeho variantu C- Pattern PPM, kde navíc požadujeme, aby vzor π pocházel z pevně dané třídy C. Za předpokladu různých strukturálních vlastností třídy C pak odvodíme jak klasické tak pa- rametrizované těžkostní výsledky. Například ukážeme, že problém C-Pattern PPM je NP-úplný kdykoliv třída C má vlastnost dlouhé cesty. Dále se zaměříme na ještě více omezenou variantu problému PPM, ve které požadu- jeme, aby i text pocházel z pevně dané třídy C. Tento...
|
host ::
RSS.