Ing. Ondřej Guth, Ph.D.

Ing. Ondřej Guth, Ph.D.

Katedra softwarového inženýrství

Ing. Ondřej Guth, Ph.D.

Ing. Tomáš Pecka

Katedra teoretické informatiky

Tato práce staví na publikaci Kędzierského and Radoszewského, kteří představili vylepšené polynomiální algoritmy řešící problém k-přibližných pokrytí řetězců nad Hammingovou, Levenshteinovou a váženou editační vzdáleností. Práce tyto algoritmy důkladně popisuje, vysvětluje a poskytuje jiný úhel pohledu. Algoritmy jsou implementovány a problémy, které řesí jsou zasazeny do kontextu dalších pravidelností v řetězcích. Implementce je experimentálně otestována a jsou popsány hlavní implementační kroky.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Miroslav Skrbek, Ph.D.

Katedra softwarového inženýrství

Ing. Ondřej Guth, Ph.D.

Mgr. Petr Matyáš

Katedra softwarového inženýrství

Cieľom tejto bakalárskej práce je vytvoriť informačný systém na organizáciu matematického korešpondenčného seminára Riešky. Po dôkladnom preskúmaní súčasného stavu organizácie a analýze požiadaviek organizátorov bol navrhnutý informačný systém ako webová aplikácia vo frameworku Ruby on Rails s využitím databázy MySQL. Implementovaná webová aplikácia bola ďalej riadne otestovaná jednotkovými testami aj samotnými organizátormi súťaže. Výsledný informačný systém bol nasadený na server organizácie pomocou nástrojov Phusion Passenger a Capistrano. Informačný systém má v budúcnosti uľahčiť a zefektívniť prácu organizátorov.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

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

Katedra softwarového inženýrství

Cílem práce je navrhnout, implementovat a otestovat desktopový klient pro sociální síť Twitter. Tento klient je určený pro desktopové prostředí KDE Plasma 5 jako miniaplikace která je připnutá na ploše počítače. Aplikace přímo na ploše zobrazuje upozornění a nejnovější příspěvky ze sítě Twitter, umožňuje na síť vkládat příspěvky, umí odesílat a zobrazovat soukromé zprávy. Výsledkem této práce je funkční aplikace, která byla řádně otestována.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Tomáš Pecka

Katedra teoretické informatiky

Táto práca sa zaoberá popisom automatových algoritmov na hľadanie približných rozšírených pokrytí a uvoľnených približných rozšírených pokrytí a ich implementáciou do knižnice algoritmov ALT. Maximálny počet chýb, ktorým je vyjadrená približnosť, je počítaný Hammingovou vzdialenosťou. Základom algoritmov je deterministický sufixový konečný automat, ktorý vzniká z nedeterministického sufixového konečného automatu podmnožinovou metódou.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

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

Katedra teoretické informatiky

Tato diplomová práce si dává za úkol navrhnout a vyvinout vylepšené integrované vývojové prostředí, které vyřeší problémy a zreviduje schopnosti stávajícího Scriptovacího Editoru. Tento Scriptovací Editor je užíván k vývoji a implementaci skriptu, používající DET skriptovací jazyk popsán v diplomové práci \cite{grankin_2019}. DET jazyk má syntaxi založenou na Java jazyce s vlastními rozšířeními reprezentující Java proměnné a Java metody. Vady předchozí implementace jsou řešeny v prototypu projektu, který je předmětem této práce. K rozvoji podpory pro DET skriptovací jazyk jsou použity dnešní moderní postupy. Současný stav je prezentován společně s preferovanou metodologií zpracování uživatelských vstupů.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

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

Katedra softwarového inženýrství

Práce obsahuje analýzu, návrh, implementaci a testování prototypu aplikace, která přiděluje učitelům rozvrhová místa na základě jejích preferencí. Nástroj se skládá ze serveru napsaného v jazyce Java a webového rozhraní pro administrátory a učitele, implementovaného s využitím šablonového enginu Thymeleaf. Účelem systému je přijímat od učitelů preferované možnosti rozvrhu a vytvářet možné rozvrhy, které tyto možnosti splňují. Základní část funkčního modulu, algoritmus typu backtracking, provádí paralelní a asynchronní výpočet rozvrhů. Práce začíná obecnou analýzou problému, včetně jeho primárních aspektů, funkčních a nefunkčních požadavků, případů užití, zkoumání existujících řešení a doménových modelů. Následující kapitoly se zabývají návrhem a implementací prototypu. Nakonec práce končí koncepty budoucích vylepšení na základě provedeného uživatelského testování hlavní funknosti.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

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

