|
Minimum Weight Triangulation (MWT)
Charvát, Pavel ; Kolingerová, Ivana (advisor) ; Ferko, Andrej (referee)
For a long time, it has been neither known whether MWT is solvable in a polynomial time nor whether it belongs to NP. As we now, its status still remain unknown. We present severalknown approaches to MWT such as modifications of the problem with known time complexity or various heuristics and approximations which allow us to find an exact or at least an approximate solution in a reasonable time. We compare the approximations in some particular situations. The main part of the work is devoted to a description and implementation of an efficient heuristic with (almost?) linear expected complexity for points uniformly distributed in some convex shape. The algorithm is a modification of Drysdale's algorithm for finding GT candidates and Beurouti's computation of the modified LMT-skeleton, where we add some proofs of the correctness. We are able to complete MWT from the graph of candidate edges in O(n · d3 + n · d2+k), where d is the the maximum degree and k is the maximum number of inner components of some skeleton face. Further, we suggest a new approximation of MWT with polynomial complexity in the worst case and (almost?) linear expected complexity, which only rarely differs from the optimal triangulation and has O(1) approximation factor in the worst case. This approximation combines the LMT-skeleton...
|
|
Sampling Rate Conversion
Chrobák, Martin ; Provazník, Ivo (referee) ; Kozumplík, Jiří (advisor)
This bachelor’s thesis is engaged in design of procedure for change of sampling rate of EKG signal using 3 methods: with positive integer factor D/I, with any factor (I=8) and with any factor (I=16). Sampling rate conversion should be realized from 500 to 360 Hz and from 360 to 500 Hz in time and frequency part of signal. For this, it is used a professional computing interface of MATLAB, which is perfect for processing of signals. The output from this work should be recommendation which filters (with how long impulse characteristics) are useful for this change of sampling rate.
|
|
Data transmition security with Reed-Solomon codes
Šalanský, Jan ; Šporik, Jan (referee) ; Němec, Karel (advisor)
This Bachelor thesis deals with the security of data transmission by Reed-Solomon codes. It discusses the design of the code, coding method and primarily decoding facility. There are described particular phases of decoding: the computation of the Syndrome, determination of an error locator polynomial, finding of positions of false symbols by Chien search and calculation of error values using the Forney’s algorithm. It compares these basic algorithms to find the polynomial localization errors: Peterson-Gorenstein-Zierler algorithm, Berlekamp-Massey algorithm and the extended Euclidean algorithm. There is shown a detailed design and software implementation of a simple system with forward error correction based on these theoretical findings. Design of the system begins by selecting the appropriate Reed-Solomon code RS (63,39). Next step is construction of basic algebraic structures for this code and derivation of encoder and decoder. Design of system with forward error correction finishes by calculation of encoding and decoding. The final system with forward error correction has been programmed for platforms MS Windows and Linux. It has been based on previous calculations and examples in references.
|
|
Mathematical security methods in digital data transfer
Bartušek, Petr ; Kureš, Miroslav (referee) ; Vašík, Petr (advisor)
This master’s thesis deals with an analysis of digital security with CRC. In the thesis there is described a principle of coding theory, especially then digital security with CRC, for which there is explained a mathematical principle of their encoding and decoding, software implementation and a description of frequently used generator polynomials. The main aim of the thesis is a testing of undetected errors and a finding of number of these errors. After that it is used for the computation of probability with which undetected errors can occur. The thesis is supplemented with several programs which are programmed in the software Matlab.
|
|
O problémech seřazení při řízení servisních operací
Lín, Václav ; Vomlel, Jiří (advisor) ; Jiroušek, Radim (referee) ; Kouba, Zdeněk (referee) ; Ottosen, Thorsten Jorgen (referee)
The subject of the thesis belongs to the field of operations management. We deal with sequencing problems arising when there are multiple repair operations available to fix a broken man-made system and the true cause of the system failure is uncertain. It is assumed that the system is formally described by a probabilistic model, and it is to be repaired by a sequence of troubleshooting operations designed to identify the cause of the malfunction and fix the system. The challenge is to find a course of repair which has minimal expected cost. We study several variants of the problem proposed in the literature. We analyze computational complexity of those variants, apply integer linear programming to one variant of the problem, and examine the relation to machine scheduling.
|
|
Gröbner basis, Zhuang-Zi algorithm and attacks of multivariable cryptosystems
Doktorová, Alice ; Tomáš, Jiří (referee) ; Kureš, Miroslav (advisor)
This diploma thesis is devoted to the multivariate cryptosystems. It includes an overview of commutative algebra with emphasis on Gröbner bases. Of all algorithms, especially the ones using Gröbner bases are studied, i.e. Buchberger's algorithm, which is already implemented in Wolfram Mathematica, and F4 algorithm, for which a program package has been created in the Wolfram Mathematica environment. Also Zhuang-Zi algorithm is described. To simplify its steps a program to compute the Lagrange interpolation polynomial has been created in Python.
|
|
Workforce Optimisation
Pacinda, Štefan ; Barták, Roman (advisor) ; Klusáček, Dalibor (referee)
Title: Workforce Optimisation Author: Štefan Pacinda Department / Institute: Department of Theoretical Computer Science and Mathematical Logic (KTIML) Supervisor of the master thesis: doc. RNDr. Roman Barták Ph.D., KTIML Abstract: Workforce management deals with the problem of maintaining productive workforce for example in call centers, hospitals, transportation companies etc. It includes the problem of deciding which skills are necessarily at each given time and how many personnel with given skills is required. These decisions are followed by solving the problem of allocating particular employees to shifts while satisfying the skill demands but also other constraints derived for example from law regulations, trade unions agreements, and individual preferences. This thesis deals with workforce optimization, that is with the optimal assignment of personnel to shifts in order to cover the demand for resources that vary over time. In this paper the solved problem is described in all detail and modeled as mixed integer program. Implementation details are presented and exhaustive analysis and experiments on a real life problem instance are performed to assure that the aims of the work have been met. Keywords: Rostering, Workforce Management, Shift Scheduling
|
|
Sparse robust portfolio optimization via NLP regularizations
Branda, Martin ; Červinka, Michal ; Schwartz, A.
We deal with investment problems where we minimize a risk measure\nunder a condition on the sparsity of the portfolio. Various risk measures\nare considered including Value-at-Risk and Conditional Value-at-Risk\nunder normal distribution of returns and their robust counterparts are\nderived under moment conditions, all leading to nonconvex objective\nfunctions. We propose four solution approaches: a mixed-integer formulation,\na relaxation of an alternative mixed-integer reformulation and\ntwo NLP regularizations. In a numerical study, we compare their computational\nperformance on a large number of simulated instances taken\nfrom the literature.
|
|
C library for symbolic manipulation
Gurský, Štefan ; Bednárek, David (referee) ; Holan, Tomáš (advisor)
There are many programs doing symbolic manipulation with mathematical expressions. They are called Computer Algebra Systems and most of them contain some programming language. In this bachelor thesis a library for C programming language was created that allows using C as a language for symbolic manipulation. With provided functions user can store mathematical expressions in C variables and work with them in an easy and convenient way. It is possible to build expressions containing standard mathematical operations and functions, reduce them, expand them, find derivatives and Taylor polynomials. The library (called SymCe) is easy to understand not only for user, but also for a programmer that wishes to see its inner working and possibly extend it. Simplicity is the main feature that distinguishes SymCe from other similar pieces of software.
|
|
Aplikace optimalizačních metod na problémy výroby elektřiny
Šumbera, Jiří ; Dlouhý, Martin (advisor) ; Pelikán, Jan (referee) ; Hančlová, Jana (referee)
This thesis deals with application of optimisation methods based on linear and mixed-integer linear programming to various problems in the power sector related to electricity production. The thesis goal is to test the applicability of such methods to formulating and solving various instances from the class of real-world electricity production problems, and to find the advantages and disadvantages associated with using these methods. Introductory chapters describe the main characteristics of power markets, including the historical and regulatory context. Fundamental properties of power markets on both demand and supply side are also described, both from a real-world and a modelling point of view. Benefits of optimisation and modelling are discussed, in particular the solution feasibility and optimality as well as insights gained from sensitivity analysis which is often difficult to replicate with the original system. In the core of the thesis, optimisation techniques are applied to three case studies, each of which deals with a specific problem arising during electricity production. In the first problem, the profit of gas-fired power plant in Slovakia from selling power on the day-ahead market is maximised. The model is set up using both technical and commercial constraints. The second problem deals with the problem of representing a two-dimensional production function which primarily arises for a hydro generator with large variations in the level of its reservoir. Several representations of the original function using piecewise linear subsets are presented, compared, and characterised by their computational intensity both theoretically and practically. In the third problem, the prices on the German day-ahead market in 2011 are modelled. Contrary to the previous two models, the model does not capture an optimisation problem faced by a single producer, but incorporates a large subset of the whole market instead. Consequently the model is formed out of generic constraints relevant to all power plants whose parameters are estimated. By combining information about the aggregate availability of power plants with the estimated efficiencies a full supply curve for each day is created. Different scenarios are analysed to test the impact of uncertain inputs such as unknown or estimated constraints. The choice of the investigated problems stems from the attempt to cover electricity production problems from the point of view of multiple criteria. The three investigated electricity production problems span a broad range from the decisions of a single power plant to the modelling a power market as a whole. Formulations of the production function with different level of detail are presented ranging from a simple linear relationship to several bivariate function formulations. While each problem answers a specific question, they all illustrate the ease with which various electricity production problems can solved using optimisation methods based on linear and mixed-integer linear programming. This is mainly due to the ability of these methods to approximate even non-linear functions and constraints over non-convex domains and find global solutions in reasonable time. Moreover, models formulated with these methods allow sensitivity and scenario analyses to be carried out easily as is illustrated in each of the case studies.
|
guest ::
