|
Algorithms for decoding the Reed-Solomon error control code
Tieftrunk, Tomáš ; Číž, Radim (referee) ; Šilhavý, Pavel (advisor)
Thesis discuss about effort to ensure from error, which may occur during transmission over noisy channel. There's used Reed Solomon code. It's block, cyclic and systematic code, which is symbol orientated. Computational process of decoding is mathematically time-consuming. In thesis is closely described Berlekamp-Masey algorithm, used in decoding to evaluate error polynomial. Process is illustrated in application in Matlab. Practical realization uses Reed Solomon code in communication over RS232. Communication is established between computer and microcomputer.
|
|
Visualizing pseudospectra for polynomial eigenvalue problems
Klimentová, A. ; Šebek, Michael
The use of pseudospectra is widespread in various applications, e.g. control theory, acoustics, vibrating systems. Through pseudospectra we can gain insight into the sensitivity of the eigenvalues of a matrix to perturbations that is convenient for robut control. We have implemented in Matlab a method to visualize e-pseudospectra for n x n polynomial matrix of degree greater that 2. We compute pseudospectrum for each point of the complex plane using transfer function approach.
|
| |
|
Maticové funkce a jejich numerické aproximace
Suchá, Darja ; Hnětynková, Iveta (advisor) ; Strakoš, Zdeněk (referee)
In the presented work, we study numerical methods for approximation of a function f of a matrix A. First, we give theoretical background - definitions of matrix functions, and their properties. Further, we summarize basic numerical methods for computation of an approximation of matrix functions f(A). In many applications, we need to approximate the matrix function f(A) applied on an apriory given vector b, i.e. f(A)b. Especially, when A is large and sparse, the computation of approximation to f(A) and subsequent multiplication by the vector b can be computationaly expensive. Therefore we study methods, which compute the approximation of f(A)b directly. Main emphasis is placed on the polynomial approximation in the least squares sense, and several modifications of Krylov subspace methods. Numerical experiments compare convergence and computa- tional time required to obtain reasonable approximation to f(A)b. 1
|
|
Computational Complexity in Graph Theory
Jelínková, Eva
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.
|
|
Analysis of attacks on asymmetric cryptosystems
Tvaroh, Tomáš ; Ivánek, Jiří (advisor) ; Palovský, Radomír (referee)
This thesis analyzes various attacks on underlying computational problem of asymmetric cryptosystems. First part introduces two of the most used problems asymmetric cryptography is based on, which are integer factorization and computation of discrete logarithm. Algorithms for solving these problems are described and for each of them there is a discussion about when the use of this particular algorithm is appropriate and when it isn't. In the next part computational problems are related to algorithms RSA and ECC and it is shown, how solving the underlying problem enables us to crack the cypher. As a part of this thesis an application was developed that measures the efficiency of described attacks and by providing easy-to-understand enumeration of algorithm's steps it can be used to demonstrate how the attack works. Based on the results of performed analysis, most secure asymmetric cryptosystem is selected along with some recommendations regarding key pair generation.
|
|
Approximate Polynomial Greatest Common Divisor
Eliaš, Ján ; Zítko, Jan (advisor) ; Hnětynková, Iveta (referee)
Title: Approximate Polynomial Greatest Common Divisor Author: Ján Eliaš Department: Department of Numerical Mathematics, MFF UK Supervisor: Doc. RNDr. Jan Zítko, CSc., Department of Numerical Mathematics, MFF UK Abstract: The computation of polynomial greatest common divisor (GCD) ranks among basic algebraic problems with many applications. The Euclidean algorithm is the oldest and usual technique for computing GCD. However, the GCD computation problem is ill-posed, particularly when some unknown noise is applied to the polyno- mial coefficients. Since the Euclidean algorithm is unstable, new methods have been extensively studied in recent years. Methods based on the numerical rank estimation represent one group of current meth- ods. Their disadvantage is that the numerical rank cannot be computed reliably due to the sensitivity of singular values on noise. The aim of the work is to overcome the ill-posed sensitivity of GCD computation in the presence of noise. Keywords: AGCD, Sylvester matrix, numerical rank, TLS
|
|
Finite Integrals Semi-Analytical Computations
Veigend, Petr ; Kunovský, Jiří (referee) ; Šátek, Václav (advisor)
This bachelor thesis explains the topic of semi-analytical computation of finite integrals. It contains the mathematical definition of finite integral, along with definitions and examples for several methods that can be used to solve finite integrals analytically. For the most part however, the thesis is trying to explain how to effectively and precisely approximate finite integrals on a computer. It deals with approximations by polynomials, but mostly with the correspondence between finite integrals and differential equations. This correspondence is used in two software projects that are the part of this thesis.
|
|
Analýza výpočtu největšího společného dělitele polynomů
Kuřátko, Jan ; Zítko, Jan (advisor) ; Janovský, Vladimír (referee)
In this work, the analysis of the computation of the greatest common divisor of univariate and bivariate polynomials is presented. The whole process is split into three stages. In the first stage, data preprocessing is explained and the resulting better numerical behavior is demonstrated. Next stage is concerned with the problem of the computation of the numerical rank of the Sylvester matrix, from which the degree of the greatest common divisor is obtained. The last stage is the actual algorithm for calculating the greatest common divisor of two polynomials. Furthermore, the underlying theory behind the computation of the greatest common divisor is explained and illustrated on many examples. 1
|
|
Semi-Analytical Computations
Herzallah, Ahmad Sudqi Hussein ; Kopřiva, Jan (referee) ; Kunovský, Jiří (advisor)
This thesis discusses the analytical errors emerging from semi-analytical calculations. It also discusses about the modern method of Taylor's series for numerical calculations of ordinary differential equations and chosen methods of charachterized functions. The end solutions indicate favourable results for the semi-analytical calculations in the selected roles and responsible differential equations by direct execution of Taylor's series for solutions of polynomial functions, exponential functions & geometric functions using simulation program "TKSL". It also discusses about the definite & indefinite Intergals and methods for the solution of definite integrals. Followed by a brief introduction of Maple, Matlab & TKSL and further comparison of the result of the three programs & finding the best way of resolving the definite integrals.
|
guest ::
