|
| |
|
|
Computational Homotopy Theory
Krčál, Marek ; Matoušek, Jiří (advisor) ; Pultr, Aleš (referee) ; Romero Ibáñez, Ana (referee)
of doctoral thesis "Computational Homotopy Theory": We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of compu- tational complexity. The extension problem asks, given topological spaces X, Y , a subspace A ⊆ X, and a (continuous) map f : A → Y , whether f can be extended to a map X → Y . For computational purposes, we assume that A, X, Y are represented as finite simplicial complexes and f as a simplicial map. We study the problem under the assumption that, for some d ≥ 1, Y is d- connected, otherwise the problem is undecidable by uncomputability of the fundamental group; We prove that, this problem is still undecidable for dim X = 2d + 2. On the other hand, for every fixed dim X ≤ 2d + 1, we obtain an algorithm that solves the extension problem in polynomial time. We obtain analogous complexity results for the problem of determining the set of homotopy classes of maps X → Y . We also consider the computation of the homotopy groups πk(Y ), k ≥ 2, for a 1-connected Y . Their computability was established by Brown in 1957; we show that πk(Y ) can be computed in polynomial time for every fixed k ≥ 2. On the other hand, we prove that computing πk(Y ) is #P-hard if k is a part of input. It is a strengthening of...
|
|
| |
|
|
Problems in discrete geometry
Patáková, Zuzana ; Matoušek, Jiří (advisor) ; Bárány, Imre (referee) ; Valtr, Pavel (referee)
of doctoral thesis Problems in discrete geometry Zuzana Patáková This thesis studies three different questions from discrete geometry. A common theme for these problems is that their solution is based on algebraic methods. First part is devoted to the polynomial partitioning method, which par- titions a given finite point set using the zero set of a suitable polynomial. However, there is a natural limitation of this method, namely, what should be done with the points lying in the zero set? Here we present a general version dealing with the situation and as an application, we provide a new algorithm for the semialgebraic range searching problem. In the second part we study Ramsey functions of semialgebraic predi- cates. Conlon, Fox, Pach, Sudakov, and Suk constructed the first examples of semialgebraic predicates with the Ramsey function bounded from below by a tower function. We reduce the dimension of the ambient space in their construction and as a consequence, we provide a new geometric Ramsey-type theorem with a large Ramsey function. Last part is devoted to reptile simplices. A simplex S is k-reptile if it can be tiled by k simplices with disjoint interiors that are all mutually congruent and similar to S. We show that four-dimensional k-reptile simplices can exist only for k = m2 , where m ≥ 1...
|
|
|
Lipschitz mappings of discrete sets
Kaluža, Vojtěch ; Matoušek, Jiří (advisor) ; Šámal, Robert (referee)
In this thesis we consider Feige's question of whether there always exists a constantly Lipschitz bijection of an n2 -element set S ⊂ Z2 onto a regular lattice of n × n points in Z2 . We propose a solution of this problem in case the points of the set S form a long rectangle or they are arranged in the shape of a square without a part of its interior points. The main part is a summary of Burago's and Kleiner's article [2] and the article by McMullen [12] dealing with the problem of existence of separated nets in R2 that are not bi-Lipschitz equivalent to the integer lattice. This problem looks similar to Feige's problem. According to these articles we construct a separated net that is not bi-Lipschitz equivalent to the integer lattice, using a positive bounded measurable function that is not the Jacobian of a bi-Lipschitz homeomorphism almost everywhere. We present McMullen's construction of such a function and we complete his proof of its correctness. 1
|
|
| |
|
| |
|
|
Samodlážditelné simplexy
Safernová, Zuzana ; Matoušek, Jiří (advisor)
of the Master thesis Reptile simplices Zuzana Safernová In the present work we study tetrahedral k-reptiles. A d-dimensional simplex is called a k- reptile if it can be tiled in k simplices with disjoint interiors that are all congruent and similar to S. For d=2, triangular k-reptiles exist for many values of k and they have been completely characterized. On the other hand, the only simplicial k-reptiles that are known for d>=3 have k=md , where m>=2 (Hill simplices). We prove that for d=3, tetrahedral k-reptiles exist only for k=m3 . This partially confirms the Hertel's conjecture, asserting that the only tetrahedral k-reptiles are the Hill tetrahedra. We conjecture that k = m^d is necessary condition for existence of d-dimensional simplicial k-reptiles, d > 3.
|
|
|
High-Speed Packet Data DMA Transfers to FPGA
Kubálek, Jan ; Matoušek, Jiří (referee) ; Martínek, Tomáš (advisor)
This thesis deals on the design, implementation, testing and measuring of a firmware module for FPGA chips, which enables DMA transfers of network data from computer RAM to the FPGA chip placed on a network interface card. These transfers are carried out using a PCIe bus on the speed of up to 100 Gbps with the possible support of speeds 200 Gbps and 400 Gbps. The goal of this technology is to allow network data processing for the purpose of maintenance of backbone network nodes and data centers. The module is designed so it can be used on different types of FPGA chips, mainly those produced by companies Xilinx and Intel.
|
|
|
Network Traffic Generator for Testing of Packet Classification Algorithms
Janeček, David ; Orsák, Michal (referee) ; Matoušek, Jiří (advisor)
Pokrok při zdokonalování klasifikačních algoritmů je zpomalován nedostatkem dat potřebných pro testování. Reálná data je obtížné získat z důvodu bezpečnosti a ochrany citlivých informací. Existují však generátory syntetických sad pravidel, jako například ClassBench-ng. K vyhodnocení správného fungování, propustnosti, spotřeby energie a dalších vlastností klasifikačních algoritmů je zapotřebí také vhodný síťový provoz. Tématem této práce je tvorba takového generátoru síťového provozu, který by umožnil testování těchto vlastností v kombinaci s IPv4, IPv6 a OpenFlow1.0 pravidly vygenerovanými ClassBench-ng. Práce se zabývá různými způsoby, jak toho dosáhnout, které vedly k vytvoření několika verzí generátoru. Vlastnosti jednotlivých verzí byly zkoumány řadou experimentů. Implementace byla provedena pomocí jazyku Python. Nejvýznamnějším výsledkem je generátor, který využívá principů několika zkoumaných přístupů k dosažení co nejlepších vlastností. Dalším přínosem je nástroj, který bylo nutné vytvořit pro analýzu užitých sad klasifikačních pravidel a vyhodnocení vlastností vygenerovaného síťového provozu.
|
guest ::
RSS feed.