
Overdetermined systems of interval linear equations
Horáček, Jaroslav ; Hladík, Milan (advisor)
This work is focused on overdetermined systems of interval linear equati ons. First part consists of introduction to interval arithmetics and interval linear algebra and basic theory of interval linear systems. In the second part various methods for solving overdetermined interval linear systems are de scribed. By solution of overdetermined interval system we mean union of all solutions of all subsystems. Known and our variants of algorithms are discussed. We introduce our subsquare method. All mentioned methods are implemented in one toolbox for Matlab. Methods are tested on solvable and unsolvable overdetermined systems. For solvable systems we test solution enclosure, time and special features of methods. For unsolvable systems we test detection of unsolvability. At the end of this work we provide basic in troduction to Intlab. 1


Computational Bounded Rationality
Černý, Jakub ; Loebl, Martin (advisor) ; Hladík, Milan (referee)
This thesis formalizes a model of bounded rationality in extensiveform games called gameplaying schemata. In this model, the strategies are repre sented by a structure consisting of a deterministic finite automaton and two computational functions. The automaton represents a structured memory of the player, while the functions represent the ability of the player to identify efficient abstractions of the game. Together, the schema is a realization of a pure strategy which can be implemented by a player in order to play a given game. The thesis shows how to construct correctly playing schema for every pure strategy in any multiplayer extensiveform game with perfect recall and how to evaluate its complexity. It proves that equilibria in schemata strategies always exist and computing them is PPADhard. Moreover, for a class of efficiently representable strategies, computing MAXPAYEFCE can be done in polynomial time. 1


Determinants of Interval Matrices
Matějka, Josef ; Horáček, Jaroslav (advisor) ; Hladík, Milan (referee)
This work focuses on the determinants of interval matrices. After a short introduction into interval arithmetics, the works focus on time complexity of computation tight enclosures of interval determinants, we show what complexity class this problem belongs to and how hard is approximation with relative and absolute error. Next chapter works with various preconditions of a matrix, which could lead to better results. After we analyse preconditioning of matrices we show several methods for computing determinants, starting with Gauss elimination, en ding method using Cramer's rule. We also ponder about special cases of matrices like symmetric, tridiagonal and Toeplitz. At the end we test shown methods. 1


Evaluation of interval polynomials
Firment, Roman ; Hladík, Milan (advisor) ; Hartman, David (referee)
In this thesis, we deal with the finding of an enclosure of the range of the real and interval polynomials in one variable. There are presented functional forms of the real polynomials which we implemented in the Matlab environment that is using interval arithmetic of the toolbox INTLAB. These forms can be used to effectively evaluate an enclosure of a polynomial. In the theoretical part there is introduced a reduction that makes possible to use an arbitrary functional form computing an enclosure of a real polynomial to evaluate an enclosure of interval polynomial. A numerical comparison is also the part of this thesis. Based on its results we designed two global functions solving our problem that apply one of the forms. A user has a possibility to indirectly influence the choice of the form by nonmandatory parameter that is specifying the strategy of computation. This parameter defines speed of evaluation and the amount of overestimation of the computed interval.


The optimal solution set of interval linear programming problems
Garajová, Elif ; Hladík, Milan (advisor) ; Zimmermann, Karel (referee)
Determining the set of all optimal solutions of a linear program with interval data is one of the main problems discussed in interval optimization. We review two methods based on duality in linear programming, which are used to approximate the optimal set. Additionally, another decomposition method based on complementary slackness is proposed. This method provides the exact description of the optimal set for problems with a fixed coefficient matrix. The second part of the thesis is focused on studying the topological and geometric properties of the optimal set. We examine sufficient conditions for closedness, boundedness, connectedness and convexity. We also prove that testing boundedness is co NPhard for inequalityconstrained problems with free variables. Stronger results are derived for some special classes of interval linear programs, such as problems with a fixed coefficient matrix. Furthermore, we study the effect of transformations commonly used in linear programming on interval problems, which allows for a direct generalization of some results to different types of interval linear programs. Powered by TCPDF (www.tcpdf.org)


