|
|
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.
|
|
|
Cryptographic schemes based on the discrete logarithm problem
Kadlček, Tomáš ; Holub, Štěpán (advisor) ; Růžička, Pavel (referee)
In the paper we try to give a view of the discrete logarithm problem, especially of related problems that appear in literature since 2001. These problems are based on a computation of Weil and Tate pairing on eliptic curves. We give a view of these problems including some reductions. We mention some chosen schemes based on these problems that are iteresting because of their practical parametrs, primaci of security proofs or because these schemes introduced the new problem. We try to cover precisely the most important definitions in this sector of cryptography because these definition are omitted in the literature and it is often left up to reader to presume details by himself.
|
|
| |
|
| |
|
| |
|
|
Extension of fields and solvability of algebraic equations
Štíchová, Kateřina ; Stanovský, David (referee) ; Růžička, Pavel (advisor)
Xaxev praee: Hoxsifeni teles a reseni algebraickyeh rovnie Autor: Katerina fit iehova Katedra (ustav): Kafedra algebry Matematicko-fyxikalni f a k u l t y \ Pnixe Vedouoi bakalarske praee: Mgr. Pavel Kuxioka, Ph.I), Kaledra algebry e-mail vedoueiho: Pavel. Huxieka " i n f f . e u n i . e / Abstrakt: V pfedlo/ene praei se x'rnujciiK1 i'rsciii al^rbrairkvrh rovnic di'iilirhu ax pa- trho sT.u])iir a, CJaluisuvr ti'oiii. \i rasli jr po])s;i.n xpusnli rrscni ai^chraickyrh rovnic. s])ocialnr ( 'a.rda.novy vxnrcu. Dale jc nvcdcna rrorir trios, ktcrii jc stavcliniin prvkrin ])ro iiiishxlujici ka pi loin vlasl ni (ialoisovy t.curir, jcv, jc jadrcni t.rt.u prii.cc. I'o- slcdni ka.])itola sc 7a.l)yv;i aplika.ci (JaJoisovy t.coric. konkrctnc nt'n'sit.i'luosti rovnicc pateho stupno v ra.dikalccli. V Tlvodu. ]>ro Aplikaer a. ])rik!ady a jsinc vyeliaxeli lila.vnc xc /.droje ,7 . Vc 2. ka- ])ilolc jsme sc inspirovali f3] a. |0j. v Tcorii rclcs jsnic pou/ili -'2 . Dalo -1. ka.pitola byla. na])s;ina jioinoci 1 Title: Field extensions and solution of algebraic equations Author: Katerina Stiehova Department: I)c])art incut of Algebra Sii]>crvisor: Mj;r, l'a\'el Huxieka. Pli.D Supervisor's e-mail addre>s Pavel.l\u/icka u infi.cuni.cx Abstract: In the ]ji'cseiit \vork \vc s( udy solut ion of general algebraic c(|iiat Jcjns of...
|
|
| |
|
| |
|
| |
|
| |
guest ::
