|
|
Complexity and Computational Capacity of Discrete Dynamical Systems
Hudcová, Barbora ; Mikolov, Tomáš (vedoucí práce) ; Aubrun, Nathalie (oponent) ; Kupsa, Michal (oponent)
Hlavním cílem této disertační práce je studovat pojmy "složitost" a "výpočetní kapa- cita" diskrétních dynamických systémů a propojit je s rigorózně měřitelnými vlastnostmi. V první části práce navrhujeme metodu, jak formálně měřit složitost diskrétních systémů, založenou na numerických odhadech jejich asymptotického času konvergence. Díky této metodě identifikujeme oblast komplexních systémů odpovídající fázovému přechodu z uspořádané do chaotické fáze. Tyto výsledky dále doplňujeme analytickým studiem fá- zových přechodů v diskrétních systémech s využitím nově vyvinutých nástrojů z oblasti statistické fyziky. Konkrétně pro diskrétní systémy z určité třídy ukazujeme, že variace počátečních konfigurací může vést k prudkým změnám chování systému, a popisujeme přesné polohy těchto přechodů. Druhá část této disertační práce se věnuje analýze vý- početní kapacity celulárních automatů prostřednictvím pojmu relativní simulace. Nefor- málně lze říci, že automat B simuluje A, pokud B umí efektivně reprodukovat jakoukoliv dynamiku A. Zavádíme konkrétní pojem simulace automatu a formalizujeme jej v al- gebraickém jazyce. To nám umožnilo zodpovědět otevřené otázky týkající se výpočetní kapacity celulárních automatů s využitím známých algebraických výsledků. Konkrétně dokazujeme, že určité třídy afinních automatů jsou...
|
host ::
RSS.