Detail práce
Abstraction in Automata Algorithms
Tato práce si klade za cíl implementaci a experimentální porovnání protiřetězcových algoritmů s abstrakcí a bez abstrakce, které testují prázdnost alternujících automatů. Autor také navrhuje vlastní algoritmy s abstrakcí a navrhuje několik optimalizací pro existující abstraktní algoritmy. Práce popisuje teoretické pozadí studovaných algoritmů a navrhuje efektivní způsob implementace datových struktur, které jsou těmito algoritmy používány. Experimentální vyhodnocení na náhodných automatech ukazuje, že algoritmy bez abstrakce vykazují obecně lepší výsledky, neboť nevyužívají náročné operace průniku a komplementace shora a zdola uzavřených množin. V případě automatů s vysokou hustotou přechodů však algoritmy bez abstrakce zpomalují a algoritmy s abstrakcí naopak zrychlují.
alternující konečný automat, abstrakce, protiřetězec, prázdnost jazyka, konkrétní doména, abstraktní doména, pevný bod, rozklad
Student nejprve prezentoval výsledky, kterých dosáhl v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Student následně odpověděl na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studenta na položené otázky rozhodla práci hodnotit stupněm B.
- Uměl byste rozdělit tabulku 7.1 na dvě části podle toho, zda prázdnost platí nebo ne, ideálně doplnit i o počty automatů, maxima a směrodatnou odchylku? (a ukázat výsledné tabulky na obhajobě, tj. nestačí odpovědět "Ano")
- Jaké jsou další plány v tomto směru?
Grézl František, Ing., Ph.D. (UPGM FIT VUT), člen
Martínek Tomáš, doc. Ing., Ph.D. (UPSY FIT VUT), člen
Peringer Petr, Dr. Ing. (UITS FIT VUT), člen
Ryšavý Ondřej, doc. Ing., Ph.D. (UIFS FIT VUT), člen
@bachelorsthesis{FITBT24926,
author = "Tom\'{a}\v{s} Kocourek",
type = "Bakal\'{a}\v{r}sk\'{a} pr\'{a}ce",
title = "Abstraction in Automata Algorithms",
school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}",
year = 2022,
location = "Brno, CZ",
language = "english",
url = "https://www.fit.vut.cz/study/thesis/24926/"
}