|
Výpočet triangulace s minimální váhou (MWT)
Charvát, Pavel ; Kolingerová, Ivana (vedoucí práce) ; Ferko, Andrej (oponent)
Pro výpočet MWT už dlouhou dobu není znám žádný polynomiální algoritmus a ani se neví, zda je NP. Tento stav zůstává podle našich zdrojů stále neznámý. V práci uvádíme přehled možných přístupů k problému, jako jsou modifikace zadání se známou složitostí nebo hledání nejrůznějších heuristik a aproximací, umožňujících v rozumném čase najít přesné nebo alespoň přibližné řešení, a porovnáváme jejich kvalitu v konkrétních situacích. Hlavní částí je popis a implementace efektivní heuristiky s (téměř?) lineární očekávanou složitostí pro rovnoměrně rozložené body v konvexní oblasti. Algoritmus modifikuje Drysdalův algoritmus hledání kandidátních hran GT a Beuroutiho výpočet modifikovaného LMT-skeletonu, u kterého navíc doplňujeme důkazy správnosti. MWT dokončíme z grafu kandidátních hran v O(n · d3 + n · d2+k), kde d je maximální stupeň vrcholu a k je největší počet vnitřních komponent nějaké stěny skeletonu. Dále navrhujeme novou aproximaci s polynomiální složitostí a (téměř?) lineární očekávanou složitostí, která se jen zřídka liší od optimální triangulace, a lze dokázat její nejhorší možný aproximační faktor O(1). Aproximace kombinuje heuristiku modifikovaného LMT-skeletonu s omezenou quasi-greedy triangulací a s triangulací minimální kostry. Minimální triangulace nakonec aplikujeme v praktickém problému výpočtu...
|
|
Konverze vzorkovací frekvence
Chrobák, Martin ; Provazník, Ivo (oponent) ; Kozumplík, Jiří (vedoucí práce)
Tato bakalářská práce se zabývá návrhem postupu pro změnu vzorkovacího kmitočtu signálu EKG pomocí tří metod: s celočíselným faktorem D/I, s libovolným faktorem (I=8) a s libovolným faktorem (I=16). Konverze vzorkovací frekvence má být provedena z 500 do 360 Hz a z 360 do 500 Hz v časové i frekvenční oblasti. K tomu se využívá profesionální výpočetní prostředí MATLAB, které je výborné pro zpracování signálů. Výstupem z této bakalářské práce by mělo být doporučení, jaké filtry, s jak dlouhou impulsní charakteristikou, jsou pro tuto změnu vzorkovací frekvence nejvýhodnější.
|
|
Zabezpečení přenosu dat Reedovými-Solomonovými kódy
Šalanský, Jan ; Šporik, Jan (oponent) ; Němec, Karel (vedoucí práce)
Tato bakalářská práce se zabývá zabezpečením přenosu dat Reedovými-Solomonovými kódy. Rozebírá konstrukci kódu, způsob kódování a především prostředky dekódování. Postupně popisuje jednotlivé fáze dekódování: výpočet syndromového vektoru, nalezení lokalizačního polynomu chyb, určení pozic chybných symbolů Chienovým vyhledáváním a výpočet opravných symbolů pomocí Forneyova algoritmu. Pro nalezení lokalizačního polynomu chyb srovnává tyto základní algoritmy: Petersonův–Gorensteinův–Zierlerův algoritmus, Berlekampův-Masseyův algoritmus a rozšířený Euklidův algoritmus. Na základě těchto teoretických poznatků je zde ukázán podrobný proces návrhu a softwarové realizace jednoduchého protichybového systému. Návrh systému začíná zvolením vhodného Reedova-Solomonova kódu R-S(63,39). Pokračuje konstrukcí základních algebraických struktur pro tento kód a odvozením kodéru a dekodéru. Návrh protichybového systému končí ukázkovým výpočtem kódování a dekódování. Na základě těchto výpočtů a za použití ukázkových příkladů uvedených ve zdrojové literatuře byl naprogramován výsledný protichybový systém pro platformy MS Windows a Linux.
|
|
Matematické metody zabezpečení přenosu digitálních dat
Bartušek, Petr ; Kureš, Miroslav (oponent) ; Vašík, Petr (vedoucí práce)
Tato diplomová práce se zabývá analýzou zabezpečení digitálních dat pomocí CRC. V práci je popsán princip bezpečnostního kódování, zejména pak zabezpečení dat pomocí CRC, u něhož je vysvětlen matematický princip zabezpečení, softwarová implementace a popis využívaných generujících polynomů. Hlavním cílem práce je pak testování nedetekovaných chyb a zjištění jejich počtu pro následný výpočet pravděpodobnosti vzniku nedetekované chyby. Práce je doplněna o několik programů naprogramovaných v prostředí Matlab.
|
|
O problémech seřazení při řízení servisních operací
Lín, Václav ; Vomlel, Jiří (vedoucí práce) ; Jiroušek, Radim (oponent) ; Kouba, Zdeněk (oponent) ; Ottosen, Thorsten Jorgen (oponent)
Jedním z témat operačního managementu je udržení provozuschopnosti produkčních systémů a rychlé obnovení provozu v případě poruchy. V předkládané práci se zabýváme problémem optimálního seřazení dostupných servisních operací při odstraňování poruchy produkčního systému. Cílem je nalezení posloupnosti operací s nejnižší očekávanou cenou nebo dobou opravy. Studujeme několik variant tohoto problému známých z literatury. Zabýváme se výpočetní složitostí, algoritmy a vztahem k teorii rozvrhů.
|
|
Gröbnerovy báze, Čuang-c’ův algoritmus a ataky multivariačních kryptosystémů
Doktorová, Alice ; Tomáš, Jiří (oponent) ; Kureš, Miroslav (vedoucí práce)
Tato diplomová práce je zaměřena na multivariační kryptosystémy. Její součástí je přehled komutativní algebry se zaměřením na Gröbnerovy báze. Z algoritmů jsou studovány především ty, které využívají Gröbnerovy báze a to Buchbergerův algoritmus, který je již implementován v programu Wolfram Mathematica, a F4 algoritmus, pro který byl vytvořen programový balík v prostředí Wolfram Mathematica. Jako poslední je popsán Čuang-c'ův algoritmus, pro který byl pro zjednodušení vytvořen program pro počítání Lagrangeova interpolačního polynomu v jazyce Python.
|
|
Workforce Optimisation
Pacinda, Štefan ; Barták, Roman (vedoucí práce) ; Klusáček, Dalibor (oponent)
Název práce: Optimalizace pracovních sil Autor: Štefan Pacinda Katedra / Ústav: Katedra teoretické informatiky a matematické logiky Vedoucí diplomové práce: doc. RNDr. Roman Barták Ph.D., KTIML Abstrakt: Optimalizace pracovních sil se zabývá udržováním produktivity pracovní síly například v nemocnicích, či dopravních společnostech. Zahrnuje problém rozhodování o nutnosti použití jednotlivých dovedností v každém okamžiku, stejně jako rozhodování o množství vyžadovaného personálu. Po těchto rozhodnutí následuje řešení problému alokování určitých zaměstnanců ke směnám za současného plnění požadavků na dovednosti ale i jiných omezení odvozených z na příklad právních regulací, odborových dohod a vlastních preferencí. Tato práce se zabývá optimalizací pracovních sil, tedy optimálním nasazením personálu na směny za účelem pokrytí požadavků na zdroje, které se mění v čase. V této práci je řešený problém detailně rozebrán, popsán a namodelován jako problém celočíselného programování. Jsou zde prezentovány detaily o implementaci a vyčerpávající analýza a experimenty s instancí problém z praxe za účelem prokázání naplnění cílů, které si práce klade. Klíčová slova: Rostering, Optimalizace pracovních sil, Rozvrhování směn
|
|
Sparse robust portfolio optimization via NLP regularizations
Branda, Martin ; Červinka, Michal ; Schwartz, A.
We deal with investment problems where we minimize a risk measure\nunder a condition on the sparsity of the portfolio. Various risk measures\nare considered including Value-at-Risk and Conditional Value-at-Risk\nunder normal distribution of returns and their robust counterparts are\nderived under moment conditions, all leading to nonconvex objective\nfunctions. We propose four solution approaches: a mixed-integer formulation,\na relaxation of an alternative mixed-integer reformulation and\ntwo NLP regularizations. In a numerical study, we compare their computational\nperformance on a large number of simulated instances taken\nfrom the literature.
|
|
C library for symbolic manipulation
Gurský, Štefan ; Bednárek, David (oponent) ; Holan, Tomáš (vedoucí práce)
There are many programs doing symbolic manipulation with mathematical expressions. They are called Computer Algebra Systems and most of them contain some programming language. In this bachelor thesis a library for C programming language was created that allows using C as a language for symbolic manipulation. With provided functions user can store mathematical expressions in C variables and work with them in an easy and convenient way. It is possible to build expressions containing standard mathematical operations and functions, reduce them, expand them, find derivatives and Taylor polynomials. The library (called SymCe) is easy to understand not only for user, but also for a programmer that wishes to see its inner working and possibly extend it. Simplicity is the main feature that distinguishes SymCe from other similar pieces of software.
|
|
Aplikace optimalizačních metod na problémy výroby elektřiny
Šumbera, Jiří ; Dlouhý, Martin (vedoucí práce) ; Pelikán, Jan (oponent) ; Hančlová, Jana (oponent)
Tato práce se zabývá aplikací optimalizačních metod založených na lineárním a celočíselném programování na různé problémy vyskytující se v energetice při výrobě elektřiny. Cílem této práce je ověřit aplikovatelnost těchto optimalizačních metod na formulování a následné vyřešení různých optimalizačních úloh vznikajících při výrobě elektřiny, a tím i zjistit výhody a nevýhody těchto metod. Úvodní kapitoly popisují hlavní charakteristiky energetických trhů, včetně historického kontextu a hlavní regulace. Fundamentální vlastnosti trhů s elekřinou jsou popsány jak z pohledu skutečného provozu tak z hlediska modelování. Dále jsou popsány výhody optimalizačních metod a modelování obecně, s důrazem na přípustnost a optimalitu řešení a dále na výhody citlivostních analýz, které lze v reálném provozu jen obtížně uskutečnit. V hlavní části disertace jsou optimilizační metody aplikovány na tři případové studie, z nichž každá se zabývá konkrétním problémem vznikajícím při výrobě elektřiny. První úloha řeší maximalizaci zisku paroplynové elektrárny na Slovensku na denním trhu s elektřinou. V úloha obsahuje jak technická, tak i komerční omezení. Druhá úloha se zabývá reprezentací dvourozměrné produkční funkce, která se primárně vyskytuje u vodních elektráren s velkou variací výšky hladiny. Je prezentováno několik aproximačních metod původní funkce založených na lokální linearizaci. Tyto aproximační metody jsou dale srovnány dle jejich teoretické i praktické výpočetní náročnosti. Ve třetí úloze jsou namodelovány ceny na německém denim trhu v roce 2011. Na rozdíl od dvou přechozích úloh neobsahuje problém optimalizační úlohu jediného výrobce, ale modeluje významnou cast celého trhu. I z tohoto důvodu tvoří úlohu obecná technická omezení elektráren, jejichž parametry byly odhadnuty. Kombinací informace o celkkové dostupnosti spolu s odhadnutou účinností umožňuje sestavit relevantní nákladovou křivku pro každý den roku. V několika scénářích je testován dopad odhadnutých vstupích parametrů. Volba zkoumaných problémů vychází z motivace pokrýt množinu úloh vznikajících při výrobě elektřiny z celé řady kritérií. Tři vybrané úlohy pokrývají široké spektrum od rozhodnutí jednotlivé elektrárny až po modelování celého trhu s elektřinou. V úlohách jsou prezentovány různé formulace produkční funkce od lineárního vztahu až po dvourozměrnou závislost. Zatímco každá případová studie dává odpověď na konkrétní otázku, všechny případy ukazují, jak snadno lze úlohy vznikající při výrobě elektřiny řešit pomocí optimalizačních metod založených na lineárním a celočíselném programování. Toho je dosaženo především díky schopnosti daných metod aproximovat i nelineární vztahy a omezení nad nekonvexními množinami a nalézat globální řešení v přípustných časech. Neméně významná je i snadná možnost provádět scénářové analýzy a citlivosti, jak je ukázáno v jednotlivých řešených úlohách.
|
host ::
