Název práce: O síle slabých rozšírení teorie V0 Autor: Sebastian Müller Katedra: Katedra Algebry Vedoucí disertační práce: Prof. RNDr. Jan Krajíček, DrSc., Katedra Algebry. Abstrakt: V predložené disertacní práci zkoumáme sílu slabých fragmentu arit- metiky. Činíme tak jak z modelově-teoretického pohledu, tak z pohledu důkazové složitosti. Pohled skrze teorii modelu naznačuje, že malý iniciální segment libo- volného modelu omezené aritmetiky bude modelem silnější teorie. Jako příklad ukážeme, že každý polylogaritmický řez modelu V0 je modelem VNC. Užitím známé souvislosti mezi fragmenty omezené aritmetiky a dokazatelností v ro- zličných důkazových systémech dokážeme separaci mezi rezolucí a TC0 -Frege systémem na náhodných 3CNF-formulích s jistým poměrem počtu klauzulí vůci počtu proměnných. Zkombinováním obou výsledků dostaneme slabší separační výsledek pro rezoluci a Fregeho důkazové systémy omezené hloubky. Klíčová slova: omezená aritmetika, důkazová složitost, Fregeho důkazový systém, Fregeho důkazový systém omezené hloubky, rezoluce Title: On the Power of Weak Extensions of V0 Author: Sebastian Müller Department: Department of Algebra Supervisor: Prof. RNDr. Jan Krajíček, DrSc., Department of Algebra....

Title: Numerical Methods in Discrete Inverse Problems Author: Marie Kubínová Department: Department of Numerical Mathematics Supervisor: RNDr. Iveta Hnětynková, Ph.D., Department of Numerical Mathe- matics Abstract: Inverse problems represent a broad class of problems of reconstruct- ing unknown quantities from measured data. A common characteristic of these problems is high sensitivity of the solution to perturbations in the data. The aim of numerical methods is to approximate the solution in a computationally efficient way while suppressing the influence of inaccuracies in the data, referred to as noise, that are always present. Properties of noise and its behavior in reg- ularization methods play crucial role in the design and analysis of the methods. The thesis focuses on several aspects of solution of discrete inverse problems, in particular: on propagation of noise in iterative methods and its representation in the corresponding residuals, including the study of influence of finite-precision computation, on estimating the noise level, and on solving problems with data polluted with noise coming from various sources. Keywords: discrete inverse problems, iterative solvers, noise estimation, mixed noise, finite-precision arithmetic - iii -

This thesis presents an investigation of the possibility of using the fixed-point arithmetic in the inertial navigation systems, which use the local level navigation frame mechanization equations. Two square root filtering methods, the Potter's square root Kalman filter and UD factorized Kalman filter, are compared with respect to the conventional Kalman filter and its Joseph's stabilized form. The effect of rounding errors to the Kalman filter optimality and the covariance matrix or its factors conditioning is evaluated for a various lengths of the fractional part of the fixed-point computational word. Main contribution of this research lies in an evaluation of the minimal fixed-point arithmetic word length for the Phi-angle error model with noise statistics which correspond to the tactical grade inertial measurements units.

My thesis is focused mainly on my own electronic work sheets for children with limited hand mobility - the second class of elementary school. The introduction deals with methodology of chosen topics which I have used in my work sheets. I compare teaching methods which I have used with alternative ones. The main part of my thesis aims at SMART Board 10 software for interactive whiteboard which I have used for creating my work sheets, secondly on its use, thirdly on its tools from the tool kit and at last but not at least on description of my work sheets. I also describe the teaching of a physically disabled girl with limited hand mobility that I have taught. The conclusion consists of summarizing my experience with teaching based on my work sheets and assessing my teaching lessons.

My dissertation is mainly focused on work sheets created in Smart notebook 10 which are intended for the third-grade pupils of primary school. At the beginning I am dealing with the didactic part of chosen curriculum in material which was made by me. Futhermore I am comparing available mathematic schoolbooks which are intended for the third grade. The main part contains methodical manual for users of the working sheets which were created in Smart Notebook 10. It is mainly focused on the operation, the usage and the right method of working out the particular tasks. In conclusion of my dissertation I am summarizing my conclusions of hours and I am evaluating my experience gained from teaching at the primary school during which I used the chosen working sheets.

