doc. Ing. Jan Janoušek, Ph.D.

Vedoucí Katedry teoretické informatiky

Závěrečné práce

Dizertační práce

Arbologie

Stupeň
Téma dizertační práce
Popis tématu

Formální stromové jazyky, formalismy pro jejich generování a popis, a výpočetní modely pro zpracování stromových jazyků tvoří jednu z oblastí teorie formálních jazyků a automatů. Praktickými souvisejícími tématy výzkumu jsou také efektivní algoritmy pro různé úlohy zpracování stromů, jako jsou vyhledávání, indexování nebo výpočet repetic ve stromech. Mezi různé typy uvažovaných stromů patří například seřazené a neseřazené stromy, nebo ohodnocené a neohodnocené stromy. Mezi uvažované třídy formálních stromových jazyků patří například regulární nebo bezkontextové stromové jazyky. Modely výpočtů pro zpracování stromových jazyků zahrnují různé typy stromových automatů nebo zásobníkové automaty, které čtou lineární zápisy stromů. Cílem studia je rozvíjet teorii formálních stromových jazyků a efektivních algoritmů pro sekvenční a paralelní zpracování stromů.

Bakalářské práce

Jednoduchý sémantický webový vyhledávač

Autor
Václav Dajbych
Rok
2012
Typ
Bakalářská práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Oponenti
Ing. Petr Šlegr

Simulace nedeterministického zásobníkového automatu pro indexování stromů

Autor
Jan Milík
Rok
2012
Typ
Bakalářská práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Oponenti
Ing. Jan Trávníček, Ph.D.

Vizualizace konečných automatů

Autor
Petr Lessner
Rok
2012
Typ
Bakalářská práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Oponenti
Ing. Martin Poliak, Ph.D.

Formální specifikace šablonovacího jazyka Latte a implementace pluginu pro platformu IntelliJ IDEA

Autor
Jan Tvrdík
Typ
Bakalářská práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Oponenti
Ing. Radomír Polách

Implementace zrychlené LR analýzy

Autor
Jakub Doupal
Rok
2016
Typ
Bakalářská práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Oponenti
Ing. Jan Trávníček, Ph.D.
Anotace
Tato bakalářská práce se zabývá implementací zrychlené LR syntaktické analýzy do automatové knihovny vyvíjené na Katedře teoretické informatiky na Fakultě informačních technologií ČVUT v Praze. Tato knihovna umožňuje práci s automaty, stromy, jazyky a gramatikami, a experimenty s početnými algoritmy z tohoto odvětví. Na knihovně se neustále pracuje a je rozvíjena, po dokončení jejího vývoje ji bude možné používat jako výukový nástroj v předmětech BI-AAG, BI-PJP, MI-SYP aj. Zatímco LR analýza se používá pro práci s bezkontextovými LR gramatikami, zobecněnou LR analýzu lze použít i u nejednoznačných gramatik. Vzhledem k velkému množství zásobníkových operací existují požadavky analýzu urychlit, k čemuž slouží metoda zrychlené LR analýzy, která snižuje počet operací výměnou za větší paměťovou náročnost. To může být využito zobecněnou LR analýzou. Cílem práce je seznámit se s prostředím automatové knihovny a relevantními algoritmy a implementovat zrychlenou metodu LR analýzy.

Implementace indexu stromu pro stromové vzorky

Autor
Lukáš Vozáb
Rok
2016
Typ
Bakalářská práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Oponenti
Ing. Jan Trávníček, Ph.D.
Anotace
Tato práce se zabývá implementací indexace a vyhledávání vzorků ve stromových strukturách. Je použita nová metoda využívající kompaktní suffixový automat, který představuje především drastickou paměťovou úsporu. Vyhledávací fáze pak dokáže poskytnout množinu výskytů stromových vzorků v čase nezávislém na celkovém množství dat.

Analýza dynamického SQL kódu v projektu Manta

Autor
Artur Nasyrov
Rok
2018
Typ
Bakalářská práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Anotace
Cílem práce je analýza typických případů použití dynamického SQL v datových skladech a rozšíření projektu Manta sadou strategií, které umožní analýzu dynamického SQL kódu v některých případech. Předmětem práce je vyhledání typických případů užití dynamického SQL v datových skladech, návrh zlepšení existující sady strategií, následující implementace a testování výsledků.

Diplomové práce

Vyhledávání repetic v XML

Autor
Petr Vaněk
Rok
2012
Typ
Diplomová práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Oponenti
Ing. Martin Poliak, Ph.D.

Vyhledávání nelineárních vzorků ve stromech

