Teoretická informatika

Závěrečné práce

Diplomové práce

Zpětné reference v rozšířených regulárních výrazech

Autor
Martin Hron
Rok
2020
Typ
Diplomová práce
Vedoucí
Ing. Ondřej Guth, Ph.D.
Oponenti
Ing. Jan Trávníček, Ph.D.
Anotace
Zpětné reference (odkazy) jsou rozšíření regulárních výrazů bežně podporované v dnešních nástrojích. Regulární výrazy se zpětnými referencemi mají zvýšenou vyjadřovací sílu, ale jejich vyhledávání (matching) je NP-úplné. Tato práce poskytuje přehled existujících přístupů pro vyhledávání regulárních výrazů se zpětnými referencemi a také teoretického výzkumu na toto téma. V rámci této práce byl implementován nástroj pro vyhledávání regulárních výrazů založený na modelu paměťových automatů (memory automata). Vyhledávání regulárních výrazů s počtem zpětných referencí na různé skupiny omezených konstantou pomocí paměťových automatů má polynomiání časovou složitost. Byla implementována další nedávno zveřejněná metoda založená na paměťových automatech, která poskytuje polynomiální složitost i pro výrazy s neomezeným počtem zpětných referencí splňujících jistou vlastnost. V rámci této práce byl navržen a implementován alternativní algoritmus pro výpočet této vlastnosti. Model paměťového automatu byl dále rozšířen pro podporu kvantifikátorů omezeného počtu opakování a další rozšíření byla implementována. Experimentální vyhodnocení ukázalo, že implementovaný nástroj je mnohem odolnější vůči katastrofickému backtrackování než existující implementace podporující zpětné reference. Žádný z testovaných útoků přes algoritmickou složitost nevyvolal znatelné zpomalení.

Modulární a rozšiřitelný nástroj pro lokalizaci softwarových chyb

Autor
Petr Nevyhoštěný
Rok
2020
Typ
Diplomová práce
Vedoucí
Ing. Petr Máj
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Anotace
Lokalizace chyb je považována za jeden z nejvíce únavných a časově náročných úkolů při vývoji software. Přesto je stále často prováděna manuálně. Lokalizace softwarových chyb (anglická zkratka SFL) je oblast výzkumu zabývající se vývojem automatizovaných technik pro usnadnění této aktivity. Navzdory množství práce, která byla tomuto výzkumu věnována, nesplňují aplikace navržených metod kompletně potřeby praxe. Tato magisterská práce proto popisuje nový nástroj a framework pro lokalizaci softwarových chyb s názvem \emph{Aardwolf}, jehož hlavním cílem je usnadnit použití SFL technik v praxi. Toho je dosaženo velmi modulárním designem, umožňujícím snadnou rozšiřitelnost, a aplikováním doporučení, která lze naleznout v publikovaných uživatelských studiích. Pro demonstraci možností nástroje Aardwolf byla implementována trojice různých SFL technik a frontendy pro programovací jazyky C a Python. Integrace do dvou větších softwarových projektů byla popsána jako ukázka aplikovatelnosti. Předběžné výsledky ukazují, že je efektivita nástroje srovnatelná s literaturou. Zaměření na uživatelskou přívětivost a rozšiřitelnost řešení je ovšem významné zlepšení oproti současnému stavu v tomto odvětví.

Kombinatorické hry typu Taking and Breaking

Autor
Šimon Lomič
Rok
2019
Typ
Diplomová práce
Vedoucí
RNDr. Tomáš Valla, Ph.D.
Anotace
V této práci analyzujeme několik otevřených problémů v oblasti nestranných i stranných her typu Taking and Breaking. Pro nestranné odčítací hry dokážeme existenci hry s aperiodickou nim-sekvencí a periodickou sekvencí výhra-prohra. Analyzujeme ekvivalenční třídy těchto her a nalézáme řešení jedné z těchto tříd. Také představujeme novou hru typu Taking and Breaking, kterou z velké části vyřešíme. V oblasti stranných her provedeme analýzu několika odčítacích her a her typu Pure Breaking. Pro tyto hry také představíme obecnou techniku testování aritmetické periodicity. Pro automatické řešení nestranných her typu Taking and Breaking navrhujeme několik algoritmů. Práci uzavíráme důkazem PSPACE-těžkosti nestranné zobecněné odčítací hry a EXPTIME-těžkosti této hry ve stranné variantě.

Parametrizované algoritmy pro Steinerovské stromy

