Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 290)
Detail práce
   Přihlásit přes CAS
Algebraický přístup k CSP
Název práce v češtině: Algebraický přístup k CSP
Název v anglickém jazyce: The Algebraic Approach to CSP
Klíčová slova: problém splňování omezení, barvení grafů, konečná šířka, speciální triáda
Klíčová slova anglicky: constraint satisfaction problem, graph coloring, bounded width, special triad
Akademický rok vypsání: 2008/2009
Typ práce: diplomová práce
Jazyk práce: angličtina
Ústav: Katedra algebry (32-KA)
Vedoucí / školitel: doc. Mgr. Libor Barto, Ph.D.
Řešitel: skrytý - zadáno a potvrzeno stud. odd.
Datum přihlášení: 11.11.2008
Datum zadání: 11.11.2008
Datum a čas obhajoby: 16.09.2010 00:00
Datum proběhlé obhajoby: 16.09.2010
Oponenti: doc. Mgr. Pavel Růžička, Ph.D.
 
 
 
Zásady pro vypracování
Práce se bude zabývat algebraickým přístupem k problému CSP (Constraint Satisfaction Problem). Lze se zaměřit na studium některých speciálních struktur (různé druhy orientovaných stromů a jiných grafů), rozpracování relevantních algebraických nástrojů, zjednodušení důkazů známých vět algebraickými metodami, apod.
Seznam odborné literatury
[1] L. Barto, M. Kozik, M. Maroti, R. McKenzie, T. Niven, Congruence modularity implies cyclic terms for finite algebras, to appear in Alebra Universalis
[2] L. Barto, M. Kozik, M. Maroti, T. Niven, CSP dichotomy for special triads, manuscript
[3] L. Barto, M. Kozik, T. Niven, Graphs, Polymorphisms and the Complexity of Homomorphism Problems, Proceedings of the 40th ACM Symposium on Theory of Computing, STOC'08 (2008), 789-796
[4] T. Feder, Classification of Homomorphisms to Oriented Cycles and of k-Partite Satisfiability, SIAM Journal on Discrete Mathematics 14/4 (2001), 471 - 480
[5] D. Hobby, R. McKenzie, The structure of finite algebras, AMS Contemporary Mathematics vol. 76, revised edition (1991).
Předběžná náplň práce
Práce se bude zabývat algebraickým přístupem k problému CSP (Constraint Satisfaction Problem). Lze se zaměřit na studium některých speciálních struktur (různé druhy orientovaných stromů a jiných grafů), rozpracování relevantních algebraických nástrojů, zjednodušení důkazů známých vět algebraickými metodami, apod.
Předběžná náplň práce v anglickém jazyce
The thesis will be devoted to the algebraic approach to the CSP (Constraint Satisfaction Problem). The student may study selected special structures (various kinds of oriented trees, or other types of graphs), develop new algebraic tools, simplify proofs of known results by the algebraic methods, etc.
 
Univerzita Karlova | Informační systém UK