Národní úložiště šedé literatury Nalezeno 6 záznamů.  Hledání trvalo 0.00 vteřin. 
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...
Computational Complexity of Graph Planarity Testing
Krčál, Marek ; Bálek, Martin (vedoucí práce) ; Škovroň, Petr (oponent)
V tomto článku ukážeme, že testování planarity je v SL (symetrický nedeterministický LOGSPACE). Hlavní část našeho důkazu je redukce na problém testování rovinnosti grafu s maximálním stupněm tři. Povšiměte si, že obvyklé nahrazování vrchol větších stupňů "malými kružnicemi" může rovinnost pokazit, musíme si počínat šikovněji. Testování rovinnosti grafu s maximálním stupněm tři už bylo vyřešeno ve článku "Symmetric complementation" Johna Reifa. Už dříve Meena Mahajan a Eric Allender ("Complexity of planarity testing") ukázali, že testování rovinnosti je v SL. Jejich důkaz se však sestává z SL implementace velmi složitého paralelního algoritmu od Johna Reifa a Vijayi Ramachandran ("Planarity testing in parallel"). Ten je však nejspíše zbytečně komplikovaný pro účely prostorové složitosti. Tento výsledek spolu s nedávným průlomem Omera Reingolda dokazujícího, že SL = L ("Undirected ST-connectivity in log-space") zcela řeší otázku složitosti testování planarity, protože to je těžké pro L (toto je též dokázáno v "Complexity of planarity testing"). Zkonstruujeme algoritmus používající logaritmický prostor, který převede vstupní graf G na G0 s maximálním stupněm 3 tak, že G je rovinný tehdy a jen tehdy, když G0 je rovinný.
Online algorithms for variants of bin packing
Veselý, Pavel ; Sgall, Jiří (vedoucí práce) ; Krčál, Marek (oponent)
Online algoritmus se musí rozhodovat okamžitě a nevratně podle části vstupu bez jakékoliv znalosti budoucí části vstupu. Představíme kompetitivní analýzu online algoritmů, což je standardní analýza nejhoršího případu, a hlavní výsledky této analýzy pro problém online bin packingu a pro některé jeho varianty. V bin packingu je úkolem naskládat posloupnost položek o maximální velikosti 1 do minimálního počtu košů jednotkové kapacity. Zaměříme se hlavně na barevný bin packing, v němž mají položky také barvu a je zakázáno mít v koši dvě položky stejné barvy vedle sebe. Vylepšíme některé předchozí výsledky pro problém omezený na dvě barvy a představíme první výsledky pro neomezený počet barev. Hlavním výsledkem je optimální 1.5-kompetitivní algoritmus pro důležitý případ, v němž mají všechny položky velikost 0. Pro položky jakékoliv velikosti dokážeme dolní odhad 2.5 a vytvoříme 3.5-kompetitivní algoritmus. Powered by TCPDF (www.tcpdf.org)
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...
Toky a cesty s omezením
Knop, Dušan ; Kolman, Petr (vedoucí práce) ; Krčál, Marek (oponent)
Název práce: Toky a cesty s omezením Autor: Dušan Knop Katedra: Katedra aplikované matematiky Vedoucí diplomové práce: Doc. Mgr. Petr Kolman, PhD, Katedra aplikované matematiky Abstrakt: V předložené práci studujeme problém délkou omezených řezů mezi dvojicí vr- cholů grafu. V tomto problému je cílem odebrat hrany z grafu tak, aby po jejich odebrání měla předem specifikovaná dvojice vrcholů předepsanou vzdálenost. Práce poskytuje přehled o základní literatuře o tomto problému a prezentuje souvislosti s jinými problémy. V rámci tohoto také nabízí mnoho aplikací délkou omezených toků a řezů. Pro tento NP-těžký problém popisuje heuristiky pro redukci dat. Hlavním výsledkem práce pak je polynomiální algoritmus pro sériově-paralelní grafy. Klíčová slova: řezy, sériově-paralelní grafy, algoritmus, složitost
Computational Complexity of Graph Planarity Testing
Krčál, Marek ; Škovroň, Petr (oponent) ; Bálek, Martin (vedoucí práce)
V tomto článku ukážeme, že testování planarity je v SL (symetrický nedeterministický LOGSPACE). Hlavní část našeho důkazu je redukce na problém testování rovinnosti grafu s maximálním stupněm tři. Povšiměte si, že obvyklé nahrazování vrchol větších stupňů "malými kružnicemi" může rovinnost pokazit, musíme si počínat šikovněji. Testování rovinnosti grafu s maximálním stupněm tři už bylo vyřešeno ve článku "Symmetric complementation" Johna Reifa. Už dříve Meena Mahajan a Eric Allender ("Complexity of planarity testing") ukázali, že testování rovinnosti je v SL. Jejich důkaz se však sestává z SL implementace velmi složitého paralelního algoritmu od Johna Reifa a Vijayi Ramachandran ("Planarity testing in parallel"). Ten je však nejspíše zbytečně komplikovaný pro účely prostorové složitosti. Tento výsledek spolu s nedávným průlomem Omera Reingolda dokazujícího, že SL = L ("Undirected ST-connectivity in log-space") zcela řeší otázku složitosti testování planarity, protože to je těžké pro L (toto je též dokázáno v "Complexity of planarity testing"). Zkonstruujeme algoritmus používající logaritmický prostor, který převede vstupní graf G na G0 s maximálním stupněm 3 tak, že G je rovinný tehdy a jen tehdy, když G0 je rovinný.

Viz též: podobná jména autorů
5 Krčál, Martin
Chcete být upozorněni, pokud se objeví nové záznamy odpovídající tomuto dotazu?
Přihlásit se k odběru RSS.