Katedra softwarového inženýrství

Cílem práce je navrhnout, implementovat a otestovat klient pro službu Toggl, jejíž hlavní vlastností je počítání času stráveného na každé virtuální ploše. Klient je určen uživateli desktopového prostředí KDE. Část návrhu je postavena na výsledcích získaných při analýze existujících aplikací a na analýze uživatelských požadavků. Implementační část popisuje technologii, která byla použita při realizaci programu. Klient je otestován klasickými metodami testování softwaru a ohodnocen uživateli pomocí testování použitelnosti.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Daniel Dombek, Ph.D.

Katedra softwarového inženýrství

Tato bakalářská práce řeší návrh, implementaci a testování aplikace pro datové spojení Studijního informačního systému KOS a softwaru pro tvorbu rozvrhu Scientia Syllabus Plus. Svého účelu dosahuje pomocí grafického rozhraní. To umí zobrazit data z obou systémů a rozdíly mezi nimi. Dále umožňuje částečné převody na úrovni jednotlivých položek. Výsledek práce poslouží fakultnímu rozvrháři při tvorbě rozvrhu na Fakultě informačních technologií.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Michal Valenta, Ph.D.

Katedra softwarového inženýrství

Bakalářská práce se věnuje návrhu a implementaci mobilni aplikace, která slouži k zobrazováni statistik soutěži pořádaných Českým Tenisovým Svazem. Dále se tato práce zabývá návrhem a implementaci softwaru sloužiciho k ziskáváni a zpracováváni dat z webových stránek českého tenisového svazu.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Tomáš Kalvoda, Ph.D.

Katedra softwarového inženýrství

Cieľom tejto bakalárskej práce je analyzovať, navrhnúť a implementovať Administrátorskú časť rezervačného systému pre FIT. Aplikácia získava dáta zo školských systémov a poskytuje ich formou webovej služby. Implementácia je založená na platforme Java EE.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Katedra teoretické informatiky

Ing. Ondřej Guth, Ph.D.

Ing. Lukáš Bařinka

Katedra softwarového inženýrství

Tato práce pojednává o návrhu a implementaci miniaplikace na plochu určené k organizaci úkolů využívající služby Remember the milk. Na základě požadavků a výsledků analýzy je navržena nová miniaplikace eliminující problémy předcházejících řešení. V práci je uvedena analýza, návrh, postup řešení a testování klienta. Výsledkem implementační části práce je miniaplikace na plochu linuxového prostředí KDE Plasma 5.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Eliška Šestáková

Katedra teoretické informatiky

Cilem této práce je návrh a implementace vylepšeného skriptovaciho enginu, řešeni problémů a návrh nových vlastnosti existujici proprietárni implemen- tace tohoto enginu. Skriptovaci engin se použivá ke zpracováni skriptů nap- saných v jazyce založeném na Javě. Hlavni nedokonalost existujiciho skrip- tovaciho enginu DET je použiti výhradně regulárnich výrazů na zpracováni skriptu. Toto je řešeno v prototypu, který je předmětem této práce. Důraz je kladen na běžně použivanou techniku konstrukce překladačů: skriptovaci jazyk je popsán gramatikou, dále se pracuje s abstraktnim syntaktickým stromem.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Michal Šoch, Ph.D.

Katedra softwarového inženýrství

Práce se zabývá analýzou stávajícího systému pro správu ubytovacích zařízení a implementací nového. Na základě analýzy a nových potřeb uživatelů jsou definovány požadavky nového systému. Rešerše zkoumá hotová řešení a porovnává tři z nejpoužívanějších PHP frameworků. V každém z těchto frameworků je napsána ukázková aplikace demonstrující jeho fungování. Na základě požadavků je navržena nová aplikace, která je implementována ve frameworku Symfony a její funkčnost je otestována pomocí automatických testů. Nová aplikace je oproti stávající optimalizována pro mobilní zařízení a přináší správu vícejazyčného obsahu a rezervační systém. Závěrem je provedeno testování použitelnosti a jsou opraveny nalezené nedostatky.

Ing. Ondřej Guth, Ph.D.

Mgr. Andor Pathó

Katedra softwarového inženýrství

