|
|
Theory and Applications of Monte Carlo Methods
Hruda, Petr ; Šimek, Václav (referee) ; Bidlo, Michal (advisor)
This bachelor thesis deals with applications of Monte Carlo methods on various problems. In particular, Metropolis algorithm and Simulated Annealing were applied on optimization of Traveling Salesman Problem and the problem of graph coloring. Moreover, "traditional" Monte Carlo approach was utilized for statistical analysis of electronic circuits in which the values of components exhibit random variations with a given tolerance. The results are evaluated for different setups of Monte Carlo methods.
|
|
|
Computational complexity in graph theory
Doucha, Martin ; Kratochvíl, Jan (advisor) ; Dvořák, Zdeněk (referee)
This work introduces two new parameterizations of graph problems generalizing vertex cover which fill part of the space between vertex cover and clique width in the hierarchy of graf parameterizations. We also study parameterized complexity of Hamiltonian path and cycle, vertex coloring, precoloring extension and equitable coloring parameterized by these two parameterizations. With the exception of precoloring extension which is W[1]-hard in one case, all the other problems listed above are tractable for both parameterizations. The boundary between tractability and intractability of these problems can therefore be moved closer to parameterization by clique width.
|
|
|
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.
|
|
|
Methods for Coloring Nodes in Multigraf
Knotek, Martin ; Kunovský, Jiří (referee) ; Šátek, Václav (advisor)
This thesis deals with algorithms for verticies coloring and their application to the coloring elements of electrical low voltage grid. Result of this thesis is a program, which displays progress of coloring five implemented algorithms on a selected graph. The graph represents electricity distribution network in a city.
|
|
|
Optimalization of an Agent Code
Hemala, Luboš ; Kočí, Radek (referee) ; Zbořil, František (advisor)
This work continues in an effort to improve the compiler of the AHLL agent language. The main focus is to integrate optimizations that would reduce the size of the target ALLL code, therefore global register allocation by graph coloring is implemented in this version. Some changes to the language are introduced as well, but which impose a more complicated compiler structure. The overall results of the new compiler then indicate a 35 % decrease in the size of the code on average for the evaluated complex agents.
|
|
|
Graph Coloring
Procházka, Lukáš ; Goldefus, Filip (referee) ; Masopust, Tomáš (advisor)
This thesis is about graph coloring, which is assigning colors to vertices of a graph such that no two vertices, which are linked with an edge, have the same color. This problem is very computational hard, because it's NP-complete. It's also very important, because it has many practical applications. Here are described some of the heuristic algorithms, which try to solve this problem by iteratively improving the initial solution with given number of colors. Three of them have been implemented, tested on different graphs and compared considering several criteria.
|
|
|
Information System for a School Including Automated Timetabling
Švadlenka, Jiří ; Jurka, Pavel (referee) ; Chmelař, Petr (advisor)
This thesis devote itself to use of information system for school agenda administration. Schools are forced to administer big amounts of informations, not only referred to their students. Broad issue is very extensive and disparate, so the most common types of data and demands on school information system operation are stated. The system for automatic generation of timetables is part of the school information system. At the first, basic conceptions of scheduling scope are defined and tied together with them are methods and algorithms for timetable creation problem solving. School timetabling is problem of scheduling lessons with certain limitative conditions. Further, thesis is engaged in design of school information system, data organization in such system and solving of system design problems. Designed information system accentuates on easy expandability and wide range of usage possibilities. Also suggested algorithm for solving of defined school timetabling is stated in this part of thesis.
|
|
| |
|
| |
guest ::
