|
|
Optimization of a circulating multi-car elevator system
Pantůčková, Kristýna ; Fink, Jiří (advisor) ; Matzner, Filip (referee)
Circulating multi-car elevator is a system holding multiple cars in two shafts, where cars move upwards in one shaft and downwards in the other shaft. This system is similar to the paternoster, but cars have to stop on floors and open doors to load and unload passengers. Besides many technical challenges, this sys- tem brings algorithmic problems regarding efficient control of all cars. This thesis studies an off-line optimization problem, where the most efficient elevator system is searched for a fixed set of passengers. For this purpose, we created a computer program, implementing a genetic algorithm for searching for the most efficient elevator control and a discrete event simulation for evaluation of the efficiency of the control. The program provides a graphical user interface for input of parame- ters, generating passengers and displaying the results. 1
|
|
| |
|
|
Extension of Machinations Framework
Guth, Robert ; Gemrot, Jakub (advisor) ; Fink, Jiří (referee)
Framework Machinations is a tool for representing board games mechanics and mechanics of some computer games. Its main purpose is to allow game designers to test and tune the game's parameters before games release. However, current framework is not able to create models of some game mechanics and by that, it forces its users to simplify their models. The aim of this work is to extend framework machinations into a tool capable of simulating board game mechanics without having to simplify them. Thesis includes a program for working with an extended framework and a case study detailing the implementation of the Stone Age game in the extended framework.
|
|
|
Prediction of energy load profiles
Bartoš, Samuel ; Fink, Jiří (advisor) ; Van Leeuwen, Richard (referee)
Prediction of energy load profiles is an important topic in Smart Grid technologies. Accurate forecasts can lead to reduced costs and decreased dependency on commercial power suppliers by adapting to prices on energy market, efficient utilisation of solar and wind energy and sophisticated load scheduling. This thesis compares various statistical and machine learning models and their ability to forecast load profile for an entire day divided into 48 half-hour intervals. Additionally, we examine various preprocessing methods and their influence on the accuracy of the models. We also compare a variety of imputation methods that are designed to reconstruct missing observation commonly present in energy consumption data.
|
|
|
Construction of Gray codes with special properties
Novotný, Tomáš ; Dvořák, Tomáš (advisor) ; Fink, Jiří (referee)
A (cyclic) Gray code is a (cyclic) sequence of all n-bit strings in which consecutive strings differ in a single bit. Ruskey and Savage in 1993 asked whether every matching in a hypercube can be extended to a cyclic Gray code. An affirmative answer is known for perfect matchings (Fink, 2007) while the ge- neral case is still open. The main contribution of this thesis is a generalization of Fink's result to Gray codes with prescribed ends. The characterization of perfect matchings extendable in this way is verified for n = 5 with the assistance of a com- puter, which is useful as a basis for the inductive proof of the general statement. The other part of the thesis is focused on smallest maximal matchings in hyper- cubes which could possibly form especially hard instances of the Ruskey-Savage problem. We devise a novel method which provides - in particular for small di- mensions - maximal matchings of smaller size than the classical asymptotically optimal construction (Forcade, 1973). An adjusted program from the first part is then applied to test the Ruskey-Savage problem over these matchings, however, the extending Gray code is always discovered. 1
|
|
|
Evolutionary algorithms and active learning
Repický, Jakub ; Holeňa, Martin (advisor) ; Fink, Jiří (referee)
Názov práce: Evoluční algoritmy a aktivní učení Autor: Jakub Repický Katedra: Katedra teoretické informatiky a matematické logiky Vedúci diplomovej práce: doc. RNDr. Ing. Martin Holeňa, CSc., Ústav informa- tiky, Akademie věd České republiky Abstrakt: Vyhodnotenie ciel'ovej funkcie v úlohách spojitej optimalizácie často do- minuje výpočtovej náročnosti algoritmu. Platí to najmä v prípade black-box fun- kcií, t. j. funkcií, ktorých analytický popis nie je známy a ktoré sú vyhodnocované empiricky. Témou urýchl'ovania black-box optimalizácie s pomocou náhradných modelov ciel'ovej funkcie sa zaoberá vel'a autorov a autoriek. Ciel'om tejto dip- lomovej práce je vyhodnotit' niekol'ko metód, ktoré prepájajú náhradné modely založené na Gaussovských procesoch (GP) s Evolučnou stratégiou adaptácie ko- variančnej matice (CMA-ES). Gaussovské procesy umožňujú aktívne učenie, pri ktorom sú body pre vyhodnotenie vyberané s ciel'om zlepšit' presnost' modelu. Tradičné náhradné modely založené na GP zah'rňajú Metamodelom asistovanú evolučnú stratégiu (MA-ES) a Optimalizačnú procedúru pomocou Gaussovských procesov (GPOP). Pre účely tejto práce boli oba prístupy znovu implementované a po prvý krát vyhodnotené na frameworku Black-Box...
|
|
|
Hamiltonicity of hypercubes without k-snakes and k-coils
Pěgřímek, David ; Gregor, Petr (advisor) ; Fink, Jiří (referee)
A snake (coil) is an induced path (cycle) in a hypercube. They are well known from the snake-in-the-box (coil-in-the-box) problem which asks for the longest snake (coil) in a hypercube. They have been generalized to k-snakes (k-coils) which preserve distances between their every two vertices at distance at most k − 1 in hypercube. We study them as a variant of Locke's hypothesis. It states that a balanced set F ⊆ V (Qn) of cardinality 2m can be avoided by a Hamiltonian cycle if n ≥ m + 2 and m ≥ 1. We show that if S is a k-snake (k-coil) in Qn for n ≥ k ≥ 6 (n ≥ k ≥ 7), then Qn − V (S) is Hamiltonian laceable. For a fixed k the number of vertices of a k-coil may even be exponential with n. We introduce a dragon, which is an induced tree in a hypercube, and its generalization a k-dragon which preserves distances between its every two vertices at distance at most k−1 in hypercube. By proving a specific lemma from my Bachelor thesis that was previously verified by a computer, we finish the proof of the theorem regarding Hamiltonian laceability of hypercubes without n-dragons.
|
|
|
Probabilistic Methods in Discrete Applied Mathematics
Fink, Jiří ; Loebl, Martin (advisor) ; Koubek, Václav (referee) ; Sereni, Jean-Sébastein (referee)
One of the basic streams of modern statistical physics is an effort to understand the frustration and chaos. The basic model to study these phenomena is the finite dimensional Edwards-Anderson Ising model. We present a generalization of this model. We study set systems which are closed under symmetric differences. We show that the important question whether a groundstate in Ising model is unique can be studied in these set systems. Kreweras' conjecture asserts that any perfect matching of the $n$-dimensional hypercube $Q_n$ can be extended to a Hamiltonian cycle. We prove this conjecture. The {\it matching graph} $\mg{G}$ of a graph $G$ has a vertex set of all perfect matchings of $G$, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle. We prove that the matching graph $\mg{Q_n}$ is bipartite and connected for $n \ge 4$. This proves Kreweras' conjecture that the graph $M_n$ is connected, where $M_n$ is obtained from $\mg{Q_n}$ by contracting all vertices of $\mg{Q_n}$ which correspond to isomorphic perfect matchings. A fault-free path in $Q_n$ with $f$ faulty vertices is said to be \emph{long} if it has length at least $2^n-2f-2$. Similarly, a fault-free cycle in $Q_n$ is long if it has length at least $2^n-2f$. If all faulty vertices are...
|
|
|
Optimization and Statistics
Fink, Jiří ; Loebl, Martin (advisor)
CONTENTS Nazev prace: Autor: Katedra (ustav-): Vedouci diplomove prace: E-mail vedouciho: Kh'cova slova; Abstrakt: Optimization and Statistics Jifi Fink Katedra aplikovane matematiky Doc. RNDr. Martin Loebl, CSc. loebl@kam.mff, cuni.cz Edwards-Anderson Ising model, Teorie grafu, T-join, Gaussovska distribuce Jedni'm ze zakladnich problemu moderni statisticke fyzikj' je'snada porozumet frus- traci a chaosu. Zakladnfm modelem je konecne dimenzionalni Edwards-Anderson Ising model. V optimalizaci to odpovida zkoumam minimalni'ch T-joinu v konecnych mnzkach s nahodnymi vahami na hranach. V teto praci studujeme "random join", coz je nahodna cesta mezi dvema pevne danj^mi \Tcholy. Puvodni definice je pfilis slozita; a tak jsme ukazali jednodussi. Tato defmice je pouzita k pfesnernu vypoctu "random join" na kruznici. Take jsme ukazali specialm algoritmus, ktery hleda cestu v mrfzce s danymi hranami. Tento algoritmus muze byt pouzit k experimentalnimu studovani "random join". Title: Author: Department: Supervisor: Supervisor's e-mail address: Keywords: Abstract: Optimization and Statistics Jin Fink Department of Applied Mathematics Doc. RNDr. Martin Loebl, CSc. loebl@kam.mff.cuni.cz Edwards-Anderson Ising model, Graph theory, T-join, the Gaussian distribution One of the basic streams of modern statistics physics is...
|
|
|
Optimization and Statistics
Fink, Jiří ; Kratochvíl, Jan (referee) ; Loebl, Martin (advisor)
One of the basic streams of modern statistics physics is an effort to understand the frustration and chaos. The basic model to study these phenomena is the finite dimensional Edwards-Anderson Ising model. In discrete optimisation this corresponds to the minimal T-joins in a finite lattice with random weights of edges. This thesis studies a random join which is a random path between two given vertices. The original definition of the random join is very complex, and we have managed to find an equivalent one which is more natural. We use our definition to exactly compute the random join on circles. We also propose an algorithm which finds the shortest path in a large lattice with given weights of edges. This algorithm can be used for an experimental study of the random join.
|
guest ::
