|
|
Praktické datové struktury
Pokorný, Michael ; Mareš, Martin (advisor) ; Babka, Martin (referee)
In this thesis, we implement several data structures for ordered and unordered dictionaries and we benchmark their performance in main memory on synthetic and practical workloads. Our survey includes both well-known data structures (B-trees, red-black trees, splay trees and hashing) and more exotic approaches (k-splay trees and k-forests). Powered by TCPDF (www.tcpdf.org)
|
|
|
Properties of universal hashing
Babka, Martin
The aim of this work is to create a model of hashing with an acceptable worst case time complexity. The model is based on the idea of universal hashing and the expected time of every operation is constant. The used universal class of functions consists of linear transformations between vector spaces. This class has already been studied with a good asymptotic result. This work improves the result and proves that the expected amortised time of the scheme is constant.
|
|
|
Self-organizing linear lists
Kulman, Igor ; Koubková, Alena (advisor) ; Babka, Martin (referee)
Self-organizing linear lists are data structures for fast search, provided that certain elements stored in them are searched more frequently than others, while the probability of access to individual elements is generally not known in advance. Efficient search is achieved using different permutation rules that keep changing the list structure so that the more frequently searched elements are closer to the beginning. This thesis gives an overview of known algorithms for solving this problem (with the theoretical results about their complexity, if they are known), and experimental study of their behavior (using its own or freely available implementations and software for generating input data, testing algorithms and processing the results of experiments). Powered by TCPDF (www.tcpdf.org)
|
|
| |
|
|
Extensions to the class of matched formulae
Chromý, Miloš ; Kučera, Petr (advisor) ; Babka, Martin (referee)
We can associate an incidence graph with any CNF formula. It's a bipartite graph, in which he first part corresponds to variables and the second one to clauses. We can define matched formulas and biclique satisfiable formulas, based on this incidence graph. Both of these classes share an interesting property: Given a formula F which is matched or biclique satisfiable, F remains satisfiable even after we switch polarity of any occurrence of any literal. Class of formulas with this property is called var-satisfiable. In this thesis, we consider a parameterized algorithm introduced by Stefan Szeider for deciding satisfiability of formulas with small deficiency. Here deficiency of a formula is defined as a difference between the number of clauses and the number of variables in the formula. We explain why this algorithm cannot be simply generalized for the case of biclique satisfiable formulas. Since the problem of determining whether a formula is biclique satisfiable is NP-complete, we introduce a heuristic, which tries to find some biclique cover in time O(n2 e), where n denotes the number of variables and e denotes the length of the input formula. We performed experiments testing this heuristic on random formulas. The results of these experiments suggest, that there is a phase transition in the behaviour of the heuristic....
|
|
|
Application of system dynamics in project management
Baláž, Ján ; Křivánek, Mirko (advisor) ; Babka, Martin (referee)
The thesis deals with possibilities of an application of system dynamics methodics for an understanding and teaching the project management. A dynamic simulation model has been created for this purpose by using Vensim. A web simulator for the project management, which is based on the simulation model, has been created in the next part of the thesis. The benefit of the simulator over the model is its user- friendliness and its self-explanatory graphic interface, which makes it possible to use the simulation model for purposes of teaching and further reaserch in the field of project management. Powered by TCPDF (www.tcpdf.org)
|
|
|
A fingerpring database
Kubát, Jaroslav ; Babka, Martin (advisor) ; Lokoč, Jakub (referee)
The main goal of this thesis is to provide full description of an implementation of an application that is supposed to be a complex dactyloscopic database tool. The text is divided into parts according to the functional blocks of the application. The parts are namely processing of input fingerprint, the minutiae point analysis, the description of minutiae representation, the database and index structure described with its operations. Usually we describe multiple algorithms for a single task. In this case we provide their comparison. At the end of this thesis, there is a user manual describing the main usage scenarios. Powered by TCPDF (www.tcpdf.org)
|
|
|
Praktické datové struktury
Pokorný, Michael ; Mareš, Martin (advisor) ; Babka, Martin (referee)
In this thesis, we implement several data structures for ordered and unordered dictionaries and we benchmark their performance in main memory on synthetic and practical workloads. Our survey includes both well-known data structures (B-trees, red-black trees, splay trees and hashing) and more exotic approaches (k-splay trees and k-forests). Powered by TCPDF (www.tcpdf.org)
|
|
|
Properties of universal hashing
Babka, Martin
The aim of this work is to create a model of hashing with an acceptable worst case time complexity. The model is based on the idea of universal hashing and the expected time of every operation is constant. The used universal class of functions consists of linear transformations between vector spaces. This class has already been studied with a good asymptotic result. This work improves the result and proves that the expected amortised time of the scheme is constant.
|
|
|
DaktylDB
Kubát, Jaroslav ; Babka, Martin (advisor) ; Jančík, Pavel (referee)
This bachelor work focuses on implementation of application for fingerprints database maintenance. It consists of three parts. The first part is about detection of friction ridge endings and branches. For that purpose, there are three algorithms implemented and their results are discussed in the last chapter. Second part of the work is about preprocessing of extracted points for the purpose of database insert and search. There are algorithms of triangulation and clusterization used. The last part of this work is focused on database insert and search. Powered by TCPDF (www.tcpdf.org)
|
guest ::
RSS feed.