V práci je vysvětlen současný systém vývoje softwaru ve firmě Dlubal Software s.r.o. Všechny informace o úkolech a chybách jsou evidovány informačním systémem NET Genium. Ve vývojových týmech probíhá komunikace o úkolech pomocí fyzické přehledové tabule umístěné v kancelářích. Na tabulích jsou informace zkopírovány z NET Genia. Práce vysvětluje nedostatky současného řešení. Proto je vypracované nové řešení -- program týmových tabulí, který nahrazuje fyzickou tabuli a odstraňuje zjištěné nedostatky současného řešení. V práci je vypracována analýza a implementace programu týmových tabulí. Závěrečná část práce se zabývá testováním použitelnosti, které odhaluje nedostatky návrhu a implementace. Obsahem práce je také návod k nastavení vývojového prostředí a kompilaci programu na nasazení.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Jiří Daněček

Katedra softwarového inženýrství

Táto práca sa zaoberá návrhom a tvorbou užívateľského rozhrania rezervačného systému učební FIT, formou webovej aplikácie postavenej na platforme Java EE.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Miroslav Prágl, MBA

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

Tato práce se zabývá propojením (neboli integrací) poštovního klienta Mozilla Thunderbird s e-mailovým serverem Microsoft Exchange pomocí Exchange Web Services (EWS). Řešení je realizováno jako zásuvný modul, který se do klienta Thunderbird musí nainstalovat. Mezi hlavní cíle této práce patří uživatelská přívětivost při instalaci modulu i jeho používání. Dále by modul měl být nezávislá jednotka, tzn. nemělo by být nutné, aby uživatel musel instalovat nebo spouštět další software pro správný chod. Funkčnost modulu je omezena na přijímání a odesílání e-mailových zpráv. Modul by měl být dostupný pro operační systémy Microsoft Windows a Linux jako svobodný software s otevřeným kódem (opensource). Jak všech cílů bylo dosaženo je popsáno v této práci.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Jiří Novák, Ph.D.

Katedra softwarového inženýrství

Cílem této práce je implementaci čtyř vybraných vícevláknových algoritmů do knihovny JGraphT. Jedná se o Java knihovnu poskytující grafové datové struktury a související algoritmy. Čtyři vybrané vícevláknové algoritmy jsou BFS, DFS, Dijkstra a Bellman-Ford. První část práce se zabývá samotnou knihovnou a popisem jejích hlavních částí. Druhá část se soustředí na samotné algoritmy, přesněji jejich vícevláknové verze a jejich teoretický popis. Třetí část obsahuje implementační požadavky a technické detaily samotné implementace. Poslední část práce potom prezentuje výsledky testů, hodnotí efektivitu jednotlivých implmementovaných algoritmů a zkoumá naplnění implementačních požadavků. Hlavním výstupem této práce je implementace daných algoritmů, která vhodně využívá prvky knihovny JGraphT, je řádně otestována a zdokumentována.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

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

Katedra softwarového inženýrství

Tato práce popisuje proces analýzy, návrhu, implementace a testování systému pro vyhledávání spolucestujících. Tento systém se skládá z aplikace pro Android a serveru. Celý systém je vyvíjen pomocí moderních technologií. Server je nasazen do cloudového prostředí a využívá různé služby nabízené poskytovatelem cloudu. Výsledkem této práce je kompletní systém, který je připraven k distribuci široké veřejnosti. Na základě provedeného uživatelského testování je zde prostor pro budoucí vylepšení a rozšíření systému o nové funkce.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

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

Katedra teoretické informatiky

V této práci jsem se zaměřil na dva algoritmy hledající vlastní přibližná jádra řetězců. Na řešení tohoto problému existují dva odlišné algoritmy. Za účelem jejich srovnání jsem provedl sadu experimentů s těmito algoritmy. Experimenty byly zaměřeny na vliv jednotlivých parametrů tohoto problému na vlastnosti těchto algoritmů, a také na jejich srovnání. Proto abych nemluvil pouze o černých skříňkách, nachází se v této práci i popis těchto algoritmů a popis problému, které řeší.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Michal Šoch, Ph.D.

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

Bakalářská práce se zabývá návrhem a implementací autentizačního řešení pro Java Enterprise Edition (Java EE) aplikace se systémem jednotného přihlášení Shibboleth, s využitím standardních nástrojů Java EE a aplikačního serveru GlassFish. V závěru je popsáno ověření funkčnosti a zhodnocení implementovaného řešení.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Jiří Mlejnek

Katedra softwarového inženýrství

Tato bakalářská práce se zabývá vývojem mobilní aplikace pro Android, jejímž primárním cílem je zobrazování rozvrhových událostí studentů a učitelů na Fakultě informačních technologií ČVUT a volných místností. Aplikace čerpá data z aplikačních rozhraní Sirius a KOSapi. V aplikaci bylo použito OAuth 2.0 protokolu za účelem autorizace. Práce postupně popisuje jednotlivé fáze vývoje aplikace od analýzy, návrhu přes realizaci až po testování. Nakonec je popsán směr, kterým bude aplikace v budoucnu směřovat. Výsledek práce je funkční mobilní aplikace s prototypem uživatelského rozhraní.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Tomáš Pecka

