|
|
Extremal Polyominoes
Steffanová, Veronika ; Valtr, Pavel (advisor) ; Cibulka, Josef (referee)
Title: Extremal Polyominoes Author: Veronika Steffanová Department: Department of Applied Mathematics Supervisor: Doc. RNDr. Pavel Valtr, Dr. Abstract: The thesis is focused on polyominoes and other planar figures consisting of regular polygons, namely polyiamonds and polyhexes. We study the basic geometrical properties: the perimeter, the convex hull and the bounding rectangle/hexagon. We maximise and minimise these parameters and for the fixed size of the polyomino, denoted by n. We compute the extremal values of a chosen parameter and then we try to enumerate all polyominoes of the size n, which has the extremal property. Some of the problems were solved by other authors. We summarise their results. Some of the problems were solved by us, namely the maximal bounding rectan- gle/hexagon and maximal convex hull of polyiamonds. There are still sev- eral topics which remain open. We summarise the literature and offer our observations for the following scientists. Keywords: Polyomino, convex hull, extremal questions, plane 1
|
|
|
Extremal combinatorics of matrices, sequences and sets of permutations
Cibulka, Josef ; Valtr, Pavel (advisor) ; Füredi, Zoltán (referee) ; Jelínek, Vít (referee)
Title: Extremal combinatorics of matrices, sequences and sets of permutations Author: Josef Cibulka Department: Department of Applied Mathematics Supervisor: Doc. RNDr. Pavel Valtr, Dr., Department of Applied Mathematics Abstract: This thesis studies questions from the areas of the extremal theory of {0, 1}-matrices, sequences and sets of permutations, which found many ap- plications in combinatorial and computational geometry. The VC-dimension of a set P of n-element permutations is the largest integer k such that the set of restrictions of the permutations in P on some k-tuple of positions is the set of all k! permutation patterns. We show lower and upper bounds quasiexponential in n on the maximum size of a set of n-element permutations with VC-dimension bounded by a constant. This is used in a paper of Jan Kynčl to considerably improve the upper bound on the number of weak isomorphism classes of com- plete topological graphs on n vertices. For some, mostly permutation, matrices M, we give new bounds on the number of 1-entries an n × n M-avoiding matrix can have. For example, for every even k, we give a construction of a matrix with k2 n/2 1-entries that avoids one specific k-permutation matrix. We also give almost tight bounds on the maximum number of 1-entries in matrices avoiding a fixed layered...
|
|
|
Twilight Struggle
Asník, Lukáš ; Cibulka, Josef (advisor) ; Majerech, Vladan (referee)
The aim of this work is to create a computer version of famous and popular board game Twilight Struggle. The program allows users to play the game in hotseat mode or in mode against computer controlled opponent. Automatic checking and enforcement of game rules accelerates the game. Game can be saved at any time. Program is developed in JAVA programming language and is multi-platform.
|
|
|
Risk
Štola, Miroslav ; Cibulka, Josef (advisor) ; Forst, Libor (referee)
The main goal of this thesis is to implement a strategy board game called Risk with modified rules and to create an artificial intelligence. It is possible to play the game in the hot-seat mode on one computer in case of multiple human players. The artificial intelligence is based on a search tree. Additi- onally, a straightforward artificial intelligence was created. Both AI players are tested against one another and also against human players. At the end of the thesis the results are presented and discussed. 1
|
|
|
Monkey Bank Robbers
Škoda, Dominik ; Lidický, Bernard (advisor) ; Cibulka, Josef (referee)
The project concerns of creation of computer game inspirated by the game RoboRally. The program is based on Client-Server architecture and allowes players to play together via Internet. The application running on server manages individual games and takes care of synchronization between players. The program allowes to implement artificial inteligence which can join individual game with another players. Each player can create any map and play a game with any map. The project is designed for simple extension in future. The program is developed in JAVA language.
|
|
|
Elevator scheduling algorithms
Hlísta, Peter ; Cibulka, Josef (advisor) ; Lidický, Bernard (referee)
This thesis compares various systems of elevator solutions in high-rise buildings using computer simulation. These systems are compared according to the various criteria. The basic criterion is the average waiting time for the elevator. The other criteria are the costs of the transport and the longest waiting time. The algorithms for the management of the various types of elevators are tested on the larger group of people than in the most of the available literature that examine the improvements mostly on two or three persons. The results show that it is meaningful to consider all algorithms because each of them has its advantages and disadvantages.
|
|
|
Konvexně nezávislé podmnožiny konečných množin bodů
Zajíc, Vítězslav ; Valtr, Pavel (advisor) ; Cibulka, Josef (referee)
Let fd(n), n > d ≥ 2, be the smallest positive integer such that any set of fd(n) points, in general position in Rd , contains n points in convex position. Let hd(n, k), n > d ≥ 2 and k ≥ 0, denote the smallest number with the property that in any set of hd(n, k) points, in general position in Rd , there are n points in convex position whose convex hull contains at most k other points. Previous result of Valtr states that h4(n, 0) does not exist for all n ≥ 249. We show that h4(n, 0) does not exist for all n ≥ 137. We show that h3(8, k) ≤ f3(8) for all k ≥ 26, h4(10, k) ≤ f4(10) for all k ≥ 147 and h5(12, k) ≤ f5(12) for all k ≥ 999. Next, let fd(k, n) be the smallest number such that in every set of fd(k, n) points, in general position in Rd , there are n points whose convex hull has at least k vertices. We show that, for arbitrary integers n ≥ k ≥ d + 1, d ≥ 2, fd(k, n) ≥ (n − 1) (k − 1)/(cd logd−2 (n − 1)) , where cd > 0 is a constant dependent only on the dimension d. 1
|
|
|
Triplanetary
Huječek, Adam ; Cibulka, Josef (advisor) ; Gemrot, Jakub (referee)
The main purpose of this work is to bring the almost forgotten turn-based board game Triplanetary from the 70s and the beginning of the 80s of the last century to the screens of today's computers. The program allows multiple players to play on one computer in the so called hotseat mode two of the several scenarios available in the original game - racing Grand Tour with the option to play with computer controlled opponents and battle Nova for three players. However thanks to the suitable design it is easy to implement the rest of scenarios or of course add completely new ones provided the user has the knowledge of JAVA which the game is programmed in. Another advantage is the option to save and exit the game at any time and return to it later.
|
|
|
Software package for polyhedra operation
Steffanová, Veronika ; Hladík, Milan (advisor) ; Cibulka, Josef (referee)
Title: Software package for polyhedra operation Author: Veronika Steffanová Department: Department of Applied Mathematics Supervisor: Mgr. Milan Hladík, Ph.D., Department of Applied Mathematics Abstract: The topic of the thesis is focused on convex polyhedra and algorithms for working with them. At first we give the theorem about vertex and facet description and then we describe selected algorithms connected to the problem of the conversion between these two descriptions. In the practical part we implement three functions using three selected algorithms and a few other functions, which are simple results of the three algorithms. Finally we get a MATLAB library, which contains functions for vertex enumeration, facet enumeration, convex union of two polyhedra, intersection of two polyhedra and irredudancy problem for facets and vertices, too. By the way we compare our two implemented algorithms for facet enumeration, but not only accor- ding the running time, also according the memory requirements and the implemen- tation complexity. Keywords: polyhedron, MATLAB, linear programming, convex hull 1
|
|
|
Erdos-Szekeres type theorems
Eliáš, Marek ; Matoušek, Jiří (advisor) ; Cibulka, Josef (referee)
Let P = (p1, p2, . . . , pN ) be a sequence of points in the plane, where pi = (xi, yi) and x1 < x2 < · · · < xN . A famous 1935 Erdős-Szekeres theorem asserts that every such P contains a monotone subsequence S of √ N points. Another, equally famous theorem from the same paper implies that every such P contains a convex or concave subsequence of Ω(log N) points. First we define a (k + 1)-tuple K ⊆ P to be positive if it lies on the graph of a function whose kth derivative is everywhere nonnegative, and similarly for a negative (k + 1)-tuple. Then we say that S ⊆ P is kth-order monotone if its (k + 1)- tuples are all positive or all negative. In this thesis we investigate quantitative bound for the corresponding Ramsey-type result. We obtain an Ω(log(k−1) N) lower bound ((k − 1)-times iterated logarithm). We also improve bounds for related problems: Order types and One-sided sets of hyperplanes. 1
|
guest ::
RSS feed.