|
|
Algebraické vlastnosti barevnosti grafů
Bulánek, Jan ; Kráľ, Daniel (advisor) ; Jelínek, Vít (referee)
We study algebraic tools for proving the existence of graph colorings and focus a classical method of Alon-Tarsi from this area. In particular, we prove Alon-Tarsi Theorem, provide examples of some known applications and give a new application to colorings of squares of cycles.
|
|
|
The Online Labeling Problem
Bulánek, Jan ; Koucký, Michal (advisor) ; Brodal, Gerth (referee) ; Iacono, John (referee)
A sorted array is a fundamental algorithmic concept. Its on-line variant gives rise to the online labeling problem. In the online labeling problem we are given an array of size m and a stream of n integers from the universe {1, ..., r} coming in an arbitrary order. Our task is to maintain all received items in the array in sorted order. The inserted items do not have to be stored consecutively in the array. Since the final order of the items is not known until we see all the items, moves of already inserted items are allowed but should be minimized. We present two algorithms which together provide an optimal solution for almost all values of m as a function of n. We provide tight lower bounds for almost all ranges of m. We introduce a notion of the limited universe and prove lower bounds also in that setting. Some of our lower bounds also apply to randomized algorithms. Powered by TCPDF (www.tcpdf.org)
|
|
|
Datové struktury pro setříděné ukládání dat
Bulánek, Jan ; Koucký, Michal (advisor) ; Kráľ, Daniel (referee)
In this work we study two variants of a bucketing game. This game is used for the lower bound proof of time complexity of item insertion into a sorted array, a data structure for the order maintenance problem. We show that these two variants of the bucketing game have the same time complexity up to a constant factor. Then we show that sorted arrays can use cache efficiently for certain operations. Finally, we present one implementation of the order maintenance data structure using the array of size n1+e.
|
|
|
Data structures for file maintenance problem
Bulánek, Jan
In this work we study two variants of a bucketing game. This game is used for the lower bound proof of time complexity of item insertion into a sorted array, a data structure for the order maintenance problem. We show that these two variants of the bucketing game have the same time complexity up to a constant factor. Then we show that sorted arrays can use cache efficiently for certain operations. Finally, we present one implementation of the order maintenance data structure using the array of size n1+e.
|
|
|
Data structures for file maintenance problem
Bulánek, Jan
In this work we study two variants of a bucketing game. This game is used for the lower bound proof of time complexity of item insertion into a sorted array, a data structure for the order maintenance problem. We show that these two variants of the bucketing game have the same time complexity up to a constant factor. Then we show that sorted arrays can use cache efficiently for certain operations. Finally, we present one implementation of the order maintenance data structure using the array of size n1+e.
|
|
|
The Online Labeling Problem
Bulánek, Jan ; Koucký, Michal (advisor) ; Brodal, Gerth (referee) ; Iacono, John (referee)
A sorted array is a fundamental algorithmic concept. Its on-line variant gives rise to the online labeling problem. In the online labeling problem we are given an array of size m and a stream of n integers from the universe {1, ..., r} coming in an arbitrary order. Our task is to maintain all received items in the array in sorted order. The inserted items do not have to be stored consecutively in the array. Since the final order of the items is not known until we see all the items, moves of already inserted items are allowed but should be minimized. We present two algorithms which together provide an optimal solution for almost all values of m as a function of n. We provide tight lower bounds for almost all ranges of m. We introduce a notion of the limited universe and prove lower bounds also in that setting. Some of our lower bounds also apply to randomized algorithms. Powered by TCPDF (www.tcpdf.org)
|
|
|
Automatic assembly of jigsaw puzzles from digital images
Ondrúška, Peter ; Sedlář, Jiří (advisor) ; Bulánek, Jan (referee)
This thesis describes a new approach to automatic assembly of classical jigsaw puzzles by computer. The process involves processing scanned images of puzzle pieces, computing a solution based on piecewise compatibility and producing an image of the solution. Whereas previous approaches to this problem were mostly concentrated on using only the shape of the pieces, the method we proposed uses both shape and colour information. The method also introduced several improvements in different aspects of solving. The method was able to successfully solve a puzzle of more than 1000 pieces and thus outperformed previous algorithms.
|
|
|
Datové struktury pro setříděné ukládání dat
Bulánek, Jan ; Koucký, Michal (advisor) ; Kráľ, Daniel (referee)
In this work we study two variants of a bucketing game. This game is used for the lower bound proof of time complexity of item insertion into a sorted array, a data structure for the order maintenance problem. We show that these two variants of the bucketing game have the same time complexity up to a constant factor. Then we show that sorted arrays can use cache efficiently for certain operations. Finally, we present one implementation of the order maintenance data structure using the array of size n1+e.
|
|
|
Algebraické vlastnosti barevnosti grafů
Bulánek, Jan ; Jelínek, Vít (referee) ; Kráľ, Daniel (advisor)
We study algebraic tools for proving the existence of graph colorings and focus a classical method of Alon-Tarsi from this area. In particular, we prove Alon-Tarsi Theorem, provide examples of some known applications and give a new application to colorings of squares of cycles.
|
guest ::
