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

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

Ing. Petr Máj

Katedra softwarového inženýrství

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.

Práce na DSpace

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

Ing. Ladislav Vagner, Ph.D.

Katedra teoretické informatiky

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.

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

Ing. Jan Baier

Katedra teoretické informatiky

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

Ing. Tomáš Pecka

Katedra teoretické informatiky

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.

Práce na DSpace

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

Ing. Martin Poliak, Ph.D.

Katedra teoretické informatiky

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

Mgr. Petr Matyáš

Katedra teoretické informatiky

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.

Práce na DSpace

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

Ing. Radomír Polách

Katedra teoretické informatiky

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.

Práce na DSpace

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

Ing. Tomáš Pecka

Katedra softwarového inženýrství

Tato práce zkoumá proces nahrazení ručně psaného parseru v Algorithms Lib- rary Toolkit novým parserem generovaným pomocí nástroje ANother Tool for Language Recognition 4 (ANTLR4). Práce začíná seznámením čtenáře se zá- kladními koncepty parsování a parserů, stejně jako s představením ANTLR4 a Algorithms Library Toolkit. Následně je v práci popsán proces integrace gene- rovaného parseru, pomocí nástroje ANTLR4, do stávajícího kódu Algorithms Library Toolkit. Dále jsou popisovány postupy použité k ověření správnosti nového parseru.

Práce na DSpace

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

Ing. Tomáš Pecka

Katedra softwarového inženýrství

Práce se zaměřuje na další rozvoj webového rozhraní knihovny ALT věnované datovým strukturám a algoritmům z oblasti stringologie, arbologie a částečně grafů. Původní verze webového rozhraní je nejprve analyzována se zaměřením na typické případy užití, uživatelské rozhraní, použité technologie i implementaci. Praktická část práce obsahuje analýzu, návrh a samotnou implementaci řešení existujících nedostatků webového rozhraní, především chybějících funkcionalit a chyb. Veškeré změny jsou prováděny v souladu s existujícím řešením s využitím knihoven React a Redux. Konečná verze je otestována pomocí uživatelského testování s důrazem na testování použitelnosti, díky kterému je získána zpětná vazba k novým změnám ale i celkově k webovému rozhraní knihovny ALT.

Práce na DSpace

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

Ing. Radomír Polách

Katedra teoretické informatiky

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.

Práce na DSpace

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

Katedra softwarového inženýrství

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.

Práce na DSpace

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

Ing. Jan Baier

Katedra teoretické informatiky

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.

Práce na DSpace

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

Ing. Radomír Polách

Katedra teoretické informatiky

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

Ing. Radomír Polách

Katedra teoretické informatiky

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.

Práce na DSpace

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

Ing. Jan Baier

Katedra teoretické informatiky

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.

Práce na DSpace

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

Mgr. Jiří Toušek

Katedra softwarového inženýrství

Tato bakalářská práce si klade za cíl ukázat proveditelnost implementace generického extraktoru metadat pro DBMS pomocí JDBC API. V rámci studie byl implementován JDBC extraktor metadat, který může být použit pro všechny relační databázové systémy, které poskytují JDBC rozhraní. Motivací za implementací generického extraktoru metadat bylo vyřešit absenci vhodného generického extraktoru pro všechny databáze v softwarových řešeních Manta pro analýzu datových toků. Byl implementován generický extraktor metadat, který využívá JDBC API pro získání metadat. Extraktor je schopen získávat různé informace, jako je jméno, katalog a schéma procedur, funkcí, tabulek a pohledů. Navíc poskytuje informace o parametrech a návratových typech těchto rutin. Extraktor může získávat informace o sloupcích a jejich datových typech tabulek a pohledů. Extraktor byl testován a jeho schopnost získávat informace o struktuře databáze byla demonstrována. Extrahované položky jsou ukládány do paměti nebo H2 databází pomocí slovníku, který byl implementován pomocí abstrakcí slovníku Manta. Výsledky studie ukázaly, že je proveditelné implementovat generický extraktor metadat pro RDBMS pomocí JDBC API. Implementovaný extraktor může být použit pro databázové systémy podporované JDBC rozhraním. Může poskytnout informace o struktuře databáze, které jsou potřebné pro analýzu dat. Další vývoj a optimalizace extraktoru by mohl vést k ještě efektivnější a výkonnější analýze databáze.

Práce na DSpace

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

Ing. Radomír Polách

Katedra teoretické informatiky

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.

Práce na DSpace

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

Ing. Ondřej Guth, Ph.D.

Katedra teoretické informatiky

Tato bakalářská práce popisuje dopřednou a zpětnou Burrows-Wheelerovu transformaci a obsahuje rešerši existujících algoritmů řešících problém vyhledávání přesného vzorku v transformovaném textu. Přiložena je potom naše otestovaná implementace popsaných datových struktur a algoritmů do fakultního projektu Algorithms Library Toolkit.

