|
|
The influence of caches on the efficiency of sorting
Hrdina, Karol ; Koubková, Alena (advisor) ; Yaghob, Jakub (referee)
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.
|
|
|
Dynamic hash tables
Vitovják, Radek ; Koubková, Alena (advisor) ; Koubek, Václav (referee)
The aim of the work is to describe various methods allowing the change of an internal hash table size in dependence on the number of inserted records and to compare them on the basis of known theoretical results. Then to make an experimental study of performance and mutual comparison of chosen methods on simulated data. To compare the results with theoretical findings and published precedent results, if any exist. The first part of the work describes implementation of hash tables and the analysis of expected number of key comparison for a successful and unsuccessful search. The next part contains experimental results of the performance of hash tables implemented on the basis of description stated in the previous part.
|
|
|
Experimental analysis of shortest paths algorithms
Truchlý, Peter ; Koubková, Alena (advisor) ; Mareš, Martin (referee)
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.
|
|
|
Fraktální komprese časových řad
Lysík, Martin ; Skopal, Tomáš (advisor) ; Koubková, Alena (referee)
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.
|
|
|
Deletion in coalesced hashing
Mrkva, Lukáš ; Koubková, Alena (advisor) ; Skopal, Tomáš (referee)
Nazev pracc: Opcra.ee DELETE ve srustajicim luisovani Autor: Lukas Mrkva Katedra (listav): Katedra softwaroveho inzenyrstvi Vedouci diplomovc prace: R.NDr. Alona Koubkova, CSc. E-rnail vedouciho: koubkova@ksi.ms.mff.cuni.cz Abstrakt: Diplomova pnioe jo vcnovana opcraci DELETE vo srustajicim hasovani. Nejprve jsou uvodeny principy hasovani a nektere jeho zakladni druhy. O srnstajicim hasovani pojednava ka])itola 3, kde jsou podrobnc ]>o- psany i ruznc melody koikstrukce h;usovaoi tal)ulky ro/dekuio die pofadi ko- liznich zaznamu a pfitonniosti sklepa. Dale jsou ])fcdstaveny tri rozdilne al- goritmy pro opora.ci DKLI^TK a dctailne diskutovtiny jojich implnincntacc pro jcdnutlivo inotody srustajiciho ha.sova.ni. Po tooroticke cayti naslcdiiji vy- slodky a koinontafo oxpcriincntu na siniulovanych datodi. Pracr jc zainefcna zejmena na porovnani casovu narooiiosti jednotlivych mazacich algoritnm a na porovnani ca.su potfcl)nych k vyhlcdavani za'/nanm prod a po smazani cast! tabulky. Pouzito algoritiny iiu])lciu(1iitovane v ja/yco C' a vyslodky ex- pcrimcntn jsou ]>rilozouy na CD. Klfcova slova: srustajici hasovani. delcto Title: Deletion in Coalesced Hashing Author: Lukas Mrkva Department: Dopartnicnt of Software Engineering Supervisor: RXDr. Aleua Koulikova,CSc. Supervisor's e-mail address:...
|
|
|
Representation of chains in hash tables
Urbánek, Vít ; Koubková, Alena (advisor) ; Koubek, Václav (referee)
The essential problem of hashing is a solving of collisions of elements. One of possible solutions of this problem is chaining of colliding elements. The chains are stored inside or outside the table and they are usually represented as unsorted linear lists. The aim of this thesis is to design some alternative structures (sorted linear lists, self-organizing linear lists, etc.) for representation of colliding elements, to implement them into known algorithms and experimentally evaluate their effect on efficiency of dictionary operations (Insert, Member, Delete).
|
|
|
Use of Markov decision processes for modelling of collective games
Zákutný, Roman ; Antoch, Jaromír (advisor) ; Koubková, Alena (referee)
In this thesis, a model based on the continuous-time Markov process is built and implemented and later applied on an one chosen collective game. An extensive analysis of available data is carried out to build a regression model to estimate parameters of the game model. An usableness of the game model is shown by a simulation process. Pros and cons are evaluated in a comparison analysis against the application of the discrete-time Markov chains, how it was described in my bachelor thesis [Roman Zákutný (2007)]. In conclusion are discussed possible extensions for other collective games.
|
|
| |
|
|
The influence of caches on the efficiency of sorting
Hrdina, Karol ; Koubková, Alena (advisor) ; Yaghob, Jakub (referee)
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 ; Koubková, Alena (advisor) ; Koubek, Václav (referee)
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.
|
guest ::
RSS feed.