Aktuální informace FIT ke koronaviru najdete zde.

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

Závěrečné práce

Bakalářské práce

Nástroj pro extrakci metadat z databáze SAP Hana

Autor
Ondřej Hlaváč
Rok
2020
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Anotace
Statická analýza SQL skriptů vyžaduje informace o objektech uložených v instanci relační databáze, se kterou skript pracuje. Těmto objektům se říká metadata. Tato práce je zaměřena na analýzu metadat v databázi SAP Hana. Popisuje typy databázových objektů využívaných ve skriptech toho databázového stroje a ukazuje jejich možné způsoby extrakce. Také je srovnává s metadaty databáze Microsoft SQL Server a Oracle. Výsledky této analýzy jsou poté využity u návrhu a implementace extrakčního nástroje. Tento nástroj je součástí projektu Manta a je integrován do nástroje Manta Flow. Manta Flow je nástroj používaný k analýze informačních systému pro jejich datové toky, ze kterých následně tvoří vizuální reprezentaci pomocí datových linií. Analýzou informačních systémů se rozumí jejich zdrojový kód, zejména SQL skripty. Výsledný extrakční nástroj z této bakalářské práce plně funkční extraktor nástroje Manta Flow.

Implementace algoritmů vyhledávání v řetězcích s konstantní pracovní pamětí navíc

Autor
Jan Jirák
Rok
2020
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Mgr. Petr Matyáš
Anotace
Cilem této práce je uvedeni do problematiky přesného vyhledáváni v řetězci s požadavkem použiti pouze konstantniho množstvi paměti. Práce se dále zabývá implementaci probiraných algoritmů, které tento problém řeši. Tyto implementace budou integrovány do Algorithms Library Toolkit vyvijeného na FIT ČVUT v Praze. Implementace jsou založeny čistě na pseudokódech z odkazované literatury.

Webový editor konečných automatů

Autor
Petr Svoboda
Rok
2019
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. David Bernhauer
Anotace
Bakalářská práce popisuje proces návrhu a realizace webové aplikace v podobě dynamického editoru konečných automatů. Analyzují se stávající řešení a jejich přínos. Následně se zdůvodňuje výběr zvolených webových technologií a jak byly využity. Práce dále rozebírá problematiku importu a exportu dat pomocí souborů různých formátů a automatické pozicování vytvořených automatů pozicovacími algoritmy. Tato funkčnost je navržena tak, aby byla modulární a nezávislá na zbytku aplikace. V práci se také řeší tvorba přívětivého uživatelského prostředí.

Rozšíření kontejnerů standardní knihovny o notifikace

Autor
Michal Drabina
Rok
2019
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Petr Máj
Anotace
Tato práce se zabývá návrhem a implementací rozšíření kontejnerů standardní knihovny C++ o oznámení pokusů o změnu jejich obsahu. Na základě výsledků vyhodnocení posluchači se operace provede nebo zruší. Implementace je otestována z pohledu funkcionality a poždavků na typy objektů uložených v kontejneru.

Lexikální analyzátor pro C++ generovaný v čase kompilace

Autor
Boris Rúra
Rok
2019
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Ladislav Vagner, Ph.D.
Anotace
Užitečnost lexikální analýzy je nepopiratelná, ať už se jedná o zpracování přirozených jazyků, jako jsou textové zprávy, nebo zpracování zdrojových kódů kompilátory. Zjednodušení jejich tvorby a zvýšení jejich výkonnosti je proto vždy vítáno. Tato práce si klade za cíl ukázat odlišný přístup v tvorbě lexikálních analyzátorů řešením problematiky z metaprogramovací perspektivy s využitím připravovaného standardu C++20. Dokazuje, že metaprogramovací přístup může přinést přinejmenším stejne kompaktní spustitelné soubory jako standartní a zároveň konkurenceschopnou rychlost lexikální analýzy. Dochází k závěru, že se jedná o schodný přístup k problematice a odstraňuje potřebu externích programů, které generují lexikální analyzátory, přestože se překladače v této oblasti stále vyvíjejí a časy kompilace mohou působit potíže.

