Sökning: "Constraint Satisfaction Problem"

Visar resultat 1 - 5 av 18 avhandlingar innehållade orden Constraint Satisfaction Problem.

  1. 1. Beating a Random Assignment Approximating Constraint Satisfaction Problems

    Detta är en avhandling från Stockholm : KTH

    Författare :Gustav Hast; Johan Håstad; Uri Zwick; [2005]
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Datalogi; TECHNOLOGY Information technology Computer science Computer science; TEKNIKVETENSKAP Informationsteknik Datavetenskap Datalogi;

    Sammanfattning : An instance of a Boolean constraint satisfaction problem, CSP, consists of a set of constraints acting over a set of Boolean variables. The objective is to find an assignment to the variables that satisfies all the constraints. LÄS MER

  2. 2. Constructing Algorithms for Constraint Satisfaction and Related Problems Methods and Applications

    Detta är en avhandling från Institutionen för datavetenskap

    Författare :Ola Angelsmark; Peter Jonsson; Brahim Hnich; [2005]
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; constraint satisfaction; CSP; graph problems; algorithm construction; computational complexity; microstructures; graph colouring; decision problems; optimisation problems; quantum computing; molecular computing; TECHNOLOGY Information technology Computer science; TEKNIKVETENSKAP Informationsteknik Datavetenskap;

    Sammanfattning : In this thesis, we will discuss the construction of algorithms for solving Constraint Satisfaction Problems (CSPs), and describe two new ways of approaching them. Both approaches are based on the idea that it is sometimes faster to solve a large number of restricted problems than a single, large, problem. LÄS MER

  3. 3. Aspects of a Constraint Optimisation Problem

    Detta är en avhandling från Linköping : Linköping University Electronic Press

    Författare :Johan Thapper; Peter Jonsson; David Cohen; [2010]
    Nyckelord :TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; TECHNOLOGY; TEKNIKVETENSKAP;

    Sammanfattning : In this thesis we study a constraint optimisation problem called the maximum solution problem, henceforth referred to as Max Sol. It is defined as the problem of optimising a linear objective function over a constraint satisfaction problem (Csp) instance on a finite domain. LÄS MER

  4. 4. Symmetry Breaking Ordering Constraints

    Detta är en avhandling från Uppsala : Data- och systemvetenskap

    Författare :Zeynep Kiziltan; Andreas Hamfelt; Toby Walsh; Pedro Meseguer; [2004]
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Datavetenskap; Constraint satisfaction; constraint programming; modelling; symmetry breaking; global constraints; Datavetenskap; TECHNOLOGY Information technology Computer science; TEKNIKVETENSKAP Informationsteknik Datavetenskap;

    Sammanfattning : Many problems in business, industry, and academia can be modelled as constraint programs consisting of matrices of decision variables. Such “matrix models” often have symmetry. In particular, they often have row and column symmetry as the rows and columns can freely be permuted without affecting the satisfiability of assignments. LÄS MER

  5. 5. Strong Partial Clones and the Complexity of Constraint Satisfaction Problems Limitations and Applications

    Detta är en avhandling från Uppsala : Data- och systemvetenskap

    Författare :Victor Lagerkvist; Peter Jonsson; Christer Bäckström; Nadia Creignou; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES;

    Sammanfattning : In this thesis we study the worst-case time complexity of the constraint satisfactionproblem parameterized by a constraint language (CSP(S)), which is the problem of determining whether a conjunctive formula over S has a model. To study the complexity of CSP(S) we borrow methods from universal algebra. LÄS MER