|
|
Watson-Crick Models for Formal Language Processing
Hammer, Jan ; Tomko, Martin (referee) ; Křivka, Zbyněk (advisor)
Tato práce se zabývá Watson-Crickovými jazyky, které jsou inspirovány výpočty nad DNA, dále jejich modely a algoritmy pro rozhodování členství řetězců v těchto jazycích. Analyzuje nedávno představený algoritmus nazvaný WK-CYK a prezentuje algoritmus založený na prohledávání stavového prostoru, jehož základem je standardní prohledávání prostoru do šířky, ale používá množství optimalizací a heuristik, aby byl v praxi efektivnější a dokázal analyzovat delší vstupy. Klíčové jsou heuristiky pro prořezávání stavového prostoru (detekují slepé větve) a heuristiky pro výběr nejslibnějších větví pro další výpočet. Tyto dva algoritmy jsou testovány na 20 různých Watson-Crickových gramatikách (40 včetně jejich verzí v Chomského normální formě). Zatímco WK-CYK je schopen rozhodnout členství v jazyce v rozumném čase u vstupů o délce zhruba 30-50 symbolů, jeho efektivnost je velmi konzistentní u různých gramatik a různých vstupů, algoritmus prohledávající stavový prostor je obvykle (v 89-98 % případů) efektivnější a je schopen provést výpočet pro vstupy s délkou o stovkách často i tisících symbolů. Tedy tento algoritmus má potenciál být vhodným nástrojem pro praktické použití při rozhodování členství ve Watson-Crickových jazycích a nabízí vhodný základ pro další vývoj a vylepšení, která by dále zvyšovala efektivitu algoritmu.
|
|
|
Accelerated Neural Networks on GPU
Tomko, Martin ; Zachariášová, Marcela (referee) ; Krčma, Martin (advisor)
This thesis deals with the implementation of an application for artificial neural networks simulation and acceleration using a graphics processing unit. The computation and training of feedforward neural networks using the Backpropagation algorithm are the main focus of this thesis, but the application also supports other network types, and it makes it possible to extend the application with different training algorithms. Next, the application allows us to create neural networks with structural anomalies, and thus, to test the neural network's fault tolerance. The application is implemented in the C++ language, using OpenCL to manage GPU computation. The Backpropagation acceleration results were compared with the free open source library FANN.
|
|
|
Support for Educational Intermediate Language
Krejčí, Ondřej ; Tomko, Martin (referee) ; Křivka, Zbyněk (advisor)
This bachelor's thesis deals with the creation of software support for educational intermediate codes IPPcode, IFJcode and VYPcode which are used at FIT BUT in courses covering compilers. The aim of this thesis is the creation of an extension for an existing source code editor which adds syntax highlighting, interpreter and debugger for the mentioned intermediate codes. This thesis contains an evaluation of possible editors. Subsequently, it describes options for extending the selected editor Visual Studio Code and the implementation of the extensions.
|
|
|
Parser Systems
Kunda, Matej ; Tomko, Martin (referee) ; Meduna, Alexandr (advisor)
The goal of this thesis is to make a formal model of a new grammar system, which can combine different methods of syntax analysis. The inspiration for the making of the new grammar system were cooperating distributed grammar systems, from which an idea of communication symbols came from. With the help of communication symbols, components of the grammar system can cooperate on creating one sentential form. The thesis describes the formalization of the grammar system, its application in syntax analysis and finally its implementation. The result of this thesis is an application, which works on the principle of the formalized grammar system and combines two methods of syntax analysis.
|
|
| |
|
| |
|
|
Multi-Level Automata and Their Applications
Pšenák, Kamil ; Tomko, Martin (referee) ; Meduna, Alexandr (advisor)
In this thesis, we will add to already known fnite automata paradigm. We start with basic defnitions used in theoretical informatics. Afterwards we defne multi-level fnite automata, which is the base of this thesis. Then we move on to the compilation process and construction of a compiler. With that we defne lexical analysis as our example for multi-level fnite automata implementation. Once we implement the concept, we compare the new and the old way. Then we dig deeper into theoretical informatics to defne parallel right-linear grammars and languages. To prove a concept we create another concept with implementation strategy, using multi-level framework. Lastly, we mention some other areas in informatics, where this multi-level concept could be useful.
|
|
|
Formal Models and Their Applications in Music
Makiš, Jozef ; Tomko, Martin (referee) ; Meduna, Alexandr (advisor)
Main subject of this study are different kinds of formal models. We discuss which of them could be applied in music. Those that are applied are scattered context grammars and absolutely unlimited deep pushdown automata. They are applied in music structure as theme and variations. The main topic of a song is the theme, and variations diversify it. Resulting algorithm is based on compilation of a LL scattered context grammar. This algorithm shows how we can generate variations.
|
|
|
Regulated Grammar Systems
Tomko, Martin ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
Práce poskytuje přehled základů teorie formálních jazyků, regulovaných gramatik a analýzy LL(1) jazyků. Je zde navržen a analyzován algoritmus pro analýzu programovaných gramatik, inspirován LL(1) analyzátorem. Třída jazyků přijímaná tímto algoritmem je striktní nadtřídou LL(1) jazyků, obsahující některé jazyky, které nejsou bezkontextové. Tato třída se však jeví být neporovnatelná s třídou bezkontextových jazyků.
|
|
|
Formal Language Theory Applied in Musicology
Straková, Tereza ; Tomko, Martin (referee) ; Meduna, Alexandr (advisor)
The aim of this thesis is to apply formal models in music. Specifically, it concentrates on the generation of musical strings. In the thesis, a scattered context grammar for generating variations of a musical motif was designed. Next, an algorithm was designed for table driven parsing of the grammars. The algorithm uses a list of stored rules, which allows it to work with only the top of a stack. The algorithm was implemented as an application, which allows the generated motifs to be played or saved.
|
guest ::
RSS feed.