Rozpoznání konečného automatu z obrazu

Autor
Ondřej Hamák
Rok
2019
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Jakub Novák
Anotace
Tato práce se zabývá převodem obrazu (fotografie) konečného automatu do digitálního textového formátu. Představuje problémy zpracování fotografie, segmentace obrazu a identifikace prvků ručně kreslených diagramů. Součástí práce je návrh algoritmu pro převod diagramu do navržené textové reprezentace a implementace prototypu aplikace na platformě Android.

Návrh a implementace knihovny pro parsování bezkontextových gramatik

Autor
Patrik Valkovič
Rok
2018
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Miroslav Hrončok
Anotace
Cílem práce je vytvořit knihovnu, která striktně oddělí syntaktickou a sémantickou část zpracování strukturovaného textu při zachování snadného použití a jednoduchosti. Práce se zaměřuje na parsování bezkontextových gramatik v jazyce Python. Pro implementaci byl zvolen Cocke-Younger-Kasami algoritmus z důvodu největší robustnosti v oblasti bezkontextových gramatik. Pro zjednodušení práce knihovna implementuje transformace gramatik do Chomského normální formy i jejich opačnou verzi nad parsovacím stromem. Tím knihovna poskytuje univerzální nástroj pro parsování. Knihovna byla úspěšně implementovaná a publikována. Funkčnost knihovny je demonstrována na lambda kalkulu, jenž je parsován a interpretován.

Quick search vyhledávání ve stromech

Autor
Michal Cvach
Rok
2018
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Tomáš Pecka
Anotace
Práce se zabývá problémem hledání stromových vzorů ve stromech. V práci je navržena a následně implementována adaptace algoritmu Quick Search pro hledání stromových vzorů ve stromech. Algoritmus je implementován v projektu Automatová knihovna, dále je též implementován v souboru nástrojů Forest fire & Fire wood, ve kterém byl extenzivně testován a následně porovnán s ostatními algoritmy pro řešení stejného problému, především s algoritmem protisměrného vyhledávání ve stromech. Prezentovaný algoritmus poskytuje o 30 % lepší výsledky než algoritmus protisměrného vyhledávání ve stromech.

Implementace vyhledávání v řetězcích pomocí kompaktního suffixového automatu

Autor
Josef Erik Sedláček
Rok
2018
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Ondřej Guth, Ph.D.
Anotace
Práce se zabývá problémem rozhodnout, jestli pro zadaná slova w a u platí, že u je podslovem w a případně vrátit množinu pozic, kde se u nachází. Konkrétně se zabývá přímou konstrukcí kompaktního suffixového automatu, který dokáže problém rozhodnout s lineární časovou i paměťovou složitostí vzhledem k délce slova w. Výsledkem je implementace algoritmu pro konstrukci automatu v jazyce C++ do Algoritmové knihovny ALIB.

Grafy a grafové algoritmy pro knihovnu algoritmů

Autor
Jan Uhlík
Rok
2018
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Radomír Polách
Anotace
Tato bakalářská práce vylepšuje implementaci grafů a grafových algoritmů v knihovně algoritmů ALib vyvíjené na Katedře teoretické informatiky FIT ČVUT v Praze. Hlavní důraz je kladen na univerzalitu návrhu, který vede ke snadnému používaní a jednoduchému rozšíření. Práce dále přidává do této knihovny nové doposud nenaimplementované algoritmy pro prohledávání grafů a hledání cest v nich. Práce také obsahuje měření původních i nově přidaných algoritmů a porovnává experimentálně naměřené hodnoty s teoretickými poznatky.

Návrh a implementace modifikací algoritmu protisměrného vyhledávání ve stromech

