Výpočetní historie Turingových strojů a jejich generování gramatikami s rozptýleným kontextem

Název anglicky

Computational Histories of Turing Machines and Their Generation by Scattered Context Grammars

Jazyk práce

český

Abstrakt

Cílem této diplomové práce je navrhnout metodu, která by na vstupu očekávala Turingův stroj a na výstupu by byla propagujucí gramatika s roptýleným kontextem.Jazyk výstupní gramatiky by byl tvořený množinou řetězců reprezentující všechny validní výpočetní historie stroje na vstupu.Následně se tato práce zabývá otázkami, které z existence takového algoritmu vystávají, zejména ve vztahu k předpokladům, které dosud o výpočetní síle propagujících gramatik s rozptýleným kontextem existují.Názorné ukázky práce s těmito gramatikami a implementace představeného algoritmu v jazyce Haskell jsou také součástí této diplomové práce.

Klíčová slova

{gramatiky s rozptýleným kontextem, Turingův stroj, algoritmus,

Haskell, propagujíci gramatiky s rozptýleným kontextem,

teoretická informatika, výpočetní historie

Ústav

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

Studijní program

Informační technologie, obor Matematické metody v informačních technologiích

Soubory

Text práce 592 kB

Stav

obhájeno, hodnocení A

Obhajoba

24. června 2015

Oponent

Soukup Ondřej, Ing.

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

Z jakého důvodu je třeba v algoritmu zvlášť řešit první konfiguraci Turingova stroje? Uvádíte i jednodušší alternativní verzi, rozdíl je skutečně jen v oddělovačích?
Výsledné gramatiky obsahují i pro jednoduché Turingovi stroje množství pravidel. Bylo by možné provést nějakou vhodnou redukci?

Komise

Vojnar Tomáš, prof. Ing., Ph.D. (UITS FIT VUT), předseda
Burget Radek, doc. Ing., Ph.D. (UIFS FIT VUT), člen
Drahanský Martin, prof. Ing., Dipl.-Ing., Ph.D. (UITS FIT VUT), člen
Hrubý Martin, Ing., Ph.D. (UITS FIT VUT), člen
Rozinajová Viera, doc. Ing., Ph.D. (FIIT STU), člen
Ryšavý Ondřej, doc. Ing., Ph.D. (UIFS FIT VUT), člen

Citace

KAJAN, Dušan. Výpočetní historie Turingových strojů a jejich generování gramatikami s rozptýleným kontextem. Brno, 2015. Diplomová práce. Vysoké učení technické v Brně, Fakulta informačních technologií. 2015-06-24. Vedoucí práce Meduna Alexander. Dostupné z: https://www.fit.vut.cz/study/thesis/16787/

BibTeX

@mastersthesis{FITMT16787,
    author = "Du\v{s}an Kajan",
    type = "Diplomov\'{a} pr\'{a}ce",
    title = "V\'{y}po\v{c}etn\'{i} historie Turingov\'{y}ch stroj\r{u} a  jejich generov\'{a}n\'{i} gramatikami s rozpt\'{y}len\'{y}m kontextem",
    school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}",
    year = 2015,
    location = "Brno, CZ",
    language = "czech",
    url = "https://www.fit.vut.cz/study/thesis/16787/"
}