|
|
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.
|
|
|
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.
|
|
|
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.
|
|
|
Optimization of traffic engineering problems
Le, Huy ; Hošek, Jaromír (referee) ; Hrabec, Dušan (advisor)
This bachelor thesis focuses on optimization of traffic light control of intersection, more specifically looks for optimal minimal signal plan of intersection considering given requirements. Theoretical part is about suppositions and basic definitions, after that usable algorithms for this problem are described in details. Practical part deals with application of these algorithms on specific example of intersection and compares obtained results afterwards.
|
|
|
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.
|
|
|
Graph Colouring, Graph Clique, Algorithms and Applications
Valachová, Alžbeta ; Dvořák, Jiří (referee) ; Šeda, Miloš (advisor)
This thesis deals with the problem of graph coloring and finding cliques in a graph, with a focus on the description of algorithms and their applications. Graph coloring is the process of assigning colors to individual vertices of a graph so that adjacent vertices have different colors. This issue is important for solving various optimization problems. The work also focuses on finding cliques in a graph, which is an important problem in social network analysis or image recognition. The aim of this thesis is to provide a complex overview of graph coloring, finding cliques in a graph, introduce and analyze existing algorithms and show their applications in practice.
|
|
|
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.
|
|
|
Variants of graph labeling problems
Masařík, Tomáš ; Fiala, Jiří (advisor) ; Fellows, Michael R. (referee) ; Hell, Pavol (referee)
This thesis consists of three parts devoted to graph labeling, hereditary graph classes, and parameterized complexity. Packing coloring, originally Broadcasting Chromatic number, assigns natural numbers to vertices such that vertices with the same label are in distance at least the value of the label. This problem is motivated by the assignment of frequencies to the transmitters. We improve hardness on chordal graphs. We proof that packing coloring on chordal graphs with diameter 3 is very hard to approximate. Moreover, we discuss several positive results on interval graphs and on related structural graph parameters. Hereditary graph classes are preserved under vertex deletion. We study graphs that do not contain an induced subgraph H. We prove that 3-coloring is polynomial-time solvable for (P3 + P4)-free and (P2 + P5)-free graphs and thus we have solved the last open cases for the problem on H-free graphs where H has up to 7 vertices. Fair problems are a modification of graph deletion problems, where, instead of minimizing the size of the solution, the aim is to minimize the maximum number of neighbors in the deleted set. We show that those problems can be solved in FPT time for an MSO1 formula parameterized by the size of the formula and the twin cover of the graph. Moreover, we define a basic...
|
|
|
Optimization of traffic engineering problems
Le, Huy ; Hošek, Jaromír (referee) ; Hrabec, Dušan (advisor)
This bachelor thesis focuses on optimization of traffic light control of intersection, more specifically looks for optimal minimal signal plan of intersection considering given requirements. Theoretical part is about suppositions and basic definitions, after that usable algorithms for this problem are described in details. Practical part deals with application of these algorithms on specific example of intersection and compares obtained results afterwards.
|
guest ::