Autor
Kamil Červený
Rok
2018
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Tomáš Pecka
Anotace
V této práci je navrhnutý nový algoritmus pro vyhledávání ve stromech. Jeho fungování je založeno na myšlence heuristiky good-suffix-shift algoritmu Boyer-Moore pro vyhledávání v řetězcích a poznatcích z existujícího adaptovaného algoritmu Morris-Pratt pro stromy. Algoritmus najde všechny výskyty vyhledávaného vzoru stromu v daném prohledávaném stromě, k tomu využívá dvě pomocné datové struktury. Při běhu algoritmu jsou vstupní stromy převedeny do linearizované podoby, konkrétně do postfixové, rankové notace. Implementovaný algoritmus je na závěr testován s nejlepšími existujícími algoritmy pro vyhledávání ve stromech a výsledky měření ukazují, že se řadí mezi nejrychlejší z nich.

Vylepšení GUI ke knihovně algoritmů ALIB

Autor
Martin Hanzík
Rok
2018
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Ondřej Guth, Ph.D.
Anotace
Předmětem této práce je analyzovat nedostatky grafického uživatelského rozhraní existující aplikace pro práci s algoritmovou knihovnu ALT, navrhnout jejich vylepšení a implementovat je. Text se věnuje návrhovému vzoru "pipes and filters" a prozkoumání existujících aplikací využívajících tento vzor. Dále analyzuje způsob, kterým knihovna poskytuje informace o existujících algoritmech a prozkoumá možnosti plánování paralelního provádění pomocí kombinace synchronizačních primitiv a plánovacích algoritmů. Nakonec je provedeno jednoduché uživatelské testování.

Konstrukce a simulace vyhledávacích automatů přesného a přibližného vyhledávání

Autor
Tomáš Čapek
Rok
2018
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Radomír Polách
Anotace
Cílem této práce je implementovat algoritmy konstrukce vyhledávacích automatů. Dále se práce zabývá simulacemi tohoto druhu automatů. V práci jsou implementovány metody, používající Hammingovu, Levenshteinovu a Zobecněnou Levenshteinovu vzdálenost. Tato práce je součástí projektu Algoritmová knihovna.

Podpora pro tvorbu semestrální práce z předmětu Programovací jazyky a překladače

Autor
Jan Dejdar
Rok
2017
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Radomír Polách
Anotace
Tato bakalářská práce se zabývá tvorbou dokumentace pro semestrální práci z předmětu Programovací jazyky a překladače na Fakultě informačních technologií ČVUT a aktualizací dodávaných materiálů tak, aby využívaly aktuální stabilní verzi skupiny kompilátorů GCC. Práce se zejména zaměřuje na rozhraní pro komunikaci přední a střední části překladače ve skupině kompilátorů GCC a tvorbu abstraktního syntaktického stromu.

Implementace algoritmu hledání repetic ve stromech

Autor
Aleksandr Shatrovskii
Rok
2017
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Ondřej Guth, Ph.D.
Anotace
Předmětem této práce je implementace algoritmu hledání repetic v ohodnocených označených uspořádaných stromech. V práci je podrobně analyzován a popsán efektivní algoritmus, předloženy Michalisem Christou a dalšími, je prozkoumaná vnitřní reprezentace stromových struktur v Automatové knihovně. Algoritmus a další potřebné podpůrné struktury jsou začleněny do Automatové knihovny. Implementace je otestována pomocí předdefinovaných a náhodně generovaných stromů.

Návrh a implementace jazyka s jednoduchou, bezpečnou a efektivní správou paměti

Autor
Miroslav Kravec
Rok
2017
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Radomír Polách
Anotace
Jednoduchosť použitia, efektívne využívanie prostriedkov, a bezpečnosť voči poškodeniu pamäte sú dôležité vlastnosti správ pamätí. Pre ich dosiahnutie sa práca zameriava na správu pamäte založenú na regiónoch . V práci boli analyzované existujúce jazyky, navrhnutý vlastný jazyk a k nemu implementovaný prototyp ako predná časť prekladača LLVM.

Návrh a implementace stromových datových struktur pro C++

Autor
Vladimír Vojáček
Rok
2017
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Ondřej Guth, Ph.D.
Anotace
Ve své bakalářské práci jsem se zaměřil na návrh a implementaci stromových struktur v programovacím jazyce C++. Struktury jsem navrhl s ohledem na analýzu referenčních algoritmů Aho Corasick a Position heap. Na základě návrhu jsem struktury implementoval a jejich správnou funkci otestoval na zmíněných algoritmech. Čtenář se může v této práci seznámit s návrhem a připravenými strukturami, které může v této podobě použít, nebo na jejich základě vytvářet vlastní struktury se specializovanými požadavky.

