|
White Test for the Least Weighted Squares
Bludská, Věra ; Víšek, Jan Ámos (advisor) ; Krištoufek, Ladislav (referee)
The Least Weighted Squares (LWS) is a robust method for computing coefficients in linear regression models. An inherent problem of LWS is the complexity of its estimator and, consequently, the lack of an analytical solution or fast exact algorithms for its evaluation. To remedy this situation a novel exact algorithm running in polynomial time has been proposed. The algorithm implemented in MATLAB programming language has been employed for testing computationally more efficient non-exact LWS methods. In addition to many potential uses of LWS in robust econometrics (e.g. outlier diagnostics) the method has been applied to the problem of regression estimation in the presence of heteroscedasticity. It has been demonstrated that the combined use of the LWS estimator and White's test for heteroscedasticity significantly improves the efficiency of the robust regression estimation.
|
|
Application of genetic algorithm for production scheduling of engineering company
Stariat, Jiří ; Skočdopolová, Veronika (advisor) ; Zouhar, Jan (referee)
This thesis is engaged in scheduling problem, his special types and methods of solving. Scheduling problem is a common operations research problem, which ranks among combinatorial problems. The aim of the scheduling problem is to assign certain activities and resources to individual time moments. Scheduling problem is NP-complete problem. Its computational complexity is thus so high, that there is currently no known algorithm that precisely solve its any instance in polynomial time. Is therefore used for its solution heuristics and metaheuristcs. In this thesis is described in detail metaheuristics of genetic algorithm. Application of genetic algorithm for production scheduling of specific engineering company is the main objective of this thesis.
|
|
Numerical simulation of compressible flows with the aid of multigrid methods
Živčák, Andrej ; Dolejší, Vít (advisor) ; Knobloch, Petr (referee)
We deal with the numerical solution of the Navier-Stokes equations describing a motion of viscous compressible flows. The governing equations are discretized with the aid of discontinuous Galerkin finite element method which is based on a discontinuous piecewise polynomial approximation. The discretizations leads to a large nonlinear algebraic system. In order to solve this system efficiently, we develop the so-called p-multigrid solution strategy which employ as a projec- tion and a restriction operators the L2 -projection in the spaces of polynomial functions on each element separately. The p-multigrid technique is studied, deve- loped and implemented in the code ADGFEM. The computational performance of the method is presented.
|
|
Support of management decision-making on transport networks
Přibyl, Vladimír ; Černý, Jan (advisor) ; Kavička, Antonín (referee) ; Peško, Štefan (referee)
The presented thesis is focused on a set of problems related to managerial decision-making concerning networks (particularly transportation networks), respectively - if we put it more precisely - the thesis focuses on the support of this decision-making by means of quantitative methods. A set of problems related to nets and decision-making concerning their individual parts or elements represents a very complex sphere which has been a subject of research for a number of decades. Out of this sphere, the thesis formulates and elaborates in great detail two problems, which - from the point of view of their practical significance - are important for the decision-making of managers of carriers, or the public sphere, and which have not been published in this form yet. The main point is the problem of how to find a subnet with a limited prolongation of routes between important pairs of vertices. Another problem is a design of a bus route in an area with a low demand. For each of these problems, the thesis offers an exact combinatorial solution method, furthermore a method based on integer linear programming, and - last but not least - also, of course, heuristic methods of solution. All these methods have been tested on a set of networks, which has been created for this purpose in a pseudo-random way in the frame of this thesis. The testing has been focused primarily on the comparison of the results provided by heuristic methods, which are of great importance - with regard to a great computational difficulty of exact methods - for feasible tasks on a larger scale. The tests have proved that the proposed heuristic methods are practically applicable and show results whicheven represent the optimal solution in a number of cases, or are only slightly distant from the optimal solution.
|
| |
|
Parallelization of Integer Factorization from the View of RSA Breaking
Breitenbacher, Dominik ; Henzl, Martin (referee) ; Homoliak, Ivan (advisor)
This paper follows up the factorization of integers. Factorization is the most popular and used method for RSA cryptoanalysis. The SIQS was chosen as a factorization method that will be used in this paper. Although SIQS is the fastest method (up to 100 digits), it can't be effectively computed at polynomial time, so it's needed to look up for options, how to speed up the method as much as possible. One of the possible ways is paralelization. In this case OpenMP was used. Other possible way is optimalization. The goal of this paper is also to show, how easily is possible to use paralelizion and thanks to detailed analyzation the source codes one can reach relatively large speed up. Used method of iterative optimalization showed itself as a very effective tool. Using this method the implementation of SIQS achieved almost 100 multiplied speed up and at some parts of the code even more.
|
|
NP vyhledávací problémy
Jirotka, Tomáš ; Krajíček, Jan (advisor) ; Pudlák, Pavel (referee)
Title: NP search problems Author: Tomáš Jirotka Department: Department of Algebra Supervisor: Prof. RNDr. Jan Krajíček, DrSc. Abstract: The thesis summarizes known results in the field of NP search pro- blems. We discuss the complexity of integer factoring in detail, and we propose new results which place the problem in known classes and aim to separate it from PLS in some sense. Furthermore, we define several new search problems. Keywords: Computational complexity, TFNP, integer factorization. 1
|
|
Výpočetní složitost v teorii grafů
Ondráčková, Eva ; Kratochvíl, Jan (advisor) ; Sgall, Jiří (referee)
Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other by a sequence of switches. In this thesis, we study the computational complexity the problem S(P) for a certain graph property P: given a graph G, determine if G is switching-equivalent to a graph having P. First, we give an overview of known results, including both properties P for which S(P) is polynomial, and those for which S(P) is NP-complete. Then we show the NP-completeness of the following problem for each c (0; 1): determine if a graph G can be switched to contain a clique of size at least cn, where n is the number of vertices of G. We also study the problem if, for a xed graph H, a given graph is switching-equivalent to an H-free graph. We show that for H isomorphic to a claw, the problem is polynomial. Further, we give a characterization of graphs witching-equivalent to a K1;2-free graph by ten forbidden induced subgraphs, each having ve vertices.
|
| |
|
Application of Heuristic Methods for Vehicle Routing Problem with Time Windows
Chytrá, Alena ; Fábry, Jan (advisor) ; Pelikán, Jan (referee)
This thesis demonstrates practical using of vehicle routing problem with time windows (VRPTW) and its solution by heuristic method. There are described teoretical principles of integer models, mathematical definitions of VRP with one or more vehicles, VRPTW and some heuristics for VRP. The practical part is solution of VRP by heuristic nearest neighbor. Product distribution is planed according to the firm settings in Prague. I compare existing situation and computed solution that show benefits of using described methods in conclusion.
|
guest ::
