|
Computational and analytical a posteriori error estimates for finite element methods
Segeth, Karel
The analytical a posteriori error estimates are oriented to the use in h-methods, are usually constructed only for lowest-order polynomial approximation, and often depend on unknown constatns or functions. In this review paper, we present several error estimation procedures for some particular linear partial differential problems with special regards to the needs of the hp-method. We compare the advantages and drawbacks of a posteriori error estimators including computational ones.
|
|
Relational Verification of Programs with Integer Data
Konečný, Filip ; Bouajjani, Ahmed (referee) ; Jančar, Petr (referee) ; Vojnar, Tomáš (advisor)
Tato práce představuje nové metody pro verifikaci programů pracujících s neomezenými celočíslenými proměnnými, konkrétně metody pro analýzu dosažitelnosti a~konečnosti. Většina těchto metod je založena na akceleračních technikách, které počítají tranzitivní uzávěry cyklů programu. V práci je nejprve představen algoritmus pro akceleraci několika tříd celočíselných relací. Tento algoritmus je až o čtyři řády rychlejší než existující techniky. Z teoretického hlediska práce dokazuje, že uvažované třídy relací jsou periodické a~poskytuje tudíž jednotné řešení prolému akcelerace. Práce dále představuje semi-algoritmus pro analýzu dosažitelnosti celočíselných programů, který sleduje relace mezi proměnnými programu a~aplikuje akcelerační techniky za účelem modulárního výpočtu souhrnů procedur. Dále je v práci navržen alternativní algoritmus pro analýzu dosažitelnosti, který integruje predikátovou abstrakci s accelerací s cílem zvýšit pravděpodobnost konvergence výpočtu. Provedené experimenty ukazují, že oba algoritmy lze úspěšně aplikovat k verifikaci programů, na kterých předchozí metody selhávaly. Práce se rovněž zabývá problémem konečnosti běhu programů a~dokazuje, že tento problém je rozhodnutelný pro několik tříd celočíselných relací. Pro některé z těchto tříd relací je v práci navržen algoritmus, který v polynomiálním čase vypočítá množinu všech konfigurací programu, z nichž existuje nekonečný běh. Tento algoritmus je integrován do metody, která analyzuje konečnost běhů celočíselných programů. Efektivnost této metody je demonstrována na několika netriviálních celočíselných programech.
|
| |
|
Interval data and sample variance: computational aspects
Sokol, Ondřej ; Černý, Michal (advisor) ; Rada, Miroslav (referee)
This thesis deals with the calculation of the upper limit of the sample variance when the exact data are not known but intervals which certainly contain them are available. Generally, finding the upper limit of the sample variance knowing only interval data is an NP-hard problem, but under certain conditions imposed on the input data an appropriate efficient algorithm can be used. In this work algorithms were modified so that, even at the cost of exponential complexity, one can always find the optimal solution. The goal of this thesis is to compare selected algorithms for calculating the upper limit of sample variance over interval data from the perspective of the average computational complexity on the generated data. Using simulations it is shown that if the data meets certain conditions, the complexity of the average case is polynomial.
|
|
Řešení 3D elektrostatických problémů se singulaturou s použitím adaptivní hp-FEM
Kůs, Pavel ; Šolín, Pavel ; Doležel, Ivo
For most numerical methods, accurate resolution of singularities occurring at sharp re-entrant corners or edges of electrically conductive objects is highly problematic. Finite differences are known for their inability to treat complex geometries, and traditional low-order (piecewise-linear or quadratic) finite element methods (FEM) exhibit extremely poor convergence. Nowadays, the best numerical method for the solution of most singular problems is the adaptive hp-version of the FEM (hp-FEM). This method is based on spatial refinements toward the singularities combined with optimal variation of polynomial degrees on the elements. The hp-FEM has mathematically proven exponential convergence, and also in practical computations typically it is by several orders of magnitudes faster than standard FEM.
|
|
Teaching aids for 2D computer graphics
Malina, Jakub ; Průša, Zdeněk (referee) ; Rajmic, Pavel (advisor)
In this master’s thesis we focus on the basic properties of computer curves and their practical applicability. We explain how the curve can be understood in general, what are polynomial curves and their composing possibilities. Then we focus on the description of Bezier curves, especially the Bezier cubic. We discuss in more detail some of fundamental algorithms that are used for modelling these curves on computers and then we will show their practical interpretation. Then we explain non uniform rational B-spline curves and De Boor algorithm. In the end we discuss topic rasterization of segment, thick line, circle and ellipse. The aim of master’s thesis is the creation of the set of interactive applets, simulating some of the methods and algorithm we discussed in theoretical part. This applets will help facilitate understanding and will make the teaching more effective.
|
|
Teaching aids for 2D computer graphics
Malina, Jakub ; Průša, Zdeněk (referee) ; Rajmic, Pavel (advisor)
In this master’s thesis we focus on the basic properties of computer curves and their practical applicability. We explain how the curve can be understood in general, what are polynomial curves and their composing possibilities. Then we focus on the description of Bezier curves, especially the Bezier cubic. We discuss in more detail some of fundamental algorithms that are used for modelling these curves on computers and then we will show their practical interpretation. Then we explain non uniform rational B-spline curves and De Boor algorithm. In the end we discuss topic rasterization of segment, thick line, circle and ellipse. The aim of master’s thesis is the creation of the set of interactive applets, simulating some of the methods and algorithm we discussed in theoretical part. This applets will help facilitate understanding and will make the teaching more effective.
|
|
SIGA 2011
Kolman, Radek ; Linkeová, I. ; Okrouhlík, Miloslav ; Pařík, Petr
The conference SIGA 2011 aimed to bring together mathematicians, physicists, computer designers and engineers dealing with splines who are using them for the numerical solutions of partial differential equations of various problems in mechanics and physics. In computational mechanics, it is isogeometric analysis (IGA) which is being dynamically developed. This numerical method employs shape functions based on different types of splines (B-splines, NURBS, T-splines and many others), and the fields of unknown quantities are consequently described the same way as the geometry of the studied domain. In addition, this approach provides a higher degree of continuity than that offered by the classical finite element (FE) method based on Lagrangian polynomials. Isogeometric analysis aims to integrate FE ideas in CAD systems without necessity to regenerate mesh. The conference intends to create a forum for further discussion in multidisciplinary scientific areas involving mathematics, computer graphics, geometry, physics, engineering and software engineering, respectively.
|
|
Visualization in vector spaces
Klímek, Jakub ; Hladík, Milan (referee) ; Fiala, Jiří (advisor)
The goal was to create a set of Java applets, which would serve as an addition to the teaching of Linear algebra. These applets make possible to compute with rational numbers, real numbers, complex numbers and Zp - integers modulo prime p using addition, subtraction, multiplication and division. It is also possible to compute with vectors of elements of those spaces using addition and subtraction of vectors and multiplication and division by scalar. In addition, the vector calculator can figure coordinates of a vector, determine a linearly independent subset of vectors and, when in standard scalar product space, figure an orthogonal projection onto a subspace generated by a set of vectors. The advantage of these applets is their ease of use simulating a classical handheld calculator.
|
|
Minesweeper game - computational complexity and solver implemetation
Hoder, Kryštof ; Fiala, Jiří (advisor) ; Pangrác, Ondřej (referee)
In the present work we study construction of tree decompositions with respect to graphs useful for playing the Minesweeper game. We also formalize rules of the game and present necessary terminology. We provide the set of game configurations whose consistency can be decided in polynomial time - problem of consistency-deciding of general game configuration has been proven NP-compete in other works. We also provide algorithms that classify game configurations and decide about consistency of those configurations, which we can decide about in polynomial time.
|
guest ::