Implementace klienta a serveru pro ovládání a interpretaci robota Karel

Autor
Stefan Ćirić
Rok
2017
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Radomír Polách
Anotace
Obsahem této práce je implementace systému klient-server pro robota Karla. Systém bude implementován na čipu Arduino ESP8266 WiFi, na který se uživatelé připojí pomocí WiFi a budou tak schopni komunikovat s robotem prostřednictvím poskytované webové stránky. Práce podrobně popisuje čip Arduino ESP8266 WiFi, na kterém je systém vyvíjen, zároveň plně vysvětluje pojmy programovací jazyk Karel, robot Karel a ukazuje, co je robotovým úkolem a čeho může dosáhnout. Druhá část se zaměřuje na návrh a implementační techniky vybrané pro splnění práce a předvádí vnitřní strukturu a architekturu projektu.

Detekce nespecifikovaného chování v C

Autor
Martin Holoubek
Rok
2016
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Ladislav Vagner, Ph.D.
Anotace
Tato práce se zabývá problematikou nespecifikovaného chování programovacího jazyka C v kompilátoru GCC. Dále je představen a diskutován algoritmus detektoru nespecifikovaného chování. Zvolené řešení je popsáno a implementováno do kompilátoru GCC. Výsledky této práce rozšiřují schopnosti kompilátoru a usnadňují práci s ním.

Měření v automatové knihovně

Autor
Radovan Červený
Rok
2016
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Jan Baier
Anotace
Předmětem této práce je rozšíření Automatové knihovny pro měření času běhu algoritmu, paměti spotřebované algoritmem, a obecných událostí pro profilování algoritmu. Dále jsou navrženy a implementovány aplikace pro automatizaci měření a základní zpracování výsledků měření. Automatová knihovna je rozšířena o tři nové implementace algoritmů pro řetězcové vyhledávání. Nakonec jsou prezentovány výsledky experimentálního měření nových i některých již existujících algoritmů Automatové knihovny.

Automatová knihovna - konstrukce LR analyzátoru

Autor
Martin Kočička
Rok
2016
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Jan Baier
Anotace
Předmětem této práce jsou základní LR parsovací algoritmy. Práce v úvodu popisuje obecně bottom-up a shift-reduce parsování. Dále se zaměřuje na LR parsování, specificky LR(0) a SLR(1) parsery. Práce obsahuje návrh potřebných datových struktur a algoritmů pro implementaci těchto parserů. Jsou prozkoumána existující řešení, a přidán základní popis Automatové knihovny. Práce je součástí projektu Automatová knihovna.

Generátor syntaktického analyzátoru s transformacemi gramatik

Autor
Matěj Uzel
Rok
2016
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Petr Máj
Anotace
Práce rozebírá principy provádění deterministické jednoprůchodové syntaktické analýzy. Především je kladen důraz na přístup shora dolů metodu rekurzivního sestupu. Dále se práce zabývá transformacemi gramatik na LL(1) gramatiky, které jsou očekávaným vstupem zmíněné metody, dále také překladem popsaným S-atributovanými a L-atributovanými překladovými gramatikami. Součástí práce je dokumentace implementovaného generátoru parseru, který implementuje zmíněnou teorii.

Automatová knihovna - Stromové automaty a algoritmy nad stromy

Autor
Štěpán Plachý
Rok
2015
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Radomír Polách
Anotace
Práce se zabývá konečnými stromovými automaty, což je výpočetní model pro zpracování regulárních stromových jazyků, a jejich implementací v projektu Automatová knihovna. V práci jsou navrženy a implementovány datové struktury stromů a stromových automatů, kterými je nutné knihovnu rozšířit. Z algoritmů je v práci navrženo a implementováno generování náhodných ohodnocených a neohodnocených označených uspořádaných stromů, determinizace bottom-up konečného stromového automatu, přijetí ohodnoceného stromu deterministickým a nedeterministickým bottom-up stromovým automatem a hledání výskytů jazyka deterministického bottom-up konečného stromového automatu v ohodnoceném stromu.