Práce na DSpace

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

Ing. Ondřej Guth, Ph.D.

Katedra teoretické informatiky

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

Práce na DSpace

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

Ing. Jakub Novák

Katedra softwarového inženýrství

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.

Práce na DSpace

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

Ing. Eliška Šestáková, Ph.D.

Katedra teoretické informatiky

Tato bakalářská práce se zaobírá návrhem a implementací prototypu editoru konečných automatů na iPad zařízení a následném uživatelském testováním na vytvořeném prototypu. Také obsahuje analýzu webového rozhraní knihovny Algorithms Library Toolkit, této knihovny samotné a přístupů rozeznávání tahů na dotykových zařízení.

Práce na DSpace

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

Ing. Miroslav Hrončok

Katedra softwarového inženýrství

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.

Práce na DSpace

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

doc. RNDr. Alena Šolcová, Ph.D.

Katedra softwarového inženýrství

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

Ing. Tomáš Pecka

Katedra teoretické informatiky

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.

Práce na DSpace

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

Ing. Radomír Polách

Katedra softwarového inženýrství

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.

Práce na DSpace

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

Ing. Ladislav Vagner, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

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

Ing. Ondřej Guth, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

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

Ing. Ondřej Guth, Ph.D.

Katedra teoretické informatiky

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

Práce na DSpace

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

Ing. Radomír Polách

Katedra teoretické informatiky

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.

Práce na DSpace

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

Ing. Ondřej Guth, Ph.D.

Katedra softwarového inženýrství

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

Ing. Radomír Polách

Katedra teoretické informatiky

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.

Práce na DSpace

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

Ing. Radomír Polách

Katedra teoretické informatiky

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.

Práce na DSpace

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

Ing. Jan Baier

Katedra teoretické informatiky

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

Ing. David Bernhauer

Katedra softwarového inženýrství

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

Práce na DSpace

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

Ing. Petr Máj

Katedra teoretické informatiky

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.

Práce na DSpace

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

Ing. Ondřej Guth, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

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

Ing. Petr Košvanec

Katedra teoretické informatiky

Tato práce se zaměřuje na analýzu datových toků v nástroji Azure data factory. Zkoumá reprezentaci datových toků projektu Manta. Prozkoumává a popisuje zdrojové soubory Azure data factory a následně navrhuje způsob, jak analyzovat tyto zdrojové kódy. Všechna zjištění pak využívá při implementaci prototypu skeneru, který bude součástí projektu Manta.

Práce na DSpace

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

Ing. Radomír Polách

Katedra teoretické informatiky

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.

Práce na DSpace

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

Katedra softwarového inženýrství

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.

Práce na DSpace

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

Ing. Tomáš Pecka

Katedra teoretické informatiky

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.

Práce na DSpace

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

Katedra teoretické informatiky

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.

Práce na DSpace

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

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

Katedra teoretické informatiky

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

Práce na DSpace

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

Ing. Radomír Polách

Katedra teoretické informatiky

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.

Práce na DSpace

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

Katedra softwarového inženýrství

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

Práce na DSpace

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

Ing. Ondřej Guth, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

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

Mgr. Jiří Toušek

Katedra softwarového inženýrství

Tato práce se zabývá analýzou datových toků specifikovaných v příkazech SQL dialektu využívaným databází SAP Hana. Nejdříve popisuje, co data lineage je, a různé postupy jejího získání. Dále popisuje jednotlivé SQL příkazy a jejich datové toky. Zahrnuje taktéž návrh a implementaci prototypového nástroje, integrovaného do Manta Flow, který dokáže tvořit grafy na základě poskytnutých vstupních skriptů.

Práce na DSpace

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

Ing. Štěpán Plachý

Katedra teoretické informatiky

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

Práce na DSpace

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

Ing. Radomír Polách

Katedra softwarového inženýrství

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

Ing. Tomáš Pecka

Katedra teoretické informatiky

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

Práce na DSpace

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

Katedra softwarového inženýrství

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

Práce na DSpace

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

Ing. Radomír Polách

Katedra teoretické informatiky

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.

Práce na DSpace

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

Mgr. Radek Mácha

Katedra teoretické informatiky

Tato diplomová práce zkoumá dialekt Databricks SQL a navrhuje metodu automatické analýzy skriptů a prototyp skeneru pro nástroj Manta, který se zabývá data lineage. Data lineage je nezbytná pro integritu a správu dat. Výsledky výzkumu zahrnují komplexní analýzu datového toku v Databricks SQL, návrh a implementaci prototypu skeneru a důkladné testování. Tato práce rozšiřuje schopnosti nástroje Manta v práci se systémy Databricks a poskytují cenný analytický nástroj pro organizace, které spoléhají na Databricks SQL pro zpracování dat.

Práce na DSpace