Original title:
Návrh výpočetních struktur v celulárních automatech
Translated title:
Design of Computing Structures in Cellular Automata
Authors:
Luža, Jindřich ; Drábek, Vladimír (referee) ; Bidlo, Michal (advisor) Document type: Master’s theses
Year:
2014
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
za pomocí celulárních automatů. Práce popisuje principy fungování celulárních automatů a zabývá se jejich způsoby jejich využítí pro stanovený cíl. Na 1D a 2D rozměrných celulárních automatech vybraných typů jsou ukázány možné způsoby jak Turingovsky univerzálního výpočtu tak i další řešící specifické úlohy. Tímto je demonstrována schopnost celulárních automatů provádět výpočet a zároveň jsou ukázány rozlišné způsoby interpretace vstupů a výstupů výpočtů na celulárním automatu. S přihlédnutím k těmto poznatkům jsou pro vybrané obvody navrženy testy mající za úkol nalézt realizaci těchto obvodů na celulárních automatech za pomoci zvoleného evolučního algoritmu. Nalezené výsledky jsou pak porovnány z hlediska jejich nároků na evoluční algoritmus a spotřebované výpočetní zdroje.
The goal of this master thesis is to examine possibilities of realizing comptutational structures in cellular automata. The work describes the fundamental principles of cellular automata and summarizes some ways of how to achive the specified goal. An overview of Turing-complete and other specialized computational tasks is proposed considering both 1D and 2D cellular automata. It is shown that different computational scenarios in cellular automata can be considered with various setups of the input and output arrangements. With regard to showed inputs and outputs arrangement, sets of tests is designed to find solutions of choosen computational structures on cellular automata with use of choosen evolutionary algorithm. Found solutions are compared by computational resources consumption and difficulty of discovery later.
Keywords:
Cellular automata; evolutionary algorithms.; Game of Life; non-uniform cellular automata; uniform cellular automata; universal computation; Celulární automaty; evoluční algoritmy.; Game of Life; neuniformní celulární automaty; uniformní celulární automaty; univerzální výpočet
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/53332