|
|
Length bounded cuts in graphs
Berg, Michal ; Kolman, Petr (advisor) ; Dvořák, Pavel (referee)
In this thesis we will focus on a problem of length bounded cut, also known as L-bounded cut. We are going to show a combinatorial algorithm for finding a minimal L-bounded cut on graphs with bounded treewidth based on dynamic programming. Then we going to show that this algorithm can also be used for finding minimal L-bounded cut on plannar graphs. We are also going to look at problem of (dG(s, t) + 1)-bounded cut. This problem is known to be NP-hard for general graphs. But it is an open problem whether this problem is also NP-hard on plannar graphs with special vertices on the outer face. We will try to outline a way, which might lead to showing that this problem is solvable in a polynomial time.
|
|
|
Application for the Dynamic Programming Demonstration
Nereča, Tomáš ; Bartík, Vladimír (referee) ; Burgetová, Ivana (advisor)
A result of this bachelor thesis is a web application which focuses on computer programming method called dynamic programming. Principles and advantages of dynamic programming are explained on several examples. Dynamic programming algorithm is explained both theoretically and also practically by a dynamically filled up table. Dynamic programming solution is also compared with simple recursive solution in charts and table.
|
|
|
Dynamic Programming in Graph Algorithms
Biloš, Martin ; Křivka, Zbyněk (referee) ; Burgetová, Ivana (advisor)
This work is about graph algorithms, their use and the benefit of the optimization method of dynamic programming. This benefit is show to the user via the graphic application. Graph algorithms find use in many sectors of human activity. They are used in packet routing or, for example, navigation. There are three methods of graph algorithms used in this work. This problems are solved with classic and dynamic way and measured data are compared.
|
|
|
Online System for Visual Geo-Localization in Natural Environment
Pospíšil, Miroslav ; Čadík, Martin (referee) ; Brejcha, Jan (advisor)
The goal of this master thesis is creation of an online system serving as a performing application for presentation results of visual geo-localization in nature and mountain environment. The system offers the users to choose one of the pre-defined photographs or~to~upload one's own photography while choosing a file or inserting an URL address. The~system will localizate a camera of a given image based on a visual geo-localization. The~geo-localization uses the mountain horizon as a key characteristic when searching for similar horizons. The~curve line of the horizon is extracted by a fully automatic algorithm based on supervised learning and dynamic programming. Visual geo-localization running on the server which using new inversed index with cache politic. This allows further scaling of the system. The server processing detected horizon curve and respond with set of the best candidates on results. Results are visualised to the user in form of classic map, detailed sattelite view and rendering of found panorama.
|
|
|
Network Protocols Semiautomatic Diagnostics
Svoboda, Ondřej ; Ryšavý, Ondřej (referee) ; Holkovič, Martin (advisor)
This thesis is about semiautomatic network protocol diagnostics and creating protocol description from eavesdropped communication. Several network eavesdropping techniques and some common programs for network analysis are introduced. Well-known network protocols are described, with focus on their communication messages. Some already existing methods for creating models from examples are mentioned and their characteristics defined. Next we design architecture of developed tool and some methods, that create protocol description. After that we explain implementation of this tool and finally the tool is tested and experimented with.
|
|
|
Risk-Sensitive Optimality in Markov Games
Sladký, Karel ; Martínez Cortés, V. M.
The article is devoted to risk-sensitive optimality in Markov games. Attention is focused on Markov games evolving on communicating Markov chains with two-players with opposite aims. Considering risk-sensitive optimality criteria means that total reward generated by the game is evaluated by exponential utility function with a given risk-sensitive coefficient. In particular, the first player (resp. the secondplayer) tries to maximize (resp. minimize) the long-run risk sensitive average reward. Observe that if the second player is dummy, the problem is reduced to finding optimal policy of the Markov decision chain with the risk-sensitive optimality. Recall that for the risk sensitivity coefficient equal to zero we arrive at traditional optimality criteria. In this article, connections between risk-sensitive and risk-neutral Markov decisionchains and Markov games models are studied using discrepancy functions. Explicit formulae for bounds on the risk-sensitive average long-run reward are reported. Policy iteration algorithm for finding suboptimal policies of both players is suggested. The obtained results are illustrated on numerical example.
|
|
|
Design of dynamic decision-making strategies for futures trading
Vosáhlo, Jaroslav ; Guy, Tatiana Valentine (advisor) ; Lachout, Petr (referee)
This thesis deals with an issue of futures derivative trading from a perspective of a minor speculator. The aim of this work is to find and design an optimal trading strategy using dynamic programming and approximate dynamic programming. We use means of Bayesian statistics to obtain predictions of variate's behavior and risk indicators to form a rate of carefulness. Effectivity of algorithm is afterwards tested in Matlab program. Available data for testing the success of the method offer more then 15.000 trading days.
|
|
|
Lot-sizing problem
Kafka, Ondřej ; Branda, Martin (advisor) ; Bejda, Přemysl (referee)
Title: Lot-sizing problem Author: Ondřej Kafka Department: Department of probability and mathematical statistics Supervisor: RNDr. Martin Branda, Ph.D. Abstract: In the present work, we define the basic concepts of lot-sizing. We introduce Wagner-Whitin's dynamic lot size problem and derive a dynamic programming algorithm for the solution. Next we look at the case of PCLSP (Profit maximizing capacitated lot size problem) problem with fixed prices and negligable setup costs and solve it using specialized linear programming algorithm. Everything we try to explain with concrete examples. In the end we verify the efficiency of those algorithms by numerical study on random data comparing the performance of programmed algorithms with the professional optimization solver Gurobi. Keywords: Lot-sizing, dynamic programming, linear programming
|
|
|
Transient and Average Markov Reward Chains with Applications to Finance
Sladký, Karel
The article is devoted to Markov reward chains, in particular, attention is primarily focused on the reward variance arising by summation of generated rewards. Explicit formulae for calculating the variances for transient and average models are reported along with sketches of algorithmic procedures for finding policies guaranteeing minimal variance in the class of policies with a given transient or average reward. Application of the obtained results to financial models is indicated.
|
|
| |
guest ::
