Toto byla zásadní část práce, student pracoval naprosto samostatně a velmi dobře. Prostudoval, pochopil, a hlavně, sám nalezl poměrně vyčerpávající množinu relevantních prací, které potom také vyhodnotil a částečně použil.

Práce byla řešena průběžně, technický obsah byl dokončen včas a konzultován, části textu byly konzultovány, části byly dokončeny na poslední chvíli. 

Prezentační úroveň technické zprávy je vynikající. Jednotlivé kapitoly na sebe smysluplně navazují, odkazují vhodným způsobem na dříve představené pojmy. Každý klíčový teorém je poctivě podepřen důkazem. Text obsahuje velké množství příkladů pro snazší pochopení prezentovaných pojmů. Tyto příklady přitom nejsou ani příliš triviální, ani příliš překombinované. Jsou rovněž doprovázeny kvalitně zhotovenými obrázky pro ještě snazší pochopení pojmů. Každý obrázek je v textu řádně odkazován.

Na problém jsem narazil u Obrázku 4.5, který demonstruje netriviální výpočet vedoucí k nalezení takzvaných mostů v konečném automatu. Tento obrázek nekoresponduje správně s vysvětlovanými pojmy a je poněkud matoucí.

Důkaz u Algoritmu 1 používá mírně zavádějícím způsobem jednu proměnnou ve více kontextech.

Tabulka 5.8 obsahuje v záhlaví obrovské množství zkratek názvů různých heuristik, tyto zkratky ale nejsou příliš přehledné a nejsou nikde vysvětleny. 

Jinak ovšem nemám žádné další výhrady.

Student v implementační části práce navázal na datové struktury z existující automatové knihovny Mata, implementoval vlastní datové struktury pro regulární výrazy a automaty s regulárními výrazy na hranách. Hlavní část implementace tvoří různé metody pro převod automatů na regulární výrazy.

V této fázi jsem si všiml několika nedostatků. Metoda vertikálního štěpení vyžaduje nalezení takzvaných mostů v automatu. Kód hledající tyto stavy ovšem nefunguje dle očekávání. Kvůli chybné propagaci pomocných hodnot při prohledávání automatu do hloubky implementace falešně pozitivně detekuje některé stavy jako mosty, což má dopad na smysluplnost a efektivitu vertikálního štěpení. Tento problém se projeví již u poměrně malého automatu.

Některé metody jsou také naimplementované poměrně naivním a neefektivním způsobem. Kupříkladu u metody dynamický InOutProduct by velmi jednoduchými optimalizacemi bylo možné zlepšit asymptotickou časovou složitost až o lineární faktor.

Kód je jinak přehledný, čitelný, decentně komentovaný. Některé komentáře ale působí trochu nepatřičně, jako kdyby komentovaly nevyřešené problémy z pracovní verze implementace. Zejména komentář TODO: we are ingoring [sic] self-loops. is it safe???? vyvolává dojem, že korektnost této části kódu nebyla při odevzdání plně ověřena.

Naopak oceňuji, že se student zamýšlel nad tím, jak efektivně implementovat datové struktury pro generalizované automaty a regulární výrazy. Zejména jeho implementace regulárních výrazů je velmi solidní.

V experimentální části práce provedl pan Klymenko řadu experimentů na relevantní automatové sadě. Dokázal bych si ale představit, že by některé z těchto experimentů byly lépe popsány a data by byla lépe prezentována.

Většina tabulek ukazuje pro metriky času a alfabetické velikosti pouze minimum, maximum, průměr a medián. Pro komplexnější analýzu tyto hodnoty nemusí stačit, neboť průměr může být ovlivněn extrémními hodnotami a medián neříká nic o rozptylu.

Experiment 2 dochází k závěru, že algebraické úpravy regulárních výrazů (jako např. změna R + R za R, R** za R* apod.) nemají téměř žádný vliv na alfabetickou velikost výsledku. Experiment ale nijak neukazuje, jaké množství jakých úprav (a zda vůbec nějaké) byly při převodu provedeny.

Experiment 3 se soustředí pouze na automaty s nenulovým počtem mostů ve snaze otestovat možný vliv vertikálního štěpení. Pomineme-li, že implementace mosty detekuje nesprávně, experiment mi nepřipadá příliš průkazný, neboť z většiny pracuje s automaty, u nichž je počet mostů i tak zanedbatelný.

Experiment 4 přichází se značně zajímavým zjištěním, že u automatů bez mostů má volba vhodné metody eliminace stavů větší vliv na velikost výsledného regulárního výrazu než u automatů s mosty. Toto zjištění považuji za velmi pozitivní přínos práce, ocenil bych ale jeho hlubší analýzu.

Evaluation level: zadání splněno

Zadání hovoří o srozumitelných a čitelných regulárních výrazech. Jelikož srozumitelnost je v tomto kontextu poměrně nejasný a neformální pojem, pan Klymenko jej musel nejprve přesněji uchopit. Ve své práci se soustředil především na metriky alfabetické velikosti a míry algebraických redundancí. Ačkoliv by se dalo uvažovat i o dalších metrikách čitelnosti a srozumitelnosti regulárních výrazů, zvolené metriky byly v textu zpracované natolik kvalitním a vyčerpávajícím způsobem, že zadání v tomto směru považuji za splněné.

Práci s literaturou považuji za příkladnou. Student vedle veškerých doporučených zdrojů uvedených v zadání využil i řadu kvalitních publikací týkajících se tématu. Bibliografie navíc neobsahuje nerelevantní publikace. Všechny převzaté myšlenky jsou v textu řádně citovány.