|
|
Minimal coverings of pairs by triples
Hladíková, Veronika ; Krump, Lukáš (advisor) ; Kazda, Alexandr (referee)
In this thesis we deal with solving a combinatorics problem of finding the minimal covering of pairs by triples for a fixed finite set. We will show what is the minimal size of these coverings and more ways how to construct them. Second part of the thesis is a description of the attached program, which generates a minimal covering for a given set. 1
|
|
|
Image reconstruction using graphical models
Ficová, Klára ; Kazda, Alexandr (advisor) ; Bulín, Jakub (referee)
Graphical models represent probability relations among random variables using a graph. They offer an effective way of modelling real life situations and are frequently used in machine learning and statistical thinking. The main goal of this thesis is to describe and implement techniques of denoising an image using graphical models. The graphical model we choose is factorgraph, representing pixels in image and interactions between them as nodes. Using algorithms on the graph, we determine the most probable true image. We also apply those theoretical methods on noisy images and compare the results. 1
|
|
|
Properties of delta-matroids
Šíma, Lucien ; Kazda, Alexandr (advisor) ; Rolínek, Michal (referee)
We investigate delta-matroids which are formed by families of subsets of a finite ground set such that the exchange axiom is satisfied. We deal with some natural classes of delta-matroids. The main result of this thesis establishes sev- eral relations between even, linear, and matching-realizable delta-matroids. Fol- lowing up on the ideas due to Geelena, Iwatab, and Murota [2003], and apply- ing the properties of field extensions from algebra, we prove that the class of strictly matching-realizable delta-matroids, the subclass of matching-realizable delta-matroids, is included in the class of linear delta-matroids. We also show that not every linear delta-matroid is matching-realizable by giving a skew-symmetric matrix representation to the non matching-realizable delta-matroid constructed by Kazda, Kolmogorov, and Rol'ınek [2019].
|
|
|
Presentations of subgroups
Jakubec, Tomáš ; Růžička, Pavel (advisor) ; Kazda, Alexandr (referee)
This bachelor thesis shows, how to create the presentation of subgroup, if the presentation of group is known by Reidemeister-Schreier method. At first, a term presentation of group is defined and then the text shows, how to obtain the group, which is isomorphic to the original group, from this presentation and how the presentation can be changed, although the group, which is ob- tained from the presentation, stays same. Then the text finds presentation of subgroup from the presentation of group, however this presentation cannot be in general used in practice. The obtained presentation of subgroup can be simplified by Reidemeister theorem, Schreier theorem and appropriate genera- tors of subgroup. This thesis also contains solved examples of application of Reidemeister-Schreier method. The text is intended as an educational material for students of combinatorial group theory. 1
|
|
| |
|
|
On impossibility of elementary integration
Zelina, Michael ; Pražák, Dalibor (advisor) ; Kazda, Alexandr (referee)
This work is devoted to studying of problem of (non)existence an elementary pri- mitive function of a given function. In the first place, we introduce the structure of a differential field and then we find a suitable way of formalizing the concept of the elementary function. This tools opens up the possibility to formulate and prove the crucial theorem which says what form an elemental primitive function must necessarily have if it exists. Then we use it to find the conditions for the existence of an ele- mentary integrals of two functions in a special but still quite general form. By using these conditions, we will show the nonelementarity of a number of more or less known integrals. 3
|
|
|
Key dependent message security
Hostáková, Kristina ; Hojsík, Michal (advisor) ; Kazda, Alexandr (referee)
In this work, we deal with cryptosystems which are provably secure even if we encrypt a key-dependent message. These cryptosystems are called KDM-secure. First, we define KDM-security and discuss its relationship with other kinds of security, especially IND-CPA-security. Thereafter, we construct the public- key and the symmetric-key encryption scheme of Applebaum et al. (CRYPTO 2009) and we prove KDM-security of these cryprosystems with respect to the set of affine functions. The security of our cryptosystems is based on the LWE problem and the LPN problem as its special case. We study these problems and their variants. Moreover, we give a brief introduction to lattices and hard lattice problems because there exist reductions from hard lattice problems to LWE. 1
|
|
|
Homomorphic encryption schemes
Titěrová, Anežka ; Kazda, Alexandr (advisor) ; Hojsík, Michal (referee)
Title: Homomorphic encryption schemes Author: Anežka Titěrová Department: Department of Algebra Supervisor: RNDr. Alexandr Kazda, Department of Algebra Abstract: Rivest et al. posed in 1978 the cryptographic problem how to correctly compute arbitrary functions over encrypted data without direct decrypting. This problem is solved by using of a fully homomorphic encryp- tion scheme, which was discovered and first described by Craig Gentry in 2009. This work gives a summary of contemporary knowledge in this field. The attention will be restricted to a general overview how to construct the fully homomorphic encryption scheme with respect to the information security. The results will be applied in an implementation of a somewhat homomorphic encryption scheme as a computer program. Fully homomorphic encryption schemes have abundant applications, especi- ally in secure cloud computing. Nevertheless, the greatest challenge for scien- tists is finding out more efficient algorithm because existing implementations are not as effective and fast as required for everyday use. Keywords: homomorphic encryption, fully homomorphic encryption scheme, lattice cryptography, logic circuit
|
|
|
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
|
|
|
Model building using CSP
Peterová, Alena ; Stanovský, David (advisor) ; Kazda, Alexandr (referee)
In the present work, we study algorithms for building finite models of sets of first-order axioms with the aim of proposing and implementing a new method, based on translation onto constraint satisfaction problem (CSP). In the theoretical part, we describe the standard MACE-style method, based on translating problems onto SAT, and advanced techniques that improve the effectiveness of this method: clause splitting, term definitions and static symmetry reduction. Next, we propose an alternative method, which translates problems onto CSP in a similar way. In addition, we have newly proposed a static symmetry reduction technique for binary functions. Next, we describe an implementation of the alternative method using a CSP-modelling language MiniZinc and a CSP-solver Gecode. Finally, we compare performance of our model finder against state-of-the-art representatives of standard methods, systems Paradox and Mace4.
|
guest ::
