|
|
Recongition of symbols in digitalized mathematical expressions
Haas, František ; Valla, Tomáš (advisor) ; Mareš, Martin (referee)
This bachelor thesis focuses on finding suitable methods and algorithms for text segmentation and character recognition using artificial neural networks. Firstly, the thesis covers basic principles of artificial neuron and artificial neural networks, structure of convolutional neural networks and mainly backpropagation algorithm and stochastic Levenberg-Marquardt algorithm. Then the thesis describes image processing and image segmentation to single symbols using graph algorithms. This thesis also includes implementation of these methods and algorithms in an application which converts digital mathematical expressions to vector format.
|
|
|
Combinatorial Games Theory
Valla, Tomáš ; Nešetřil, Jaroslav (advisor) ; Sgall, Jiří (referee) ; Spirakis, Paul (referee)
Title: Combinatorial Games Theory Author: Tomáš Valla Department / Institute: IUUK MFF UK Supervisor: Prof. RNDr. Jaroslav Nešetřil, DrSc., IUUK MFF UK Abstract: In this thesis we study the complexity that appears when we consider the competitive version of a certain environment or process, using mainly the tools of al- gorithmic game theory, complexity theory, and others. For example, in the Internet environment, one cannot apply any classical graph algorithm on the graph of connected computers, because it usually requires existence of a central authority, that manipu- lates with the graph. We describe a local and distributed game, that in a competitive environment without a central authority simulates the computation of the weighted vertex cover, together with generalisation to hitting set and submodular weight func- tion. We prove that this game always has a Nash equilibrium and each equilibrium yields the same approximation of optimal cover, that is achieved by the best known ap- proximation algorithms. More precisely, the Price of Anarchy of our game is the same as the best known approximation ratio for this problem. All previous results in this field do not have the Price of Anarchy bounded by a constant. Moreover, we include the results in two more fields, related to the complexity of competitive...
|
|
|
Competitive filling of a plane region
Slabý, David ; Valtr, Pavel (advisor) ; Valla, Tomáš (referee)
Two players take alternating turns filling a rectangular board with unit squares without rotation, but may be otherwise arbitrary. Squares may not overlap and the game ends when there is no space for the next one. The result of the game is the number of turns. The constructor aims to maximize this quantity while the destructor wants to minimize it. We would like to get close to this value, provided that both players use their optimal strategy. We prove some new lower and upper bound for the game. This thesis extends results given by Tamás Hubai in his paper Competitive rectangle filling. Furthermore, we have a look at other board shapes and shapes to fill with.
|
|
|
Artificial intelligence in abstract 2-player games
Veselý, Pavel ; Valla, Tomáš (advisor) ; Baudiš, Petr (referee)
In this thesis we focus on algorithms for searching for the best move in a given position in an abstract strategy 2-player game. We describe algorithms Alpha-beta and Proof-number Search with their enhancements and we come with new ideas for making them quicker. We also propose an algorithm for choosing randomly between moves not much worse than the best move and ideas how to play in lost positions. We apply the algorithms on the game Tzaar which is special for having a lot of possible moves which makes the game hard for a computer. Our goal is to create a robot for playing Tzaar as good as possible. We show that our artificial intelligence can play on the level of best human and computer players. We also examine experimentally how enhancements of the algorithms help making computations quicker in this game.
|
|
|
Algorithms for solving strong positional games with high symmetry
Novotná, Jitka ; Valla, Tomáš (advisor) ; Kit, Michal (referee)
In this thesis, we analyse several algorithms for solving strong positional games, mostly based on PN-search. We focus on games with high symmetry of the game plan, where it is possible to substantially reduce the partial game tree by joining isomorph positions. We review several known enhancements of PN-search and also propose some of our own design. We measure the effect of the enhancements on the clique game. A part of the thesis is a software solver for clique game for K=4 and N=5...8. We were able to solve (6,4) and (7,4) clique games and prove that the second player has a draw strategy, which was expected but not shown previously.
|
|
|
Planning algorithms and plan simulation in logistics domain
Štefan, Zdeněk ; Toropila, Daniel (advisor) ; Valla, Tomáš (referee)
The goal of this thesis is to compare some means of planning in the logistics domain.The aim was to compare the capabilities of those techniques among each other and against plans designed by humans.Because some planners do not return parallel plans,it is necessary to parallelize them.It is shown that some algorithms achieve good results in comparison to plans designed by hu- mans. However, due to their high time and memory consumptions they cannot be nowadays commonly used to solve more difficult tasks.
|
|
|
PNS for the game Arimaa
Majerech, Ondřej ; Hric, Jan (advisor) ; Valla, Tomáš (referee)
The game of Arimaa is a strategic board game that has proved to be a challenge to computers. Not only because of its huge branching factor, but also thanks to the difficulty in creating a good evaluation function to be used with the Alpha-Beta algorithm. Proof-Number Search is an algorithm that does not depend on a heuristic evaluation function and it has been successfully applied to solving endgames of various other games. In this work, we adapt and implement the Proof-Number Search method for the game of Arimaa.
|
|
|
Visualisation of algorithms
Bašista, Peter ; Valla, Tomáš (referee) ; Mareš, Martin (advisor)
The goal of this work is to design a computer program for visualisation of algorithms and their execution in a classroom. The user writes the algorithm and attaches the prepared visualisation components to its data structures. The program will then record the progress of the computation and displays it as an interactive animation, alternatively it creates a PDF document with the key moments of the animation. In the presented work we introduce the Algorithm Animation Library. This library has been designed to be as flexible as possible, and at the same time as easy and friendly to use as possible. We present our approach towards animation of algorithms, briefly compare the developed library with the alternatives and conclude on when it is convenient to use the Algorithm Animation Library.
|
|
| |
|
|
Music effects
Marko, Matej ; Valla, Tomáš (referee) ; Bálek, Martin (advisor)
Title: Music effects Author: Matej Marko Department: Department of applied mathematics Supervisor: Mgr. Martin Bálek Supervisor's e-mail address: Martin.Balek@mff.cuni.cz Abstract: The effects have crucial position in the proccess of creating music. They enrich song's arrangement and make it all more colorful. Aim of the work is to create application that allows the user to play a sound file and apply chosen effets on it's content in real-time. All changes in effects' settings are imidiatelly transformed into the hearable results. Certain settings can be applied on the whole file and the results afterwards exported to the file. Part of the application is naturally implementation of chosen effects. Main topic of the work's text are methods used to implement the effects. Keywords: effects, music, sound
|
guest ::
