|
Nestandardní analýza dynamických systémů
Slavík, Jakub ; Pražák, Dalibor (advisor) ; Růžička, Pavel (referee)
In the presented thesis, we study an application of nonstandard analysis to dynamical systems, in particular to ω-limit set, stability and global attractor. We recall the definition and properties of elementary embedding, in detail ex- plore the introduction of infinitesimals to the real line and study metric spaces using nonstandard methods, in particular continuity and compactness which are closely related to the theory of dynamical systems. Last we attend to dynamical systems and present nonstandard characterizations of some of its properties such as asymptotic compactness and dissipativity and using these characterizations we prove one of the basic results of this theory - existence of a global attractor. 1
|
| |
|
Combinatorial group theory and cryptography
Ferov, Michal ; Příhoda, Pavel (advisor) ; Růžička, Pavel (referee)
In the presented work we focus on applications of decision problems from combinatorial group theory. Namely we analyse the Shpilrain-Zapata pro- tocol. We give formal proof that small cancellation groups are good platform for the protocol because the word problem is solvable in linear time and they are generic. We also analyse the complexity of the brute force attack on the protocol and show that in a theoretical way the protocol is immune to attack by adversary with arbitrary computing power.
|
|
Compressing Pseudorandom sequences
Vald, Denis ; Holub, Štěpán (advisor) ; Růžička, Pavel (referee)
Generators of pseudorandom sequences are widely used objects, not in the least place because of their application in stream ciphers. One of the ways to improve resistance to different types of attack is to use compression on the generated sequence in order to remove redundant information, that might lead to an attack against the generator. In this work we try to explore from a wider perspective the theoretical foundations for compressing pseudorandom sequences created thus far. Using this general view we will examine some known attacks against the PRN generators and look for a way to resist such attacks.
|
|
Gröbner bases
Petržilková, Lenka ; Žemlička, Jan (advisor) ; Růžička, Pavel (referee)
In this thesis we remind you of the basic Buchberger algorithm for com- puting the Gröbner base over commutative polynomial rings. We also observe uniqueness of the Gröbner base for the ideal. Next we research less known, but more effective (for some instances) Faugère F4 algorithm. At the end of the first chapter we compare these two algorithms. In the second chapter we analyze a generalization of the Buchberger algorithm for noncommutative rings both for free algebra and factor algebra. On the contary to the commu- tative case, Gröbner bases can be infinite in this case, even for some finitely generated ideals. Among other things, we investigate quasi-zero elements,i.e. such elements, that we get zero by multiplying them with an arbitrary term, and their role in the division of a polynom by set of polynoms. 1
|
| |
| |
| |
| |
|
Algebraický přístup k CSP
Bulín, Jakub ; Barto, Libor (advisor) ; Růžička, Pavel (referee)
For a finite relational structure A, the Constraint Satisfaction Problem with template A, or CSP(A), is the problem of deciding whether an input relational structure X admits a homomorphism to A. The CSP dichotomy conjecture of Feder and Vardi states that for any A, CSP(A) is either in P or NP-complete. In the first part we present the algebraic approach to CSP and summarize known results about CSP for digraphs, also known as the H-coloring problem. In the second part we study a class of oriented trees called special polyads. Using the algebraic approach we confirm the dichotomy conjecture for special polyads. We provide a finer description of the tractable cases and give a construction of a special polyad T such that CSP(T) is tractable, but T does not have width 1 and admits no near-unanimity polymorphisms.
|