|
|
Automated Generating of Processing Elements for FPGA
Lengál, Ondřej ; Tobola, Jiří (referee) ; Žádník, Martin (advisor)
Some information processing applications, such as computer networks monitoring, need to continuously perform processing of rapidly incoming data. As the speed of the incoming data increases, it is desirable to perform the processing in the hardware. This work proposes a configuration system that generates a VHDL specification of a hardware data processing circuit based on a user-provided definition of data and computation operations. The system focuses on network traffic monitoring in multi-gigabit computer networks.
|
|
|
Web Application for Ebook Library Management
Kocman, Radim ; Rogalewicz, Adam (referee) ; Lengál, Ondřej (advisor)
The aim of this work is to create a web application for ebook library management which builds a web interface around Calibre. A particular focus was given to extensibility and accessibility for a large spectrum of users. The base of the system is the PHP programming language and the Nette Framework library. The text of this thesis describes the complete development process from the analysis of current situation, requirements analysis, system design and user interface design to implementation details and the analysis of testing on a sample of users.
|
|
|
Functional Verification of Processor Execution Units
Valach, Lukáš ; Lengál, Ondřej (referee) ; Masařík, Karel (advisor)
The thesis deals with integration of functional verification into the design cycle of execution units in a hardware-software co-design environment of the Codasip system. The aim of the thesis is to design and implement a verification environment in SystemVerilog in order to verify automatically generated hardware representation of the execution units. In the introduction, advantages and basic methods of functional verification and principles of the Codasip system are discussed. Next chapters describe the process of design and implementation of the verification environment of arithmetic-logic unit as well as the analysis of the results of verification. In the end, a review of accomplished goals and the suggestions for future development of the verification environment are made.
|
|
|
Efficient Algorithms for Finite Automata
Hruška, Martin ; Rogalewicz, Adam (referee) ; Lengál, Ondřej (advisor)
Nondeterministic finite automata are used in many areas of computer science, including, but not limited to, formal verification, the design of digital circuits or for the representation of a regular language. Their advantages over deterministic finite automata is that they may represent a language in even exponentially conciser way. However, this advantage may be lost if a naive approach to some operations is taken, in particular for checking language inclusion of a pair of automata, the naive implementation of which performs an explicit determinization of one of the automata. Recently, several new techniques for this operation that avoid explicit determinization (using the so-called antichains or bisimulation up to congruence) have been proposed. The main goal of the presented work is to efficiently implement these techniques as a new extension of the VATA library. The implementation has been evaluated and is superior to other implementations in over 90% of tested cases by the factor of 2 to 100.
|
|
|
An Efficient Finite Tree Automata Library
Lengál, Ondřej ; Konečný, Filip (referee) ; Vojnar, Tomáš (advisor)
Numerous computer systems use dynamic control and data structures of unbounded size. These data structures have often the character of trees or they can be encoded as trees with some additional pointers. This is exploited by some currently intensively studied techniques of formal verification that represent an infinite number of states using a finite tree automaton. However, currently there is no tree automata library implementation that would provide an efficient and flexible support for such methods. Thus the aim of this Mas- ter's Thesis is to provide such a library. The present paper first describes the theoretical background of finite tree automata and regular tree languages. Then it surveys the cur- rent implementations of tree automata libraries and studies various verification techniques, outlining requirements for the library. Representation of a finite tree automaton and algo- rithms that perform standard language operations on this representation are proposed in the next part, which is followed by description of library implementation. Through a series of experiments it is shown that the library can compete with other available tree automata libraries, in certain areas being even significantly superior to them.
|
|
|
Tool for Büchi Automata
Schindler, Petr ; Lengál, Ondřej (referee) ; Rogalewicz, Adam (advisor)
This thesis elaborates the Büchi automata theory and introduces a library that enables working with them. Basics of the automata theory is explained. The main part of this work is focused on Büchi automata, which belong to finite automata. The main properties of Büchi automata are explained and proved. The knowledge of those properties is important for understanding the algorithms mentioned in this work. The next part describes those algorithms and explains their principles in details. The design of library is described in the next part of this work. Main part is aimed at the implementation of the library and auxiliary scripts. The most interesting and important parts of methods are described in detail. Closing part describes testing of library functionality.
|
|
|
Simulator of Turing Machines Described by Means of Composite Diagrams
Siska, Josef ; Lengál, Ondřej (referee) ; Rogalewicz, Adam (advisor)
In this thesis, the theory related to Turing machines and means of their description (with focus on composite diagrams) is presented. The aim of this work is to create an application that allows editing Turing machines described by means of composite diagrams and simulating their computation on specified input configuration (including non-deterministic and multi-tape machines). Furthermore, within the application it will be possible to run the termination analysis of Turing machine in order to determine whether this machine or any of its parts always halt. The resulting application is implemented in Java and the termination analysis is performed using the well-founded orders. And so, one of the results created during this work is a software tool which allows designing and testing of Turing machines described by means of composite diagrams. Resulting application may be used especially during lectures on theoretical computer science, where it can be used to demonstrate computation of some Turing machine.
|
|
|
A Decision Procedure for the WSkS Logic
Fiedor, Tomáš ; Rogalewicz, Adam (referee) ; Lengál, Ondřej (advisor)
Různé typy logik se často používají jako prostředky pro formální specifikaci systémů. Slabá monadická logika druhého řádu s k následníky (WSkS) je jednou z nich a byť má poměrně velkou vyjadřovací sílu, stále je rozhodnutelná. Ačkoliv složitost testování splnitelnosti WSkS formule není ani ve třídě ELEMENTARY, tak existují přístupy založené na deterministických automatech, implementované např. v nástroji MONA, které efektně řeší omezenou třídu praktických příkladů, nicméně nefungují pro jiné. Tato práce rozšiřuje třídu prakticky řešitelných příkladů, a to tak, že využívá nedávno vyvinutých technik pro efektní manipulaci s nedeterministickými automaty (jako je například testování universality jazyka pomocí přístupu založeného na antichainech) a navrhuje novou rozhodovací proceduru pro WSkS využívající právě nedeterministické automaty. Procedura je implementována a ve srovnání s nástrojem MONA dosahuje v některých případech řádově lepších výsledků.
|
|
|
A Hidden GNU/Linux File System
Pavlásek, Martin ; Smrčka, Aleš (referee) ; Lengál, Ondřej (advisor)
Some sensitive data need such a way of hiding that hides not only the content of the data but its preserve itself. The goal of this Bachelor's thesis is to create a file system that enables hiding of files with sensitive data to other files. This text contains an overview of principles used in current file systems and a description of the structure and use of the FUSE technology. Further, the work describes the design of a filesystem that hides files into ID3 tags of MP3 music files and it's implementation in C++. The created filesystem is experimentally assessed and evaluated.
|
|
|
A Verified Data Structures Library
Rychnovský, Jan ; Holík, Lukáš (referee) ; Lengál, Ondřej (advisor)
This bachelor thesis deals with a methodology of writing verified programs using the VCC tool. The mentioned methodology is based in the principle of extending the program code with additional annotations, which provide a specification of the desired functionality. The VCC tool then uses formal methods to check whether the source code is correct with respect to the given specification. The first part describes formal verification and three basic approaches to it. Subsequently, the satisfiability problems of propositional formulae (SAT) and formulae in theories of predicate logic (SMT) are described. Then the thesis describes the VCC verification tool, its functionality, methodology, syntax and semantics of commands of its intermediate annotation language BoogiePL. The second part of this thesis is focused on the design and implementation of a verified data structures library, which contains singly linked, doubly linked, and circular lists, a binary search tree and a Treiber's stack. The text concludes with a discussion of the learnt knowledge about the programming methodology based on writing verified code.
|
guest ::
