Theses

doc. RNDr. Dušan Knop, Ph.D.

Mgr. Michal Opler, Ph.D.

Department of Theoretical Computer Science

This thesis focuses on winner selection in committee election. We provide an overview of voting systems for single-winner and multi-winner election. Winner selection is often computationally hard, therefore we introduce election with structured preferences. In election with structured preferences, the votes are in some way restricted which may help to create more efficient winner selection algorithms. We describe some of the known structured preferences. We provide an overview of the current literature on the topic of structured and nearly structured preferences. We also review current work on committee election with structured preferences and usage of ordered weighted average (OWA) in committee election. We propose polynomial-time algorithms for finding a winning committee for approval election with OWA vector (0, ..., 0, 1) and interval preference restrictions. In such election, a voter approves a committee only if she approves all of its members. We use this property and show two approaches for finding a winning committee.

Thesis on DSpace

doc. Ing. Filip Křikava, Ph.D.

Vitaly Bragilevsky, MSc.

Department of Theoretical Computer Science

Haskell is one of the most well-known instances of a programming language that uses non-strict semantics. On the one hand, this brings the convenience of infinite data structures, user-defined control flow, and the possibility to avoid unnecessary computation. On the other hand, these benefits are hampered by the runtime overhead and hard-to-predict the behaviour of call-by-need. This begs the question: Is laziness worth it? To answer this question, we need to understand how laziness is used in the wild. To this end, we develop a tool for dynamic analysis used to trace the evaluation of function parameters. It is implemented as a compiler plugin for the Glasgow Haskell Compiler.

Thesis on DSpace

doc. RNDr. Dušan Knop, Ph.D.

Ing. Václav Blažej, Ph.D.

Department of Theoretical Computer Science

In the Roommate diversity problem, agents that belong to one of the two types have to be allocated to fixed size rooms based on their preferences, which depend solely on the fraction of agents of their own type among their potential roommates. In this work we study the stability of outcomes with respect to the room size and structured preferences. We provide a new randomized algorithm for finding core stable outcomes and show the results which we have obtained with the algorithm. We have found a small single-peaked instance with empty core and have verified, that every instance of the Roommate diversity problem with room size = 3, all preferences single peaked and number of agents <= 30, room size = 3 and number of agents <= 15, room size = 4, all preferences single peaked and number of agents = 30, admits an outcome that is core stable. We present arguments why we believe that every instance of this problem with room size = 3, room size = 4 and all preferences single peaked, admits an outcome that is core stable.

Thesis on DSpace

doc. RNDr. Pavel Surynek, Ph.D.

MSc. Juan Pablo Maldonado Lopez, Ph.D.

Department of Theoretical Computer Science

This thesis addresses the problem of evacuation from buildings and open areas from the perspective of cooperative path-finding algorithms. We define a problem called Multi-Agent Evacuation based on undirected graphs with agents (such as people, robots, or game characters) located in their vertices. Each vertex can either be marked as safe or as endangered. The task consists of moving the agents from endangered to safe vertices as quickly as possible. There are centralized algorithms for solving this problem that are optimal with respect to various objectives. Such algorithms are hardly applicable to real-world scenarios because real agents are unable to follow the centrally generated plan and must react to changes in the environment. Therefore, we designed and implemented an evacuation planning algorithm based on local cooperative path finding techniques. Simulations on various realistic situations show that solutions generated by this algorithm are of a quality similar to the solutions from centralized algorithms.

Thesis on DSpace

doc. Ing. Ivan Šimeček, Ph.D.

RNDr. Tomáš Valla, Ph.D.

Department of Theoretical Computer Science

Edit distance can be computed with the well-known dynamic programming algorithm in O(n^2) time, where n is the length of the input strings. The Four-Russians algorithm improves this complexity by a factor of (log(n))^2 by using a lookup table. In this thesis, the algorithm is thoroughly examined and important implementation details are discussed, with special consideration given to parallelizing the algorithm and reducing the size of the lookup table. An implementation in C++ is provided and its performance is compared with a popular edit distance library in several experiments. The results indicate that the algorithm is a viable option in practice, but not optimal

Thesis on DSpace

RNDr. Petr Štěpán, Ph.D.

doc. RNDr. Pavel Surynek, Ph.D.

