Original title: Vážené klony
Translated title: Vážené klony
Authors: Vančura, Jiří ; Barto, Libor (advisor) ; Příhoda, Pavel (referee)
Document type: Master’s theses
Year: 2014
Language: eng
Abstract: [eng] [cze]
The well know constraint satisfaction problem (CSP) can be generalized to a class of optimization problems - VCSP. In 2012, D. A. Cohen, M. C. Cooper, P. Creed, P. G. Jeavons and S. Živný proved that weighted clones and weighted relational clones play the same role for the VCSP as do clones and relational clones for the CSP. However the structure of weighted clones remains unknown even for two element domain. This thesis presents a more detailed proof of the result mentioned above and then it investigates the structure of weighted clones. For Boolean domain, we present a complete classification of weighted clones over all seven minimal clones. Powered by TCPDF (www.tcpdf.org) Známý problém splnitelnosti dané formule CSP je možné zobecnit na třídu optimalizačních problémů VCSP. V roce 2012 dokázali D. A. Cohen, M. C. Cooper, P. Creed, P. G. Jeavons a S. Živný, že stejnou roli jakou mají klony a relační klony pro CSP mají vážené klony a vážené relační klony pro VCSP. Samotná struktura vážených klonů ale zůstává neprozkoumaná a to i pro dvouprvkový obor hodnot. Tato práce podává detailnější důkaz výše zmíněného výsledku a dále zkoumá strukturu vážených klonů. Pro dvouprvkový obor hodnot uvádíme kompletní klasifikaci vážených klonů nad všemi sedmi minimálními klony. Powered by TCPDF (www.tcpdf.org)
Keywords: Relational clones; VCSP; Weighted clones; Relační klony; VSCP; Vážené klony

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/63083

Permalink: http://www.nusl.cz/ntk/nusl-332233


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses