|
|
Relational Approach to Universal Algebra
Opršal, Jakub ; Barto, Libor (advisor) ; Růžička, Pavel (referee) ; Mayr, Peter (referee)
Title: Relational Approach to Universal Algebra Author: Jakub Opršal Department: Department of Algebra Supervisor: doc. Libor Barto, Ph.D., Department of Algebra Abstract: We give some descriptions of certain algebraic properties using rela- tions and relational structures. In the first part, we focus on Neumann's lattice of interpretability types of varieties. First, we prove a characterization of vari- eties defined by linear identities, and we prove that some conditions cannot be characterized by linear identities. Next, we provide a partial result on Taylor's modularity conjecture, and we discuss several related problems. Namely, we show that the interpretability join of two idempotent varieties that are not congruence modular is not congruence modular either, and the analogue for idempotent va- rieties with a cube term. In the second part, we give a relational description of higher commutator operators, which were introduced by Bulatov, in varieties with a Mal'cev term. Furthermore, we use this result to prove that for every algebra with a Mal'cev term there exists a largest clone containing the Mal'cev operation and having the same congruence lattice and the same higher commu- tator operators as the original algebra, and to describe explicit (though infinite) set of identities describing supernilpotence...
|
|
|
Problém realizace von Neumannovsky regulárních okruhů
Mokriš, Samuel ; Růžička, Pavel (advisor) ; Žemlička, Jan (referee)
Title: The realization problem for von Neumann regular rings Author: Samuel Mokriš Department: Department of Algebra Supervisor of the master thesis: Mgr. Pavel Růžička, Ph.D., Department of Algebra Abstract: With every unital ring R, one can associate the abelian monoid V (R) of isomor- phism classes of finitely generated projective right R-modules. Said monoid is a conical monoid with order-unit. Moreover, for von Neumann regular rings, it satisfies the Riesz refinement property. In the thesis, we deal with the question, under what conditions an abelian conical re- finement monoid with order-unit can be realized as V (R) for some unital von Neumann regular ring or algebra, with emphasis on countable monoids. Two generalizations of the construction of V (R) to the context of nonunital rings are presented and their interrelation is analyzed. To that end, necessary properties of rings with local units and modules over such rings are devel- oped. Further, the construction of Leavitt path algebras over quivers is presented, as well as the construction of a monoid associated with a quiver that is isomorphic to V (R) of the Leavitt path algebra over the same quiver. These methods are then used to realize directed unions of finitely generated free abelian monoids as V (R) of algebras over any given field. A method...
|
|
|
Multivariate cryptography
Jančaříková, Irena ; Žemlička, Jan (advisor) ; Růžička, Pavel (referee)
This thesis deals with multivariate cryptography. It includes specifically a description of the MQ problem and the proof of it's NP-completness. In the part of the MQ problem there is a description of a general pattern for the creation of the public part of asymetric cryptosystems based on the MQ problem. It this part the thesis describes the QMLE problem, which is important for the figure of the cryptosystem private key based on the MQ problem. Further, the thesis includes a description of the influence of the structure display, which appears in the QMLE problem, on time solution complexity of QMLE problem. The influence of time complexity has been detected by means of experimental measurement with programed algorithm. At the end of the thesis there is specified description of selected multivariety cryptosystems based on the MQ problem. Selected cryptosystems are provided with detailed description of encryption and decryption by means of selected cryptosystems and time estimations of these operations. The thesis includes estimations of memory requirements on saving of private and public key of the selected cryptosystems. Powered by TCPDF (www.tcpdf.org)
|
|
|
An algorithmic approach to resolutions in representation theory
Ivánek, Adam ; Šťovíček, Jan (advisor) ; Růžička, Pavel (referee)
In this thesis we describe an algorithm and implement a construction of a projective resolution and minimal projective resolution in the representation the- ory of finite-dimensional algebras. In this thesis finite-dimensional algebras are KQ /I where KQ is a path algebra and I is an admissible ideal. To implement the algorithm we use the package QPA [9] for GAP [2]. We use the theory of Gröbners basis of KQ-modules and the theory described in article Minimal Pro- jective Resolutions written by Green, Solberg a Zacharia [5]. First step is find a direct sum such that i∈Tn fn∗ i KQ = i∈Tn−1 fn−1 i KQ ∩ i∈Tn−2 fn−2 i I. Next important step to construct the minimal projective resolution is separate nontri- vial K-linear combinations in i∈Tn−1 fn−1 i I + i∈Tn fn i J from fn∗ i . The Modules of the minimal projective elements are i∈Tn (fn i KQ)/(fn i I). 1
|
|
| |
|
|
Constraint satisfaction, graphs and algebras
Bulín, Jakub ; Barto, Libor (advisor) ; Růžička, Pavel (referee) ; Bulatov, Andrei (referee)
Constraint satisfaction, graphs and algebras Jakub Bulín Abstract This thesis consists of three papers in the area of algebraic approach to the constraint satisfaction problem. In the first paper, a joint work with Deli'c, Jackson and Niven, we study the reduction of fixed template CSPs to digraphs. We construct, for every relational structure A, a digraph D(A) such that CSP(A) and CSP(D(A)) are logspace equivalent and most rele- vant properties carry over from A to D(A). As a consequence, the algebraic conjectures characterizing CSPs solvable in P, NL and L are equivalent to their restrictions to digraphs. In the second paper we prove that, given a core relational structure A of bounded width and B ⊆ A, it is decidable whether B is an absorbing subuniverse of the algebra of polymorphisms of A. As a by-product, we show that Jónsson absorption coincides with the usual absorption in this case. In the third paper we establish, using modern algebraic tools (e.g. absorption theory and pointing operations), the CSP dichotomy conjecture for so-called special oriented trees and in particular prove that all tractable core special trees have bounded width. Keywords: constraint satisfaction problem, algebra of polymorphisms, absorbing subuniverse, bounded width, oriented tree.
|
|
|
Maximal Orders
Tlustá, Stanislava ; Příhoda, Pavel (advisor) ; Růžička, Pavel (referee)
Maximal Orders Stanislava Tlustá Abstract This thesis summarizes basic properties of lattices and orders over Dedekind domain in separable algebras. The concepts of reduced norm and reduced trace are introduced and applied to few examples of rational algebras. By that the maximal orders are found. The properties of maximal orders are stated and used to explore new types of ideals: normal ideals and Λ-ideals. At the end of this thesis the isomorphisms of lattices are examined and the Jordan-Zassenhaus theorem is proved. 1
|
|
|
Generalized injectivity and approximation
Sahinkaya, Serap ; Trlifaj, Jan (advisor) ; Jirásko, Josef (referee) ; Růžička, Pavel (referee)
Title: Generalized injectivity and approximations Author: Serap S¸ahinkaya Department:Algebra Faculty of Mathematics and Physics, Charles University Supervisor: Prof. RNDr. Jan Trlifaj, DSc, Faculty of Mathematics and Physics, Charles University Abstract: Injective modules form a basic class studied in contemporary module theory. One of their generalizations, inspired by tilting theory, is the notion of a cotilting module. While tilting modules behave well with respect to localization, we show that colocalization is the correct approach when comparing the struc- ture of cotilting modules over commutative noetherian rings R with the structure of cotilting modules over their localizations Rm where m runs over the maximal spectrum of R. This is done in Chapter 2 of this Dissertation whose main results were published in the paper [33]. In Chapter 3, we investigate approximation properties of other classic generalizations of injective modules, the Ci- and quasi- injective modules, introduced by Harada et al. Suprisingly, we prove that these classes provide for approximations only in exceptional cases (when all Ci mod- ules are injective, or pure-injective). The Dissertation ends with a set of open problems. Keywords: Commutative noetherian ring, (co)tilting module, (generalized) injec- tive module. 1
|
|
|
Tracking mortar shell
Miklín, Vojtěch ; Tůma, Jiří (advisor) ; Růžička, Pavel (referee)
This thesis aims to summarize possibilities of using Kalman filter for state estimation of a discrete dynamic system known only from inaccurate measurements. Firstly the notion of statistics, dynamic system and coordinate systems (Cartesian and spherical) are defined. Then the Kalman filter algorithm is described and a physical model for the filter is derived. This thesis is based on chapter 7 of [Tomasi, 1997] (textbook for the CS 205 lecture at Stanford University). Carlo Tomasi applies theory on a simplified example of mortar shell tracking. One of this thesis' objectives was to generalize the method for the case when the observer is not located in the 2D plain of flight of a shell. Another task was to include air resistance and wind in the model equations.
|
|
|
Testování náhodnosti a použití statistických testů v kryptografii
Nižnanský, Petr ; Růžička, Pavel (advisor) ; Holub, Štěpán (referee)
Pseudorandom generators belong to the primary focus of cryptology. The key to every cipher has to be generated at random, otherwise the security of the whole cipher is threatened. Another point of importance is the pseudorandom generators' close relationship to the stream ciphers. In this work, we first introduce statistical theory related to randomness testing. Then, we describe 8 classical statistical tests. We introduce a concept of next bit testing and derive variants of previous tests. Moreover, with this new battery of tests we examine the randomness of SHA-3 second round candidates and present the results. Also a sensitivity of tests is investigated and several useful transformations are shown. Powered by TCPDF (www.tcpdf.org)
|
guest ::
RSS feed.