Katedra teoretické informatiky

Předmětem této práce je seznámení s algoritmy řešícími problém hledání pravidelností v textech. Konkrétně se v práci probírají přesná pokrytí řetězců a přibližná pokrytí řetězců pro Hammingovu vzdálenost. Všechny algoritmy této práce jsou postavené na konečných automatech. Hlavním cílem práce je implementace zkoumaných algoritmů do Algoritmové knihovny vyvíjené na katedře Teoretické informatiky FIT ČVUT v Praze.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

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

Katedra teoretické informatiky

Rozšířením tradiční syntaxe regulárních výrazů o zpětné reference vznikne mocný prostředek, kterým lze popsat jazyky silnější než regulární. Tato bakalářská práce se zabývá problémem zpracování regulárních výrazů se zpětnými referencemi. V práci je implementován v jazyce C++ algoritmus založený na konstrukci vícepáskového Turingova stroje a algoritmus od Schmida, který řeší verzi tohoto problému parametrizovanou stupněm aktivních proměnných (active variable degree). V závěru je program testován a porovnán s již existujícími nástroji pro práci s regulárními výrazy na vytvořených sadách testů. Mimo jiné je v práci předložen alternativní důkaz věty o NP-úplnosti zkoumaného problému.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

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

Katedra softwarového inženýrství

Tato práce se zaměřuje na návrh a implementaci grafického uživatelského rozhraní pro automatovou knihovnu ALIB. Text obsahuje popis knihovnou nabízených funkcí a analýzu podmnožiny funkcí, které budou nabízeny grafickým rozhraním. Dále obsahuje rešerši existujících aplikací pracujících s automaty a jejich porovnání, návrh vlastního grafického rozhraní a architektury aplikace. Cílem práce bylo vytvořit pro uživatele zajímavé grafické rozhraní k ovládání automatové knihovny ALIB. Hlavní myšlenkou navrženého rozhraní je poskytnout uživateli stavební bloky, funkce knihovny, a nechat jej seskládat řešení jeho problému. Původně bylo možné využít funkce knihovny pouze z příkazové řádky. Při implementaci byl využit programovací jazyk C++ a framework Qt. Výstupem práce je vlastní program s grafickým rozhraním zpřístupňující funkce knihovny ALIB. Vzniklý kód je pod opensource licencí.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Eliška Šestáková

Katedra softwarového inženýrství

Tato práce se zaměřuje na tvorbu aplikace umožňující jazykovou kontrolu textu napsaného v jazyku \LaTeX{}. Jedná se o aplikaci, která sama neprovádí kontrolu textu, ale umožňuje ji pomocí externích služeb. V této práci se využívá služba Grammarly, která umožňuje kontrolu anglických textů. Součástí práce je rešerše služby Grammarly, rešerše již jednoho existujícího řešení, které ale spolupracuje s jinou externí službou, a analýza požadavků. Na základě požadavků byl navrhnut a implementován prototyp výše zmíněné aplikace. Prototyp byl implementován v programovacím jazyce Java a JavaFX jako desktopová multiplatformní aplikace.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Katedra softwarového inženýrství

Ing. Ondřej Guth, Ph.D.

Ing. Josef Vogel, CSc.

Katedra softwarového inženýrství

Tato bakalářská práce popisuje vznik aplikace implementované jako systémový modul pro prostředí KDE Plasma 5. Aplikace využívá jako svůj základ projekt Howdy. Hlavní náplní práce je popis vzniku aplikace a příslušných instalačních balíčků pro distribuce Linux Mint, Gentoo a OpenSUSE. Práce obsahuje analýzu, návrh, postup řešení jednotlivých problémů a konečné otestování.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Petr Máj, Ph.D.

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

V tomto projektu studujeme zranitelné vstupy regulárních výrazů v implementaci platformy Java, známé také jako OpenJDK. Tyto vstupy mohou způsobit útok regulárního výrazu Denial of Service na systém, který by mohl způsobit, že cílový systém nebude dostupný skutečným uživatelům. OpenJDK je považováno za chráněné proti ReDoS útoku, zejména ve verzích 9 a vyšších, kde byla přidána optimalizace algoritmů pro párování regulárních výrazů. Ale i s tímto vylepšením ukážeme, že stále existují zranitelné vstupy regulárních výrazů, které mohou způsobit exponenciální problémy za běhu a potenciálně způsobit odmítnutí služby, a to i v nejnovější verzi OpenJDK. V této práci uvidíte, které optimalizace byly přidány ve verzi 9, jak tato vylepšení ovlivňují OpenJDK dnes a co tyto optimalizace nestihly pokrýt. Pro každý ze zranitelných vstupů regulárních výrazů dostanete také vývojový diagram, který ukazuje proces párovacích algoritmů, proč dochází k exponenciálním problémům za běhu a možná řešení.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Tomáš Kalvoda, Ph.D.

