|
|
Fraktální komprese časových řad
Lysík, Martin ; Koubková, Alena (referee) ; Skopal, Tomáš (advisor)
The aim of this work was looking for single dimensional distributions of fractals in real world time series and use them to compress these time series. Usability of these principles for both lossless and lossy compression was examined. Base on the problem analysis was as first designed and implemented the basic compression algorithm. This was progressively extended with simple heuristics for better performance and also other techniques, which should have reduced its deficiencies. As the result were created two more extended compression algorithms and one algorithm with different data processing. Properties of these algorithms, output sizes and quality of decompressed data were compared on several input data and algorithms were also compared with existing compress algorithms and methods for storing time series data.
|
|
|
Expected height of binary search trees
Langhammer, Martin ; Koubková, Alena (advisor) ; Koubek, Václav (referee)
In this thesis we study the expected height and some other qualities of the binary serach trees. We make the inquiry about the expected height by skewed trees and by the two probably best-known and most widely used variations of the balanced trees, it means the AVL and the red-black trees. In addition to the value of the expected height of the trees we found out the scatter of the tree heights and some other statistics. In this thesis we attach to experimental solution of the problems. We also write down all the theoretical results that were known to us. We focus especially on comparing the measured values with the theoretically counted results. We try to acquire as exact assessment as possible in the case of unexisting theoretical results. Besides we compare the di erences between the various trees. We measured speeds of the tree's generation only marginally. We also inquire the dependence on di erent kinds of enter data within the experiments, such as the sorted data or generated data from various sorts of division. We use the standard statistic methods for the interpretation of the results, especially the method of linear regression.
|
|
|
Experimental analysis of shortest paths algorithms
Truchlý, Peter ; Mareš, Martin (referee) ; Koubková, Alena (advisor)
Shortest paths problem is one of the most encountered graph problems, which is commonly solved as subroutine in large variety of other, more complex tasks. If some algorithm or implementation fits the specific purpose, may, or may not, be completely obvious in practice. In some instances, theoretically correct solution behaves poorly in practice, lacking by more than order of magnitude after concurrent solution. Main goal of thesis, is to provide up to date overview of current algorithms, extended by experimentally obtained data and guidelines for their best usage. Majority of listed algorithms was tested on the same system, to provide wide and consistent comparison. Mainly, listed algorithms belongs to class SSSP, and are implementable to commodity hardware. Algorithms belonging to other classes, like OPSP or APSP are also mentioned. Special attention is dedicated to current growth of parallelism on hardware side, such as multi-core CPUs and massively parallel computing environments derived from GPU.
|
|
|
The influence of caches on the efficiency of sorting
Hrdina, Karol ; Yaghob, Jakub (referee) ; Koubková, Alena (advisor)
Classical algorithms for sorting in internal memory were designed with an assumption, that the memory is homogenous. But modern computers have hierarchically structured memory with various speeds of it's layers. Execution time of algortihm is dependant not only on operation count, but also on count of transfers between memory layers. Therefore internal algorithms are having some characteristics of external algorithms. In this paper we set our goal to summarize some existing approaches to this problem and summarize known optimalizations of internal sorting algorithms. Our main goal however is to impelent chosen algorithms and measure their performance experimentally.
|
|
| |
|
|
Relaxed rebalancing of binary search trees
Kříž, Martin ; Koubek, Václav (referee) ; Koubková, Alena (advisor)
In standard binary trees the rebalancing is carried out in connection with and immediately folowing the updates. Relaxed balancing allows to separate updates and rebalancing. First advantage of this approach is to keep the tree partially unbalanced and leave rebalancing to the different time when system is idle. Other great benefit of presented relaxed balancing algorithms in concurrent enviroment is necessity of keeping only small constant number of locks for modifying operations and thus allowing more modifying operations in the tree at the same time. The aim of this thesis is to empirically compare standard and relaxed variant of AVL tree in several different scenarios in concurrent enviroment according to number of data compares, number and type of rotations and according to the time requirements.
|
|
| |
|
|
Simulation of market store
Bartušek, Martin ; Koubková, Alena (referee) ; Černý, Jakub (advisor)
The goal of this work is an implementation of a supermarket simulator. You can build your own supermarket by placement of cases with goods, cashier counters etc. until you create the whole shop. Then we try to simulate shopping patterns of real customers. We focus on placement of best offers, discounts, … and the success of their placement. Naturally we want to maximize spendings of each customer. To confront with the reality I designed a real supermarket. Many data like average shopping time and average total costs corresponeded to the real ones. Further in my thesis I survey marketing techniques and tricks to influence shopping patterns of customers and I verify their effect in the simulation. At the end I shortly describe commercial simulation software.
|
|
|
Min - max heaps
Neuvirth, Jan ; Žemlička, Michal (referee) ; Koubková, Alena (advisor)
The object of the diploma thesis is detailed description of doublended priority queues. Heap data structure is commonly used as their base. Simultaneously we are trying to uncover behavior of these data structures while working with big data and measure its quality on the basis of obtained results in experimental tests. The aim of the thesis is not to indicate the best min{max heap, but to offer a reader a satisfactory amount of useful information, which enable him to choose an optimal structure in certain conditions.
|
|
|
Chromatic trees
Nezval, Kamil ; Koubek, Václav (referee) ; Koubková, Alena (advisor)
Red-black trees are the binary search trees that guarantee logarithmic complexity also in the worst case. In order to speed up the response time of the operations and to allow a high degree of concurrency in parallel environment, relaxed balancing was introduced. The main idea is to uncouple the rebalancing from the updating. The aim of the diploma thesis is experimental comparison of standard red-black trees and three relaxed balanced versions in non-parallel environment while working with large data.
|
guest ::
RSS feed.