|
|
Applications of Gray codes in cache-oblivious algorithms
Mička, Ondřej ; Fink, Jiří (advisor) ; Gregor, Petr (referee)
Modern computers employ a sophisticated hierarchy of caches to decrease the latency of memory accesses. This led to the development of cache-oblivious algorithms that strive to achieve the best possible performance on such memory hierarchies with minimal knowledge of the exact parameters of the hierarchy. A common technique used in the design of cache-oblivious algorithms is a recursion-based divide-and-conquer method. In this work, we show an alternative technique based on the Gray codes. We use the binary reflected Gray code to traverse arrays in the cache-oblivious way, allowing us to design algorithms for problems such as matrix transposition, naive matrix multiplication or naive convolution that match the asymptotic performance of their recursion-based counterparts. The advantage is that our algorithms can be implemented without recursion (or a stack that simulates it) by using a loopless algorithm. We also introduce a variant of the binary reflected Gray code tuned to certain applications of our technique and an almost loopless algorithm to generate it. Apart from the theoretical analysis of our technique's performance, we also examine its practical performance on the problem of matrix transposition.
|
|
|
Anomaly Detection Using Generative Adversarial Networks
Měkota, Ondřej ; Fink, Jiří (advisor) ; Pilát, Martin (referee)
Generative adversarial networks (GANs) are able to capture distribution of its inputs. They are thus used to learn the distribution of normal data and then to detect anoma- lies, even if they are very rare; e.g. Schlegl et al. (2017) proposed an anomaly detection method called AnoGAN. However, a major disadvantage of GANs is instability during training. Therefore, Arjovsky et al. (2017) proposed a new version, called Wasserstein GAN (WGAN). The goal of this work is to propose a model, utilizing WGANs, to detect fraudulent credit card transactions. We develop a new method called AnoWGAN+e, partially based on AnoGAN, and compare it with One Class Support Vector Machines (OC-SVM) (Schöl- kopf et al. (2001)), k-Means ensemble (Porwal et al. (2018)) and other methods. Perfor- mance of studied methods is measured by area under precision-recall curve (AUPRC), and precision at different recall levels on credit card fraud dataset (Pozzolo (2015)). AnoW- GAN+e achieved the highest AUPRC and it is 12% better than the next best method OC-SVM. Furthermore, our model has 20% precision at 80% recall, compared to 8% precision of OC-SVM, and 89% precision at 10% recall as opposed to 79% of k-Means ensemble. 1
|
|
|
The complexity of constrained graph drawing
Hora, Martin ; Jelínek, Vít (advisor) ; Fink, Jiří (referee)
A labeled embedding of a planar graph G is a pair (G, g) consisting of a planar drawing G of G and a function g assigning labels (colors) to the faces of G. We study the problem of Embedding Restriction Satisfiability (ERS) that investi- gates whether a given graph has a labeled embedding satisfying a provided set of conditions. ERS is a relatively new problem, so not much is known about it. Nevertheless, it has great potential. It generalizes several problems looking for a particular drawing of a planar graph, such as the problem of Partially Embedded Planarity. Therefore, ERS may become a focal point in the area of graph draw- ing. In this thesis, we examine the computational complexity of ERS. We show that ERS is NP-complete. After that, we look at the complexity of some specific classes of its instances. We try to locate the boundary between the NP-complete and the polynomial variants of the problem. 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.
|
|
|
Optimization of a circulating multi-car elevator system
Pantůčková, Kristýna ; Fink, Jiří (advisor) ; Matzner, Filip (referee)
Circulating multi-car elevator is a system holding multiple cars in two shafts, where cars move upwards in one shaft and downwards in the other shaft. This system is similar to the paternoster, but cars have to stop on floors and open doors to load and unload passengers. Besides many technical challenges, this sys- tem brings algorithmic problems regarding efficient control of all cars. This thesis studies an off-line optimization problem, where the most efficient elevator system is searched for a fixed set of passengers. For this purpose, we created a computer program, implementing a genetic algorithm for searching for the most efficient elevator control and a discrete event simulation for evaluation of the efficiency of the control. The program provides a graphical user interface for input of parame- ters, generating passengers and displaying the results. 1
|
|
| |
|
|
Extension of Machinations Framework
Guth, Robert ; Gemrot, Jakub (advisor) ; Fink, Jiří (referee)
Framework Machinations is a tool for representing board games mechanics and mechanics of some computer games. Its main purpose is to allow game designers to test and tune the game's parameters before games release. However, current framework is not able to create models of some game mechanics and by that, it forces its users to simplify their models. The aim of this work is to extend framework machinations into a tool capable of simulating board game mechanics without having to simplify them. Thesis includes a program for working with an extended framework and a case study detailing the implementation of the Stone Age game in the extended framework.
|
|
|
Prediction of energy load profiles
Bartoš, Samuel ; Fink, Jiří (advisor) ; Van Leeuwen, Richard (referee)
Prediction of energy load profiles is an important topic in Smart Grid technologies. Accurate forecasts can lead to reduced costs and decreased dependency on commercial power suppliers by adapting to prices on energy market, efficient utilisation of solar and wind energy and sophisticated load scheduling. This thesis compares various statistical and machine learning models and their ability to forecast load profile for an entire day divided into 48 half-hour intervals. Additionally, we examine various preprocessing methods and their influence on the accuracy of the models. We also compare a variety of imputation methods that are designed to reconstruct missing observation commonly present in energy consumption data.
|
|
|
Construction of Gray codes with special properties
Novotný, Tomáš ; Dvořák, Tomáš (advisor) ; Fink, Jiří (referee)
A (cyclic) Gray code is a (cyclic) sequence of all n-bit strings in which consecutive strings differ in a single bit. Ruskey and Savage in 1993 asked whether every matching in a hypercube can be extended to a cyclic Gray code. An affirmative answer is known for perfect matchings (Fink, 2007) while the ge- neral case is still open. The main contribution of this thesis is a generalization of Fink's result to Gray codes with prescribed ends. The characterization of perfect matchings extendable in this way is verified for n = 5 with the assistance of a com- puter, which is useful as a basis for the inductive proof of the general statement. The other part of the thesis is focused on smallest maximal matchings in hyper- cubes which could possibly form especially hard instances of the Ruskey-Savage problem. We devise a novel method which provides - in particular for small di- mensions - maximal matchings of smaller size than the classical asymptotically optimal construction (Forcade, 1973). An adjusted program from the first part is then applied to test the Ruskey-Savage problem over these matchings, however, the extending Gray code is always discovered. 1
|
|
|
Evolutionary algorithms and active learning
Repický, Jakub ; Holeňa, Martin (advisor) ; Fink, Jiří (referee)
Názov práce: Evoluční algoritmy a aktivní učení Autor: Jakub Repický Katedra: Katedra teoretické informatiky a matematické logiky Vedúci diplomovej práce: doc. RNDr. Ing. Martin Holeňa, CSc., Ústav informa- tiky, Akademie věd České republiky Abstrakt: Vyhodnotenie ciel'ovej funkcie v úlohách spojitej optimalizácie často do- minuje výpočtovej náročnosti algoritmu. Platí to najmä v prípade black-box fun- kcií, t. j. funkcií, ktorých analytický popis nie je známy a ktoré sú vyhodnocované empiricky. Témou urýchl'ovania black-box optimalizácie s pomocou náhradných modelov ciel'ovej funkcie sa zaoberá vel'a autorov a autoriek. Ciel'om tejto dip- lomovej práce je vyhodnotit' niekol'ko metód, ktoré prepájajú náhradné modely založené na Gaussovských procesoch (GP) s Evolučnou stratégiou adaptácie ko- variančnej matice (CMA-ES). Gaussovské procesy umožňujú aktívne učenie, pri ktorom sú body pre vyhodnotenie vyberané s ciel'om zlepšit' presnost' modelu. Tradičné náhradné modely založené na GP zah'rňajú Metamodelom asistovanú evolučnú stratégiu (MA-ES) a Optimalizačnú procedúru pomocou Gaussovských procesov (GPOP). Pre účely tejto práce boli oba prístupy znovu implementované a po prvý krát vyhodnotené na frameworku Black-Box...
|
guest ::
