| |
|
Non-Returning Turing Machines
Surovič, Marek ; Vrábel, Lukáš (referee) ; Meduna, Alexandr (advisor)
This work introduces a restricted variant of the Turing machine which cannot move left, thus return on its tape. Other properties, such as the potentially infinite symbol tape or the ability to rewrite symbols on the tape, remain unchanged. By introducing this restriction we limit the expressive power of the Turing machine to the point, where a non-returning Turing machine is equivalent to a finite automaton and can be transformed into one. A transformation algorithm is presented and described in detail.
|
|
Visualization of Finite Automata, Pushdown Automata and Turing Machines Work
Syrový, Ondřej ; Láník, Aleš (referee) ; Zuzaňák, Jiří (advisor)
This bachelor`s thesis is focusing on concept and development of computer application for demonstration of finite automata, pushdown automata and Turing machines work. Theoretic volume of this work deals with theories of formal languages and grammars and automata theory. Created program allows to load deterministic and nondeterministic automata variants from the text file, their graphic representation by state diagram and stepping their calculation process.
|
|
Simulator of Turing Machines Described by Means of Composite Diagrams
Siska, Josef ; Lengál, Ondřej (referee) ; Rogalewicz, Adam (advisor)
In this thesis, the theory related to Turing machines and means of their description (with focus on composite diagrams) is presented. The aim of this work is to create an application that allows editing Turing machines described by means of composite diagrams and simulating their computation on specified input configuration (including non-deterministic and multi-tape machines). Furthermore, within the application it will be possible to run the termination analysis of Turing machine in order to determine whether this machine or any of its parts always halt. The resulting application is implemented in Java and the termination analysis is performed using the well-founded orders. And so, one of the results created during this work is a software tool which allows designing and testing of Turing machines described by means of composite diagrams. Resulting application may be used especially during lectures on theoretical computer science, where it can be used to demonstrate computation of some Turing machine.
|
|
The Comparison of the Algorithms for the Solution of Travel Sales Problem
Kopřiva, Jan ; Všetička, Martin (referee) ; Dostál, Petr (advisor)
The Master Thesis deals with logistic module innovation of information system ERP. The principle of innovation is based on implementation of heuristic algorithms which solve Travel Salesman Problems (TSP). The software MATLAB is used for analysis and tests of these algorithms. The goal of Master Thesis is the comparison of selections algorithm, which are suitable for economic purposes (accuracy of solution, speed of calculation and memory demands).
|
|
Interactive simulation by means of Flash technology
Látal, Pavel ; Šedá, Jitka (referee) ; Matoušek, Radomil (advisor)
This bachelor thesis is interested in designing of six interactive simulations by means of Flash technology. The presented interactive simulations are follows: an extended version of Conway’s cellular automata which was realized on orthogonal and hexagonal grid, simulation of 1D cellular automata, demonstration of selected selection principles of evolutionary algorithms, possible graphic representation of 2D Turing machine, and application for demonstration of ant colony behavior.
|
|
Super-Turing Computational Potential of Cognitive and Evolutionary Systems
Wiedermann, Jiří
The computational potential of artificial living systems is investigated. Each organism is modelled by so-called cognitive automaton. It is any finite state device with a finite configuration space that processes infinite streams of input symbols. Examples of such automata are finite state automata, discrete neural networks, Boolean circuits, etc. It is shown that non-uniform families of cognitive automata and community of cognitive automata possess a super-Turing computing potential.
|
| |