Department of Theoretical Computer Science

Thesis focuses on using convolutional neural networks to detect known object in a video with emphasis on real-time data processing. It provides introduction to machine learning, neural networks and their implementation in Python programming language and overview of the state-of-the-art technologies used for object detection. Then the thesis deals with design of several architectures, creating and processing of two different datasets and evaluation of designed architectures.

Thesis on DSpace

RNDr. Tomáš Valla, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Department of Theoretical Computer Science

In this thesis, we study the m-eternal domination problem. Given graph G, guards are placed on vertices of G. Then vertices are subject to sequential attacks. After each attack, a guard must move into the attacked vertex. At most one guard is allowed to occupy any vertex. We denote the minimum number of guards, that can defend G indefinitely as g[?]m(G). We consider cactus graphs G, such that every edge in G is on a cycle of size 3k + 1 for some k [?] N. We show that for every such G on n vertices, g[?]m(G) = 1 + (n [?] 1)/3. We introduce the m-eternal guard configuration problem, being the same as the m-eternal domination problem, except it allows multiple guards on single vertex. We denote the minimum number of required guards in G as G[?]m(G). We present a linear algorithm for computing G[?]m(G) in cactus graphs, where every articulation is in two blocks. Moreover, we design a linear-time algorithm for computing g[?]m in clique trees. We include a C++ implementation of these algorithms, together with an exponential algorithm for both problems in general graphs.

Thesis on DSpace

Ing. Tomáš Čejka, Ph.D.

Ing. Viktor Černý

Department of Theoretical Computer Science

Network traffic monitoring is a necessary part of nowadays computer networks administration. Gathered information is not only used to provide basic network functionality and problem detection, but also for security analysis. Due to user privacy and reduction of data volume, approaches based on network flows are used. This work focuses on exporting flow records with application protocol extension. Contribution of this work is a new version of existing open source flow exporter from NEMEA project. This software module was optimized and successfully ported to embedded devices with OpenWrt system. It is possible to create network monitoring probe from low performance cheap home routers and enhance awareness of traffic on network including malicious traffic detection. Besides memory and performance optimizations, the module is extended of capability reading packets from network interface with the libpcap library. Flow cache, that is used to store flow records during the computation, was improved in order to handle application protocol information. The implemented version of the flow exporter contains two new example plugins for parsing HTTP and DNS protocols. In addition, the exporter is now able to export data in the IPFIX format.

Thesis on DSpace

Ing. Tomáš Čejka, Ph.D.

Department of Theoretical Computer Science

Assessment of security alerts is a quite difficult task which includes analysis of great amount of events and seeking additional information. One of the systems which handles security events is Network Entity Reputation Database (NERD) developed and led by association CESNET. Based on detected events NERD collects potentially harmful network entities and seeks further relevant information. This bachelor thesis follows up the extension of NERD by gaining additional information about the entities and realization of automatic classification of entities based on their behaviour. The main contribution of this thesis is the design and implementation of the module for classification of entities by the classification rules, which can be configured. The functional and tested solution has been deployed to the production version of NERD system used by security teams.

Thesis on DSpace

Mgr. Jan Starý, Ph.D.

Ing. Radek Richtr, Ph.D.

Department of Theoretical Computer Science

The purpose of this work is to produce a program which generates suitable molecules based on user's request. Starting with a database of molecules provided by the user, generations of new molecules are generated and evaluated by a virtual molecule screener, obtaining a measure of fitness with respect to the request. We choose a suitable data model of a molecule and design appropriate genetic operators of crossover and mutation. The result is a set of unix utilities performing the individual steps of a genetic algorithm. Based on the user's input, the program produces a large set of molecules satisfying the given constraints.

Thesis on DSpace

Ing. Jan Bělohoubek

Ing. Miroslav Skrbek, Ph.D.

Department of Theoretical Computer Science

This bachelor's thesis first describes current coverage of CERT C Secure Coding Standard guidelines relevant to software development for simple embedded systems. The practical part then focuses on implementation of some guidelines of the Standard -- which were not previously well covered by freely available tools -- in a new extensible tool based on Clang's LibTooling library. The efficacy of the tools is then demonstrated on real projects' source code by finding very likely sources of errors.

Thesis on DSpace