
Heuristics for paths in maps
Kudláčková, Lada ; Mareš, Martin (advisor) ; Kratochvíl, Miroslav (referee)
The content of the thesis is a description of heuristic procedures, which are used to find the shortest paths in the graphs and verify their effec tiveness on the actual data. It deals with heuristics for Dijkstra's algorithm, especially the A* algorithm, which uses a lower distancetotarget estimate. Heuristics are implemented and tested on the road network of the Czech Re public. 1


Compact I/OEfficient Graph Representations
Tětek, Jakub ; Gavenčiak, Tomáš (advisor) ; Mareš, Martin (referee)
The objective of this thesis is to develop a fast memoryefficient representa tion of some graphs that occur in realworld applications. We consider separable graph classes (e.g. planar graphs or graphs of bounded genus) and show how to represent them in a way that (1) makes accessing vertices in a walk cacheefficient on average and (2) is highly memoryefficient. In particular, we show a compact representation of separable graph classes with the I/O cost of a random walk of length k being O(K/(Bw)1−c ) w.h.p. In the second part of the thesis, we consider layout of trees with optimal worstcase I/O cost for roottoleaf traversal, show an additive (+1)approximation of I/O optimal compact layout and contrast this with a proof of NPhardness of exact solution. In this thesis, we also prove generalisations of the recursive separator theo rem. The first one generalises the theorem for weighted graphs and the second one replaces minimum region size by average region size in the bound. 1


Passive emitter tracking
Hrach, Jan ; Klusáček, David (advisor) ; Mareš, Martin (referee)
We have implemented a TDOA multilateration of transmitters on an unmodified rtlsdr receiver using transmitters with known location as a timing reference. We present a brief theoretical background and describe the measurement process which includes several approaches that correct the timing and frequency errors between the receivers. Additionally, we have implemented an angle of arrival direction finder using coherent rtlsdr.


Modern applications of zeroknowledge protocols
Krňák, Tomáš ; Hubáček, Pavel (advisor) ; Mareš, Martin (referee)
zkSNARK is a cryptographic protocol, which enables transformation of an arbitrary computation into short effectively verifiable argument of correctness of this computation. Further more, it enables a prover to decide exactly, which inputs of the computation will be public and which inputs will stay private. The goal of this work is to present features, construction and applications of modern zkSNARKs. In a construction part of this work we describe construction based on linear PCP and Paillier cryptosystem. In an application part we explain principles of anonymous cryptocurrency Zcash and we describe a completely new application of zkSNARKs in networks of trust. 1


A Minimalistic Directory Service
Hrubý, Ondřej ; Mareš, Martin (advisor) ; Kratochvíl, Miroslav (referee)
We present a light, simple and secure network protocol for accessing di rectory services called Featherweight Directory Access Protocol (FDAP). It is inspired by Lightweight Directory Access Protocol (LDAP), but the con cept of a directory service is built from scratch. This decision is supported by analysis of shortcomings of LDAP which has seen widespread use in the past. We provide specifications both of an FDAP service and the protocol, exam ples of welltested server implementation, client library and an application as a proof of concept.


Compact description of directory trees
Končický, Václav ; Mareš, Martin (advisor) ; Majerech, Vladan (referee)
There exist many copies of data stored as directory trees whose consistency we need to verify. In this work we create a new binary format describing directory trees. It allows to record names, hashed contents, and other metadata of the files. In order to verify data consistency, we can compare two such descriptions. This format is designed with focus on its compactness and high read speed. We present a program which builds such description for a given tree and compares two descriptions. In order to maximize speed we use parallelization techniques and tree hashing, taking properties of hard disk drives into account. 1


Mobile application for canteens
Mareš, Martin ; Kofroň, Jan (advisor) ; Matěna, Vladimír (referee)
This thesis focuses on the design and development of a mobile application for Android platform. This application can be used for browsing and ordering meals at public canteens. Unlike other similar projects, this application is extensible by plugins. This approach gives the user the ability to browse meals from different canteens in the environment of one application. This application also supports multiple user profiles and works in offline mode. This thesis also includes a few plugins as an example and plugin development documentation for the easy extension of new plugins. 1


An implicit representation of sets
Lieskovský, Matej ; Mareš, Martin (advisor) ; Majerech, Vladan (referee)
The 2003 paper by Gianni Franceschini and Roberto Grossi titled "Optimal WorstCase Operations for Implicit CacheOblivious Search Trees" suggests a data structure that supports Insert, Find and Delete operations in O(log n) worstcase time while also being implicit and cacheoblivious. We explain the general idea of the original data structure, identify flaws and gaps in its description, and describe a reimagined version of one of the two major components of the data structure. 1


Generator of nanotubes
Macková, Kateřina ; Mareš, Martin (advisor) ; Král, Karel (referee)
The clay mineral called halloysite with crystalline structure is widely used in the world of physics due to its effective properties. The main goal of this thesis is to create a program that creates various tubular nanostructures of this material according to input crystal cell and other parameters. After the creation, whole halloysite structure can be used for other physical research.


Expander codes
Calábková, Markéta ; Mareš, Martin (advisor) ; Hušek, Radek (referee)
Wherever information is transmitted we can find errorcorrecting codes. LDPC (low density parity check) codes are one of frequently used classes of codes and expander codes are promising members of this class. In this work, we explain what expander code are. We also show that expander codes simulta neously have both asymptotically optimal parameters and lineartime encoding and decoding. Unfortunately, our constructions grant us codes, which are too big for regular use, for example for packet transmission. However, we believe that with better construction of expander graphs we will be able to construct short codes with significant practical applications. 1