Přední část překladače GCC pro vnitřní formu GCC

Autor
Martin Senko
Rok
2015
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Radomír Polách
Anotace
Tato praca analyzuje jeden zo vstavanych vystupnych formatov vnutornej reprezentacie programu v GCC a informacnu hodnotu, ktoru obsahuje. Praca dalej obsahuje navrhy na jeho rozsirenie a popisuje implementaciu prednej casti prekladaca, ktora prijma dany vystupny format a realizuje jeho preklad do vnutornej reprezentacie GENERIC.

Porovnání implementací předních částí překladačů GCC a LLVM

Autor
Ivan Ryšavý
Rok
2015
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Radomír Polách
Anotace
Práce se zabývá implementací předních částí překladačů GCC a LLVM. Přední části zpracují a analyzují zdrojový kód jazyka Mila, který transformují ve vnitřní formu daného překladače. Jazyk Mila je zde rozebrán a je pro něj implementován lexikální analyzátor, parser a abstraktní syntaktický strom, což je v práci dokumentováno. V práci je kladen důraz na detailní popis a porovnání využitých rozhraní GCC a LLVM. Na základě tohoto popisu může kdokoliv další vytvořit novou přední část pro zmíněné překladače. Porovnáním bylo zjištěno, že implementace přední části pro LLVM je oproti GCC náročnější, protože se od přední části vyžaduje větší předzpracování zdrojového kódu. Obě přední části byly úspěšně implementovány a jsou otestovány sadou vzorových programů, které pokrývají všechny implementované funkcionality. Zdrojové kódy předních částí a vzorových programů jsou spolu s kompletní LL(k) gramatikou jazyka Mila k nalezení v příloze.

Vizualizace protisměrného vyhledávání ve stromech

Autor
Josef Rypáček
Rok
2015
Typ
Bakalářská práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Radomír Polách
Anotace
Tato bakalářská práce se zabývá vizualizací protisměrného vyhledávání vzorků ve stromech. Popisuje návrh a požadované vlastnosti vizualizace. Pojednává o výběru technologií a na základě požadavků a analýzy implementuje vizualizaci. V práci jsou porovnávány způsoby implementace a jejím výsledkem je webová aplikace pro vizualizaci algoritmu.

Diplomové práce

Nástroj na extrakci datových toků pro programovací jazyk Cobol

Autor
Andrej Taňkoš
Rok
2021
Typ
Diplomová práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Anotace
Táto práca sa zaoberá analýzou dátových tokov programovacieho jazyka COBOL, konkrétne IBM COBOL dialektu. Práca najprv skúma rôzne prístupy k analýze dátových tokov, ich reprezentáciu a vizualizáciu v projekte Manta. Následne je jazyk IBM COBOL analyzovaný s cieľom identifikovať dôležité konstrukty jazyka, v ktorých prebieha presun a používanie dát. Práca obsahuje rešerš existujúcich riešení, ktoré by pomohli pri syntaktickej analýze jazyka COBOL. Na základe existujúcich riešení a výsledku analýzy je extraktor dátových tokov navrhnútý a implementovaný pre projekt Manta. Funkčnosť výsledného riešenia je ukázaná na sade testov a príkladov.

Quantum leap vyhledávání v linearizovaných stromech

Autor
Josef Erik Sedláček
Rok
2021
Typ
Diplomová práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Štěpán Plachý
Anotace
Práce se zabývá vyhledáváním stromových vzorů ve stromech. Konkrétně se pracuje s linearizovanými stromy v prefixové notaci. Práce přejímá myšlenku algoritmu Quantum Leap pro vyhledávání v řetězcích a využívá ji pro vyhledávání vzorů ve stromech. Několik verzí algoritmu je implementováno do souboru nástrojů Forest FIRE a nejlepší z nich jsou srovnány s již existujícími algoritmy ve zmíněném souboru nástrojů.

