|
| |
|
|
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...
|
|
| |
|
|
Problems in discrete geometry
Patáková, Zuzana ; Matoušek, Jiří (vedoucí práce) ; Bárány, Imre (oponent) ; Valtr, Pavel (oponent)
dizertační práce Problémy diskrétní geometrie Zuzana Patáková V této práci se věnujeme třem různým problémům z oblasti diskrétní geometrie. Společným pojítkem těchto problémů je, že jejich řešení využívá algebraické metody. První problém se zabývá tzv. polynomiální metodou, která konečnou množinu bodů rozdělí pomocí nulové množinu polynomu. Limitujícím fak- torem této metody je, co dělat s body, které leží v nulové množině získaného polynomu? V práci představujeme obecnou verzi, která řeší popsanou situaci, a jako aplikaci uvádíme nový algoritmus pro tzv. semialgebraický range searching problém. V druhé části práce se věnujeme studiu Ramseyových funkcí semialge- braických predikátů. Conlon, Fox, Pach, Sudakov a Suk zkonstruovali první příklady semialgebraických predikátů s Ramseyovou funkcí zespoda odhad- nutou věžovitou funkcí. My snížíme dimenzi příslušného prostoru v jejich konstrukci a jako důsledek ukážeme novou geometrickou větu Ramseyova typu s velkou Ramseyovou funkcí. V poslední části se zabýváme samodlážditelnými simplexy. Simplex S je k-samodlážditelný, pokud je sjednocením k navzájem shodných simplexů s disjunktními vnitřky, které jsou navíc podobné simplexu S. V...
|
|
|
Lipschitzovská zobrazení diskrétních množin
Kaluža, Vojtěch ; Matoušek, Jiří (vedoucí práce) ; Šámal, Robert (oponent)
V této práci se zabýváme Feigeho otázkou existence konstantně lipschitzov- ské bijekce každé n2 -prvkové podmnožiny S ⊂ Z2 na pravidelnou mřížku n × n bodů v Z2 . Uvedeme řešení tohoto problému v případě, že body v S jsou uspořá- dány ve tvaru dlouhého obdélníku nebo ve tvaru čtverce bez vnitřku. Hlavní částí práce je rešerše článků Buraga a Kleinera [2] a McMullena [12], zabývajících se problémem existence bilipschitzovsky neekvivalentních separovaných sítí, který je podobný Feigeho problému. Dle těchto článků zkonstruujeme separovanou síť v R2 bilipschitzovsky neekvivalentní Z2 na základě konstrukce kladné omezené měřitelné funkce, která není Jakobiánem žádného bilipschitzovského homeomor- fismu skoro všude. Ukážeme McMullenovu konstrukci takové funkce a doplníme důkaz její správnosti. 1
|
|
| |
|
| |
|
|
Samodlážditelné simplexy
Safernová, Zuzana ; Matoušek, Jiří (vedoucí práce)
V předložené práci se zabýváme problémem k-samodlážditelnosti čtyřstěnů. Simplex S je k-samodlážditelný, pokud se dá rozdělit na k navzájem shodných simplexů (s disjunktními vnitřky), jež jsou navíc podobné původnímu simplexu S. V rovině jsou všechny k-samodlážditelné trojúhleníky charakterizovány, na druhou stranu jediné k-samodlážditelné simplexy v dimenzi d>=3 jsou známy pro hodnotu k=md , kde m>=2, tzv. Hillovy simplexy. V práci dokážeme, že v dimenzi 3 existují k-samodlážditelné čtyřstěny pouze pro k=m3 , což částečně potvrzuje Hertelovu domněnku, že jediné k-samodlážditelné čtyřstěny jsou Hillovy. Domníváme se, že k= md je nutná podmínka pro existenci k-samodlážditelných simplexů (d>3).
|
|
|
Vysokorychlostní paketové DMA přenosy do FPGA
Kubálek, Jan ; Matoušek, Jiří (oponent) ; Martínek, Tomáš (vedoucí práce)
Tato práce se zabývá návrhem, implementací, testováním a měřením firmwarového modulu pro čip FPGA, který zajišťuje DMA přenosy síťových dat z RAM počítače do samotného čipu na síťové kartě. Tyto přenosy jsou prováděny přes sběrnici PCIe rychlostí až 100Gb/s s možností podpory rychlostí 200 Gb/s a 400 Gb/s. Cílem této technologie je umožnit zpracování síťového provozu za účelem údržby páteřních uzlů sítě a datových center. Modul je současně navržen tak, aby jej bylo možné použít na různých typech FPGA čipů a to především od firem Xilinx a Intel.
|
|
|
Network Traffic Generator for Testing of Packet Classification Algorithms
Janeček, David ; Orsák, Michal (oponent) ; Matoušek, Jiří (vedoucí práce)
Efforts to improve classification algorithms are being slowed down by lack of data required for testing. For confidentiality and security reasons it is difficult to obtain real data. Good rule set generation tools, such as ClassBench-ng, exist. However, in order to evaluate proper functioning, throughput, power consumption, and other properties of packet classification algorithms, it is necessary to also use network traffic. Subject of this thesis is creating a network traffic generator that would allow for testing of such properties using IPv4, IPv6, and OpenFlow1.0 rules created by ClassBench-ng. The work explores different ways to achieve this, which resulted in several versions of the generator. Those were experimented with and evaluated. Implementation was done using Python. The primary result is a generator combining multiple approaches to achieve the best properties of created header traces. Another contribution of this thesis is a tool that was necessary to create for analyzing rule sets and evaluating generated header traces.
|
host ::
RSS.