|
|
Boolean methods in knowledge compilation
Kaleyski, Nikolay Stoyanov ; Čepek, Ondřej (advisor) ; Gregor, Petr (referee)
The open problem in knowledge compilation of whether the language PI is at least as succinct as MODS is answered in the negative. For this purpose a class of Boolean functions with a number of prime implicants that is superpolynomial in their number of false points is constructed. A lower bound (proving that PI is not at least as succinct as MODS), an upper bound (proving that the counterexample cannot yield an exponential separation of PI and MODS) and the precise number of the prime implicants of these functions is computed. Powered by TCPDF (www.tcpdf.org)
|
|
|
Rozklady propojovacích sítí na dlouhé cesty
Měkuta, Kryštof ; Gregor, Petr (advisor) ; Dvořák, Tomáš (referee)
❚✐t❧❡✿ P❛rt✐t✐♦♥s ♦❢ ✐♥t❡r❝♦♥♥❡❝t✐♦♥ ♥❡t✇♦r❦s ✐♥t♦ ❧♦♥❣ ♣❛t❤s ❆✉t❤♦r✿ ❑r②➨t♦❢ ▼➙❦✉t❛ ❉❡♣❛rt♠❡♥t✿ ❉❡♣❛rt♠❡♥t ♦❢ ❚❤❡♦r❡t✐❝❛❧ ❈♦♠♣✉t❡r ❙❝✐❡♥❝❡ ❛♥❞ ▼❛t❤❡♠❛t✐❝❛❧ ▲♦❣✐❝ ❙✉♣❡r✈✐s♦r✿ ▼❣r✳ P❡tr ●r❡❣♦r✱ P❤✳❉✳✱ ❑❚■▼▲ ❆❜str❛❝t✿ ❲❡ s✉r✈❡② s♦♠❡ ❜❛s✐❝ ♣r♦♣❡rt✐❡s ♦❢ s❡❧❡❝t❡❞ ✐♥t❡r❝♦♥♥❡❝t✐♦♥ ♥❡t✇♦r❦s✱ ♠♦r❡ ♣r❡❝✐s❡❧② ♠♦❞✐✜❝❛t✐♦♥s ♦❢ ❤②♣❡r❝✉❜❡s✳ ■♥ ♣❛rt✐❝✉❧❛r✱ ✇❡ st✉❞② ❢❛✉❧t✲t♦❧❡r❛♥❝❡ ♦❢ ❛✉❣♠❡♥t❡❞ ❝✉❜❡s ✇✐t❤ r❡s♣❡❝t t♦ t❤❡ ❡①✐st❡♥❝❡ ♦❢ ❍❛♠✐❧t♦♥✐❛♥ ❝②❝❧❡s✳ ❲❡ ❛❧✲ s♦ ♣r❡s❡♥t ❛ ♠❡t❤♦❞ t♦ ❝♦♥str✉❝t ♠❛♥② s♣❛♥♥✐♥❣ s✉❜❣r❛♣❤s ♦❢ AQn ✐s♦♠♦r♣❤✐❝ t♦ Qn ✉s✐♥❣ ❡❧❡♠❡♥t❛r② ❢❛❝ts ❢r♦♠ ❧✐♥❡❛r ❛❧❣❡❜r❛✳ ❲❡ ♣r♦✈❡ t❤❛t n✲❞✐♠❡♥s✐♦♥❛❧ ❛✉❣♠❡♥t❡❞ ❝✉❜❡ AQn ✇✐t❤ f ❢❛✉❧t② ❡❞❣❡s ❝♦♥t❛✐♥s ❛ ❝♦♣② ♦❢ n✲❞✐♠❡♥s✐♦♥❛❧ ❤②♣❡r✲ ❝✉❜❡ Qn ✇✐t❤ ❛t ♠♦st n 2n−1 f ❢❛✉❧t② ❡❞❣❡s✳ ❯s✐♥❣ t❤✐s r❡s✉❧t ✇❡ ❛r❡ ❛❜❧❡ t♦ ❡❛s✐❧② tr❛♥s❢❡r s❡✈❡r❛❧ ♣r♦♣❡rt✐❡s ♦❢ Qn ✇✐t❤ ❢❛✉❧t② ❡❞❣❡s t♦ AQn ✇✐t❤ ✭♠♦r❡✮ ❢❛✉❧t② ❡❞❣❡s✳ ❆♣♣❧②✐♥❣ s✐♠✐❧❛r ♠❡t❤♦❞✱ ✇❡ ❛❧s♦ s❤♦✇ t❤❛t ✐❢ f ≤ 3n−7 ❛♥❞ ❡✈❡r② ✈❡rt❡① ♦❢ AQn ✐s ✐♥❝✐❞❡♥t t♦ ❛t ❧❡❛st t✇♦ ♥♦♥✲❢❛✉❧t② ❡❞❣❡s✱ t❤❡♥ AQn ❤❛s ❛ ♥♦♥✲❢❛✉❧t② ❤❛♠✐❧t♦♥✐❛♥ ❝②❝❧❡✳ ▼♦r❡♦✈❡r✱ ✇❡ s❤♦✇ t❤❛t ❡✈❡r② t✇♦ ♠♦♥♦♠♦r♣❤✐s♠s ♦❢ G1 t♦ AQn ❛♥❞ G2 t♦ AQm ❝❛♥ ❜❡ ❝♦♠♣♦s❡❞ ✐♥t♦ ❛ ♠♦♥♦♠♦r♣❤✐s♠ ♦❢ t❤❡ ❈❛rt❡s✐❛♥ ♣r♦❞✉❝t G1 G2 t♦ AQn+m✳ ❑❡②✇♦r❞s✿ ❤②♣❡r❝✉❜❡✱ ❛✉❣♠❡♥t❡❞ ❝✉❜❡✱ ❤❛♠✐❧t♦♥✐❝✐t②✱ ❢❛✉❧t② ❡❞❣❡s
|
|
|
Analysis of GPS data in orienteering sports
Picek, Štěpán ; Gregor, Petr (advisor) ; Kučera, Petr (referee)
In orienteering sports, there are many analytical tools used for determining the performance of competitors and the visualization of the routes. However, none of these tools allows automatic comparison and subsequent analysis of competitors' completed track between each single control point. The thesis intends to use the Needleman-Wunsch bioinformatics algorithm for comparison of GPS data, and their visualization within a web application. The application allows comparison of the track with other competitors, analysis of the performance and the connection with other tools. It is created on the ASP.NET Core platform and the Model- View-Controller design pattern with the use of other technologies such as HTML, CSS and TypeScript.
|
|
|
Applications of Gray codes in cache-oblivious algorithms
Mička, Ondřej ; Fink, Jiří (advisor) ; Gregor, Petr (referee)
Modern computers employ a sophisticated hierarchy of caches to decrease the latency of memory accesses. This led to the development of cache-oblivious algorithms that strive to achieve the best possible performance on such memory hierarchies with minimal knowledge of the exact parameters of the hierarchy. A common technique used in the design of cache-oblivious algorithms is a recursion-based divide-and-conquer method. In this work, we show an alternative technique based on the Gray codes. We use the binary reflected Gray code to traverse arrays in the cache-oblivious way, allowing us to design algorithms for problems such as matrix transposition, naive matrix multiplication or naive convolution that match the asymptotic performance of their recursion-based counterparts. The advantage is that our algorithms can be implemented without recursion (or a stack that simulates it) by using a loopless algorithm. We also introduce a variant of the binary reflected Gray code tuned to certain applications of our technique and an almost loopless algorithm to generate it. Apart from the theoretical analysis of our technique's performance, we also examine its practical performance on the problem of matrix transposition.
|
|
|
Parity vertex colorings
Soukup, Jan ; Gregor, Petr (advisor) ; Kučera, Petr (referee)
A parity path in a vertex colouring of a graph G is a path in which every colour is used even number of times. A parity vertex colouring is a vertex colouring having no parity path. Let χp(G) be the minimal number of colours in a parity vertex colouring of G. It is known that χp(Bn) ≥ √ n where Bn is the complete binary tree with n layers. We show that the sharp inequality holds. We use this result to obtain a new bound χp(T) > 3 √ log n where T is any binary tree with n vertices. We study the complexity of computing the parity chromatic number χp(G). We show that checking whether a vertex colouring is a parity vertex colouring is coNP-complete and we design an exponential algorithm to com- pute it. Then we use Courcelle's theorem to prove the existence of a FPT algorithm checking whether χp(G) ≤ k parametrized by k and the treewidth of G. Moreover, we design our own FPT algorithm solving the problem. This algorithm runs in polynomial time whenever k and the treewidth of G is bounded. Finally, we discuss the relation of this colouring to other types of colourings, specifically unique maximum, conflict free, and parity edge colourings.
|
|
|
Genetic Approach To Hypercube Problems
Kuboň, David ; Gregor, Petr (advisor) ; Pilát, Martin (referee)
The main focus of this thesis are hypercubes. In the first part, we introduce hypercubes, which form an interesting class of graphs that has practical uses in networks and distributed computing. Because of their varied applications, the thesis describes the graph-theory problems related to hypercubes such as searching for detour spanners, minimizing their maximal degree and finding multiple edge- disjoint spanners. It also overviews current results on selected hypercube problems and proposes a solution using a genetic algorithm. The genetic algorithm is designed, implemented and its performance is evaluated. The conclusion is that applying a genetic algorithm to some hypercube problems is a viable, but not the most effective method.
|
|
|
Hamiltonian cycles in Kneser graphs
Hulcová, Tereza ; Šámal, Robert (advisor) ; Gregor, Petr (referee)
In this thesis, we will discuss existence of hamiltonian cycles in Kneser graphs: graphs K(n,k) with vertex set corresponding to k-element subsets from set of n elements, and vertices will be adjacent if and only if their corresponding k-sets are disjoint. Lovász's conjecture about vertex transitive graphs implies hamiltonicity of Kneser graphs for n ≥ 2k + 1. Chen proved that K(n, k) are hamiltonian for n ≥ 3k. Later she improved her result to n ≥ 2.6k + 1. In both cases she used Baranyai's partition theorem. Recent proof of Middle levels conjecture allowed to show hamiltonicity of bipartite Kneser graphs. We will get familiar with some these results.
|
|
|
Boolean methods in knowledge compilation
Kaleyski, Nikolay Stoyanov ; Čepek, Ondřej (advisor) ; Gregor, Petr (referee)
The open problem in knowledge compilation of whether the language PI is at least as succinct as MODS is answered in the negative. For this purpose a class of Boolean functions with a number of prime implicants that is superpolynomial in their number of false points is constructed. A lower bound (proving that PI is not at least as succinct as MODS), an upper bound (proving that the counterexample cannot yield an exponential separation of PI and MODS) and the precise number of the prime implicants of these functions is computed. Powered by TCPDF (www.tcpdf.org)
|
|
|
Hamiltonicity of hypercubes without k-snakes and k-coils
Pěgřímek, David ; Gregor, Petr (advisor) ; Fink, Jiří (referee)
A snake (coil) is an induced path (cycle) in a hypercube. They are well known from the snake-in-the-box (coil-in-the-box) problem which asks for the longest snake (coil) in a hypercube. They have been generalized to k-snakes (k-coils) which preserve distances between their every two vertices at distance at most k − 1 in hypercube. We study them as a variant of Locke's hypothesis. It states that a balanced set F ⊆ V (Qn) of cardinality 2m can be avoided by a Hamiltonian cycle if n ≥ m + 2 and m ≥ 1. We show that if S is a k-snake (k-coil) in Qn for n ≥ k ≥ 6 (n ≥ k ≥ 7), then Qn − V (S) is Hamiltonian laceable. For a fixed k the number of vertices of a k-coil may even be exponential with n. We introduce a dragon, which is an induced tree in a hypercube, and its generalization a k-dragon which preserves distances between its every two vertices at distance at most k−1 in hypercube. By proving a specific lemma from my Bachelor thesis that was previously verified by a computer, we finish the proof of the theorem regarding Hamiltonian laceability of hypercubes without n-dragons.
|
|
|
Minimální reprezentace víceintervalových booleovských funkcí
Bártek, Filip ; Kučera, Petr (advisor) ; Gregor, Petr (referee)
When we interpret the input vector of a Boolean function as a binary number, we define interval Boolean function fn [a,b] so that fn [a,b](x) = 1 if and only if a ≤ x ≤ b. Disjunctive normal form is a common way of representing Boolean functions. Minimization of DNF representation of an interval Boolean function can be per- formed in linear time. The natural generalization to k-interval functions seems to be significantly harder to tackle. In this thesis, we discuss the difficulties with finding an optimal solution and introduce a 2k-approximation algorithm.
|
guest ::