Autor
Peter Mitura
Rok
2019
Typ
Diplomová práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Anotace
Je-li dán vážený graf a podmnožina jeho vrcholů zvaných terminály, problém Steinerova stromu spočívá v nalezení souvislého podgrafu s nejmenší váhou, který obsahuje všechny terminály. Jedná se o známý NP-těžký problém, který nalézá užití kupříkladu v návrhu integrovaných obvodů, nebo počítačových a dopravných sítích. V této práci rozebereme algoritmus od Dreyfuse a Wagnera, od Ericksona, Monmy a Veinotta, a Nederlofův algoritmus, které řeší verzi tohoto problému parametrizovanou počtem terminálů, a algoritmus využívající dynamické programování a matici řezů pro parametrizaci dle stromové šířky. Pro všechny popsané algoritmy vytvoříme optimalizovanou implementaci a pro porovnání s jinými řešeními ukážeme její výsledky v soutěži PACE 2018.

Podchycování cest v grafech

Autor
Radovan Červený
Rok
2018
Typ
Diplomová práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
RNDr. Tomáš Valla, Ph.D.
Anotace
Problém zvaný d-Path Vertex Cover, d-PVC spočívá v nalezení podmnožiny F vrcholů daného grafu G=(V,E) takové, že G \ F neobsahuje žádnou cestu na d vrcholech. Cesty, které chceme takto podchytit, nemusí být indukované. Je známo, že problém d-PVC je NP-úplný pro každé d >= 2. Dále je známo, že problém 5-PVC parametrizovaný velikostí řešení k je řesitelný v čase O(5^k*n^O(1)). V této práci přicházíme s algoritmem používající iterativní kompresi, který řeší problém 5-PVC v čase O(4^k*n^O(1)).

Algoritmus pro hledání podgrafu založený na barevném kódování

Autor
Josef Malík
Rok
2016
Typ
Diplomová práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
RNDr. Tomáš Valla, Ph.D.
Anotace
Tato práce popisuje řešení problému izomorfismu podgrafů pomocí techniky barevného kódování. V práci je popsán problém izomorfismu podgrafů, jeho varianty a jeho aplikace. Dále je rozebrán problém tvorby hezkého stromového rozkladu optimální šířky pro zadaný graf, jelikož takováto struktura je pro daný přístup vyžadována. Jako hlavní část práce je popsáno několik modifikací a optimalizací původního algoritmu založeného na barevném kódování. Praktickým výsledkem práce je modul implementovaný v jazyce C, který je navržen pro řešení velkých instancí problému izomorfismu podgrafů včetně výpisu nalezených výsledků.

Indexování XML dokumentů

Autor
Eliška Šestáková
Rok
2015
Typ
Diplomová práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Oponenti
Ing. Jan Trávníček, Ph.D.
Anotace
Výzkum v oblasti indexování řetězců má již mnoho prezentovaných výsledků, což však neplatí pro ostatní datové struktury, jakými jsou například stromy. Tato práce obsahuje v prvé řadě shrnutí metod pro indexování řetězců a stromů. Dále se podrobně zabývá rešerší existujících řešení indexování XML dokumentů. Představena je zde nová jednoduchá metoda využívající deterministický konečný automat, jež umožňuje efektivně zpracovat XPath dotazy skládající se z libovolné kombinace child (/) a descendant-or-self (//) os, sloužících k navigaci v XML dokumentu. Spolu s touto metodou byly dále navrženy dva další konečné automaty na podporu jednodušších dotazů obsahujících vždy pouze jednu z uvedených os. Ke konstrukci indexu pro daný XML dokument D s n elementy je využit odpovídající XML stromový model T. Zpracování dotazu Q o m elementech proběhne v čase O(m) nezávislém na n. Výsledkem dotazu je poté množina elementů splňujících dané požadavky. Ačkoli automat podporující všechny dotazy s // osou indexuje až O(2^n) různých dotazů, počet stavů vlastního deterministického automatu je O(h^k), kde h je výška XML stromového modelu T a k je počet listů T. Pro běžné XML dokumenty lze navíc tuto mez triviálně snížit až na O(h.2^k).

Inkrementální komprese založená na clusterování

Autor
Luboš Krčál
Rok
2014
Typ
Diplomová práce
Vedoucí
prof. Ing. Jan Holub, Ph.D.
Oponenti
Ing. Jan Trávníček, Ph.D.

Vyhledávání a indexování v neseřazených stromech

Autor
Vojtěch Sobota
Rok
2013
Typ
Diplomová práce
Vedoucí
prof. Ing. Bořivoj Melichar, DrSc.
Oponenti
doc. Ing. Jan Janoušek, Ph.D.