Solving Endgames in Large ImperfectInformation Games such as Poker
Ha, Karel ; Hladík, Milan (advisor) ; Bošanský, Branislav (referee)
Title: Solving Endgames in Large ImperfectInformation Games such as Poker Author: Bc. Karel Ha Department: Department of Applied Mathematics Supervisor: doc. Mgr. Milan Hladík, Ph.D., Department of Applied Mathematics Abstract: Endgames have a distinctive role for players. At the late stage of games, many aspects are finally clearly defined, deeming exhaustive analysis tractable. Specialised endgame handling is rewarding for games with perfect information (e.g., Chess databases precomputed for entire classes of endings, or dividing Go board into separate independent subgames). An appealing idea would be to extend this approach to imperfectinformation games such as the famous Poker: play the early parts of the game, and once the subgame becomes feasible, calculate an ending solution. However, the problem is much more complex for imperfect information. Subgames need to be generalized to account for information sets. Unfortunately, such a generalization cannot be solved straightaway, as it does not generally preserve optimality. As a consequence, we may end up with a far more exploitable strategy. There are currently three techniques to deal with this challenge: (a) disregard the problem entirely; (b) use a decomposition technique, which sadly retains only the same quality; (c) or formalize improvements of...


Solving interval systems by the least squares method
Tomandl, David ; Hladík, Milan (advisor) ; Hartman, David (referee)
This thesis is describing, comparing and implementing enclosure methods for solving overdetermined system of interval linear equations by the least squares method. Input data of the methods are within given intervals. We describe the structure of the solution set, which is the basis of algorithms for computing interval hull of the solution set. Although computation of the interval hull is NPhard problem, there exist algorithms which encloses the solution set with less than exponential steps. We are heavily focusing on these algorithms. The solution set can be alternatively characterized as a solution to the symmetric interval system. Therefore the work includes solvers of the symmetric interval system. This thesis contains numerical experiments for comparing the methods. All methods are implemented in Matlab with utilisation of the interval toolbox Intlab. Powered by TCPDF (www.tcpdf.org)


Duality in interval linear programming
Novotná, Jana ; Hladík, Milan (advisor) ; Bartl, David (referee)
This thesis combines a traditional concept of linear programming and interval analysis. Interval analysis ensures that a result belongs to a counted interval and allows us to put an interval instead of a single value on the input. It can be useful especially in practical problems where we get data from measurements and we do not know exact values. The first explored topic is the optimal value range with respect to values and its bounds. Also, the classical concept of duality gap is expanded to interval linear programmimg, necessary and sufficient conditions for zero duality gap and connections between zero duality gap and a continuous set of optimal values are determined. Possible values of duality gap in an interval linear program are shown in examples. The last topic are weak and strong duality in interval linear programming, strong duality types for bounds of the optimal value range and their extensions. Powered by TCPDF (www.tcpdf.org)


Interval linear systems with linear dependencies
Král, Ondřej ; Hladík, Milan (advisor) ; Rada, Miroslav (referee)
The main problem discussed in this thesis is about finding an enclo sure of the solution set of an interval linear system with linear dependencies. We get familiar with definitions from interval arithmetic and analysis. Then we extend them to matrices and linear systems, where we introduce several modern approaches to finding an enclosure and divide them thematically. Most of them are implemented in MATLAB using INTLAB library. We compare their precision and computational time on Toeplitz, symmetric and random matrices. For depen dencies we design our memory saving representation. The results are interpreted and the final function, which can compute either fast, sharp or memory efficient, is build on individual methods. Powered by TCPDF (www.tcpdf.org)


Interval solver for nonlinear constraints
Garajová, Elif ; Hladík, Milan (advisor) ; Pergel, Martin (referee)
The thesis is focused on the Sivia algorithm (Set Inverter via Interval Ana lysis) designed for solving a continuous constraint satisfaction problem using interval methods and propagation techniques. Basic properties of the algorithm are derived, including the correction of its presented complexity bound. Some improvements concerning the testing of constraint satisfaction and optimiza tion of the number of interval boxes describing the solution are proposed. The thesis also introduces contractors used to enhance the effectivity of the Sivia algorithm by reducing the interval boxes processed. Presented algorithms were implemented in a solver for nonlinear constraints with a simple visualization of the result using the Matlab language. A comparison of basic contractors on specific examples is given.
