Název: Výpočetní historie Turingových strojů a jejich generování gramatikami s rozptýleným kontextem
Překlad názvu: Computational Histories of Turing Machines and Their Generation by Scattered Context Grammars
Autoři: Kajan, Dušan ; Soukup, Ondřej (oponent) ; Meduna, Alexandr (vedoucí práce)
Typ dokumentu: Diplomové práce
Rok: 2015
Jazyk: cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [cze] [eng]
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 . The purpose of this thesis is to show a method, that would transform given Turing machine into propagating scattered context grammar, which language contains all valid computational histories of that particular Turing machine. Afterwards this thesis deals with questions arising from existence of such algorithm, especially in regards to the current knowledge about power of propagating scattered context grammars. Practical examples and implementation of proposed algorithm is also part of this thesis.
Klíčová slova: algoritmus; Haskell; propagujíci gramatiky s rozptýleným kontextem; teoretická informatika; Turingův stroj; výpočetní historie; { gramatiky s rozptýleným kontextem; algorithm; computational history; Haskell; propagating scattered context grammars; scattered context grammars; theory of computation; Turing machine

Instituce: Vysoké učení technické v Brně (web)
Informace o dostupnosti dokumentu: Plný text je dostupný v Digitální knihovně VUT.
Původní záznam: http://hdl.handle.net/11012/64036

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-264935


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce > Diplomové práce