|
|
Pattern matching in compilers
Bílka, Ondřej ; Hubička, Jan (advisor) ; Mareš, Martin (referee)
Title: Pattern matching in compilers Author: Ondřej Bílka Department: Department of Applied Mathematics Supervisor: Jan Hubička, Department of Applied Mathematics Abstract: In this thesis we develop tools for effective and flexible pattern matching. We introduce a new pattern matching system called amethyst. Amethyst is not only a generator of parsers of programming languages, but can also serve as an alternative to tools for matching regular expressions. Our framework also produces dynamic parsers. Its intended use is in the context of IDE (accurate syntax highlighting and error detection on the fly). Amethyst offers pattern matching of general data structures. This makes it a useful tool for implement- ing compiler optimizations such as constant folding, instruction scheduling, and dataflow analysis in general. The parsers produced are essentially top-down parsers. Linear time complexity is obtained by introducing the novel notion of structured grammars and reg- ularized regular expressions. Amethyst uses techniques known from compiler optimizations to produce effective parsers. Keywords: Packrat parsing, dynamic parsing, structured grammars, functional programming 1
|
|
|
An annotating disassembler
Hluzín, Petr ; Mareš, Martin (advisor) ; Holub, Viliam (referee)
In this work disassembler for monolithic microproces or (micro-controllers) Microchip PIC was created. For typical programs this disasambler statically determines values of runtime address registers, thus complting the address from partial address in instruction. On its basis the disassembler recognizes procedures, creates procedure call-graph and recognizes control structures. Described disassembler separates usage of a register us do for variables of multiple procedures and sorts them to procedures inputs, locally modified variables and returned variables. Contemporary disassemblers for this architecture restrict themselves to printing instructions with incomplete addresses, because they do not perform any analysis. Powered by TCPDF (www.tcpdf.org)
|
|
|
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.
|
|
|
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).
|
|
|
Visualization algorithms for graphs
Kuča, Tomáš ; Valla, Tomáš (advisor) ; Mareš, Martin (referee)
In the present work we study the algorithms for graph drawing. We focus mainly on planar graphs, but we also show a few algorithms for non-planar graphs and the methods which convert a non-planar graph into a planar one. We extend the algorithm based on the areas of inner faces by a new force, taking into account the size of angles. We describe how to use the algorithm for nding maximum independent set on circle graphs in planarization. Finally, we present a plugin for editor VRR developed to test these algorithms.
|
|
|
Persistent data structures
Kupec, Martin ; Mareš, Martin (advisor) ; Straka, Milan (referee)
This thesis discusses persistent data structures, that is structures which preserve their own history. We focus on pointer-based structures, where it is possible to reach both full and partial persistence in constant amortized time and space per operation. Persistent arrays are also discussed, but the existence of optimal persistent arrays remains an open problem. We also include specific applications of the general techniques and also examples of use of persistent data structures.
|
|
|
Hledání shluků v grafech
Navrátil, Jan ; Lidický, Bernard (advisor) ; Mareš, Martin (referee)
The goal of this thesis is to create an application which will be able to identify clusters in graphs. The application contains modified algorithms from cluster analysis and graph algorithms used for identifying communities in complex networks. The purpose of this work is not speed optimalisation of implementation but the opportunity to try and compare results of each algorithm and verify whether special graph algorithms are truly better. The core of this task was to modify algorithms from classical cluster analysis (four were chosen, with a set of settings each) to work with graphs and implement and present them within one application along with community detection algorithms (two, in more versions each).
|
|
| |
|
|
Hybrid databases
Hušek, Radek ; Mareš, Martin (advisor) ; Lokoč, Jakub (referee)
This thesis presents design and implementation of a data structure, which tries to combine advantages of both databases and regular data structures. Main advantages of databases we try to retain are data persistence through storing data on a hard disk and working with data using transactions which allows us parallel access without danger of inconsistency. From data structures we borrow the implementation as a library of functions and the aim on simplicity and storing data in memory. Our implementation is built around the concept of (software) transactional memory; all data are stored on hard drive as log of operations. 1
|
|
|
Nowhere-dense classes of graphs
Tůma, Vojtěch ; Dvořák, Zdeněk (advisor) ; Mareš, Martin (referee)
In this thesis we study sparse classes of graphs and their properties usable for design of algorithms and data structures. Our specific focus is on the con- cepts of bounded expansion and tree-depth, developed in recent years mainly by J. Nešetřil and P. Ossona de Mendez. We first give a brief introduction to the theory as whole and survey tools and results from related areas of parametrised complexity and algorithmic model theory. The main part of the thesis, application of the theory, presents two new dynamic data structures. The first is for keeping a tree-depth decomposition of a graph, the second counts appearances of fixed subgraphs in a given graph. The time and space complexity of operations of both structures is guaranteed to be low when used for sparse graphs. 1
|
guest ::
RSS feed.