Pojem polymorfismu relační struktury hraje klíčovou roli v algebraickém přístupu k Problému splňování omezení (CSP). Cílem práce je nastudovat základy algebraického přístupu k CSP a pomocí modelovacího jazyka MiniZinc a vhodného CSP solveru (např. Gecode) implementovat test, zda má daná relační struktura "zajímavé" polymorfismy (tj. zda splňuje některé mal'cevské podmínky související se složitostí CSP). Dále generovat malé relační struktury a hledat exempláře se zajímavými algebraickými vlastnostmi. Výstupem práce bude analýza a interpretace získaných empirických dat, empirické potvrzení (nebo vyvrácení) některých hypotéz, a dále konkrétní relační struktury s neznámou složitostí CSP.
Seznam odborné literatury
L. Barto, D. Stanovský. Polymorphisms of small digraphs, In Novi Sad J. Math. 40/2 (2010), 95--109.
A. Bulatov, M. Valeriote. Recent results on the algebraic approach to the CSP, Complexity of Constraints: An Overview of Current Research Themes, Springer-Verlag, 2008, 68-92.
N. Nethercote, P. J. Stuckey, R. Becket, S. Brand, G. J. Duck, G. Tack. MiniZinc: Towards a Standard CP Modelling Language, In Christian Bessière, editor, CP’07, volume 4741 of LNCS, p. 529-543. Springer.
Předběžná náplň práce
Cílem práce je implementovat hledání zajímavých polymorfismů relačních struktur pomocí modelovacího jazyka MiniZinc a CSP solveru. Dále generovat a testovat malé relační struktury, hledat mezi nimi zajímavé exempláře (např. s neznámou složitostí CSP) a analyzovat získaná empirická data.
Předběžná náplň práce v anglickém jazyce
The aim of the thesis is to implement searching for interesting polymorphisms on relational structures using the modelling language MiniZinc and a CSP solver. Then generate and test small relational structures, isolate the interesting ones (e.g. those with unknown complexity of CSP) and analyze obtained empirical data.
