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

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ů.

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

Ing. Petr Šlegr

Katedra softwarového inženýrství

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

Ing. Jan Trávníček, Ph.D.

Katedra teoretické informatiky

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

Ing. Martin Poliak, Ph.D.

Katedra teoretické informatiky

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

Ing. Radomír Polách

Katedra teoretické informatiky

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

Ing. Jan Trávníček, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

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

Ing. Jan Trávníček, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

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

Katedra teoretické informatiky

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ů.

Práce na DSpace

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

Ing. Martin Poliak, Ph.D.

Katedra softwarového inženýrství

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

Ing. Jan Trávníček, Ph.D.

Katedra teoretické informatiky

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

Katedra teoretické informatiky

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

Ing. Tomáš Zahradnický, Ph.D.

Katedra počítačových systémů

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

Ing. Jan Trávníček, Ph.D.

Katedra teoretické informatiky

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

Ing. Jan Trávníček, Ph.D.

Katedra teoretické informatiky

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).

Práce na DSpace

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

Katedra teoretické informatiky

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ů.

Práce na DSpace

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

Ing. Radomír Polách

Katedra teoretické informatiky

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.

Práce na DSpace

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

Ing. Jan Trávníček, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

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

Ing. Radomír Polách

Katedra teoretické informatiky

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).