Analýza datových toků v Google BigQuery skriptech

Autor
Kyrylo Bulat
Rok
2021
Typ
Diplomová práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Anotace
Tato práce je zaměřena na analýzu datových toků v Google BigQuery skriptech a jejich reprezentaci. Nejprve popisuje přístupy, které se používají pro data lineage, analýzu zdrojového kódu a vizualizaci toku dat v systému Manta. Poté zkoumá technologii Google BigQuery, její databázové objekty a syntaxi jejího SQL dialektu. Pokračuje popisem architektury a návrhu implementovaného prototypu. Poslední kapitoly této práce jsou věnovány testování a prezentaci výstupů vytvořeného prototypového řešení.

Implementace vylepšených suffixových polí a jejich použití

Autor
Minh Trieu Quang
Rok
2020
Typ
Diplomová práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Ondřej Guth, Ph.D.
Anotace
Hlavní nevýhodou suffixového stromu je velká paměťová náročnost. Jedna z paměťově efektivnějších struktur je suffixové pole, a nedávno se ukázalo, že každý algoritmus řešený suffixovým stromem lze nahradit stejně časově efektivním algoritmem využívajícím suffixového pole, pokud jej rozšíříme o další informace a struktury. Řešení navrhuje datovou strukturu vylepšeného suffixového pole (ESA) v C++ a implementaci vybraných algoritmů, které simulují tři odlišné průchody suffixového stromu. Toto řešení je důkladně otestováno, vyzkoušeno a proběhlo experimentální vyhodnocení algoritmů využívající suffixový strom a navrhovanou datovou strukturu.

Extrakce metadat, parsování a detekce datových toků pro sql dialekt Snowflake

Autor
Marek Tornóci
Rok
2020
Typ
Diplomová práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Anotace
Práca sa zaoberá analýzou dátových tokov SQL dialektu Snowflake a možnosťami ich reprezentácie. Práca najprv skúma spôsob akým je potrebné analyzovať zdrojové SQL skripty, ich reprezentáciu a vizualizáciu dátových tokov pomocou systému Manta. Práca sa ďalej zaoberá skúmaním databázových objektov, ich metadát potrebných k extrakcií, spôsobom akým je možné tieto objekty extrahovať a analyzuje samotný SQL dialekt Snowflake. Na základe tejto analýzy vznikne návrh prototypu riešenia a jeho implementácia pokrytá testami, ktoré overujú jeho funkčnosť.

Analýza datových toků jazyka SAS code

Autor
Miroslav Špak
Rok
2019
Typ
Diplomová práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Anotace
Práce se zabývá analýzou datových toků v jazyce SAS a možnostmi jejich reprezentace. Nejprve zkoumá způsob analýzy zdrojových kódů, jejich reprezentaci a následnou vizualizaci datových toků pomocí cílového systému Manta. Poté přejde k syntaxi a sémantice jazyka SAS a zmíní rozdíly oproti jiným jazykům používaným v systémech pro ukládání dat. Pokračuje možnostmi nástroje SAS studio, prozkoumá data uložená za pomocí tohoto nástroje, jejich strukturu a možnosti práce s těmito daty pomocí jazyka SAS. Na základě této analýzy vznikne návrh prototypu řešení, jeho implementace a testy ověřující správnou funkčnost.

Převod konečných stromových automatů na stromové regulární výrazy

Autor
Jakub Doupal
Rok
2019
Typ
Diplomová práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Tomáš Pecka
Anotace
Tato diplomová práce studuje regulární stromové výrazy a metodu převodu ze stromového automatu na regulární stromový výraz pomocí rovnic. Daná metoda je poté implementována v knihovně algoritmů vyvíjené na Katedře teoretické informatiky na Fakultě informačních technologií na ČVUT v Praze. Tato práce dále studuje axiomy pro regulární stromové výrazy a také navrhuje nové. Tyto axiomy pak jsou také implementovány v knihovně algoritmů.

Konverze stromových konečných automatů na stromové regulární výrazy metodou eliminace stavů

