|
|
Délkově omezené řezy v grafech
Berg, Michal ; Kolman, Petr (vedoucí práce) ; Dvořák, Pavel (oponent)
V této práci se budeme zabývat problémem délkově omezeného řezu, nazývaného také L-omezený řez. Ukážeme kombinatorický algoritmus pro hledání minimálního L-omezeného řezu na grafech omezené stromové šířky založený na dynamickém programování. Následně také ukážeme, že se tento algoritmus dá použít i pro hledání L-omezeného řezu na rovinných grafech. Také se podíváme na problém (dG(s, t) + 1)-omezeného řezu. Je známé, že tento problém je NP-těžký na obecných grafech. Ale to, jestli je NP-těžký i na rovinných grafech se speciálními vrcholy na vnější stěně, je otevřený problém. Pokusíme se nastínit způsob, kterým bychom možná mohli ukázat, že tento problém je řešitelný v polynomiálním čase.
|
|
|
Aplikace na podporu výuky dynamického programování
Nereča, Tomáš ; Bartík, Vladimír (oponent) ; Burgetová, Ivana (vedoucí práce)
Webová aplikácia, ktorá je výsledkom tejto práce, sa zaoberá technikou návrhu algoritmov s názvom dynamické programovanie. Aplikácia na konkrétnych príkladoch poukazuje na jej princípy a výhody. Pri každom príklade je konkrétny algoritmus teoreticky vysvetlený a jeho priebeh je znázornený pomocou dynamicky vypĺňanej tabuľky. Okrem toho aplikácia porovnáva efektivitu riešenia technikou dynamického programovania s jednoduchým rekurzívnym riešením pomocou grafov a tabuľky.
|
|
|
Využití dynamického programování v grafových algoritmech
Biloš, Martin ; Křivka, Zbyněk (oponent) ; Burgetová, Ivana (vedoucí práce)
Tato práce se zabývá grafovými algoritmy, jejich využitím a přínosem optimalizační metody dynamického programování. Tento přínos je předveden uživateli pomocí aplikace. Grafové algoritmy najdou využití v mnoha odvětvích lidské činnosti i dnes. Používají se ve směrování paketů nebo například v navigaci. V práci jsou zpracovány tři metody, které patří mezi grafové algoritmy. Tyto problémy řeším klasickým i dynamickým způsobem a následně zjištěná data jsou porovnána.
|
|
|
Online systém pro vizuální geo-lokalizaci v přírodním prostředí
Pospíšil, Miroslav ; Čadík, Martin (oponent) ; Brejcha, Jan (vedoucí práce)
Cílem této diplomové práce je vytvořit online systém, který bude fungovat jako demonstrační aplikace pro prezentaci výsledků vizuální geo-lokalizace v přírodním a horském prostředí. Systém nabídne uživateli možnost vybrat si jednu z předdefinovaných fotografií nebo nahrát vlastní fotografii výběrem souboru nebo zadáním URL adresy. Systém bude hledat pozici kamery daného obrázku na základě vizuální geo-lokalizace. Geo-lokalizace využívá horizontu hor jako klíčovou charakteristiku pro vyhledávání podobných horizontů. Křivka horizontu je extrahována z fotografie plně automatickým algoritmem, založeným na strojovém učení s učitelem a dynamickém programování. Vizuální geo-lokalizace probíhá na serveru, který využívá nový inverzní index s cachovací politikou umožňující další škálování systému. Server zpracuje detekovanou křivku horizontu a vrátí nejlepší kandidáty na výsledky, které jsou pak vizualizovány uživateli formou klasické mapy, detailního satelitního pohledu a vykreslení nalezeného panoramatu.
|
|
|
Poloautomatická diagnostika síťových protokolů
Svoboda, Ondřej ; Ryšavý, Ondřej (oponent) ; Holkovič, Martin (vedoucí práce)
Tato práce se zabývá poloautomatickou diagnostikou síťových protokolů. Řeší se zde, jak z příkladů komunikace sestavit obecný popis protokolů. Nejprve jsou představeny různé techniky odposlechu síťového provozu spolu s programy, které se často k odchytávání komunikace používají. Také budou popsány některé známé síťové protokoly se zaměřením na jejich komunikační zprávy. V další části budou popsány již existující metody získávání popisu z příkladů a definovány vlastnosti těchto metod. Následuje návrh architektury vyvíjeného nástroje společně s návrhem metod tvorby popisu protokolu. Další část se věnuje implementaci vytvářeného nástroje a na závěr je tento nástroj otestován a jsou s ním prováděny experimenty.
|
|
|
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.
|
|
|
Návrh dynamických rozhodovacích strategií pro obchodování na futures trzích
Vosáhlo, Jaroslav ; Guy, Tatiana Valentine (vedoucí práce) ; Lachout, Petr (oponent)
Práce se zabývá problematikou obchodování na komoditních trzích z hlediska investičního spekulanta a zaměřuje se na tzv. komoditní futures kontrakty. Cílem práce je pomocí metod dynamického programování a přibližného dynamického programování navrhnout optimální strategii a tuto strategii otestovat na reálných datech. K dosažení úspěšné strategie jsou použity prostředky bayesovské statistiky pro předpovědi chování náhodných veličin a rizikové ukazatele pro návrh míry opatrnosti při obchodování. Algoritmus je otestován v programu Matlab na více než 15 tisících obchodovacích dnech.
|
|
|
Lot-sizing problém
Kafka, Ondřej ; Branda, Martin (vedoucí práce) ; Bejda, Přemysl (oponent)
Název práce: Lot-sizing problém Autor: Ondřej Kafka Katedra: Katedra pravděpodobnosti a matematické statistiky Vedoucí bakalářské práce: RNDr. Martin Branda, Ph.D. Abstrakt: V předložené práci se seznámíme se základními pojmy z oblasti lot-sizingu. Představíme si Wagner-Whitinův problém a odvodíme algoritmus dynamického programování, jak jej řešit. Dále se podíváme na případ problému PCLSP (Profit maximizing capacitated lot size problem) s pevný- mi cenami a zanedbatelnými přípravnými náklady a budeme jej řešit pomocí speciálního algoritmu lineárního programování. Vše se pokusíme vysvětlit na konkrétních příkladech. V závěru práce ověříme efektivitu uvedených algoritmů pomocí numerické studie na náhodných datech, porovnáme rychlost naprogramovaných algoritmů s profesionálním optimalizačním nástrojem Gurobi. Klíčová slova: Lot sizing, dynamické programování, lineární programování
|
|
|
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.
|
|
| |
host ::
RSS.