National Repository of Grey Literature 46 records found  1 - 10nextend  jump to record: Search took 0.01 seconds. 
Worst case driver for Top trees
Ondráček, Lukáš ; Majerech, Vladan (advisor) ; Fink, Jiří (referee)
A top tree data structure solves one of the most general variants of a well- studied dynamic trees problem consisting in maintenance of a tree along with some aggregated information on paths or in individual trees, possibly in a mutable way, under operations of inserting and removing edges. It provides a simple interface separated from both an internal top tree structure representing a hierarchical partitioning of the graph, and a driver ensuring its depth to be logarithmic, which has a crucial role for the efficiency of the data structure. The driver proposed in this thesis is based on biased trees, combining techniques used in the worst-case version of link/cut trees and in the amortized driver for top trees: An input forest is decomposed into heavy paths and interleaving vertices, all of them being represented by biased trees connected together to form exactly the top tree structure. The driver is meant to be a more efficient alternative to the originally proposed one, and a comparably efficient alternative to the driver proposed by Werneck; there is a room for their experimental comparison.
Compact description of directory trees
Končický, Václav ; Mareš, Martin (advisor) ; Majerech, Vladan (referee)
There exist many copies of data stored as directory trees whose consistency we need to verify. In this work we create a new binary format describing directory trees. It allows to record names, hashed contents, and other metadata of the files. In order to verify data consistency, we can compare two such descriptions. This format is designed with focus on its compactness and high read speed. We present a program which builds such description for a given tree and compares two descriptions. In order to maximize speed we use parallelization techniques and tree hashing, taking properties of hard disk drives into account. 1
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 (
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 (
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 (
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 (
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 (

National Repository of Grey Literature : 46 records found   1 - 10nextend  jump to record:
Interested in being notified about new results for this query?
Subscribe to the RSS feed.