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.
References
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.
Preliminary scope of work
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.
Preliminary scope of work in English
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.
