|
|
Sorting algorithms
Schwarz, Jakub ; Smrž, Jaroslav (referee) ; Dvořák, Jiří (advisor)
Enormous volume of data, which has been processed during production operations, requires easy orientation and quick searching. Exact search in real time is essential for success. Correct and quick data-sorting is one of the most important activity during dataprocessing. The goal of this bachelor’s thesis is background research of sorting algorithms. To achieve the goal, basic concepts of sorting theory will be described (determined) and there will be division of sorting algorithms by different criterions. For each algorithm of internal array sorting, sorting principles will be described and analysis of efficiency will be provided. The results will be verified by experimental program.
|
|
|
Automatic Node-Placement in an Oriented Acyclic Graph in a GUI Application
Juda, Jan ; Křivka, Zbyněk (referee) ; Kolář, Dušan (advisor)
The goal of this work is to create an application for automatic node placement of acyclic oriented graphs. The work is mainly focusing on advanced possibilities of graph layout, for example selection of location of selected nodes, division of a graph into sub-graphs or support of polygonal nodes. The solution describes chosen algorithms, which are being used in the resulting application. Specifically, Fruchterman-Reingold force oriented algorithm, algorithm Kamada-Kawai and an algorithm based on Meyer's self-organizing graphs.
|
|
|
DNA Sequence Compression
Friedrich, Tomáš ; Burgetová, Ivana (referee) ; Martínek, Tomáš (advisor)
The increasing volume of biological data requires finding new ways to save these data in genetic banks. The target of this work is design and implementation of a novel algorithm for compression of DNA sequences. The algorithm is based on aligning DNA sequences agains a reference sequence and storing only diferencies between sequence and reference model. The work contains basic prerequisities from molecular biology which are needed for understanding of algorithm details. Next aligment algorithms and common compress schemes suitable for storing of diferencies agains reference sequence are described. The work continues with a description of implementation, which is follewed by derivation of time and space complexity and comparison with common compression algorithms. Further continuation of this thesis is discussed in conclusion.
|
|
|
Algorithm for word morphisms fixed points
Matocha, Vojtěch ; Holub, Štěpán (advisor) ; Žemlička, Jan (referee)
In the present work we study the first polynomial algorithm, which tests if the given word is a fixed point of a nontrivial morphism. This work contains an improved worst-case complexity estimate O(m · n) where n denotes the word length and m denotes the size of the alphabet. In the second part of this work we study the union-find problem, which is the crucial part of the described algorithm, and the Ackermann function, which is closely linked to the union-find complexity. We summarize several common methods and their time complexity proofs. We also present a solution for a special case of the union-find problem which appears in the studied algorithm. The rest of the work focuses on a Java implementation, whose time tests correspond to improved upper bound, and a visualization useful for particular entries.
|
|
|
External Economic Analysisi of an Enterprise
Baroch, Václav ; Kyjonka, Vladimír (advisor) ; Král, Jaroslav (referee)
Automatizované zpracování ekonomické analýzy podniku přináší jistá omezení. Klasická von Neumannova architektura doznala v poslední době určitých vylepšení, a je tak možné simulovat procesy, jejichž algoritmické zpracování bylo ještě před pár lety z praktického hlediska nemyslitelné, především kvůli nedostatečné početní a paměťové výkonnosti užívané IT technologie. Přes všechna zrychlení a razantní vylepšení IT technologií v posledních letech však softwarové zpracování simulace podnikových procesů naráží na dvě podstatná omezení, jež jsou popsána v práci. Je to nemožnost vytvářet izomorfní model reality a nutnost řešit simulaci interních a externích procesů v diskrétním čase.
|
|
|
Kombinatorika matematických struktur
Paták, Pavel
The combinatorics of a first order mathematical structure is the class of all formulas valid in all in it definable structures. This notion was first introduced by Krajíček in [6]. In the present work we try to characterize and compare the combinatorics of several different prominent structures (reals, complex number, dense linear order, . . . ). We also study the question of algorithmical complexity, i.e. the question how hard it is to check whether a given formula lies in the combinatorics of a given structure. We prove that this question is corecursively enumeratively complete and therefore algorithmicaly undecidable in the case of models of complete theories without strict order property (SOP) and in the case of pseudofinite structures.
|
|
|
Automatic Node-Placement in an Oriented Acyclic Graph in a GUI Application
Juda, Jan ; Křivka, Zbyněk (referee) ; Kolář, Dušan (advisor)
The goal of this work is to create an application for automatic node placement of acyclic oriented graphs. The work is mainly focusing on advanced possibilities of graph layout, for example selection of location of selected nodes, division of a graph into sub-graphs or support of polygonal nodes. The solution describes chosen algorithms, which are being used in the resulting application. Specifically, Fruchterman-Reingold force oriented algorithm, algorithm Kamada-Kawai and an algorithm based on Meyer's self-organizing graphs.
|
|
|
Comparison of Top trees implementations
Setnička, Jiří ; Majerech, Vladan (advisor) ; Mareš, Martin (referee)
Comparison of Top trees implementations - Abstract Jiří Setnička Definition and description of Top trees and introduction of problems solvable by them including problem of edge 2-connectivity. Definition and description of Topology trees used as one of the drivers for Top trees. After the initial descriptions the two top trees implementations are introduced: one based on self adjusting trees, second based on topology trees. Comparison of these implementations is done by two experiments. Measurements are discussed in conclusion - results corresponds with initial estimates but with different multiplicative constant than expected. 1
|
|
|
Algoritmické problémy související s průnikovými grafy
Ivánek, Jindřich ; Pergel, Martin (advisor) ; Rytíř, Pavel (referee)
In this thesis we study two clique-cover problems which have interesting applications regarding the k -bend intersection graph representation: the edge-clique-cover-degree problem and the edge-clique-layered-cover problem. We focus on the complexity of these problems and polynomial time algorithms on restricted classes of graphs. The main results of the thesis are NP-completness of the edge-clique-layered-cover problem and a polynomial-time 2-approximation algorithm on the subclass of diamond-free graphs for the same problem as well as some upper bounds on particular graph classes.
|
|
|
Kombinatorika matematických struktur
Paták, Pavel
The combinatorics of a first order mathematical structure is the class of all formulas valid in all in it definable structures. This notion was first introduced by Krajíček in [6]. In the present work we try to characterize and compare the combinatorics of several different prominent structures (reals, complex number, dense linear order, . . . ). We also study the question of algorithmical complexity, i.e. the question how hard it is to check whether a given formula lies in the combinatorics of a given structure. We prove that this question is corecursively enumeratively complete and therefore algorithmicaly undecidable in the case of models of complete theories without strict order property (SOP) and in the case of pseudofinite structures.
|
guest ::
