Detail práce
Watson-Crick Models for Formal Language Processing
Tato práce se zabývá Watson-Crickovými jazyky, které jsou inspirovány výpočty nad DNA, dále jejich modely a algoritmy pro rozhodování členství řetězců v těchto jazycích. Analyzuje nedávno představený algoritmus nazvaný WK-CYK a prezentuje algoritmus založený na prohledávání stavového prostoru, jehož základem je standardní prohledávání prostoru do šířky, ale používá množství optimalizací a heuristik, aby byl v praxi efektivnější a dokázal analyzovat delší vstupy. Klíčové jsou heuristiky pro prořezávání stavového prostoru (detekují slepé větve) a heuristiky pro výběr nejslibnějších větví pro další výpočet. Tyto dva algoritmy jsou testovány na 20 různých Watson-Crickových gramatikách (40 včetně jejich verzí v Chomského normální formě). Zatímco WK-CYK je schopen rozhodnout členství v jazyce v rozumném čase u vstupů o délce zhruba 30-50 symbolů, jeho efektivnost je velmi konzistentní u různých gramatik a různých vstupů, algoritmus prohledávající stavový prostor je obvykle (v 89-98 % případů) efektivnější a je schopen provést výpočet pro vstupy s délkou o stovkách často i tisících symbolů. Tedy tento algoritmus má potenciál být vhodným nástrojem pro praktické použití při rozhodování členství ve Watson-Crickových jazycích a nabízí vhodný základ pro další vývoj a vylepšení, která by dále zvyšovala efektivitu algoritmu.
Watson-Crickovy jazyky, formální gramatiky, DNA výpočty, prohledávání stavového prostoru, problém členství v jazyce
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 A.
- Aký je rozdiel vo význame okrúhlych a hranatých zátvoriek pri notácii dvojíc reťazcov?
- Čo by boli najväčšie výzvy pri paralelizácii Vášho algoritmu? Bolo by možné prevziať všetky heuristiky bez zásadných zmien?
- Do jaké míry jste studoval disertaci Radima Kocmana?
Bartík Vladimír, Ing., Ph.D. (UIFS FIT VUT), člen
Grégr Matěj, Ing., Ph.D. (UIFS FIT VUT), člen
Matoušek Petr, doc. Ing., Ph.D., M.A. (UIFS FIT VUT), člen
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT), člen
Polčák Libor, Ing., Ph.D. (UIFS FIT VUT), člen
@mastersthesis{FITMT20427,
author = "Jan Hammer",
type = "Diplomov\'{a} pr\'{a}ce",
title = "Watson-Crick Models for Formal Language Processing",
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/20427/"
}