Pro snažší hledání prací podle autora, názvu nebo sekce použijte seznam prací. V případě špatné čitelnosti rovnic v abstraktu na webu, prosím použijte následující dokument ve formátu pdf - svocabst.pdf.

Obecná syntaktická analýza pro bezkontextové gramatiky a EOL gramatiky
Radek Bidlo
Fakulta informačních technologií Vysokého učení technického v Brně,
Ročník: 5.
Vedoucí práce: doc. RNDr. Alexandr Meduna, CSc.

Abstrakt:

Tento dokument se zabývá obecnou syntaktickou analýzou založenou na sekvenčních gramatikách a paralelních E0L gramatikách s využitím některých normálních forem těchto gramatik. Pro sekvenční gramatiky jsou použity Chomského a silná Greibachové normální forma, pro paralelní E0L gramatiky potom binární normální forma. Jsou diskutovány dvě různé varianty E0L gramatik, které se liší startovací strukturou. V prvním případě je startovací strukturou jeden řetězec, ve druhém potom celý jazyk definovaný bezkontextovou gramatikou v silné Greibachové normální formě. Pro sekvencní gramatiky jsou uvedeny celkem čtyři algoritmy, které se liší přístupem k syntaktické analýze a použitou normální formou. Pro paralelní E0L gramatiky jsou uvedeny dva algoritmy. Ty se liší podle použité startovací struktury v E0L gramatice. Po jejich formálním zápisu je funkce každého z nich demonstrována na praktických příkladech. Na závěr jsou shrnuty výsledky a diskutovány výhody a nevýhody.

Syntaktická analýza založená na gramatikách s rozptýleným kontextem
Petr Blatný
Fakulta informačních technologií Vysokého učení technického v Brně
Ročník: 5.
Vedoucí práce: doc. RNDr. Alexandr Meduna, CSc.

Abstrakt:

Úkolem mé práce bylo navrhnout vhodný algoritmus pro syntaktickou analýzu, neboli parsing, nad gramatikami s rozptýleným kontextem (SCG). Množina jazyků, kterou lze získat pomocí tohoto typu gramatik, pokrývá kontextové jazyky.

Syntaktická analýza je proces určování, zda řetězec vstupních symbolů je větou daného jazyka. Je-li, určí se syntaktická struktura řetězce. Syntaktickou analýzu provádí syntaktický analyzátor. Vstupem analyzátoru je řetězec lexikálních jednotek a výstupem je syntaktický strom nebo odvozená posloupnost. Jsou zde uvedeny dvě varianty algoritmů.

Algoritmus I využívá kombinaci metody zdola nahoru a shora dolů. Součástí popisu algoritmu jsou i příklady a závěrečné zhodnocení. Uvádím i verzi upravenou pro paralelní prostredí.

Algoritmus II je založen pouze na postupu zdola nahoru. Vzhledem k jeho složitosti je uveden i podrobný popis doplněný jednoduchými příklady. Závěrecné zhodnocení srovnává oba algoritmy.

Gramatiky s fixovanou pozicí neterminálů a složitost zápisu jazyků
Lucie Ciencialová
Ústav informatiky Filozoficko - přírodovědecké fakulty Slezské univerzity
Ročník: 4.
Vedoucí práce: Doc. RNDr. Alica Kelemenová, CSc.

Abstrakt:

V této práci autorka studuje efektivnost reprezentace bezkontextových jazyků gramatikami s fixovanou pozicí neterminálů (POG). Uvádí základní fakta týkající se gramatik s fixovanou pozicí neterminálů. Pozičně ohraničené gramatiky byly definovány a studovány v článcích "Canonical forms of context-free grammars and position restricted grammar forms" a "Position restricted grammar forms and grammars" autory M. Blattnerovou a S. Ginsburgem v Lecture Notes in Computer Science 56 a Theoretical Computer Science 17 . Této problematice jsou věnovány i práce A. Kelemenové (např. Gramatical levels of the position restricted grammars. Proc. of Mathematical Foundations of Computer Science MFCS'81, Lecture Notes in Computer science 118 , Springer Verlag, Berlin, 1981) a P. Šindelářové Složitost jazyka reprezentovaného gramatikami s ohraničenou pozicí. Bakalářská práce, FPF SU, 1999.

Cílem předkládané práce je porovnat složitosti optimální reprezentace jazyků různými typy pozičně ohraničených gramatik.

Jedná se o nalezení takových algoritmů, které transformují POG typu t na POG, která je typu t' a porovnat počty pravidel původní a nově získané gramatiky. Pozornost je věnována vzájemným vztahům třech různých typů pozičně ohraničených gramatik: (m, 0, 0), (0, m, 0) a (0, 0,m). Pro různé dvojice typů POG je uveden algoritmus jejich transformace a vyhodnocen nárůst počtu pravidel. Tento nárůst můžeme vyjádřit polynomiální funkcí, jejíž stupeˇn závisí na konkrétních typech gramatik.

V důkazech jsou použity dva různé způsoby převodu jednoho typu gramatiky na jiný typ. První postup je založen na závislosti dvou vět, z nichž jedna je získaná z druhé aplikací jednoho pravidla, na typu používaných pravidel. Druhý způsob vychází z maticové reprezentace gramatiky, kterou využijeme k převodu gramatiky na Griebachové normální tvar. (Introduction to formal language theory (Harrison, M. A.: Addision Wesley P. C., Reading, Massachusets, 1978).

Výsledky uvedené v této práci jsou původní.

On the complexity of the G-reconstruction problem
Zdeněk Dvořák, Vít Jelínek
MFF UK Praha
Ročník: 5.,6.
Vedoucí práce: Prof. RNDr. Jan Kratochvíl, CSc.

Abstrakt:

Let G be a fixed unoriented graph. The G-structure of a graph F is the hypergraph H with the same set of vertices as F and with the property that a set h is a hyperedge of H iff the subgraph of F induced on h is isomorphic to G. We consider the complexity of determining whether for a given hypergraph H there exists a graph F such that H is the G-structure of F. It has been proved that this problem is polynomial if . We investigate this problem for larger graphs G and show that for some G the problem is NP-complete – in fact we prove that it is NP-complete for almost all graphs G.

Transformácie XML dokumentov
Jana Dvořáková
Fakulta matematiky, fyziky a informatiky Univerzity Komenského v Bratislave
Ročník: 5.
Vedoucí práce: Prof. RNDr. Branislav Rovan, PhD.

Abstrakt:

V práci sme definovali vlastnú štruktúru klasifikácie systémov pre transformácie XML dokumentov, ktoré sme následne zaradili do definovaných skupín. Bližšie sme skúmali štyri formálne modely, na ktorých sú niektoré z nich založené - syntaxou riadené prekladové schémy, atribútové gramatiky, stromovo-transformačné gramatiky, zostupné stromové prekladače a ich modifikácie. Definície formálnych modelov uvádzame v jednotnej terminológií a z perspektívy transformácií stromov XML dokumentov. Ďalej sme sa zaoberali ich vlastnost'ami a definovali miery zložitosti, čím sme vytvorili podklad pre d'al'šie porovnávanie. Dokázali sme niekol'ko tvrdení porovnávajúcich transformačnú silu definovaných modelov.

Biangular circle formation by asynchronous mobile robots
Branislav Katreniak
Fakulta matematiky, fyziky a informatiky Univerzity Komenského v Bratislave
Ročník: 5.
Vedoucí práce: RNDr. Rastislav Kráľovič, CSc.

Abstrakt:

Consider a community of simple autonomous robots (decentralized, asynchronous, no common coordinate system, no identities, no direct communication, no memory of the past, deterministic) moving freely in the plane and able to sense the positions of the other robots. We study the task of forming a absolutely symmetric formation – regular circle. Although we do not reach this goal for all initial configurations. We form in general case only a less symmetric formation – biangular circle. Existing algorithms for similar tasks (forming a regular circle) are known only for stronger models (synchronous) and only converge to the final formation. In this paper we present an algorithm that solves the biangular circle formation problem deterministically in finite time.

Zefektivnění syntaktické analýzy aritmetických výrazů
Zbyněk Křivka
Fakulta informačních technologií Vysokého učení technického v Brně
Ročník: 5.
Vedoucí práce: doc. RNDr. Alexandr Meduna, CSc.

Abstrakt:

Tento příspěvek vycházející z mé ročníkové práce zkoumá možnosti optimalizovat prostředky pro LR(1)-syntaktickou analýzu a zaměřuje se na gramatiky pro infixový zápis aritmetických výrazů a gramatiky s podobnou strukturou pravidel.

Redukce velikosti LR-tabulky pro LR syntaktickou analýzu gramatik pro aritmetické výrazy je založena na programovém určení binárních operátorů stejné priority s využitím nově zaváděného pojmu – gramatický strom, který hierarchickým způsobem popisuje zpracovávanou gramatiku. Gramatický strom tak usnadňuje určení terminálů s významem binárního operátoru pomocí analýzy jejich tzv. nejbližších sousedů a rozlišování priorit na základě úrovní stromu, ve kterých se daný operátor nachází.

Nejprve je nutno zavést jisté minimální rozšíření pro získání nějakého prostoru pro optimalizace. V tomto případě jsem zvolil možnost provést sdružování stejných sloupců akční části LR-tabulky a následně takovýto sloupec ohodnotit odpovídající množinou terminálů. Následně je pak možno i snížit počet řádků tabulky (potažmo stavů).

Při nezměněném algoritmu LR syntaktické analýzy zdola nahoru můžeme obdržet zmenšení velikosti LR-tabulky až o několik desítek procent a tím i zvýšení efektivity překladu až o jednotky procent pro praktické aritmetické výrazy.

Další metodou optimalizace je zřetězení operací se zásobníkem. Zavadím nové operace: zřetězené vložení na zásobník (long shift) a zřetězenou redukci obsahu zásobníku (long reduce). Tato metoda zatím nebyla algoritmizována, ale má velmi dobré výsledky okolo 20 % zrychlení při analýze praktických aritmetických výrazů. Její hlavní nevýhodou je nutnost úpravy algoritmu LR syntaktické analýzy.

Distribuovaný algoritmus pro ověřování LTL vlastností modelu
Pavel Moravec
FI MU Brno
Ročník: 5.
Vedoucí práce: Doc. RNDr. Ivana Černá, CSc.

Abstrakt:

V poslední dekádě vyvstala nutnost formální verifikace softwarových aplikací nasazovaných do kritických provozů, kde výskyt jakékoliv chyby může mít fatální následky. Úspěšnou metodou je takzvané ověřování modelu (model checking), kdy se automatickými metodami vytvoří pro daný systém jeho abstraktní model a na něm je následně ověřena platnost verifikované vlastnosti. Často používanou logikou na specifikaci vlastností je logika lineárního času LTL. Ověřování LTL vlastností modelu pomocí sekvenčních metod ovšem často selhává v důsledku nedostatečné velikosti paměti. Alternativním přístupem je použití distribuovaných algoritmů, kdy na daném problému participuje více vzájemně komunikujících počítačů.

V této práci je prezentován nový distribuovaný algoritmus pro enumerativní ověřování LTL vlastností modelu, který je navržen pro cluster počítačů komunikujících pomocí MPI. Je diskutován vliv klíčového parametru ovlivňujícího chování algoritmu. Dále jsou uvedeny některé optimalizace základní verze algoritmu. Provedené experimentální výsledky potvrzují slibné teoretické poznatky.

Visually effective information visualization of large data
Matěj Novotný
Fakulta matematiky, fyziky a informatiky Univerzity Komenského v Bratislave
Ročník: 5.
Vedoucí práce: Ing. Robert Kosara

Abstrakt:

Information visualization is a powerful tool to communicate various data to human, since the human visual system can quickly perceive and process huge amount of information if it is displayed in an appropriate form. But large data sets clutter the graphical display and make the visual representation unclear. It is hard to observe relations and pattern in an overplotted display, many features might get lost after behind others and the interaction suffers from slow application feedback. One of the solutions for this situations is using a more simple information, that requires less resources on either computer side or user side. This information has to approximate the original one as good as possible. My project introduces visual abstraction as a new concept for information visualization with respect to large size of the visualized data sets. The abstract information is gained using unsupervised data mining. The effects of this synergic approach joining human visual processing and computer-based pre-processing are illustrated on a popular infovis technique - the parallel coordinates. As the presented results show, visual abstraction offers a very effective overview, solves many problematic situations in visualization and allows to change the level of detail in the display to any desired level.

Steinerovské farbenie kubických grafov
Dávid Pál
Fakulta matematiky, fyziky a informatiky Univerzity Komenského v Bratislave
Ročník: 5.
Vedoucí práce: Doc.RNDr. Martin Škoviera, CSc.

Abstrakt:

Farbenie kubického grafu pomocou steinerovského systému trojíc je farbenie jeho hrán tak, aby farby každej trojice hrán majúcej spoločný vrchol tvorili trojicu steinerovského systému. Hlavným výsledkom mojej práce je, že kubické grafy bez sériovoparalelného konca (t.j. všetky steinerovsky zafarbitel'né grafy vöbec) sú zafarbitel'né steinerovským systémom     AG(1,3)×PG(2,2) rádu 21. Ďalej sa podarilo úplne charakterizovat' triedu kubických grafov zafarbitel'ných afínnymi steinerovskými systémami AG(n, 3) pre

Generation of Sentences with Their Parses by Scattered Context Grammars
Jiří Techet
Fakulta informačních technologií Vysokého učení technického v Brně
Ročník: 4.
Vedoucí práce: doc. RNDr. Alexandr Meduna, CSc.

Abstrakt:

Propagating scattered context grammars are used to generate their language's sentences together with their parses - that is the sequences of labels denoting productions whose use lead to the generation of the corresponding sentences. It is proved that for every recursively enumerable language, L, there exists a propagating scattered context grammar whose language consists of L's sentences followed by their parses.

Tato práce vznikla v rámci ročníkového projektu pod vedením pana doc. Meduny.

Image reconstruction using triangulation
Tóth Zsolt
Fakulta matematiky, fyziky a informatiky Univerzity Komenského v Bratislave
Ročník: 5.
Vedoucí práce: RNDr. Andrej Ferko, CSc.

Abstrakt:

Visually pleasant image reconstruction has important role in computer graphics. In this paper we explore the applicability of triangulations for image reconstruction. Two new algorithms are introduced for generation of data-dependent triangulation. The new deterministic algorithm entitled as image partitioning algorithm (IPA) shifts this reconstruction method closer to real usage. We present a new modification of the optimization technique simulated annealing with generalized look-ahead process (SALA). Also a new way of utilization of color information is presented, to achieve qualitative course of reconstruction of color images. Results show both theoretical and practical superiority over another methods. This work is a part of the APVT project Virtual Bratislava.

The stable multiple activities problem
Viera Vaľová
PF UPJŠ Košice
Ročník: 5.
Vedoucí práce: Doc. RNDr. Katarína Cechlárová, CSc.

Abstrakt:

We study a generalization of the well-known stable roommates problem, namely the stable multiple activities problem in which multiple partners and parallel edges in the underlying graph are allowed. A polynomial algorithm for finding a stable b-matching was presented by Cechlárová and Fleiner. This algorithm runs in O(m²) time, where m is the number of edges of the underlying graph. We perform a detailed analysis of this algorithm and present a new implementation, so that it runs in O(m) time. Further we show, that the result of the first phase of the algorithm does not depend on the order of deletions, we prove an analogy of the rural hospitals theorem for this problem and also the fact that the algorithm finds all stable b-matchings for a given instance of the stable multiple activities problem.

Zaoberáme sa zovšeobecnením známeho problému stabilných spolubývajúcich, konkrétne problémom stabilných multiaktivít, v ktorom sú povolení viacerí partneri a navyše aj paralelné hrany v prislúchajúcom grafe. Cechlárová a Fleiner predstavili polynomiálny algoritmus na hl'adanie stabilného b-párovania so zložitost'ou O(m²), kde m predstavuje počet hrán v popisujúcom grafe. My uvádzame jeho delailnú analýzu a predstavujeme novú implementáciu takú, že algoritmus beží v čase O(m). Ďalej ukážeme, že prvá fáza je nezávislá od poradia mazania hrán, dokážeme analógiu vety o vidieckych nemocniciach pre tento problém a tiež skutočnost', že algoritmus nájde všetky stabilné b-párovania pre danú inštanciu problému stabilných multiaktivít.

Související odkazy:

• Práce v sekci S1 - Matematická analýza
• Práce v sekci S2 - Pravděpodobnost, statistika, ekonometrie a finanční matematika
• Práce v sekci S3 - Matematické struktury
• Práce v sekci S5 - Aplikovaná matematika
• Seznam všech prací - podle sekcí