Autor
Tomáš Dejmek
Rok
2019
Typ
Diplomová práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Tomáš Pecka
Anotace
Tato diplomová práce se zabývá stromovými jazyky. Stromový jazyk se skládá z množiny stromů, podobně jako textový jazyk se skládá z množiny textových řetězců. Jelikož byla dokázána rovnost mezi třídou jazyků přijímaných konečnými stromovými automaty a třídou jazyků popisovanou regulárními stromovými výrazy, tak je možné provádět převody. Já se zaměřují na převod konečných stromových automatů na regulární stromové výrazy. Během práce je představeno jedno současné řešení a další dva nové přístupy jsou navrženy a implementovany. Práce také zahrnuje porovnání nových algoritmů včetně měření zavedené kvality výsledku.

Minimalizace stromových a zásobníkových automatů

Autor
Štěpán Plachý
Rok
2017
Typ
Diplomová práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Radomír Polách
Anotace
Práce se zabývá vztahem mezi konečnými stromovými automaty a zásobníkovými automaty, a jejich minimalizací. Konečné Stromové automaty jsou rozšířením konečných automatů a zpracovávají regulární stromové jazyky. V práci jsou popsané algoritmy redukce a minimalizace konečných stromových automatů, jejich převodu na zásobníkové automaty přijímající ekvivalentní jazyk v postfixovém zápisu a minimalizací převedených automatů. Všechny algoritmy jsou dále implementovány do projektu Automatová knihovna.

Vyhledávání ve stromech na principu mrtvých zón

Autor
Robin Obůrka
Rok
2016
Typ
Diplomová práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
doc. Ing. Jan Janoušek, Ph.D.
Anotace
V práci jsou představeny dva nové algoritmy pro vyhledávání ve stromech - sousměrný algoritmus (založený na algoritmu Morris-Pratt) a algoritmus na principu mrtvých zón. Algoritmy naleznou všechny výskyty daného stromového vzorku, které odpovídají vstupnímu stromu. Vzorek i vstupní strom jsou použity v linearizované podobě. Algoritmy používají podobné principy jako jejich řetězcové alternativy, které jsou podle potřeby modifikované. Velikost pomocné struktury, která je zkonstruovaná pro sousměrný algoritmus, je lineární vzhledem k velikosti vzorku. Algoritmus na principu mrtvých zón používá dvě pomocné struktury, jedna je opět lineární vzhledem k velikosti vzorku a druhá je lineární vzhledem k velikosti abecedy. Algoritmy jsou porovnány s doposud nejvýkonnějšími existujícími algoritmy, které jsou založeny na konečných stromových automatech, "stringpath" vyhledávání a s protisměrným algoritmem pro vyhledávání ve stromech. Měření ukazují, že dopředný algoritmus pro vyhledávání ve stromech tyto algoritmy výkonem překonává a algoritmus na principu mrtvých zón je s nimi srovnatelný. Jejich časová složitost je z teoretického úhlu pohledu o něco horší než u jejich řetězcových alternativ ale předpokládá se, že bude dále vylepšena. Pro sousměrný algoritmu může být během samotného vyhledávání počet porovnání symbolů v nejlepším případě lineární a v případě algoritmu na principu mrtvých zón dokonce sub-lineární.

Konstrukce zásobníkového automatu přijímajícího jazyk daný regulárním stromovým výrazem

Autor
Tomáš Pecka
Rok
2016
Typ
Diplomová práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Radomír Polách
Anotace
Tato práce studuje regulárni stromové výrazy, formalismus pro popis regulárnich stromových jazyků. Hlavnim přinosem práce je nový algoritmus pro převod regulárniho stromového výrazu na ekvivalentni zásobnikový automat, který přijimá stromy v lineárnim postfixovém zápisu. Výsledný automat patři do kategorie real-time height-deterministic zásobnikových automatů, což znamená, že je vždy zdeterminizovatelný. Algoritmus vytvářejici tento automat je modifikaci Glushkovova algoritmu pro převod regulárnich výrazů na nedeterministický konečný automat. Implementace převodu je v jazyce C++ jako rozšiřeni Automatové knihovny.