|
|
Web applications testing
Borovcová, Anna ; Majerech, Vladan (advisor) ; Parízek, Pavel (referee)
This diploma thesis matter is explanation of web application testing problems mainly to potential testers. That is why the thesis confides information gathered from different sources in intelligible way and it results from three years of testing and one year of teaching new testers mainly in Unicorn Corporation. The first part is dedicated to introduction to web testing; basic principles and history of internet, development process and methodologies are mentioned there. The second part deals with core aspects of testing and how they are viewed by various experienced testers from Czech Republic or foreign countries. In the third part there are chosen and introduced some techniques and tools suitable for web application. The fourth part contains practical example of some testing documents.
|
|
|
Persistent weak-AVL trees
Škrobánek, Jiří ; Mareš, Martin (advisor) ; Majerech, Vladan (referee)
This thesis investigates persistence (i.e., preservation of data by updates) of binary search trees. In particular, we explore how weak-AVL trees may be converted into efficient fully-persistent data structures. After mentioning all important properties of weak-AVL trees, we present a new method to store them with worst-case constant number of changes per update. Then we show some general schemes for conversion of binary search trees (and possibly other pointer-based data structures) into their persistent variants. Finally the established theory is used to obtain fully-persistent weak-AVL trees.
|
|
|
Minimum 0-Extensions of Graph Metrics
Dvořák, Martin ; Bulín, Jakub (advisor) ; Majerech, Vladan (referee)
We consider the Minimum 0-Extension Problem for a given fixed undirected graph with positive weights. We study the computational com- plexity of the threshold decision variant with respect to properties of the fixed graph, in particular modularity and orientability, as defined by Karzanov in [Eur. J. Comb., 19/1 (1998)]. We approach the problem from the viewpoint of the Finite-Valued CSP, which allows us to employ the rich theory that was developed to prove the Dichotomy Conjecture. On the negative side, we provide an explicit reduction from the Max-Cut Problem to obtain NP-hardness for non-modular graphs. For non-orientable graphs, we express a cost function that satisfies a certain condition which guarantees the existence of an implicit reduction from the Max-Cut Problem. On the positive side, we construct symmetric fractional polymorphisms in order to show that the so-called Basic LP Relaxation can solve two special cases of weighted modular orientable graphs: paths and rectangles. 1
|
|
|
Machine Learning for Driving of Virtual Vehicles
Kučera, Jiří ; Gemrot, Jakub (advisor) ; Majerech, Vladan (referee)
Cars in virtual worlds are typically controlled by handcrafted rules. Creating such rules is often time-consuming and has to be repeated every time environment is altered. The goal of this thesis is to explore suitable machine learning techniques and create a good looking simulation of cars driving on an urban road network. The resulting model is a feedforward network directly controlling throttle, steering, and brake. The network is capable of following the assigned road and avoid collisions with other agents on crossroads without traffic lights. The model was trained using the Proximal policy optimization algorithm enhanced by GAIL, curiosity, behavioral cloning, and curriculum learning. In this paper, we have also shown that the resulting behavior, while not completely perfect, is good enough for use in a simulation. 1
|
|
|
An implicit representation of sets
Lieskovský, Matej ; Mareš, Martin (advisor) ; Majerech, Vladan (referee)
In our bachelor thesis, we described an implicit data structure that, given a way to maintain an implicit representation of polylogarithmic buckets, could implement all the dynamic ordered dictionary operations in logarithmic time. We now fulfill our obligation and provide a corresponding construction of implicit buckets. 1
|
|
|
General Game Playing and Deepstack
Schlindenbuch, Hynek ; Gemrot, Jakub (advisor) ; Majerech, Vladan (referee)
General game playing is an area of artificial intelligence which focuses on creating agents capable of playing many games from some class. The agents receive the rules just before the match and therefore cannot be specialized for each game. Deepstack is the first artificial intelligence to beat professional human players in heads-up no-limit Texas hold'em poker. While it is specialized for poker, at its core is a general algorithm for playing two-player zero-sum games with imperfect information - continual resolving. In this thesis we introduce a general version of continual resolving and compare its performance against Online Outcome Sampling Monte Carlo Counterfactual Regret Minimization in several games.
|
|
|
Graph data analysis using deep learning methods
Vancák, Vladislav ; Svoboda, Martin (advisor) ; Majerech, Vladan (referee)
The goal of this thesis is to investigate the existing graph embedding methods. We aim to represent the nodes of undirected weighted graphs as low-dimensional vectors, also called embeddings, in order to create a rep- resentation suitable for various analytical tasks such as link prediction and clustering. We first introduce several contemporary approaches allowing to create such network embeddings. We then propose a set of modifications and improvements and assess the performance of the enhanced models. Finally, we present a set of evaluation metrics and use them to experimentally evalu- ate and compare the presented techniques on a series of tasks such as graph visualisation and graph reconstruction. 1
|
|
|
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
|
guest ::
