|
| |
|
|
Adaptive Blind Separation of Instantaneous Linear Mixtures of Independent Sources
Šembera, Ondřej ; Tichavský, Petr ; Koldovský, Zbyněk
In many applications, there is a need to blindly separate independent sources from their linear instantaneous mixtures while the mixing matrix or source properties are slowly or abruptly changing in time. The easiest way to separate the data is to consider off-line estimation of the model parameters repeatedly in time shifting window. Another popular method is the stochastic natural gradient algorithm, which relies on non-Gaussianity of the separated signals and is adaptive by its nature. In this paper, we propose an adaptive version of two blind source separation algorithms which exploit non-stationarity of the original signals. The results indicate that the proposed algorithms slightly outperform the natural gradient in the trade-off between the algorithm’s ability to quickly adapt to changes in the mixing matrix and the variance of the estimate when the mixing is stationary.
|
|
|
Computational Bounded Rationality
Černý, Jakub ; Loebl, Martin (advisor) ; Hladík, Milan (referee)
This thesis formalizes a model of bounded rationality in extensive-form games called game-playing schemata. In this model, the strategies are repre- sented by a structure consisting of a deterministic finite automaton and two computational functions. The automaton represents a structured memory of the player, while the functions represent the ability of the player to identify efficient abstractions of the game. Together, the schema is a realization of a pure strategy which can be implemented by a player in order to play a given game. The thesis shows how to construct correctly playing schema for every pure strategy in any multi-player extensive-form game with perfect recall and how to evaluate its complexity. It proves that equilibria in schemata strategies always exist and computing them is PPAD-hard. Moreover, for a class of efficiently representable strategies, computing MAXPAY-EFCE can be done in polynomial time. 1
|
|
|
Library for Profiling of Data Structures of C/C++ Programs
Pavela, Jiří ; Rogalewicz, Adam (referee) ; Fiedor, Tomáš (advisor)
Performance bugs may greatly affect the quality of the system being developed and even cause irreversible damage in some critical sectors. Hence profiling - one of the currently most widespread technique of performance analysis - is usually applied to find the bugs. However, most of the current solutions commonly lack comprehensible graphical outputs and detailed analysis of algorithms in regard to their complexity. This thesis introduces a novel profiling tool which focuses on automatic estimation of complexity of dynamic data structures. The proposed approach collects statistical data out of program runs and uses regression analysis to find the most accurate model serving as an estimate of algorithmic complexity. The resulting prototype was subjected to a series of experiments that evaluate the accuracy of the results, demonstrate practical uses and illustrate the graphical output of the tool.
|
|
|
Algorithmic metatheorems for matroids
Toufar, Tomáš ; Pangrác, Ondřej (advisor) ; Dvořák, Zdeněk (referee)
In the thesis we define a new width parameter for matroids called amal- gam width that is based on the operation of matroid amalgamation. The parameter is related to branch width for matroids representable over fixed fi- nite field in the sense that class of representable matroids of bounded branch width has bounded amalgam width. The decomposition allows us to decide monadic second-order properties in linear time on matroids of bounded amal- gam width, even for matroids that are not representable (provided we are given the decomposition). We also prove that the coefficients of the Tutte polynomial can be computed in polynomial time for matroids of bounded amalgam width.
|
|
|
Algorithms and Programming Education with a focus on the programming language Python
Kotek, Lukáš ; Novák, Jaroslav (advisor) ; Černochová, Miroslava (referee)
The thesis researches the ability of use of Python programming language in the field of high school education and uses qualitative and quantitative methods of research and finds Python suitable. The thesis also brings theoretical analysis of the Python language, including practical exams in the form of sample programs. It researchs even other programming languages used in education and their suitability for this purpose and compares them with Python programming language. It also finds two most common used programming languages at high schools, which are Pascal / Object Pascal and Java.
|
|
|
Cache-oblivious Algorithms
Vaner, Michal ; Mareš, Martin (advisor) ; Falt, Zbyněk (referee)
In this work, we study the cache-oblivious computation model, which is inspired by the behaviour of the memory hierarchy of current computers. We study several graph algorithms and techniques of their design in this model. We consider graph searching, identifying connected components and computing maximal matching. We also study sorting and matrix multiplication as subproblems of many graph algorithms. In ad- dition to previously known algorithms, we present several new ones. We study their efficiency both by the means of asymptotic complexity and by benchmarking them on real hardware and we compare them with classical algorithms.
|
|
|
Python - a Programming Language for Algorithms and Programming Education
Kotek, Lukáš ; Novák, Jaroslav (advisor) ; Škop, Miroslav (referee)
Práce představuje programovací jazyk Python jako nástroj pro výuku algoritmizace a programování. Pomocí průzkumu zkoumá vhodnost Pythonu pro tento účel. I na jeho základě konstatuje, že ho pro něj je možné použít. Popisuje jeho historii, charakteristiky a specifika vůči jiným jazykům. Vypočítává nástroje, editory a vývojová prostředí, které je s ním možné použít ve výuce, a konstatuje, že jich existuje dostatek. Obsahuje ukázky a příklady, které demonstrují jeho možná použití.
|
|
| |
|
|
Historical development of numerical methods and computational techniques.
DIVÍŠKOVÁ, Michaela
In my bachelor thesis I deal with historical development of numerical methods and computational techniques. In the first chapter, the introduction of the concept of number and the writing process. In the second chapter, I present the basic numerical methods and algorithms for a variety of mathematical operations. In the third chapter, I will devote counting techniques and aids to facilitate calculations. The final chapter, I focus on computation of periodic rational and irrational numbers.
|
guest ::
