|
| |
|
|
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...
|
|
|
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,...
|
|
|
Meze pro vzdálenostně podmíněné značkování grafů
Kupec, Martin ; Fiala, Jiří (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Problém λ − L(p, q)-značkování je přiřadit vrcholům grafu značky {0, . . . , λ} tak, aby sousední vrcholy měly značky od sebe vzdálené alespoň p a vrcholy se společným sousedem značky od sebe vzdáleny alespoň q. Zabýváme se výpočení složitostí tohoto problému a stanovujeme hraniční hodnoty λ, p a q, pro které se tento problém stává NP těžký. Důkaz je veden promocí dvou různých redukcí. Jedna je z NAE-3SATu, druhá z problémů hranového dobarvení před- barveného grafu. 1
|
|
|
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.
|
|
|
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ů.
|
|
|
Intervalová data a výběrový rozptyl: výpočetní aspekty
Sokol, Ondřej ; Černý, Michal (vedoucí práce) ; Rada, Miroslav (oponent)
Práce se zabývá problematikou výpočtu horní meze výběrového rozptylu v případě, kdy nejsou k dispozici přesná data, ale pouze intervaly, ve kterých tato data s jistotou leží. Obecně je nalezení horní meze výběrového rozptylu ze znalosti pouze intervalových dat NP-těžký problém, ale při splnění určitých podmínek kladených na vstupní intervalová data lze použít některý z efektivních algoritmů. V práci jsou upraveny algoritmy tak, aby, byť i za cenu exponenciální složitosti, dokázaly vždy najít optimální řešení. Cílem práce je porovnat vybrané algoritmy pro výpočet horní meze rozptylu intervalových dat z pohledu průměrné výpočetní složitosti na generovaných datech. Pomocí simulací je ukázáno, že za splnění určitých předpokladů kladených na data je složitost v průměrném případě pouze polynomiální.
|
|
|
Modifikované úlohy čínského listonoše - experimenty
Jelínek, Tomáš ; Fábry, Jan (vedoucí práce) ; Pelikán, Jan (oponent)
Diplomová práce popisuje modifikované úlohy čínského listonoše. Úlohy jsou řešeny pomocí (smíšeného) celočíselného lineárního programování. Modifikované úlohy i použitá metoda řešení (celočíselné programování) patří minimálně do NP složitých úloh. Práce analyzuje, porovnává a odhaduje výpočetní složitost jednotlivých modelů. Z této analýzy je vyvozena použitelnost (tj. řešitelnost v rozumnén čase) modelů pro řešení reálných úloh. Modely se primárně zaměřují na úlohy z městského prostředí, lze je tak aplikovat na problémy jako je optimalizace svozu komunálního odpadu nebo údržby silnic. Pro potřeby práce je naprogramován generátor grafů a zadání úloh.
|
|
|
Algoritmy pro řešení speciálních problémů batohu a jejich výpočetní složitost
Sem, Štěpán ; Ivánek, Jiří (vedoucí práce) ; Kalčevová, Jana (oponent)
Práce se zabývá variantami problému batohu a možnostmi jejich řešení, dále potom vlivem speciálního tvaru konkrétního zadání (instance) na efektivitu testovaného postupu. Předkládá rovněž možnosti převoditelnosti mezi popsanými úlohami, jakož i jejich spojité rozšíření (spojitou relaxaci). Z řad klasických algoritmů popisuje algoritmus L3 a řešení superklesajícího problému batohu, z řad pravděpodobnostních algoritmů Metodu Monte Carlo, simulované žíhání a genetické algoritmy. Diskutovány jsou i další možnosti. Nedílnou součást práce tvoří doprovodná aplikace, která sloužila k vytvoření podkladů zde uváděných a může být rovněž použita k řešení dalších instancí.
|
|
|
Létající amorfní počítač
Petrů, L. ; Wiedermann, Jiří
V příspěvku navrhneme formální model létajícího amorfního počítače a ukážeme, že k libovolnému počítači RAM s libovolně velkým vstupem existuje amorfní počítač, jehož velikost záleží pouze na velikosti vstupu a jenž konkrétně realizuje počítač RAM pro daný vstup s libovolně malou pravděpodobností chyby.
|
host ::
RSS.