|
|
Complexity and Computational Capacity of Discrete Dynamical Systems
Hudcová, Barbora ; Mikolov, Tomáš (advisor) ; Aubrun, Nathalie (referee) ; Kupsa, Michal (referee)
The central aim of this thesis is to study the concepts of "complexity" and "com- putational capacity" of discrete dynamical systems and to connect them to rigorously measurable properties. In the first part of the thesis, we propose a formal metric of a dis- crete system's complexity based on the numerical estimates of its asymptotic convergence time. We identify a critical region of systems corresponding to a phase transition from an ordered to a chaotic phase. Additionally, we complement this work by studying dynam- ical phase transitions of discrete systems analytically, using newly developed tools from statistical physics. Specifically, for a fixed discrete system, we demonstrate that varying its initial configurations can result in abrupt changes in the system's behaviour; and we describe exact positions of such transitions. The second part of this thesis is dedicated to analysing computational capacity of cellular automata via the notion of their relative simulation. Informally, we say that automaton B can simulate A if B can effectively reproduce any dynamics of A. We introduce a specific notion of automata simulation and formalize it in algebraic language. This allowed us to answer open questions about the computational capacity of cellular automata using well-established algebraic results. Namely,...
|
|
|
Log-optimal approach in betting, compound events
Macek, Tomáš ; Kupsa, Michal (advisor) ; Večeř, Jan (referee)
In this Thesis we deal with the log-optimal betting approach. The goal is to maximize the gambler's wealth in the long term. In the course of the Thesis, we will work our way from the basic cases to a completely general problem, while the task is always to obtain a log-optimal betting strategy. For the simplest cases, we use the connection to information theory, and for others we will formulate and prove a version of the Karush-Kuhn-Tucker conditions suitable precisely for the log-optimal betting aproach. In this work, we focus primarily on the tree betting scheme and we will derive the algorithm for obtaining the log-optimal strategy of any betting opportunity from the tree betting scheme, which co- vers a large variety of betting opportunities. We will then use this algorithm to program an application in Python, which will print out the log-optimal strategy of a given betting opportunity to the user. Finally, we will verify that the obtained results correspond to the Kelly criterion and we will show several examples of the use of the Thesis. 1
|
|
|
Vágní informace na konečných abecedách a její monotónní charakteristiky
Kovářová, Lenka ; Beneš, Viktor (advisor) ; Kupsa, Michal (referee)
Title: Vague information on finite alphabets and its monotonous characteristics Author: Mgr. Lenka Kovářová Department: Department of Probability and Mathematical Statistics Supervisor: prof. RNDr. Viktor Beneš, DrSc. Abstract: The bachelor thesis is focused on information-theoretic source of messages with vague recognition from a final general alphabet. The aim of this work is to compile an overview of existing approaches to entropy and information. There were published several approaches how to convert to the fuzzy set theory the concept of entropy, which was originally introduced in physics, mathematically expressed as an additive-probability model and adjusted for Shannon probabilistic information source. Most of these approaches maintains the additive-probability model, while the emphasis in the theory of fuzzy sets is laid on the characteristics of minimum and maximum. Keywords: Entropy, Information, Fuzzy sets, Vague Entropy, Vague Information 1
|
|
|
Recurrent properties of products and skew-products of finitely- valued random processes
Kvěš, Martin ; Kupsa, Michal (advisor) ; Dostál, Petr (referee)
In this work, we study return and hitting times in measure-preserving dy- namical systems. We consider a special type of skew-products of two Bernoulli schemes, called a random walk in random scenery. For these systems, the limit distribution of normalized hitting times for cylinders of increasing length is proved to be exponential under the assumption of finite variance of the first order dis- tribution of the Bernoulli scheme representing the walk, and provided the drift is non-zero or the scenery alphabet is finite. Mixing properties of the skew-products are discussed in order to relate our work with some known results on rescaled hitting times for strongly-mixing systems. 1
|
|
|
Mixing processes with finite alphabet
Vostal, Ondřej ; Kupsa, Michal (advisor) ; Dostál, Petr (referee)
An introduction to the theory of mixing of random processes is presented. The aim of this introduction is to be eventually able to separate general random processes, markov chains and markov chains with finite alphabet into groups which mix differently. The introduction is made complete by examples. We show, that for general processes those groups are separate, for markov chains some coincide, and for markov chains with finite alphabet all coincide. Powered by TCPDF (www.tcpdf.org)
|
|
|
Complexity in Cellular Automata
Hudcová, Barbora ; Mikolov, Tomáš (advisor) ; Kupsa, Michal (referee)
In order to identify complex systems capable of modeling artificial life, we study the notion of complexity within a class of dynamical systems called cellu- lar automata. We present a novel classification of cellular automata dynamics, which helps us identify interesting behavior in large automaton spaces. We give a detailed comparison of our results to previous methods of dynamics classification. In the second part of the thesis, we study the backward dynamics of cellular au- tomata. We present a novel representation of one-dimensional cellular automata, which can be used to charcterize all their garden of eden configurations. We demonstrate the usefulness of this method on examples. 1
|
|
|
Recurrent properties of products and skew-products of finitely- valued random processes
Kvěš, Martin ; Kupsa, Michal (advisor) ; Dostál, Petr (referee)
In this work, we study return and hitting times in measure-preserving dy- namical systems. We consider a special type of skew-products of two Bernoulli schemes, called a random walk in random scenery. For these systems, the limit distribution of normalized hitting times for cylinders of increasing length is proved to be exponential under the assumption of finite variance of the first order dis- tribution of the Bernoulli scheme representing the walk, and provided the drift is non-zero or the scenery alphabet is finite. Mixing properties of the skew-products are discussed in order to relate our work with some known results on rescaled hitting times for strongly-mixing systems. 1
|
|
|
Recurrence in a random walk on a random process
Kvěš, Martin ; Kupsa, Michal (advisor) ; Pawlas, Zbyněk (referee)
V této práci se věnujeme problému z oblasti pravděpodobnostních dynamic- kých systém· s diskrétním časem. Konstruujeme dva pravděpodobnostní dyna- mické systémy, které modelují náhodný pohyb čtecího zařízení po nekonečném náhodném řetězci nad spočetnou abecedou. V prvním systému není povolen po- hyb čtecího zařízení směrem vzad. Ve druhém systému je povolen pohyb čtecího zařízení zpět a vpřed o jednu pozici, se stejnou pravděpodobností. V obou mo- delech bude hlavním cílem najít limitní rozdělení normalizovaných dob prvního vstupu pro rostoucí délku řetězc·. Ukážeme, že v prvním systému je limitní roz- dělení exponenciální, zatímco v druhém je limitní rozdělení degenerované. 1
|
|
|
Mixing processes with finite alphabet
Vostal, Ondřej ; Kupsa, Michal (advisor) ; Dostál, Petr (referee)
An introduction to the theory of mixing of random processes is presented. The aim of this introduction is to be eventually able to separate general random processes, markov chains and markov chains with finite alphabet into groups which mix differently. The introduction is made complete by examples. We show, that for general processes those groups are separate, for markov chains some coincide, and for markov chains with finite alphabet all coincide. Powered by TCPDF (www.tcpdf.org)
|
|
|
Vágní informace na konečných abecedách a její monotónní charakteristiky
Kovářová, Lenka ; Beneš, Viktor (advisor) ; Kupsa, Michal (referee)
Title: Vague information on finite alphabets and its monotonous characteristics Author: Mgr. Lenka Kovářová Department: Department of Probability and Mathematical Statistics Supervisor: prof. RNDr. Viktor Beneš, DrSc. Abstract: The bachelor thesis is focused on information-theoretic source of messages with vague recognition from a final general alphabet. The aim of this work is to compile an overview of existing approaches to entropy and information. There were published several approaches how to convert to the fuzzy set theory the concept of entropy, which was originally introduced in physics, mathematically expressed as an additive-probability model and adjusted for Shannon probabilistic information source. Most of these approaches maintains the additive-probability model, while the emphasis in the theory of fuzzy sets is laid on the characteristics of minimum and maximum. Keywords: Entropy, Information, Fuzzy sets, Vague Entropy, Vague Information 1
|
guest ::