Nowadays high-precision computations are still more desired. Either for simulation on a level of atoms where every digit is important and inaccurary in computation can cause invalid result or numerical approximations in partial differential equations solving where a small deviation causes a result to be useless. The computations are carried over data types with precision of order hundred to thousand digits, or even more. This creates pressure on time complexity of problem solving and so it is essential to find very efficient methods for computation. Every complex physical problem is usually described by a system of equations frequently containing elementary functions like sinus, cosines or exponentials. The aim of the work is to design and implement methods that for a given precision, arbitrary elementary function and a point compute its value in the most efficent way. The core of the work is an application of methods based on AGM (arithmetic-geometric mean) with a time complexity of order $O(M(n)\log_2{n})$ 9(expresed for multiplication $M(n)$). The complexity can not be improved. There are many libraries supporting multi-precision atithmetic, one of which is GMP and is about to be used for efficent method implementation. In the end all implemented methods are compared with existing ones.

Thesis is dedicated to evaluation of roundoff impact on numerical integration methods accuracy and effectivity. Contains theoretical expectations taken from existing literature, implementation of chosen methods, experimental measurement of attained accuracy under different circumstances and their comparison with regard to time complexity. Library contains Runge-Kutta methods to order 7 and Adams-Bashforth methods to order 20 implemented using C++ templates which allow optional arbitrary-precision arithmetic. Small models with known analytic solution were used for experiments.

Languages such as C use pointers very heavily. Implementation of operations on dynamically linked structures is, however, quite difficult. This can cause the programmer to make more mistakes than usual. One method for dealing with this situation is to use the static analysis tools. This thesis elaborates on the extension to the Code Listener architecture which is an interface for building static analysis tools. Code Listener is able to construct a call-graph or a control flow graph for a given source code and send it to the analyzing tool. One ability of the architecture is that it can conduct the live variable analysis internally. It detects places in the control flow graph where some subset of variables may be killed. The problem was that every variable for which a pointer address was assigned could not been killed, before. This decision had been made because there was no assurance that the variable could never been used through the pointer. So the goal of this work was to design and incorporate a points-to analysis which is able to exclude some references from the set of considered pointers to improve the live variable analysis.

Předkládaná disertační práce se zabývá návrhem základních bloků v systému zbytkových tříd pro zvýšení výkonu aplikací určených pro digitální zpracování signálů (DSP). Systém zbytkových tříd (RNS) je neváhová číselná soustava, jež umožňuje provádět paralelizovatelné, vysokorychlostní, bezpečné a proti chybám odolné aritmetické operace, které jsou zpracovávány bez přenosu mezi řády. Tyto vlastnosti jej činí značně perspektivním pro použití v DSP aplikacích náročných na výpočetní výkon a odolných proti chybám. Typický RNS systém se skládá ze tří hlavních částí: převodníku z binárního kódu do RNS, který počítá ekvivalent vstupních binárních hodnot v systému zbytkových tříd, dále jsou to paralelně řazené RNS aritmetické jednotky, které provádějí aritmetické operace s operandy již převedenými do RNS. Poslední část pak tvoří převodník z RNS do binárního kódu, který převádí výsledek zpět do výchozího binárního kódu. Hlavním cílem této disertační práce bylo navrhnout nové struktury základních bloků výše zmiňovaného systému zbytkových tříd, které mohou být využity v aplikacích DSP. Tato disertační práce předkládá zlepšení a návrhy nových struktur komponent RNS, simulaci a také ověření jejich funkčnosti prostřednictvím implementace v obvodech FPGA. Kromě návrhů nové struktury základních komponentů RNS je prezentován také podrobný výzkum různých sad modulů, který je srovnává a determinuje nejefektivnější sadu pro různé dynamické rozsahy. Dalším z klíčových přínosů disertační práce je objevení a ověření podmínky určující výběr optimální sady modulů, která umožňuje zvýšit výkonnost aplikací DSP. Dále byla navržena aplikace pro zpracování obrazu využívající RNS, která má vůči klasické binární implementanci nižší spotřebu a vyšší maximální pracovní frekvenci. V závěru práce byla vyhodnocena hlavní kritéria při rozhodování, zda je vhodnější pro danou aplikaci využít binární číselnou soustavu nebo RNS.

The thesis deals with speedup and accuracy of numerical computation, especially when differential equations are solved. Algorithms, which are fulling these conditions are named semi-analytical. One posibility how to accelerate computation of differential equation is paralelization. Presented paralelization is based on transformation numerical solution into residue number system, which is extended to floating point computation. A new algorithm for modulo multiplication is also proposed. As application applications in solution of differential calculus are the main goal it is discussed numeric integration with modified Euler, Runge - Kutta and Taylor series method in residue number system. Next possibilities and extension for implemented residue number system are mentioned at the end.