Alternující skákající automaty a jejich aplikace

Název anglicky

Alternating Jumping Automata and Their Applications

Jazyk práce

český

Abstrakt

Tato práce zavádí alternující skákající automaty a zkoumá některé jejich vlastnosti a vyjadřovací možnosti. Tyto automaty se podobně jako klasické skákající automaty vyznačují schopností nespojitého zpracovávání vstupních řetězců. Po každém jednom čtení symbolů provádí skok na nejvzdálenější místo ve vstupní pásce od aktuální pozice čtecí hlavy a od tam následně v procesu přijímání pokračují. Výchozí počáteční pozicí čtecí hlavy je levý okraj vstupní pásky. Práce demonstruje vliv různých počátečních konfigurací na výpočetní sílu těchto automatů a na základě nově představených převodových algoritmů dokazuje ekvivalenci jejich určitých verzí s lineárními gramatikami. Součástí této práce je potom také porovnání alternujících skákajících automatů s Watson-Crick automaty, ukázka rozdílného přístupu obou těchto modelů k detekci struktury DNA a koncept automatu kombinujícího jejich přednosti.

Klíčová slova

skákající konečné automaty, alternující skákající konečné automaty, lineární jazyky, jednoduchá lineární gramatika, Watson-Crick automaty, detekce struktury DNA

Ústav

Ústav informačních systémů FIT VUT v Brně

Studijní program

Informační technologie

Soubory

Stav

obhájeno, hodnocení A

Obhajoba

13. června 2022

Oponent

Křivka Zbyněk, Ing., Ph.D.

Průběh obhajoby

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.

Otázky u obhajoby

V literatuře se běžně zavádí pojem "alternující" pro jiné modely výpočtu (např. Turingových strojů). Můžete vysvětlit, jak se principiálně liší váš přístup "alternace" a zda by nebyl vhodný jiný název.
Uvažoval jste i jiné definice alternujících skákajících automatů (např. aby se neskákalo až zcela na pravý okraj, ale tak, aby nebylo třeba stále měnit směr čtení)?
Oproti propracovaným důkazům je implementace spíše základní. Obsahuje skript DNAfilter i možnost zpracovávat vstupní řetězec podle nedeterministického alternujícího skákajícího automatu, nebo pouze deterministického?

Komise

Vojnar Tomáš, prof. Ing., Ph.D. (UITS FIT VUT), předseda
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

Citace

NEJEDLÝ, Dominik. Alternující skákající automaty a jejich aplikace. Brno, 2022. Bakalářská práce. Vysoké učení technické v Brně, Fakulta informačních technologií. 2022-06-13. Vedoucí práce Meduna Alexander. Dostupné z: https://www.fit.vut.cz/study/thesis/25068/

BibTeX

@bachelorsthesis{FITBT25068,
    author = "Dominik Nejedl\'{y}",
    type = "Bakal\'{a}\v{r}sk\'{a} pr\'{a}ce",
    title = "Alternuj\'{i}c\'{i} sk\'{a}kaj\'{i}c\'{i} automaty a jejich aplikace",
    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 = "czech",
    url = "https://www.fit.vut.cz/study/thesis/25068/"
}