|
|
Routing information exchange
Čepelík, David ; Mareš, Martin (advisor) ; Gavenčiak, Tomáš (referee)
We present an efficient method for serialization of complex objects into a compact binary form based on the Concise Binary Object Representation (CBOR). We provide a high-performance, well-tested imple- mentation of a data serialization library and implement it in the BIRD Internet Routing Daemon. 1
|
|
|
Data structure behavior with variable cache size
Král, Karel ; Koucký, Michal (advisor) ; Mareš, Martin (referee)
Cache-oblivious algorithms are well understood when the cache size remains constant. Recently variable cache sizes have been considered. We are motivated by programs running in pseudo-parallel and competing for a single cache. This thesis studies the underlying cache model and gives a generalization of two models considered in the literature. We give a new cache model called the "depth model" where pages are accessed by page depths in an LRU cache instead of their ad- dresses. This model allows us to construct cache-oblivious algorithms that cause a certain number of cache misses prescribed by an arbitrary function computable without causing a cache miss. Finally we prove that two algorithms satisfying the regularity property running in pseudo-parallel cause asymptotically the same number of cache misses as their serial computations provided that the cache is satisfying the tall-cache assumption.
|
|
|
Drawing polytopes in various dimensions
Ondráček, Lukáš ; Šámal, Robert (advisor) ; Mareš, Martin (referee)
The thesis describes implementation of an application for drawing three- and multidimensional polytopes allowing their fluent rotation. The application Geometric Figures for Linux and Windows is written in the C language using the OpenGL library and it supports plug-ins written in the Python language. Iterated perspective projection and edges coloring according to their location is used. In addition, the application is able to generate the convex hull of a set of points, cut figures with hyperplanes, stellate figures, create geometrically dual polytopes and cut off parts of figures; all functions are independent to the number of dimensions of the polytopes. The application profits from its easy extensibility using modules and its code being open-source. Powered by TCPDF (www.tcpdf.org)
|
|
|
Multicast routing
Hlavatý, Ondřej ; Mareš, Martin (advisor) ; Knop, Dušan (referee)
We implement multicast routing in the BIRD routing daemon. At first, we review basic principles of IP multicast and different modes of the PIM multicast routing protocol. Then we outline the architecture of the BIRD and discuss its aspects related to our goal. We present our solution based on adding IGMP, bidi- rectional PIM, and kernel interface as three separate BIRD protocols. Finally, we describe our framework for testing network software in complex virtual networks.
|
|
|
Succinct encodings of trees
Juraszek, Adam ; Mareš, Martin (advisor) ; Majerech, Vladan (referee)
We focus on space-efficient, namely succinct, representations of static ordinal unlabeled trees. These structures have space complexity which is optimal up to a lower-order term, yet they support a reasonable set of operations in constant time. This topic has been studied in the last 27 years by numerous authors who came with several distinct solutions to this problem. It is not only of an academic interest, the succinct tree data structures has been used in several data-intensive applications, such as XML processing and representation of suffix trees. In this thesis, we describe the current state of knowledge in this area, compare the many different approaches, and propose several either new or alternative algorithms for operations in the representations alongside. Powered by TCPDF (www.tcpdf.org)
|
|
|
Placement of map symbols
Burešová, Karolína ; Mareš, Martin (advisor) ; Pangrác, Ondřej (referee)
Placing map symbols in a way so that the resulting map looks well is a major problem in cartography. In this thesis, we deal with automatization of this process using an evolutionary algorithm. Input of this algorithm is a set of requests for symbols (signposts, ruins, street names etc) to be placed on the map, its output is a description of their placement. Unlike other studies, we deal with labels for all kind of features (not only point-features) as well as with placing the features themselves. We managed to design an evolutionary algorithm which produces acceptable maps and offers some possibilities to further enhance the quality of produced maps.
|
|
|
A backup system
Setnička, Jiří ; Mareš, Martin (advisor) ; Veselý, Pavel (referee)
An overview of existing approaches to data backup and their strengths with regard to use. After considering the previous describe the resulting backup system FenixBackup as file-oriented differential backup system capable holding more historical versions. In conclusion, outlines the possible directions which the development of the system could follow. Powered by TCPDF (www.tcpdf.org)
|
|
|
IEEE 802.11 wireless networking for HelenOS
Kolárik, Jan ; Děcký, Martin (advisor) ; Mareš, Martin (referee)
IEEE 802.11 (a.k.a. WiFi) is a popular wireless LAN specification. This thesis documents implementation of this standard within the experimental operating system HelenOS which differs from conventional operating systems with its microkernel-based design. First, the basic concepts of WiFi technology are described. Description of external tools used during development is following. Together with that, the chosen method of integrating the wireless framework into existing system is depicted. In the next chapter we analyse the implementation details of the work. There is thoroughly explained the structure of the driver for selected WiFi device and also the functionality of resulting IEEE 802.11 library. In the end of the thesis there is an evaluation of the features of final work and comparison of enclosed implementation with existing solutions.
|
|
|
Frequency Spectrum Monitoring System
Hrach, Jan ; Klusáček, David (advisor) ; Mareš, Martin (referee)
We have created several programs to be used in the field of Software Defined Radio technology: (i) A channelizer, a tool that splits wideband signal into multiple narrowband channels that can be further processed, (ii) A SDR client, an interactive GUI tool that allows exploration of signals, (iii) A scanner. Our channelizer is several times faster than a popular GnuRadio implementation and our SDR software features a network-transparent architecture with one server and multiple concurrent clients. Powered by TCPDF (www.tcpdf.org)
|
|
|
Packing rectangles
Pavlík, Tomáš ; Šámal, Robert (advisor) ; Mareš, Martin (referee)
This thesis studies the open problem of packing rectangles. Is it possible to pack rectangles with dimensions 1/n x 1/(n+1) into a unit square? The aim of this thesis is analysis of the problem and the related algorithm. Attention will be focused mainly on the implementation of this algorithm and on study of its functioning. Powered by TCPDF (www.tcpdf.org)
|
guest ::
RSS feed.