Autor
Prokop Boček
Rok
2012
Typ
Diplomová práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Oponenti
Ing. Jan Trávníček, Ph.D.

Generování cílového kódu s pomocí indexu AST

Autor
Jaroslav Málek
Rok
2013
Typ
Diplomová práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.

Studie bezpečnosti kódu v infrastruktuře překladačů LLVM

Autor
Sarmad Neamah Mohsen Al-Fatla
Typ
Diplomová práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Oponenti
Ing. Tomáš Zahradnický, Ph.D.

Zotavení se z chyb v nástrojích pro automatizovanou analýzu programových artefaktů

Autor
Jakub Valenta
Rok
2013
Typ
Diplomová práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Oponenti
Ing. Jan Trávníček, Ph.D.

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í analýza PL/SQL skriptů

Autor
Jan Strnad
Rok
2015
Typ
Diplomová práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Anotace
Tato práce se zabývá vylepšením mechanizmu transformací u systému \acrlong{mt}. Transformace umožňuje automaticky upravit \acrshort{plsql} kód, reprezentovaný pomocí \acrshort{ast}, tak, aby splňoval určitá pravidla. Typickým příkladem je převod jednoho syntaktického konstruktu na jiný, významově ekvivalentní. Sem lze zařadit např. funkci DECODE převedenou na CASE výraz. V důsledku transformace dochází ke ztrátě informace obsažené v AST reprezentaci. Původní řešení doplnění této informace spočívalo v provedení úplné opětovné syntaktické a sémantické analýzy transformovaného skriptu. Tato práce analyzuje, navrhuje a implementuje inkrementální řešení. Implementované řešení nevyžaduje provedení jakýchkoliv změn na straně již existujících transformací. Efekt inkrementálního zpracování byl experimentálně změřen na několika typických transformacích. Bylo dosaženo velmi výrazného časového zlepšení, v některých případech až v řádu stonásobků.

Kontrola kompatibility datových typů v Oracle SQL

Autor
Ondřej Pelech
Rok
2015
Typ
Diplomová práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Oponenti
Ing. Radomír Polách
Anotace
Programy v Oracle SQL mohou selhat, když obsahují chyby. V této práci představíme metodu pro odhalování chyb specifického druhu -- nekompatibilita datových typů. Analyzujeme datové typy a vestavěné funkce v dialektu Oracle SQL. Navrhneme metodu pro kontrolu kompatibility datových typů, která pracuje nad grafem datových toků. Tuto metodu implementujeme v jazyku Java.

Vyhledávání výskytů stromových vzorků v seřazených stromech s pomocí indexů stromů

Autor
Jan Milík
Rok
2016
Typ
Diplomová práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Oponenti
Ing. Jan Trávníček, Ph.D.
Anotace
Tato práce porovnává dvě existující schémata pro indexování stromů. Jedno je založené na nedeterministickém faktorovém automatu, druhé na deterministickém kompaktním sufixovém automatu. Je zde popsáno třetí, nové schéma založené na pozičních haldách - relativně nové datové struktuře. Jako vedlejší produkt je popsán algoritmus pro převod sufixových stromů na poziční haldy a načrtnuta nová datová struktura založená na pozičních haldách. Všechna schémata byla implementována a jejich rychlosti změřeny. Pro většinu vstupů bylo třetí schéma založené na pozičních haldách shledáno nejrychlejším s minimální cenou v podobě malého počtu falešných pozitiv.

Indexování stromů pro stromové vzorky s Hammingovou vzdáleností

Autor
Alžběta Zyková
Rok
2016
Typ
Diplomová práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Oponenti
Ing. Radomír Polách
Anotace
Tato práce se zabývá indexací stromů pro stromové vzorky s Hammingovou vzdáleností. Na indexaci stromu v prefixové notaci lze nahlížet jako na indexování textu, kde stromové vzorky odpovídají specifickým podsekvencím textu. Samotné indexování textu pro přibližné vyhledávání je řešeno mnoha metodami. Tato práce se v prvé řadě zabývá stávajícími indexy stromů pro stromové vzory. Dále práce obsahuje rešerši stávajících metod na indexaci textu pro přibližné vyhledávání. V práci je představena nová metoda na indexaci stromů pro stromové vzory s Hammingovou vzdáleností. Tato metoda upravuje jeden ze stávajících indexů stromů pro stromové vzory. Pro vyhledávání výskytů využívá indexy textu pro vyhledávání s chybou, které jsou upraveny na využití pro stromy. Výsledná metoda v průměrném případě dokáže vyhledat vzor velikosti m ve stromě velikosti n v čase O( km + sum(occ(Pi))) s velikostí indexu O(n logk n).