|
|
Orthogonal bases and Jordan normal form
Kučera, Daniel ; Šaroch, Jan (advisor) ; Barto, Libor (referee)
There exists an ortonormal set of eigenvectors for a linear operator if and only if it commutes with its adjoint endomorphism. The aim of this thesis is to characterize endomorphisms for which there exists a matrix representation with respect to an orthogonal basis in Jordan form. We introduce the notion of unitarily jordanisable endomorphism to capture this property. The proof of the Spectral theorem as well as the existence and uniqueness of Jordan form can be found in the first two chapters. An interesting connection with bilinear forms arises in chapter three and is used to prove that any linear operator with single eigenvalue and the length of Jordan chains bounded by two is unitarily jordanisable. The last chapter is devoted to the discussion of uniqueness of othogonal polar basis for a bilinear form and an algorithm is introduced which can determine whether or not a linear operator is unitarily jordanisable. 1
|
|
|
Constraint Satisfaction Problem and Universal Algebra
Kazda, Alexandr ; Barto, Libor (advisor) ; Růžička, Pavel (referee) ; Valeriote, Matt (referee)
The thesis consists of a collection of my contributions to universal algebra. Motivated by the Constraint Satisfaction Problem (CSP), we study the algebras of polymorphisms of relational structures. We begin by showing by an algebraic argument (and a bit of calculus) that random relational structures' CSP is almost always NP-complete. We then study digraphs with a Maltsev polymorphism, and conclude that such digraphs must also have a majority polymorphism. Next, we show how to use absorption tech- niques to prove that congruence modular reflexive digraphs must have an NU operation. We close our work by giving an algebraic proof of a result (first obtained by graph theorists) that 3-conservative relational structures with only unary and binary relations either define NP-complete CSP, or CSP for them can be solved by the local consistency algorithm. 1
|
|
| |
|
| |
|
| |
|
| |
|
| |
|
|
Primality testing using elliptic curves
Pashchenko, Olha ; Barto, Libor (advisor) ; Šťovíček, Jan (referee)
In the present work we study primality tests. A primality test is an algorithm for determining whether an input number is prime. In the first part of this work we recapitulate the basic definitions and facts about number theory and study Pocklington's algorithm, that based on the group (Z/nZ)∗ . Then we study Generalized Pocklington's primality test and Pépin's primality test for Fermat numbers. In the second part of this work we represent the basic definitions and facts about elliptic curves. Then we study Goldwasser-Killian primality test, that based on elliptic curves. One part of this work is experementation with Goldwasser-Killian primality test. 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.
|
|
| |
guest ::
