
Algoritmy pro řezy v grafech
Pecsők, Ján ; Kolman, Petr (advisor) ; Tiwary, Hans Raj (referee)
Graphpartitioning problems can be generically defined as a family of problems in which we are asked to partition a graph into two or more components. We present overview of methods and concepts used to find best graph partitions according to several criteria. We prove duality of multicommodity flow and sparsest cut problem due to work of Leighton and Rao by describing algorithm using a Linear programming relaxation and a geometric embedding. Then we present the work of Arora, Rao and Vazirani (ARV) and their algorithm based on Semidefinite programming relaxation and a geometric embedding. We also explain the concept of expander flows first introduced in the work of ARV. One section of our work is devoted to the spectral graph theory, introducing the concepts of the spectral gap, random walks, conductance and relations between them. We connect the ideas of expander flows and spectral theory in chapter about so called CutMatching game framework. Finally we present the performance results of our implementation of the LeightonRao and the CutMatching game algorithms. Powered by TCPDF (www.tcpdf.org)


Nonnegative linear operators and their use in econometric and statistic models
Horský, Richard ; Arlt, Josef (advisor) ; Vrabec, Michal (referee) ; Klazar, Martin (referee)
Nonnegative operators, in special case nonnegative matrices, are an interesting topics for many scientists and scientific teams from the beginning of the 20th century. It is not suprising because there are a lot of applications in different areas of science like economy, statistics, linear programming, computer science and others. We can give as the particular example the theory of the Markov chains in which we deal with nonnegative matrices, so called transition matrices. They are of the special form and we called them stochastic matrices. Another example is given by the nonnegative operator on spaces of infinite dimension which is employed in the theory of stochastic processes. It is the backward shift operator called the lag operator as well. The nonnegativity in these examples is considered as the piecewise nonnegativity. Another type of nonnegativity is that in the sense of inner products. In the case of matrices we talk about positivedefinite or positivesemidefinite matrices. A typical example is the covariance matrix of a random vector or symmetrization of any linear operator, for instance the symmetrization of the difference operator. The terms inverse problem or illposed problem have been gaining popularity in modern science since the middle of the last century. The subjects of the first publications in this area were related to quantum scattering theory, geophysics, astronomy and others. Thanks to powerful computers the chances for applications of the theory of inverse and illposed problems has extended in almost all fields of science which use mathematical methods. Illposed problems bear the feature of instability and there is the need of regularization if we want to get some reasonable solution. A typical example of the regularization is the differencing of stochastic process with the purpose to obtain a stationary process. Another concept of regularization used for solving e.g. integral equations with compact operators consists in application of regularization method as truncated singular value decomposition, Tichonov regularization method or Landweber iteration method. Mathematical tools employed in this work are those of the functional analysis. It is the area of mathematics in which distinct mathematical structures meet each other. They are structures built within different mathematical disciplines as mathematical analysis, topology, theory of sets, algebra (mainly linear algebra) and theory of measure (probability). The functional analysis framework enables us to obtain right formulations of definitions and problems providing the general view on the notions and problems of the theory of stochastic processes.
