|
|
An implicit representation of sets
Lieskovský, Matej ; Mareš, Martin (advisor) ; Majerech, Vladan (referee)
The 2003 paper by Gianni Franceschini and Roberto Grossi titled "Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees" suggests a data structure that supports Insert, Find and Delete operations in O(log n) worst-case time while also being implicit and cache-oblivious. We explain the general idea of the original data structure, identify flaws and gaps in its description, and describe a reimagined version of one of the two major components of the data structure. 1
|
|
|
Comparison of Top trees implementations
Setnička, Jiří ; Majerech, Vladan (advisor) ; Mareš, Martin (referee)
Comparison of Top trees implementations - Abstract Jiří Setnička Definition and description of Top trees and introduction of problems solvable by them including problem of edge 2-connectivity. Definition and description of Topology trees used as one of the drivers for Top trees. After the initial descriptions the two top trees implementations are introduced: one based on self adjusting trees, second based on topology trees. Comparison of these implementations is done by two experiments. Measurements are discussed in conclusion - results corresponds with initial estimates but with different multiplicative constant than expected. 1
|
|
|
A Controlled Searching of Game Trees
Vrba, Jan ; Hric, Jan (advisor) ; Majerech, Vladan (referee)
Title: A Controlled Searching of Game Trees Author: Jan Vrba Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: RNDr. Jan Hric Abstract: Monte-Carlo Tree Search is a search algorithm based on random Monte- Carlo playouts. Since it was first introduced in 2006, it has been successfully used in several areas. Most notably for the game Go. MCTS is intended mainly for problems with too large a state space to be fully explored in reasonable time. Working with a large state space and the fact that when evaluating a node, it first explores all possible moves leads to large memory complexity. This work explores options a user can use to regulate memory complexity based on the results of previous Monte-Carlo playouts. Keywords: MCTS, UCT, BMCTS, RAVE
|
|
|
Succinct encodings of trees
Juraszek, Adam ; Mareš, Martin (advisor) ; Majerech, Vladan (referee)
We focus on space-efficient, namely succinct, representations of static ordinal unlabeled trees. These structures have space complexity which is optimal up to a lower-order term, yet they support a reasonable set of operations in constant time. This topic has been studied in the last 27 years by numerous authors who came with several distinct solutions to this problem. It is not only of an academic interest, the succinct tree data structures has been used in several data-intensive applications, such as XML processing and representation of suffix trees. In this thesis, we describe the current state of knowledge in this area, compare the many different approaches, and propose several either new or alternative algorithms for operations in the representations alongside. Powered by TCPDF (www.tcpdf.org)
|
|
|
Inspiration-triggered search: Towards higher complexities by mimicking creative processes
Rybář, Milan ; Hamann, Heiko (advisor) ; Majerech, Vladan (referee)
The trap of local optima is one of the main challenges of stochastic optimization methods from machine learning. The aim of this thesis is to develop an optimization algorithm that is inspired by users interacting with Picbreeder, which is an online service that allows users to collaboratively evolve images via an artificial evolution. The idea is that their behaviours depict creative processes. We propose a general framework on the top of a common optimization technique called inspiration-triggered search, which mimics these processes. Instead of a fixed objective function the search algorithm is free to change the objective within certain constraints. The overall optimization task is to generate complex artefacts that cannot be generated by a greedy and direct optimization approach. The proposed method is tested in the domain of images, that is to find complex and aesthetically pleasant images for humans, and compared with the direct optimization. Powered by TCPDF (www.tcpdf.org)
|
|
|
Modeling of Cooperative Path Finding
Ježek, Milan ; Surynek, Pavel (advisor) ; Majerech, Vladan (referee)
In this thesis we describe new models for solving the cooperative pathfinding (cpf) with the requirement of minimal makespan and experimental comparison with current models is performed. These new models investigate the possibilities of encoding the cpf problem into binary integer programming (bip) or constraint satisfaction problem (csp). Mainly the new active-edges IP model tests with high number of agents yielded good results, where it fell only slightly behind the best SAT model. A new csp model reached the fastest times in tests with low number of obstacles and agent interactions while struggling heavily in the opposite cases. Powered by TCPDF (www.tcpdf.org)
|
|
|
Particular Problems Related to the Vehicle Routing Problem
Kuklis, Imrich ; Pergel, Martin (advisor) ; Majerech, Vladan (referee)
Title: Particular Problems Related to the Vehicle Routing problem Author: Imrich Kuklis Department: Department of Software and Computer Science Education Supervisor: RNDr. Martin Pergel, Ph.D., Department of Software and Computer Science Education Abstract: In this thesis we present and implement some scheduling algorithms. In the first part we discuss the vehicle routing problem and its variants. In the second part we describe the algorihms we used in the thesis. In the third part we compare the algorithm by their results on several tests. In the last chapter we describe the documentation of the programs which we implemented and discuss the possible future extension of the thesis. Powered by TCPDF (www.tcpdf.org)
|
|
|
Agent for playing Texas Hold'em poker
Bambušek, Petr ; Blažek, Jan (advisor) ; Majerech, Vladan (referee)
Main purpose of this thesis is to create agent for playing Texas Hold'em poker, which will be easily extensible by new inputs, outputs and game strategies. We present this firstly on input based on image recognition of client of chosen online poker site, secondly on simple game strategy based on expert system. Main working algorithm of agent will be encapsulated in single object and will run in separate thread. This will allow us to easily incorporate and manage agent from another programs, example way of managing and setting is presented on simple graphical application. The resulting agent can be further used as tool for testing and creation of new game strategies. Powered by TCPDF (www.tcpdf.org)
|
|
|
Genetic programming in financial markets forecasting
Krejčí, Tomáš ; Bednárek, David (advisor) ; Majerech, Vladan (referee)
The aim of this thesis is to test usability of the genetic programming for predicting of the financial markets based on historical prices. The thesis includes the study of genetic programming techniques used or useful for the market prediction. The practical part of thesis is implementation of selected methods and testing their performance on available historical data from financial markets. Powered by TCPDF (www.tcpdf.org)
|
|
|
Distributed Monte-Carlo Tree Search for Games with Team of Cooperative Agents
Filip, Ondřej ; Lisý, Viliam (advisor) ; Majerech, Vladan (referee)
The aim of this work is design, implementation and experimental evaluation of distributed algorithms for planning actions of a team of cooperative autonomous agents. Particular algorithms require different amount of communication. In the work, the related research on Monte-Carlo tree search algorithm, its parallelization and distributability and algorithms for distributed coordination of autonomous agents. Designed algorithms are tested in the environment of the game of Ms Pac-Man. Quality of the algorithms is tested in dependence on computational time, the amount of communication and the robustness against communication failures. Particular algorithms are compared according to these characteristics. Powered by TCPDF (www.tcpdf.org)
|
guest ::
