|
|
Interval solver for nonlinear constraints
Garajová, Elif ; Hladík, Milan (advisor) ; Pergel, Martin (referee)
The thesis is focused on the Sivia algorithm (Set Inverter via Interval Ana- lysis) designed for solving a continuous constraint satisfaction problem using interval methods and propagation techniques. Basic properties of the algorithm are derived, including the correction of its presented complexity bound. Some improvements concerning the testing of constraint satisfaction and optimiza- tion of the number of interval boxes describing the solution are proposed. The thesis also introduces contractors used to enhance the effectivity of the Sivia algorithm by reducing the interval boxes processed. Presented algorithms were implemented in a solver for nonlinear constraints with a simple visualization of the result using the Matlab language. A comparison of basic contractors on specific examples is given.
|
|
|
Constraint satisfaction, graphs and algebras
Bulín, Jakub ; Barto, Libor (advisor) ; Růžička, Pavel (referee) ; Bulatov, Andrei (referee)
Constraint satisfaction, graphs and algebras Jakub Bulín Abstract This thesis consists of three papers in the area of algebraic approach to the constraint satisfaction problem. In the first paper, a joint work with Deli'c, Jackson and Niven, we study the reduction of fixed template CSPs to digraphs. We construct, for every relational structure A, a digraph D(A) such that CSP(A) and CSP(D(A)) are logspace equivalent and most rele- vant properties carry over from A to D(A). As a consequence, the algebraic conjectures characterizing CSPs solvable in P, NL and L are equivalent to their restrictions to digraphs. In the second paper we prove that, given a core relational structure A of bounded width and B ⊆ A, it is decidable whether B is an absorbing subuniverse of the algebra of polymorphisms of A. As a by-product, we show that Jónsson absorption coincides with the usual absorption in this case. In the third paper we establish, using modern algebraic tools (e.g. absorption theory and pointing operations), the CSP dichotomy conjecture for so-called special oriented trees and in particular prove that all tractable core special trees have bounded width. Keywords: constraint satisfaction problem, algebra of polymorphisms, absorbing subuniverse, bounded width, oriented tree.
|
|
| |
|
|
Airport - Time and resource constrained project sheduling
Vandas, Marek ; Petříčková, Zuzana (advisor) ; Pangrác, Ondřej (referee)
This thesis identifies constraints for safe ground airport operations. These operations consist of runway assignment, taxi operations planning and gate scheduling. The aim of this thesis is to show how this problem can be formulated as constraint satisfaction problem and then solved as a scheduling problem. Based on this model, an application that ilustrates these concepts is designed and implemented. This application enables a visualisation of results. An extendable constraint solver was implemented for the purpose of this application. This solver can be used to solve problems from other domains as well and also enables easy change of search strategy.
|
|
|
Algebraický přístup k CSP
Bulín, Jakub ; Barto, Libor (advisor) ; Růžička, Pavel (referee)
For a finite relational structure A, the Constraint Satisfaction Problem with template A, or CSP(A), is the problem of deciding whether an input relational structure X admits a homomorphism to A. The CSP dichotomy conjecture of Feder and Vardi states that for any A, CSP(A) is either in P or NP-complete. In the first part we present the algebraic approach to CSP and summarize known results about CSP for digraphs, also known as the H-coloring problem. In the second part we study a class of oriented trees called special polyads. Using the algebraic approach we confirm the dichotomy conjecture for special polyads. We provide a finer description of the tractable cases and give a construction of a special polyad T such that CSP(T) is tractable, but T does not have width 1 and admits no near-unanimity polymorphisms.
|
|
|
Graphic Animation of Problem Solving Methods
Macek, Jiří ; Jurka, Pavel (referee) ; Zbořil, František (advisor)
There are many kinds of implementation artificial intelligence for automatic solving problems by computer technology. The main topics of this bachelor's thesis are some typical methods, describing of their features, comparing them among and shows some useful techniques of algoritmization and implementation too. Main purpose of this thesis is creating application, which clearly demonstrates at chosen problems methods of their solving.
|
|
|
Rule-Based Melody Harmonization
Kuchár, Pavol ; Žák, Pavel (referee) ; Fapšo, Michal (advisor)
Bachelor thesis deals with the issue of computer aided composition. The aim of the thesis was to create the program, which implements several rules of music theory and using of CSP determines appropriate tones for harmonization of melody. The result is presented in score and MIDI file.
|
|
|
Automatic Creation of Organ Overtures for Church Songs
Maňák, Ondřej ; Černocký, Jan (referee) ; Fapšo, Michal (advisor)
The focus of this master's thesis is an automatic creation of organ overtures for church songs from both theoretical and practical points of view. Organ overture is a short introduction to a church song. According to the fact that it can be described by a finite set of rules, it is possible to use techniques for solving Constraint Satisfaction Problems. An effective instrument to develop such system can be C++ programming language and Gecode library.
|
|
|
Automatic jazz arrangement
Chadim, Petr ; Karafiát, Martin (referee) ; Fapšo, Michal (advisor)
This Thesis is focused on the arranging of the melody, which is accompanied by jazz chords. It deals with creating a more harmonious voices using Block Voicing method. Distribution to target notes and passing notes is made using techniques of constraint programming (CSP). Passing notes are reharmonized by dominant seventh chord or by parallel chord. Using CSP a bass part is also created. To solve CSP is used Gecode library. The harmonious voices are arranged by Four Part Close Voicing. The application result is a tool for the music arranger.
|
guest ::
