|
|
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.
|
|
|
XML Document Schema Inference
Olšarová, Nela ; Chmelař, Petr (referee) ; Křivka, Zbyněk (advisor)
XML has become a popular format for data exchange and manipulation. The internal structure of XML documents is described by the schema that plays an important role in the data management. The main idea is to develop a method for the schema inference from the given set of XML documents. By observing published automatic methods, we discovered their disadvantages. Since there is no interactive implementation, we improve these methods with the user interaction. As a solid formal background, the principle of grammatical inference is extended in our approach.
|
|
|
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.
|
|
|
Validation and Recognition of Hierarchical Plans
Ondrčková, Simona ; Barták, Roman (advisor) ; Gemrot, Jakub (referee)
Planning is a method where we try to fulfil a certain goal or goal task by finding a sequence of actions called plan. Hierarchical Task Networks is a method of planning that decomposes tasks to subtasks until we get primitive tasks (tasks that cannot be further decomposed or actions). Plan validation takes these actions and verifies whether the goal task actually decomposes to them. Plan recognition takes prefix of these actions, finds the missing ones and verifies whether the goal task can decompose into them. In this thesis I will be creating two programs: one program that solves the plan validation and one that solves the plan recognition problem using a parsing method known in grammars.
|
|
|
Music composition based on a programming language
Pavlín, Tomáš ; Maršík, Ladislav (advisor) ; Hajič, Jan (referee)
Computer music composition brings a lot of problems which can be solved using a variety of approaches. The existing music composition programs either do not provide enough flexibility to composers or they are considerably complicated for users which do not have technical background. In this thesis, we introduce an intuitive programming language designed for music composition along with an interpreter of this language represented by user-friendly graphical interface. The interface can be utilized for music composition and production even by users without technical and musical skills. The program provides a new approach for music composition and allows an effortless music creation that can be used e.g. in game industry. In addition, the program can be used for musical accompaniment. 1
|
|
|
XML Document Schema Inference
Olšarová, Nela ; Chmelař, Petr (referee) ; Křivka, Zbyněk (advisor)
XML has become a popular format for data exchange and manipulation. The internal structure of XML documents is described by the schema that plays an important role in the data management. The main idea is to develop a method for the schema inference from the given set of XML documents. By observing published automatic methods, we discovered their disadvantages. Since there is no interactive implementation, we improve these methods with the user interaction. As a solid formal background, the principle of grammatical inference is extended in our approach.
|
guest ::
