|
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 (oponent) ; Jančar, Petr (oponent) ; Vojnar, Tomáš (vedoucí práce)
This work presents novel methods for verification of reachability and termination properties of programs that manipulate unbounded integer data. Most of these methods are based on acceleration techniques which compute transitive closures of program loops. We first present an algorithm that accelerates several classes of integer relations and show that the new method performs up to four orders of magnitude better than the previous ones. On the theoretical side, our framework provides a common solution to the acceleration problem by proving that the considered classes of relations are periodic. Subsequently, we introduce a semi-algorithmic reachability analysis technique that tracks relations between variables of integer programs and applies the proposed acceleration algorithm to compute summaries of procedures in a modular way. Next, we present an alternative approach to reachability analysis that integrates predicate abstraction with our acceleration techniques to increase the likelihood of convergence of the algorithm. We evaluate these algorithms and show that they can handle a number of complex integer programs where previous approaches failed. Finally, we study the termination problem for several classes of program loops and show that it is decidable. Moreover, for some of these classes, we design a polynomial time algorithm that computes the exact set of program configurations from which nonterminating runs exist. We further integrate this algorithm into a semi-algorithmic method that analyzes termination of integer programs, and show that the resulting technique can verify termination properties of several non-trivial integer programs.
|
| |
|
Intervalová data a výběrový rozptyl: výpočetní aspekty
Sokol, Ondřej ; Černý, Michal (vedoucí práce) ; Rada, Miroslav (oponent)
Práce se zabývá problematikou výpočtu horní meze výběrového rozptylu v případě, kdy nejsou k dispozici přesná data, ale pouze intervaly, ve kterých tato data s jistotou leží. Obecně je nalezení horní meze výběrového rozptylu ze znalosti pouze intervalových dat NP-těžký problém, ale při splnění určitých podmínek kladených na vstupní intervalová data lze použít některý z efektivních algoritmů. V práci jsou upraveny algoritmy tak, aby, byť i za cenu exponenciální složitosti, dokázaly vždy najít optimální řešení. Cílem práce je porovnat vybrané algoritmy pro výpočet horní meze rozptylu intervalových dat z pohledu průměrné výpočetní složitosti na generovaných datech. Pomocí simulací je ukázáno, že za splnění určitých předpokladů kladených na data je složitost v průměrném případě pouze polynomiální.
|
| |
|
Vytvoření interaktivních pomůcek z oblasti 2D počítačové grafiky
Malina, Jakub ; Průša, Zdeněk (oponent) ; Rajmic, Pavel (vedoucí práce)
V teto diplomove prace se budeme zabyvat popisem zakladnich vlastnosti pocitacovych krivek a jejich praktickou pouzitelnosti. Vysvetlime si, jak lze krivky chapat obecne, co to jsou polynomialni krivky a zpusoby napojovani. Pote se zamerime na popis Bezierovych krivek, hlavne pak na Bezierovy kubiky. Podrobneji probereme nektere stezejni algo- ritmy, ktere se pouzivaji pro vykreslovani techto krivek na pocitacich, a ukazeme si jejich praktickou implementaci. Pote probereme neuniformni racionalni B-spline krivky a De Booruv algoritmus. Nakonec projdeme tematem rasterizace usecky, silne cary, kruznice a elipsy. Cilem diplomove prace je vytvoreni nekolika interaktivnich appletu, simulujicich algoritmy pro rasterizaci a vykresleni krivek probirane v teoreticke casti. Tyto applety napomuzou snazsimu pochopeni teoretickych poznatku a zefektivni vyuku.
|
|
Vytvoření interaktivních pomůcek z oblasti 2D počítačové grafiky
Malina, Jakub ; Průša, Zdeněk (oponent) ; Rajmic, Pavel (vedoucí práce)
V teto diplomove prace se budeme zabyvat popisem zakladnich vlastnosti pocitacovych krivek a jejich praktickou pouzitelnosti. Vysvetlime si, jak lze krivky chapat obecne, co to jsou polynomialni krivky a zpusoby napojovani. Pote se zamerime na popis Bezierovych krivek, hlavne pak na Bezierovy kubiky. Podrobneji probereme nektere stezejni algo- ritmy, ktere se pouzivaji pro vykreslovani techto krivek na pocitacich, a ukazeme si jejich praktickou implementaci. Pote probereme neuniformni racionalni B-spline krivky a De Booruv algoritmus. Nakonec projdeme tematem rasterizace usecky, silne cary, kruznice a elipsy. Cilem diplomove prace je vytvoreni nekolika interaktivnich appletu, simulujicich algoritmy pro rasterizaci a vykresleni krivek probirane v teoreticke casti. Tyto applety napomuzou snazsimu pochopeni teoretickych poznatku a zefektivni vyuku.
|
|
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.
|
|
Linárněalgebraický jukebox - vizualizace operací ve vektorových prostorech
Klímek, Jakub ; Hladík, Milan (oponent) ; Fiala, Jiří (vedoucí práce)
Cílem práce bylo vytvoření sady appletů v Javě, která by sloužila jako doplněk výuky Lineární algebry. Applety umožňují počítání nad tělesy racionálních čísel, reálných čísel, komplexních čísel a nad tělesy Zp s operacemi sčítání, odčítání, násobení a dělení. Dále je možné počítat s vektory nad týmiž tělesy a s jejich operacemi sčítání a odčítání vektorů, násobení a dělení skalárem. Navíc lze počítat souřadnice vzhledem k bázi, zjišťovat lineárně nezávislou podmnožinu vektorů a v prostorech se standardním skalárním součinem také počítat ortogonální projekci na podprostor generovaný množinou vektorů. Předností appletů je jejich snadná ovladatelnost podobná klasické příruční kalkulačce.
|
|
Hra minolovka - výpočetní složitost a implementace hledání řešení
Hoder, Kryštof ; Fiala, Jiří (vedoucí práce) ; Pangrác, Ondřej (oponent)
V předložené práci studujeme vytváření stromových rozkladů grafu se speciálním zřetelem na grafy užitečné při hraní hry Minolovka. Zároveň formalizujeme postup hry a zavádíme potřebnou terminologii. Na základě tohoto jsme našli širokou množinu konfigurací hry, o jejichž konzistentnosti lze rozhodovat v polynomiálním čase - že problém je v obecnosti NP-úplný bylo ukázáno již dříve v jiných pracech. Taktéž popisujeme algoritmy, které klasifikují konfigurace a případně v polynomiálním čase rozhodnou o jejich konzistentnosti.
|
host ::
