|
|
Possible improvements of global optimization methods inspired by nature
Pátek, Zdeněk ; Rytíř, Pavel (advisor) ; Bálek, Martin (referee)
This study focuses on the global optimization of functions of real variables using methods inspired by nature. It contains a description of selected global optimization techniques (Differential Evolution, Self-Organizing Migrating Algorithm, Steady-State Evolutionary Algorithm, Particle Swarm Optimization, Gregarious Particle Swarm Optimizer a Hybrid Particle Swarm with Differential Evolution Operator). I have found four improvements of these techniques, discovered their suitable parameter configurations and compared them on chosen trial functions. Experimental results proved that described improvements can increase performance of the optimization techniques inspired by nature.
|
|
|
Geometric and algebraic properties of discrete structures
Rytíř, Pavel ; Loebl, Martin (advisor) ; Serra, Oriol (referee) ; Kaiser, Tomáš (referee)
In the thesis we study two dimensional simplicial complexes and linear codes. We say that a linear code C over a field F is triangular representable if there exists a two dimensional simplicial complex ∆ such that C is a punctured code of the kernel ker ∆ of the incidence matrix of ∆ over F and dim C = dim ker ∆. We call this simplicial complex a geometric representation of C. We show that every linear code C over a primefield is triangular representable. In the case of finite primefields we construct a geometric representation such that the weight enumerator of C is obtained by a simple formula from the weight enumerator of the cycle space of ∆. Thus the geometric representation of C carries its weight enumerator. Our motivation comes from the theory of Pfaffian orientations of graphs which provides a polynomial algorithm for weight enumerator of the cut space of a graph of bounded genus. This algorithm uses geometric properties of an embedding of the graph into an orientable Riemann surface. Viewing the cut space of a graph as a linear code, the graph is thus a useful geometric representation of this linear code. We study embeddability of the geometric representations into Euclidean spaces. We show that every binary linear code has a geometric representation that can be embed- ded into R4 . We characterize...
|
|
|
Algoritmické problémy související s průnikovými grafy
Ivánek, Jindřich ; Pergel, Martin (advisor) ; Rytíř, Pavel (referee)
In this thesis we study two clique-cover problems which have interesting applications regarding the k -bend intersection graph representation: the edge-clique-cover-degree problem and the edge-clique-layered-cover problem. We focus on the complexity of these problems and polynomial time algorithms on restricted classes of graphs. The main results of the thesis are NP-completness of the edge-clique-layered-cover problem and a polynomial-time 2-approximation algorithm on the subclass of diamond-free graphs for the same problem as well as some upper bounds on particular graph classes.
|
|
|
Geometric and algebraic properties of discrete structures
Rytíř, Pavel ; Loebl, Martin (advisor) ; Serra, Oriol (referee) ; Kaiser, Tomáš (referee)
In the thesis we study two dimensional simplicial complexes and linear codes. We say that a linear code C over a field F is triangular representable if there exists a two dimensional simplicial complex ∆ such that C is a punctured code of the kernel ker ∆ of the incidence matrix of ∆ over F and dim C = dim ker ∆. We call this simplicial complex a geometric representation of C. We show that every linear code C over a primefield is triangular representable. In the case of finite primefields we construct a geometric representation such that the weight enumerator of C is obtained by a simple formula from the weight enumerator of the cycle space of ∆. Thus the geometric representation of C carries its weight enumerator. Our motivation comes from the theory of Pfaffian orientations of graphs which provides a polynomial algorithm for weight enumerator of the cut space of a graph of bounded genus. This algorithm uses geometric properties of an embedding of the graph into an orientable Riemann surface. Viewing the cut space of a graph as a linear code, the graph is thus a useful geometric representation of this linear code. We study embeddability of the geometric representations into Euclidean spaces. We show that every binary linear code has a geometric representation that can be embed- ded into R4 . We characterize...
|
|
|
Lattices and Codes
Rytíř, Pavel ; Loebl, Martin (advisor) ; Pangrác, Ondřej (referee)
This thesis studies triangular con gurations, binary matroids, and integer lattices generated by the codewords of a binary code. We study the following hypothesis: the lattice generated by the codewords of a binary code has a basis consisting only of the codewords. We prove the hypothesis for the matroids with the good ear decomposition. We study the operation of edge contraction in the triangular con gurations. Especially in cycles and acyclic triangular con gurations. For an arbitrary graph we nd a triangular con guration with the skeleton containing this graph as a minor. For every binary matroid we construct a triangular con guration such that the matroid is a minor of the con guration. We prove that between the cycle spaces of the matroid and the con guration exists a bijection. The bijection maps the circuits of the matroid to the circuits of the con guration.
|
|
|
Possible improvements of global optimization methods inspired by nature
Pátek, Zdeněk ; Bálek, Martin (referee) ; Rytíř, Pavel (advisor)
This study focuses on the global optimization of functions of real variables using methods inspired by nature. It contains a description of selected global optimization techniques (Differential Evolution, Self-Organizing Migrating Algorithm, Steady-State Evolutionary Algorithm, Particle Swarm Optimization, Gregarious Particle Swarm Optimizer a Hybrid Particle Swarm with Differential Evolution Operator). I have found four improvements of these techniques, discovered their suitable parameter configurations and compared them on chosen trial functions. Experimental results proved that described improvements can increase performance of the optimization techniques inspired by nature.
|
guest ::