Katedra softwarového inženýrství

Táto bakalárska práca je zameraná na návrh a funkčnú implementáciu grafického užívateľského rozhrania webového rezervačného systému miestností na FIT. Najprv dôkladne analyzuje požiadavky potencionálnych užívateľov. Systém je navrhnutý tak, aby hlavným zdrojom dát, bola iná súčastne zadaná bakalárska práca, Administrátorská časť rezervašného systému miestností. Pri návrhu a implementácii je kladený dôraz na jednoduchosť a prehľadnosť užívateľského rozhrania. Výsledok implementácie je testovaný pomocou k tomu vhodných metód. Práca taktiež vyhodnocuje ekonomicko-manažérske prínosy rezervačného systému miestností pre FIT.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Tomáš Pecka

Katedra teoretické informatiky

Tato bakalářská práce se věnuje vyhledávání pravidelností v řetězcích, konkrétně vyhledávání jader. Obsahuje popis algoritmů vyhledávajících přesná i přibližná jádra s určitou maximální Hammingovou vzdáleností. Algoritmy jsou založené na konečných automatech a vychází přímo z definice jader. Práce také obsahuje jejich implementaci do Algoritmové knihovny katedry Teoretické informatiky na Fakultě informačních technologií ČVUT v Praze.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Tomáš Pecka

Katedra teoretické informatiky

Tato práce se zabývá regulárními výrazy s rekurzivním zanořením. Jedná se o rozšíření regulárních výrazů možností opakovaného využití podvýrazů v jiných částech výrazu. Mimo jiné i v rámci samotného podvýrazu. Nejprve zkoumáme různá rozšíření regulárních výrazů, jejich vyjadřovací sílu a přistupy k jejich zkoumání. Poté představíme nově vymyšlené algoritmy pro převod mezi regulárními výrazy s rekurzivním zanořením a bezkontextovými gramatikami. Nakonec ukážeme, že množina jazyků generovaná regulárními výrazy s rekurzivním zanořením je právě množina všech bezkontextových jazyků.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Michal Valenta, Ph.D.

Katedra softwarového inženýrství

Tato diplomová práce se věnuje návrhu a implementaci softwaru sloužícího k získávání dat týkajících se nabídek na českém realitním trhu. Dále se tato práce zabývá návrhem a implementací Discordového bota, sloužícímu k notifikování uživatelů o nabídkách, které je zajímají.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Katedra softwarového inženýrství

Diplomová práce se zabývá návrhem a implementací analytického nástroje pro strategii párového obchodování s akciemi. Pro implementaci jsou využity standardní nástroje Java Enterprise Edition, JavaServer Faces a aplikační server GlassFish. Na základě výstupů z testování je v sekci Závěr zhodnocena celá aplikace a jsou poskytnuty návrhy na její vylepšení do budoucna.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

Ing. Pavel Samec

Katedra softwarového inženýrství

Ing. Ondřej Guth, Ph.D.

Ing. Vladimír Váňa, CSc.

Katedra softwarového inženýrství

Ing. Ondřej Guth, Ph.D.

Ing. Jan Fesl, Ph.D.

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

Tato práce se zabývá návrhem plánovače cest v geoprostorových grafech, konkrétně s omezením na cesty ve městě. Plánovač nabízí různé způsoby dopravy a v určitých kombinacích také využívá vícera možností prostředků najednou. Plánovací služba je navržena dle principů tzv. mikroslužeb (microservices). K plánovací službě je přístup navržen pomocí REST API. Technologií jako Docker a Kubernetes je využito k nasazení aplikace do distribuovaného a škálovaného systému v druhé části práce. Při nasazení do Kubernetes je brán důraz na zabezpečení aplikace. Část práce je věnována možnostem škálování aplikace v distribuovaném systému Kubernetes. Je brán důraz na vysokou dostupnost aplikace jak při běžném provozu, tak při častém nasazování.

Práce na DSpace

Ing. Ondřej Guth, Ph.D.

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

Katedra teoretické informatiky

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

Práce na DSpace