|
|
Interval solver for nonlinear constraints
Garajová, Elif ; Hladík, Milan (advisor) ; Pergel, Martin (referee)
The thesis is focused on the Sivia algorithm (Set Inverter via Interval Ana- lysis) designed for solving a continuous constraint satisfaction problem using interval methods and propagation techniques. Basic properties of the algorithm are derived, including the correction of its presented complexity bound. Some improvements concerning the testing of constraint satisfaction and optimiza- tion of the number of interval boxes describing the solution are proposed. The thesis also introduces contractors used to enhance the effectivity of the Sivia algorithm by reducing the interval boxes processed. Presented algorithms were implemented in a solver for nonlinear constraints with a simple visualization of the result using the Matlab language. A comparison of basic contractors on specific examples is given.
|
|
|
Software Solution for Small and Medium-Sized Retail Companies
Hlavatý, Martin ; Bulej, Lubomír (advisor) ; Pergel, Martin (referee)
The aim of this thesis is to describe a warehouse management system and an Internet shopping website suitable for a small to medium-sized retailers. The thesis analyzes the needs of such companies, the most commonly performed operations and the persons required to carry them out. Based the results of the analysis, a software solution and its implementation is proposed. The suggested solution is built on a three-tier architecture using web services and implemented mostly in the Java and PHP languages. It is platform-independent, open-ended, and easily manageable (due to a group- and role-based authorization system).
|
|
|
Timetable generation for public mass transportation
Trenkler, Pavol ; Babilon, Robert (advisor) ; Pergel, Martin (referee)
In this work we study two problems arising in transport planning: the vehicle scheduling problem and the duty scheduling problem. We present the most promising algorithms for solving these problems optimally, based on the minimum cost multicommodity flow problem and the set partitioning problem. Then we discuss an implementation using freely available integer programming libraries, within the context of a transit scheduling application developed.
|
|
|
Hry na grafech
Gavenčiak, Tomáš ; Kratochvíl, Jan (advisor) ; Pergel, Martin (referee)
In this thesis we study properties of one cop&robber game. In this game two players (Cop and Robber) take turns in moving on a finite undirected graph. Both players move with the speed at most one edge per turn. They both know the complete game status. If at any time Cop shares a vertex with Robber, Cop wins. If that never happens, Robber wins. Games of this type are important as models of searching in graphs and networks and for the connection to the width parameters of graphs. We closely examine the class of graphs with a winning strategy for Cop (the so called cop-win graphs) and construct best strategies for both Cop and Robber. The previously known results include the fact that the number of moves in which Cop can catch Robber on every cop-win graph on n vertices is bounded by n3 and there are graphs which require n 4. We show that this number is exactly n 4.
|
|
|
Graph Visualisation
Kratochvíl, Jakub ; Pergel, Martin (advisor) ; Bálek, Martin (referee)
This thesis concentrates on drawing graphs in 3D. In the first part of the text, we concentrate on orthogonal layouts of graphs with maximum degree 6. We show how to draw graphs using high dimensional embedding (HDE) and propose a new fast algorithm based upon sampling of the HDE. Further, we developed an application for Win32 that allows the user to translate, zoom and rotate the graph drawing, thus taking full advantage of the 3D layout.
|
|
|
Geometrické reprezentace grafů
Klavík, Pavel ; Kratochvíl, Jan (advisor) ; Pergel, Martin (referee)
Intersection graphs are a well studied field of graph theory. Complexity questions of recognition have been studied for several years. Given a graph, we ask whether the graph belongs to a fixed class. In this thesis, we introduce a new problem of partial representation extension. In this problem, aside from a graph, a part of a representation is also fixed. We ask whether it is possible to extend this partial representation to the whole graph. This problem is at least as hard as recognition. We study the partial representation extension problem for several intersection defined classes. We solve extending of interval graphs in time O(n2) and proper interval graphs in time O(mn). Using an approach described by Golumbic, we further show that comparability and permutation graphs are extendable in time O( · m). There are some classes that are known to be equal, for example unit interval graphs and proper interval graphs. Surprisingly, in the case of extending, we need to distinguish them. Similarly, we show that extending of function graphs and extending of co-comparability graphs are completely different problems.
|
|
|
Using hierarchical finite automata for behavior-description
Renát, Dušan ; Pergel, Martin (advisor) ; Holan, Tomáš (referee)
In the present work we introduce and study the hierarchical finite state machines as a model of artificial intelligence of autonomous agents in various virtual environments and systems. We define the concept of hierarchical finite state machine formally, analyze its computational power compared to common types of automata and point out the possibilities of increasing it. Then we list the usual methods of artificial intelligence simulation, tell apart the direct and indirect behavioral pattern description and present advantages of hierarchical finite state machines as a tool for the direct form. We propose a library interpreting these automata, created as a part of this work. By demonstrating its usage for controlling an example robot within the Robocode environment, we show that they are generic and viable solution for this kind of settings.
|
|
|
Spread of delay on railway network
Straka, Martin ; Babilon, Robert (advisor) ; Pergel, Martin (referee)
Title: Spread of delay on railway network Author: Martin Straka Department: Department of Applied Mathematics Supervisor: Mgr. Robert Babilon Supervisor's e-mail address: babilon@kam.ms.mff.cuni.cz Abstract: The subject of this work is a simulation of late trains spreading in railway net. This program shows the single simulations and creates their statistics according to different criteria (for example changing waiting periods or changes in crossing of the trains). This work evaluates and compares the results. Next point of this work is an effort to suggest the most appropriate criteria in order to prevent the train lag. Another element of this work includes searching for weak points in grafikon, which includes the trains that are late more frequently than other or do not wait for an arrival of the previous ones on their way because of the great lag. Keywords: trains, late, simulation, statistic Keywords: trains, late, simulation, statistic
|
|
|
Information system for capital brokers
Pastorek, Jaroslav ; Tichý, Tomáš (advisor) ; Pergel, Martin (referee)
Bachelor thesis considers design and implementation of information system for capital broker based on client - server architecture. System provides storage for most important evidencies - clients, contracts, payments, trade orders and other respective evidencies. System also provides functionality for creating sevices of Centrálny depozitár cenných papierov SR and operating trades through Burza cenných papierov Bratislava. All operations accord to legal conditions of Slovenská republika.
|
|
|
Construction of Periodic Railway Timetables
Kalický, Andrej ; Babilon, Robert (advisor) ; Pergel, Martin (referee)
In the propounded thesis author studies the periodic railway timetable. The aim of this thesis is to construct time shifts among train lines so that transfers between lines would be planned in the best possible way. Author discusses the problem to solve, and its differences from standard processing of periodic railway timetable construction. Author propounds and code 2 algorithms for optimization of given timetable. At the end of thesis the solutions and algorithms are compared based on statistical data related with the process of periodic railway timetable construction.
|
guest ::
