|
|
Repetitive Substructures for Efficient Representation of Automata
Šedý, Michal ; Češka, Milan (referee) ; Holík, Lukáš (advisor)
Nedeterministické konečné automaty (NKA) jsou široce využívány napříč mnoha odvětvími počítačové vědy, například pro reprezentaci regulárních výrazů, při monitorování vysoko rychlostních sítí, v abstraktním regulárním model checkingu, k verifikaci programů, k rozhodování procedur logik WS1S a WS2S, lineární aritmetiky celých čísel, temporálních logik, nebo dokonce v bioinformatice při vyhledávání sekvencí nukleotidů v DNA. Automaty s velkým množstvím stavů mohou v řadě algoritmů vést k exponenciálnímu nárůstu stavového prostoru. Tento problém lze zmírnit použitím minimalizačních technik slučování stavů a prořezávání hran přechodů. Tyto metody však mohou i přes svou značnou efektivitu zanechat ve výsledných automatech duplicitní podstruktury s ekvivalentními přechody. Existují dokonce typy automatů, které nelze těmito standardními technikami minimalizovat vůbec. Tato práce představuje nový přístup k minimalizaci automatů založený na transformaci NKA na nedeterministický zásobníkový automat (NZA). Tato transformace identifikuje skupinu podobných podstruktur a nahradí ji jednou společnou strukturou (procedurou). Tímto způsobem jsme byli schopni zredukovat automaty až o dalších 67.3%. Myšlenka transformace NKA na NZA lze přirovnat k transformaci sekvenčního programu na program, který využívá funkce a zásobníkem volání.
|
|
|
Porovnání rozdílné technologie zpracování půdy na výnos jarního ječmene.
BENÁČEK, Vojtěch
In my diploma thesis, I will deal with the comparison of two different technologies. This work will be carried out on a stand of spring barley and will follow on from the bachelor's thesis, which was created in the same company. The first technology will be classic ploughing, while the second technology will be tillage using a chisel plow that works up to a depth of 50 cm.
|
|
|
Reduction of the Nondeterministic Finite Automata
Procházka, Lukáš ; Kořenek, Jan (referee) ; Kaštil, Jan (advisor)
Nondeterministic finite automaton is an important tool, which is used to process strings in many different areas of programming. It is important to try to reduce its size for increasing programs' effectiveness. However, this problem is computationally hard, so we need to search for new techniques. Basics of finite automata are described in this work. Some methods for their reduction are then introduced. Usable reduction algorithms are described in greater detail. Then they are implemented and tested. The test results are finally evaluated.
|
|
|
Optimization of an aircraft wing rib
Kopřiva, Lubomír ; Suchánek, Miroslav (referee) ; Petruška, Jindřich (advisor)
Topology optimization is a method providing new direction in designing of a technical objects. The aim of topology optimization is to find optimal distribution of material in design space. This diploma thesis is focused on optimization of aircraft wing rib num.6 of the airplane EV-55 using a software HW/Optistruct 7.0 implemented in a software package HyperWorks 7.0. The optimization of the rib was calculated under four different load cases. Resulting shapes of the rib were then tested by strenght calculations in software ANSYS 10.0. Finally, the obtained data of weights of optimized ribs were compared with the weight of the original rib.
|
|
| |
|
|
Reducing Size of Nondeterministic Automata with SAT Solvers
Šedý, Michal ; Havlena, Vojtěch (referee) ; Holík, Lukáš (advisor)
Nedeterministické konečné automaty (NKA) jsou široce využívány v počítačové vědě, například v oblasti formálních jazyků pro reprezentaci regulárních jazyků, k monitorování vysokorychlostních sítí, rozpoznávání obrazu, modelování hardware, nebo dokonce v bioinformatice pro vyhledávání sekvencí nukleotidových kyselin v DNA. NKA jsou také používány v abstraktním regulárním model checkingu, dále ve verifikaci programů manupulujících s řetězci, ve verifikaci programů využívajících ukazatele, pro konstrukci lineárních rovnic a nerovnic, v rozhodovacích procedurách WS1S a WS2S logiky a mnohých dalších. Minimalizace automatů je základní technikou, která pomáhá snižovat nároky na zdroje (paměť, čas nebo množství hardwarových komponentů) a urychlovat operace prováděné na automatech. Běžně používané minimalizační techniky, jakými jsou slučování stavů, odstraňování hran přechodů nebo saturace, mohou v automatech zanechat potenciální minimalizovatelné podgrafy obsahující duplicitní jazykovou informaci. Tyto fragmenty sestávají ze skupiny stavů, kde je již část jazyka jednoho stavu pokryta jazyky ostatních stavů z této skupiny. Tato práce popisuje novou techniku využívající SAT solver, který poskytuje informaci umožňující minimalizovat tyto doposud neminimalizovatelné části automatů. Nově vyvíjená metoda, která využívá pouze informaci od SAT solveru a slučování stavů minimalizuje automaty podobně efektivně, a v případě automatů s nízkým počtem přechodů dokonce rychleji než nástroj RABIT/Reduce, který využívá slučování stavů a odstraňování hran.
|
|
|
Possibilities of minimalization of induced drag
Skarolek, Vilém ; Kouřil, Martin (referee) ; Lajza, Ondřej (advisor)
Lift-induced drag is a significant part of total drag of airplane during flight, thus its minimization is desirable for economical operation of air service. This bachelor thesis deals with possibilities of induced drag minimization. First part of this thesis presents basics of induced drag origin during flight. The second part of the thesis contains overview of potential methods of induced drag minimization, their description and structural design, including comparison of particular methods of drag minimization.
|
|
|
Efficient Automata Techniques and Their Applications
Havlena, Vojtěch ; Jančar, Petr (referee) ; Mayr, Richard (referee) ; Esparza, Javier (referee) ; Vojnar, Tomáš (advisor)
Tato práce se zabývá vývojem efektivních technik pro konečné automaty a jejich aplikace. Zejména se věnujeme konečným automatům použitých pří detekci útoků v síťovém provozu a automatům v rozhodovacích procedurách a verifikaci. V první části práce navrhujeme techniky přibližné redukce nedeterministických automatů, které snižují spotřebu zdrojů v hardwarově akcelerovaném zkoumání obsahu paketů. Druhá část práce je je věnována automatům v rozhodovacích procedurách, zejména slabé monadické logice druhého řádů k následníků (WSkS) a teorie nad řetězci. Navrhujeme novou rozhodovací proceduru pro WS2S založenou na automatových termech, umožňující efektivně prořezávat stavový prostor. Dále studujeme techniky předzpracování WSkS formulí za účelem snížení velikosti konstruovaných automatů. Automaty jsme také aplikovali v rozhodovací proceduře teorie nad řetězci pro efektivní reprezentaci důkazového stromu. V poslední části práce potom navrhujeme optimalizace rank-based komplementace Buchiho automatů, které snižuje počet generovaných stavů během konstrukce komplementu.
|
|
|
Evolutionary Combinational Circuit Resynthesis
Pták, Ondřej ; Schwarz, Josef (referee) ; Sekanina, Lukáš (advisor)
This project deals with combinational digital circuits and their optimization. First there are presented main levels of abstraction utilized in the design of combinational digital circuits. Afterwards different methods are surveyed for optimization of combinational digital circuits. The next part of this project is mainly devoted to evolutionary algorithms, their common characteristics and branches: genetic algorithms, evolutionary strategies, evolutionary programming and genetic programming. The variant of genetic programming called Cartesian Genetic Programming (CGP) and the use of CGP in various areas, particularly in the synthesis and optimization of combinational logic circuits are described in detail. The project also discusses some modifications of CGP and the scalability problem of evolutionary circuit design. Consequential part of this thesis describes the method for evolution resynthesis of combinational digital circuits. There is description of design, especially the method of splitting circuits into subcircuits, and implementation details. Finally experiments with these method and their results are described.
|
|
|
Reduction of CentOS operating system
Vashkevich, Pavel ; Caha, Tomáš (referee) ; Komosný, Dan (advisor)
The goal of this bachelor's thesis is to perform a reduction of the Linux operating system. For minimalization was entered the Linux distribution CentOS 8, which is created on the basis of open-source code. This code are spread by Red Hat. The theoretical part describes the basic components of the operating system, including the Linux kernel, drivers and graphical interface. The practical part describes the suggestion of a method for minimizing the operating system. This method also includes a comparison of lightweight web browsers. The resulting size after reduction is 731 MB. Minimization automation software is published in the personal repository on GitHub under the MIT license.
|
guest ::
