|
|
Srovnávací výpočty algebraických rovnic
Nečasová, Gabriela ; Kunovský, Jiří (oponent) ; Šátek, Václav (vedoucí práce)
Práce se zabývá tématem srovnávacích výpočtů algebraických rovnic. Práce nejprve popisuje srovnání celkového počtu operací u přímých a iteračních metod, zároveň na konkrétních příkladech demonstruje metody a vysvětluje použití přímých a iteračních metod. V další části práce se zaměřuji na možné metody převodu soustav lineárních algebraických rovnic (SLAR) na soustavy diferenciálních rovnic (SDR). V závěru je popsán způsob práce s programy TKSL/C, Matlab a Maple. V rámci bakalářské práce bylo navrženo grafické uživatelské rozhraní pro program TKSL/C sloužící k pohodlné komunikaci s programem. Grafické uživatelské rozhraní bylo otestováno na konkrétních úlohách demonstrujících převod SLAR na SDR.
|
|
|
Matematické modely v logistice
Nevrlý, Vlastimír ; Holešovský, Jan (oponent) ; Popela, Pavel (vedoucí práce)
Cílem práce je modelovat dopravní sítě s charakterem podobným reálným sítím a analyzovat závislost výpočtové náročnosti na velikosti sítě pomocí testovacích výpočtů na původním optimalizačním modelu pro podporu koncepčních rozhodnutí v oblasti odpadového hospodářství nazývaného NERUDA. Tyto výpočty jsou provedeny na základě znalosti modelu NERUDA. Výsledky jsou následně zpracovány a patřičně vyhodnoceny.
|
|
|
Statistická analýza intervalových dat
Troshkov, Kirill ; Antoch, Jaromír (vedoucí práce) ; Branda, Martin (oponent)
Tradiční statistická analýza začíná výpočtem základních statistických charakteristik jako je výběrová střední hodnota E, výběrový rozptyl V , kovariance či korelace. Při výpočtu těchto charakteristik se většinou předpokládá, že odpo- vídající hodnoty dat jsou přesně známé. Ve skutečnem světě existují situace, kdy je možné získat více vypovídající informace tím, že soubor statistických dat bude intervalového typu. Například, naměřená denní maximální a minimální teplota dává realističtější pohled na počasí než obyčejné průměrné hodnoty. Při analýze životního prostředí dostáváme naměřené hodnoty znečištění jezera x(t) v různých časových okamžicích t, přičemž bychom potřebovali odhadnout statistické charak- teristiky jako je střední hodnota, rozptyl nebo korelace s jinými měřeními. Jiný příklad je z finančního prostředí. Minimum a maximum cen transakcí, denně za- znamenané pro nějaký soubor akcií poskytuje víc relevantních údajů pro finanční experty, kteří vyhodnocují akcie a volatilitu ve stejný den. Pro tyto a mnohé další případy musíme modifikovat existující statistické postupy, abychom je mohli apli- kovat na data intervalového typu. V této práci se pokusíme rozebrat statistické algoritmy, jejich složitost a modifikace vhodné pro aplikaci na intervalová data v případě výpočtu střední hodnoty,...
|
|
|
Computational Complexity in Graph Theory
Jelínková, Eva ; Kratochvíl, Jan (vedoucí práce) ; Manlove, David (oponent) ; Fiala, Jiří (oponent)
Název práce: Výpočetní složitost v teorii grafů Autor: Eva Jelínková Katedra: Katedra Aplikované Matematiky Vedoucí disertační práce: Prof. RNDr. Jan Kratochvíl, CSc., Katedra Aplikované Matematiky Abstrakt: Zabýváme se problémy teorie grafů, zejména z hlediska výpočetní složitosti. V první části práce se věnujeme výpočetní složitosti problémů sou- visejících se Seidelovým přepnutím grafů. Uvažujeme rozhodující problém, zda daný graf lze přepnout tak, aby obsahoval nejvýše daný počet hran. Dokážeme, že tento problém je NP-úplný, dokonce i pro grafy s omezenou hustotou. Částečně tak odpovídáme na otázku Matouška a Wagnera [Dis- crete Comput. Geom. 52, no. 1, 2014]. Popisujeme také nekonečně mnoho grafů H, pro které je NP-těžké rozhodnout, zda pro daný graf existuje graf, který je s ním ekvivalentní v přepnutí, a zároveň neobsahuje H jako induko- vaný podgraf. Tímto řešíme otevřený problém Kratochvíla, Nešetřila a Zýky [Annals of Discrete Math. 51, 1992]. Ve druhé části práce se zabýváme tématem párování s preferencemi. Zaměřujeme se na problém trhu s domy, konkrétně na model s duplicitními domy. Popisujeme 2-aproximační algoritmus pro maximální počet spoko- jených agentů v případě,...
|
|
|
NP vyhledávací problémy
Jirotka, Tomáš ; Krajíček, Jan (vedoucí práce) ; Pudlák, Pavel (oponent)
Název práce: NP vyhledávací problémy Autor: Tomáš Jirotka Katedra: Katedra algebry Vedoucí diplomové práce: Prof. RNDr. Jan Krajíček, DrSc. Abstrakt: Práce shrnuje dosavadní výsledky v oblasti NP vyhledávacích problémů. Podrobně diskutujeme otázku složitosti faktorizace celých čísel a před- kládáme výsledky, které zařazují tento problém do již známých složitostních tříd a v jistém smyslu se jej snaží separovat z PLS. Dále definujeme několik nových vyhledávacích problémů. Klíčová slova: Výpočetní složitost, TFNP, faktorizace čísel.
|
|
|
Computational Homotopy Theory
Krčál, Marek ; Matoušek, Jiří (vedoucí práce) ; Pultr, Aleš (oponent) ; Romero Ibáñez, Ana (oponent)
dizertační práce "Výpočetní homotopická teorie": Tato práce studuje výpočetní složitost několika základních problémů algebraické topologie, které mají souvislost s otázkami v kombinatorice a výpočetní ge- ometrií. Problém rozšiřitelnosti je zadán topologickými prostory X, Y, podpros- torem A ⊆ X a (spojitým) zobrazením f : A → Y . A otázka je, zda f může být rozšířeno na celý prostor X. Předpokládáme, že X, Y a A jsou zadány jako konečné simpliciální komplexy a f jako simpliciální zobrazení. Výpočetní složitost budeme zkoumat za předpokladu, že Y je d-souvislý pro nějaké d ≥ 1. Jinak je známo, že z teorie grup plyne, že problém rozšiřitel- nosti je nerozhodnutelný. Zde dokážeme, že rozšiřitelnost je i při tomto předpokladu nerozhod- nutelná, pokud dim X dosáhne hodnoty 2d+2. Na druhou stranu pro každou pevnou hodnotu dim X ≤ 2d + 1 nalezneme algoritmus, který řeší problém rozšiřitelnosti v polynomiálním čase. Ukážeme, že složitost výpočtu množiny všech homotopických tříd zo- brazení X → Y má podobnou charakteristiku. Dále uvážíme problém homotopických grup πk(Y ) pro 1-souvislý prostor Y a dimenzi k ≥ 2. První algoritmus na jejich výpočet našel Brown v roce 1957. My ukážeme, že πk(Y ) lze vypočíst v polynomiálním čase pro každou pevnou dimenzi k ≥ 2. Na druhou stranu dokážeme, že výpočet πk(Y ) je...
|
|
| |
|
|
Structural properties of graphs and eficient algorithms: Problems Between Parameters
Knop, Dušan ; Fiala, Jiří (vedoucí práce)
Strukturální vlastnosti grafů a efektivní algoritmy: Problémy separující parametry Dušan Knop Parametrizovaná složitost se v přůběhu posledních dvou dekád stala jednou z nejvýznamějších oblastí výpočetní složitosti. Strukturální vlastnosti grafů (také nazývané grafové šířky) hrají dnes centrální roli jak v teorii grafů tak v návrhu (parametrizovaných) algoritmů. V těto práci za pomoci studia konkrétních problémů poukazujeme na souvislost strukturálních vlastností grafů a možnosti získání parametrizovaného algoritmu. Předvádíme proto parametrizované algo- ritmy a těžkostní redukce pro problémy Target Set Selection, Minimum Length Bounded Cut a další. Vstupem problému Minimum Length Bounded Cut je graf, dva jeho vrcholy (zdroj a stok) a kladné celé číslo L. Úkolem pak je naleznout minimální množinu hran po jejímž odebrání bude vzdálenost mezi zdrojem a stokem více než L. Ukazujeme, že je možné naleznout optimální řešení pro tento problém algoritmem s časem běhu f(k)n, kde f je vyčíslitelná funkce a k je tree-depth n vrcholového grafu na vstupu. Naopak takovýto algoritmus nemůže existovat pro parametr tree-width (pokud FPT ̸= W[1]). V současné době je jen velmi málo známých problémů s touto vlastností....
|
|
|
Výpočetní složitost problémů kombinatorické optimalizace pro specifické třídy grafů
Masařík, Tomáš ; Fiala, Jiří (vedoucí práce)
Tato diplomová práce se zabývá hranovou značkovatelností grafu v závislosti na parametrech p, q a λ. Pro parametry p = 2 a q = 1 jsme dokázali dichotomii. Tedy, že problém λ′ (2,1)-značkovatelnosti grafu je polynomiální pro λ ≤ 4 a NP- úplný pro λ > 4. Hranice NP-úplnosti se tedy posouvá o jedna oproti vrcholové variantě problému, λ(p,q)-značkovatelnosti grafu, která byla již vyřešena dříve. Pro polynomiální případy získáme poměrně snadnou charakterizaci pomocí kruž- nic a cest rozšířených o několik dalších vrcholů. K NP-převodu využíváme jeden z poměrně klasických NP-úplných problémů Monotónní všude různý 3-SAT. Celý důkaz převodu je rozdělen na čtyři části, neboť kromě rozlišení sudých a li- chých λ, bylo třeba vyvořit ještě speciální převody pro λ = 5 i λ = 6. 1
|
|
|
Logic circuits as models of computation
Naumenko, Mykhailo ; Kazda, Alexandr (vedoucí práce) ; Kompatscher, Michael (oponent)
Tato práce se zaměřuje na studium logických obvodů. Vykládáme v ní teorii logických obvodů podle učebnice "Models of Computation" od Johna E. Savage a řešíme některé úlohy a cvičení z této učebnice. V této práci najdete klíčové pojmy související s logickými obvody. Věnovali jsme znač- nou pozornost hlavně odhadům dolních mezí velikostí obvodů a velikostí formulí obecných booleovských funkcí. Sestrojili jsme také několik jednoduchých příkladů známých obvodů a ukázali jsme, jak lze navrhnout další obvody. 1
|
host ::
RSS.