|
|
Vlastnosti universálního hašování
Babka, Martin ; Majerech, Vladan (referee) ; Koubek, Václav (advisor)
The aim of this work is to create a model of hashing with an acceptable worst case time complexity. The model is based on the idea of universal hashing and the expected time of every operation is constant. The used universal class of functions consists of linear transformations between vector spaces. This class has already been studied with a good asymptotic result. This work improves the result and proves that the expected amortised time of the scheme is constant.
|
|
|
Entropy coders
Uzel, Petr ; Majerech, Vladan (referee) ; Lánský, Jan (advisor)
Goal of this work is an implementation of various methods of entropy coding and measuring of their compression ratio and speed in context of the XBW project [Lan07]. These methods include arithmetic coding (with using both Moat's [Mof99] and Fenwick's [Fen96] data structures for actualization of cumulated counts), Human coding [Huf52] and Multistream Compression [KLUZ08]. There is an emphasis on using these methods on large alphabets. For the Multistream Compression method, the goal is also to design and experimentally test various methods for encoding of streams of counters.
|
|
|
Top-trees implementation
Šofka, Jiří ; Mareš, Martin (referee) ; Majerech, Vladan (advisor)
Title: Top Trees implementation Author: Jifi Sofka Department: Department of Theoretical Computer Science and Mathemat- ical Logic Supervisor: Mgr. Vladan Majerech, Dr. Supervisor's e-mail address: Vladaii.Majerech@mff.cmii.cz Abstract: Dynamic data structure Top Trees is used to represent a tree by a binary structure of tree contractions. Vertices of such a binary tree are called clusters. Each cluster represents one contraction and contains aggregated data of its children. One of the main advantages of Top Trees is the separation of cluster's data management into Create, Destroy, Join, Split and Select functions which are automatically called as the internal structure of Top Trees changes. The implementation of Top Trees is therefore independent of all the properties that are tracked about the original tree (i.e. 2-connecticity, tree median). The size of cluster's aggrefated data about one tree property may de- pend on the size of the entire original tree and its calculation can be time consuming. The operations used to query the Top Tree about different tree properties often result in Top Tree structural changes. In the original Top Tree design, each of the affected clusters needs to update the data belong- ing to all tracked properties when such structural change occurs. Not all of the properties are...
|
|
|
Methods of MCTS and the game Arimaa
Kozelek, Tomáš ; Majerech, Vladan (referee) ; Hric, Jan (advisor)
Game of Arimaa is an artificially created strategic board game with the purpose to be difficult for computers. A vast majority of introduced computer engines for Arimaa are based on successful approaches from chess, namely the minimax algorithm with pruning and further extensions. In this thesis we have analyzed the applicability of the so called MCTS methods in the game of Arimaa. MCTS methods are a state-of-the-art approach to the computer Go with bright prospects in other strategic games as well. We have implemented a MCTS based Arimaa engine called Akimot and adapted the MCTS techniques for the Arimaa environment. We have experimented with various MCTS enhancements known from computer Go and identified which are prospective in our setup. Moreover, we have proposed several new enhancements on ourselves. Performance experiments show that our MCTS approach is comparable to an average engine.
|
|
|
An Environment for the game Atari-go
Starý, Tomáš ; Majerech, Vladan (referee) ; Hric, Jan (advisor)
These days Go game and its simpler variant game Atari Go means a major challenge for Computer Science and Artificial Intelligence (AI). The Go game represents yet unresolved question in the programming of Artificial Intelligence that would have been in the game stronger than man. This Bachelor Thesis aims to create a computer environment to play Atari Go on small boards in dimension to 9 x 9 intersections. The objective of this program is to introduce users to Atari Go game and teach them how to play this game. Another aim of this program is to motivate users to switch from Atari Go game to a more difficult variant Go game. The target group of users are those users who have not played this game, but they want to learn the joy of Atari Go. Program will serve equally well to users who have tried Atari Go game and would like to get practice in the game or find out more information about the Go game.
|
|
|
Framework for the automated and semi-automated testing of software components
Foltýnek, Tomáš ; Kalibera, Tomáš (referee) ; Majerech, Vladan (advisor)
This work is a research on Test-Driven Development (TDD), the existing literature about TDD and techniques used for implementing TDD with particular focus on the system NUnit (www.nunit.org). The primary goal was to design and implement system suitable for testing software modules, which would be backward compatible with NUnit 2.2. The designed system should implement support for testing modules that run in parallel environment, performance testing and detailed analysis of errors in modules. The work includes a console application that allows running selected tests in automated fashion. Test results as an output of this application are stored in the XML format suitable for further processing. The work also includes a GUI application that gives users interactive access to tests. This application offers a list of available tests, lets users to run selected individual tests or their groups and presents results of running tests in the graphical form. The work should include the user guide, technical specification of the designed system and the source code of all implemented modules in the language C#.
|
|
|
Applications of Patterns in Game Go
Hamplová, Romana ; Hric, Jan (advisor) ; Majerech, Vladan (referee)
This work implements a solver for tactical goals in the game of Go (for example capturing stones, connecting groups). The solver is based on recognizing the shapes of stones on the desk and choosing the moves from prede ned patterns and the follow-up moves. The main part of this work features analysis and proposal of convenient representation of patterns which follow typical situations in the game and their solving considering both the attacker and the defender. User interface of the program allows execution of the solver including selection of the type of the tactical goal, creating new patterns and editing the whole database of patterns. The work also contains a precreated pattern database.
|
|
|
Prostředí pro vytváření umělých hráčů Texas Hold'em pokru
Müller, Pavol ; Majerech, Vladan (advisor) ; Hric, Jan (referee)
Hold 'em poker, a card game with incomplete, sometimes even misleading information, is probably going to be mastered by computer programs within a few years. This might be a big issue for the on-line poker gaming industry. In some variations of the Texas hold 'em poker it is already happening. This thesis explores a possibility of creating an automated no-limit tournament player for the less explored and the hardest variation of Texas hold 'em poker from a computer player point of view. Tools and methodology which allows universal and simple automated data extraction from on-line casinos based on optical recognition are going to be created. Automated operations in these casinos and environment for poker intelligence implementation will be included as well. An artificial poker player capable of playing in two casinos will be implemented in this environment to demonstrate its strength and usability. Known poker strategies and ideas are going to be introduced from the point of view of poker robot implementation. At the end, the automated poker player will be confronted in real situations and questions regarding misuse of automated poker players in on-line casinos based on gained experiences and results are going to be answered.
|
|
|
Approaches to computer cognition of musical recordings
Kadlec, Jan ; Majerech, Vladan (advisor) ; Obdržálek, David (referee)
In our study we deal with various stages of human cognition of real-life musical signals, create their models and discuss their implementation. The rst part compares time-frequency representations and their factorization into sinusoids and background noise. We combine various approaches to coupling sinusoids into trajectories. Next we examine methods for the estimation of note parameters from trajectories and methods for musical instrument classi cation. The nal part focuses on global music-theoretical features of recordings such as tempo, melodic phrases, chord accompaniment or key.
|
|
|
Non-optimal solver of permutational puzzles using divide and conquer technique
Penkala, Michal ; Vomlelová, Marta (referee) ; Majerech, Vladan (advisor)
In the present work I study the attributes of permutation puzzles and try to find the algorithms usable for solving these puzzles. The task of this project is to implement the algorithm for non-optimal solution of permutation puzzles by decomposition to sub problems and invent a suitable form of puzzle definition. The result of this project is a program with graphic interface, which allows the user to create custom permutation puzzle. With this puzzle, the user will be able to do the predefined moves, make custom positions and search the result of the position.
|
guest ::
