|
|
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.
|
|
|
Probabilistic Methods in Discrete Applied Mathematics
Fink, Jiří ; Loebl, Martin (advisor) ; Koubek, Václav (referee) ; Sereni, Jean-Sébastein (referee)
One of the basic streams of modern statistical physics is an effort to understand the frustration and chaos. The basic model to study these phenomena is the finite dimensional Edwards-Anderson Ising model. We present a generalization of this model. We study set systems which are closed under symmetric differences. We show that the important question whether a groundstate in Ising model is unique can be studied in these set systems. Kreweras' conjecture asserts that any perfect matching of the $n$-dimensional hypercube $Q_n$ can be extended to a Hamiltonian cycle. We prove this conjecture. The {\it matching graph} $\mg{G}$ of a graph $G$ has a vertex set of all perfect matchings of $G$, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle. We prove that the matching graph $\mg{Q_n}$ is bipartite and connected for $n \ge 4$. This proves Kreweras' conjecture that the graph $M_n$ is connected, where $M_n$ is obtained from $\mg{Q_n}$ by contracting all vertices of $\mg{Q_n}$ which correspond to isomorphic perfect matchings. A fault-free path in $Q_n$ with $f$ faulty vertices is said to be \emph{long} if it has length at least $2^n-2f-2$. Similarly, a fault-free cycle in $Q_n$ is long if it has length at least $2^n-2f$. If all faulty vertices are...
|
|
|
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).
|
|
|
Datové struktury pro různá rozdělení dat
Čunát, Vladimír ; Koubek, Václav (advisor) ; Mareš, Martin (referee)
In this thesis we study the predecessor problem, which consists of maintaining a dynamic ordered set of keys. After a survey of the most important published results, we provide a detailed description and analysis of a randomized variant of van Emde Boas tree structure. The variant achieves asymptotically optimal space usage, but the (log logN) time bounds are no longer worst-case but expected amortized. The best published expected amortized time bound that is achieved on the (s ; s1-d)-smooth class of distributions is equal to O(log log n). We combine the known techniques into a new structure that achieves the same time bound on a wider class of input distributions. Moreover, the new structure can utilize the optimal amortized structure proposed by Beame and Fich, which ensures that the amortized time complexity is also bound by the optimal p(log n/log log n).
|
|
| |
|
| |
|
|
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.
|
|
|
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.
|
|
| |
|
|
Fibonacci heaps - their variations and alternative data structures
Melka, Jakub ; Koubková, Alena (advisor) ; Koubek, Václav (referee)
In this paper we explore Fibonacci heaps and their variants. The alternative versions of the Fibonacci heap, the thin and thick heaps, were introduced by H. Kaplan and R. E. Tarjan in 2008. We compare these heaps from both experimental and theoretical point of view and we also include some classic types of heaps, namely regular and pairing heap. In our experiments we will be most interested in the total time required to run an algorithm that works with heap. The results show that thin and thick heaps are usually faster than the Fibonacci heap and slower than the regular heap. In conclusion, we summarize the knowledge gained from experiments.
|
guest ::
RSS feed.