@phdthesis{Seidl2006, author = {Seidl, Andreas}, title = {Cylindrical Decomposition Under Application-Oriented Paradigms}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-816}, school = {Universit{\"a}t Passau}, year = {2006}, abstract = {Quantifier elimination (QE) is a powerful tool for problem solving. Once a problem is expressed as a formula, such a method converts it to a simpler, quantifier-free equivalent, thus solving the problem. Particularly many problems live in the domain of real numbers, which makes real QE very interesting. Among the so far implemented methods, QE by cylindrical algebraic decomposition (CAD) is the most important complete method. The aim of this thesis is to develop CAD-based algorithms, which can solve more problems in practice and/or provide more interesting information as output. An algorithm that satisfies these standards would concentrate on generic cases and postpone special and degenerated ones to be treated separately or to be abandoned completely. It would give a solution, which is locally correct for a region the user is interested in. It would give answers, which can provide much valuable information in particular for decision problems. It would combine these methods with more specialized ones, for subcases that allow for. It would exploit degrees of freedom in the algorithms by deciding to proceed in a way that promises to be efficient. It is the focus of this dissertation to treat these challenges. Algorithms described here are implemented in the computer logic system REDLOG and ship with the computer algebra system REDUCE.}, subject = {Quantorenelimination}, language = {en} } @phdthesis{Walsh2024, author = {Walsh, Florian}, title = {Computing the Binomial Part of Polynomial Ideals}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-15096}, school = {Universit{\"a}t Passau}, pages = {vi, 131 Seiten}, year = {2024}, abstract = {Given an ideal in a polynomial ring over a field, we present a complete algorithm to compute its binomial part.}, language = {en} } @phdthesis{Graf2007, author = {Graf, Simone}, title = {Kamerakalibrierung mit radialer Verzeichnung - die radiale essentielle Matrix}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-12711}, school = {Universit{\"a}t Passau}, year = {2007}, abstract = {In der Bildverarbeitung wird die beobachtende Kamera meist als Lochkamera modelliert: ein Modell, das zahlreiche theoretische Vorteile bietet. So kann etwa das Abbildungsverhalten als projektive Abbildung aufgefasst werden. In einem Stereokamerasystem dieses Modells stehen korrespondierende Punkte - das sind Bildpunkte desselben 3D-Punktes - in einem linearen Zusammenhang, der auch ohne Kenntnis der Kameraparameter aus beobachteten Korrespondenzen gesch{\"a}tzt werden kann. F{\"u}r die meisten Kameras, insbesondere f{\"u}r solche mit Weitwinkelobjektiven, ist die Modellannahme einer Lochkamera allerdings sichtbar unzureichend. Deshalb m{\"u}ssen zus{\"a}tzlich zur Lochkamera noch Verzeichnungsabbildungen ins Modell integriert werden. In dieser Arbeit wird gezeigt, dass bei polynomialer radialer Verzeichnung die Parameter der Projektionsabbildung die Verzeichnungsparameter bestimmen. Dieses theoretische Ergebnis fließt in Algorithmen zur Kamerakalibrierung, d.h. zur Bestimmung der Parameter eines Kameramodells, ein. Diese wurden experimentell getestet und mit bestehenden Verfahren verglichen. Weiterhin wird die radiale essentielle Matrix eingef{\"u}hrt, die die Beziehung von korrespondierenden Punkten im Stereokamerafall bei radialer Verzeichnung beschreibt. Es werden vier Algorithmen vorgestellt, die diese theoretische Beziehung verwerten. Sie geben an, wie aus korrespondierenden Punkten die radiale essentielle Matrix gesch{\"a}tzt werden kann und welche Kameraparameter daraus gewonnen werden k{\"o}nnen. Damit ist beispielsweise eine Nachkalibrierung m{\"o}glich. Auch diese Verfahren wurden implementiert und evaluiert. Umgekehrt ist bei bekannter radialer essentieller Matrix eine Einschr{\"a}nkung des Suchraums f{\"u}r korrespondierende Punkte m{\"o}glich, die f{\"u}r die Rekonstruktion ben{\"o}tigt werden.}, subject = {Optische Messtechnik}, language = {de} } @unpublished{Kreitmeier2008, author = {Kreitmeier, Wolfgang}, title = {Optimal quantization for uniform distributions on Cantor-like sets}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-12449}, year = {2008}, abstract = {In this paper, the problem of optimal quantization is solved for uniform distributions on some higher dimensional, not necessarily self-similar \$N-\$adic Cantor-like sets. The optimal codebooks are determined and the optimal quantization error is calculated. The existence of the quantization dimension is characterized and it is shown that the quantization coefficient does not exist. The special case of self-similarity is also discussed. The conditions imposed are a separation property of the distribution and strict monotonicity of the first \$N\$ quantization error differences. Criteria for these conditions are proved and as special examples modified versions of classical fractal distributions are discussed.}, subject = {Maßtheorie}, language = {en} } @unpublished{Kreitmeier2011, author = {Kreitmeier, Wolfgang}, title = {Optimal vector quantization in terms of Wasserstein distance}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-22502}, year = {2011}, abstract = {The optimal quantizer in memory-size constrained vector quantization induces a quantization error which is equal to a Wasserstein distortion. However, for the optimal (Shannon-)entropy constrained quantization error a proof for a similar identity is still missing. Relying on principal results of the optimal mass transportation theory, we will prove that the optimal quantization error is equal to a Wasserstein distance. Since we will state the quantization problem in a very general setting, our approach includes the R\'enyi-\$\alpha\$-entropy as a complexity constraint, which includes the special case of (Shannon-)entropy constrained \$(\alpha = 1)\$ and memory-size constrained \$(\alpha = 0)\$ quantization. Additionally, we will derive for certain distance functions codecell convexity for quantizers with a finite codebook. Using other methods, this regularity in codecell geometry has already been proved earlier by Gy\"{o}rgy and Linder.}, subject = {Maßtheorie}, language = {en} } @unpublished{Kreitmeier2005, author = {Kreitmeier, Wolfgang}, title = {Optimal Quantization for Dyadic Homogeneous Cantor Distributions}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-3845}, year = {2005}, abstract = {For a large class of dyadic homogeneous Cantor distributions in \mathbb{R}, which are not necessarily self-similar, we determine the optimal quantizers, give a characterization for the existence of the quantization dimension, and show the non-existence of the quantization coefficient. The class contains all self-similar dyadic Cantor distributions, with contraction factor less than or equal to \frac{1}{3}. For these distributions we calculate the quantization errors explicitly.}, subject = {Maßtheorie}, language = {en} } @phdthesis{Ali2011, author = {Ali, Rashid}, title = {Weyl Gr{\"o}bner Basis Cryptosystems}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-23195}, school = {Universit{\"a}t Passau}, year = {2011}, abstract = {In this thesis, we shall consider a certain class of algebraic cryptosystems called Gr{\"o}bner Basis Cryptosystems. In 1994, Koblitz introduced the Polly Cracker cryptosystem that is based on the theory of Gr{\"o}bner basis in commutative polynomials rings. The security of this cryptosystem relies on the fact that the computation of Gr{\"o}bner basis is, in general, EXPSPACE-hard. Cryptanalysis of these commutative Polly Cracker type cryptosystems is possible by using attacks that do not require the computation of Gr{\"o}bner basis for breaking the system, for example, the attacks based on linear algebra. To secure these (commutative) Gr{\"o}bner basis cryptosystems against various attacks, among others, Ackermann and Kreuzer introduced a general class of Gr{\"o}bner Basis Cryptosystems that are based on the difficulty of computing module Gr{\"o}bner bases over general non-commutative rings. The objective of this research is to describe a special class of such cryptosystems by introducing the Weyl Gr{\"o}bner Basis Cryptosystems. We divide this class of cryptosystems in two parts namely the (left) Weyl Gr{\"o}bner Basis Cryptosystems and Two-Sided Weyl Gr{\"o}bner Basis Cryptosystems. We suggest to use Gr{\"o}bner bases for left and two-sided ideals in Weyl algebras to construct specific instances of such cryptosystems. We analyse the resistance of these cryptosystems to the standard attacks and provide computational evidence that secure Weyl Gr{\"o}bner Basis Cryptosystems can be built using left (resp. two-sided) Gr{\"o}bner bases in Weyl algebras.}, subject = {Gr{\"o}bner-Basis}, language = {en} } @unpublished{KreitmeierLinder2011, author = {Kreitmeier, Wolfgang and Linder, Tamas}, title = {High-Resolution Scalar Quantization with R{\´e}nyi Entropy Constraint}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-23787}, year = {2011}, abstract = {We consider optimal scalar quantization with \$r\$th power distortion and constrained R\'enyi entropy of order \$\alpha\$. For sources with absolutely continuous distributions the high rate asymptotics of the quantizer distortion has long been known for \$\alpha=0\$ (fixed-rate quantization) and \$\alpha=1\$ (entropy-constrained quantization). These results have recently been extended to quantization with R\'enyi entropy constraint of order \$\alpha \ge r+1\$. Here we consider the more challenging case \$\alpha\in [-\infty,0)\cup (0,1)\$ and for a large class of absolutely continuous source distributions we determine the sharp asymptotics of the optimal quantization distortion. The achievability proof is based on finding (asymptotically) optimal quantizers via the companding approach, and is thus constructive.}, subject = {Maßtheorie}, language = {de} } @unpublished{Kreitmeier2009, author = {Kreitmeier, Wolfgang}, title = {Hausdorff measure of uniform self-similar fractals}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-17948}, year = {2009}, abstract = {Let d \&\#8805; 1 be an integer and E a self-similar fractal set, which is the attractor of a uniform contracting iterated function system (UIFS) on Rd. Denote by D the Hausdorff dimension, by HD(E) the Hausdorff measure and by diam (E) the diameter of E. If the UIFS is parametrised by its contracting factor c, while the set \ω of fixed points of the UIFS does not depend on c, we will show the existence of a positive constant depending only on \ω, such that the Hausdorff dimension is smaller than one and HD = (E) D if c is smaller than this constant. We apply our result to modified versions of various classical fractals. Moreover we present a parametrised UIFS where \ω depends on c and HD < diam(E)D, if c is small enough.}, subject = {Maßtheorie}, language = {en} } @unpublished{Kreitmeier2009, author = {Kreitmeier, Wolfgang}, title = {Optimal quantization for the one-dimensional uniform distribution with R{\´e}nyi -α-entropy constraints}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-16983}, year = {2009}, abstract = {We establish the optimal quantization problem for probabilities under constrained R{\´e}nyi-α-entropy of the quantizers. We determine the optimal quantizers and the optimal quantization error of one-dimensional uniform distributions including the known special cases α = 0 (restricted codebook size) and α = 1 (restricted Shannon entropy).}, subject = {Maßtheorie}, language = {de} } @unpublished{Kreitmeier2009, author = {Kreitmeier, Wolfgang}, title = {Error bounds for high-resolution quantization with R{\´e}nyi - \&\#945; - entropy constraints}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-16647}, year = {2009}, abstract = {We consider the problem of optimal quantization with norm exponent r > 0 for Borel probabilities on Rd under constrained R{\´e}nyi-\&\#945;-entropy of the quantizers. If the bound on the entropy becomes large, then sharp asymptotics for the optimal quantization error are well-known in the special cases \&\#945; = 0 (memory-constrained quantization) and \&\#945; = 1 (Shannon-entropy-constrained quantization). In this paper we determine sharp asymptotics for the optimal quantization error under large entropy bound with entropy parameter \&\#945; \&\#8712; [1+r/d, \&\#8734;]. For \&\#945; \&\#8712; [0,1+r/d[ we specify the asymptotical order of the optimal quantization error under large entropy bound. The optimal quantization error decays exponentially fast with the entropy bound and the exact decay rate is determined for all \&\#945; \&\#8712; [0, \&\#8734;].}, subject = {Maßtheorie}, language = {en} } @phdthesis{Kreitmeier2006, author = {Kreitmeier, Wolfgang}, title = {Optimale Quantisierung verallgemeinerter Cantor-Verteilungen}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-913}, school = {Universit{\"a}t Passau}, year = {2006}, abstract = {F{\"u}r verallgemeinerte Cantor-Verteilungen, die im Eindimensionalen mittels klassischer Wischkonstruktion bzw. in h{\"o}heren Dimensionen {\"u}ber iterierte Funktionensysteme definiert werden, wird das Problem der optimalen Quantisierung unter bestimmten Voraussetzungen vollst{\"a}ndig gel{\"o}st. Es werden die optimalen Codeb{\"u}cher bestimmt und Formeln f{\"u}r den optimalen Quantisierungsfehler bewiesen. Im eindimensionalen Fall wird eine Existenzcharakterisierung der Quantisierungsdimension gegeben und unter bestimmten Voraussetzungen die Nichtexistenz des Quantisierungskoeffizienten gezeigt. Auch in h{\"o}heren Dimensionen wird f{\"u}r die betrachteten Verteilungen bewiesen, dass der Quantisierungskoeffizient, bei existenter Quantisierungsdimension, nicht existiert. Die gewonnenen Resultate werden auf die Gleichverteilungen von modifizierten klassischen fraktalen Mengen, wie das Sierpinski-Dreieck, die Cantormenge und den Cantor-Staub angewandt.}, subject = {Maßtheorie}, language = {de} } @unpublished{Kreitmeier2007, author = {Kreitmeier, Wolfgang}, title = {Optimal quantization of probabilities concentrated on small balls}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-12010}, year = {2007}, abstract = {We consider probability distributions which are uniformly distributed on a disjoint union of balls with equal radius. For small enough radius the optimal quantization error is calculated explicitly in terms of the ball centroids. We apply the results to special self-similar measures.}, subject = {Maßtheorie}, language = {en} } @unpublished{Kreitmeier2007, author = {Kreitmeier, Wolfgang}, title = {Asymptotic order of quantization for Cantor distributions in terms of Euler characteristic, Hausdorff and Packing measure}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-7374}, year = {2007}, abstract = {For homogeneous one-dimensional Cantor sets, which are not necessarily self-similar, we show under some restrictions that the Euler exponent equals the quantization dimension of the uniform distribution on these Cantor sets. Moreover for a special sub-class of these sets we present a linkage between the Hausdorff and the Packing measure of these sets and the high-rate asymptotics of the quantization error.}, subject = {Maßtheorie}, language = {en} } @phdthesis{Lauren2005, author = {Lauren, Verena}, title = {Semilineare Approximation in der Bildrekonstruktion}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-730}, school = {Universit{\"a}t Passau}, year = {2005}, abstract = {In der Bildverarbeitung spielen Segmentierungsalgorithmen, bei denen die Art der zu segmentierenden Menge schon im Voraus festgelegt werden kann und nur noch ihre Gr{\"o}ße und Lage angepasst werden muss, eine eher untergeordnete Rolle. Gr{\"u}nde hierf{\"u}r sind vor allem komplizierte Zielfunktionen und daraus resultierende lange Rechenzeiten, die zudem meist kein optimales Ergebnis liefern. Dabei kann eine mengenbasierte Segmentierung durchaus sinnvoll eingesetzt werden, wenn gewisse Rahmenbedingungen eingehalten werden. In dieser Arbeit wird eine Theorie zur allgemeinen mengenbasierten Segmentierung vorgestellt und untersucht, unter welchen Bedingungen optimale Segmentierungsergebnisse erreicht werden k{\"o}nnen. Die anschließenden Anwendungen best{\"a}tigen die N{\"u}tzlichkeit dieser Theorie.}, subject = {Optimale Rekonstruktion}, language = {de} } @phdthesis{Fischer2005, author = {Fischer, Andreas}, title = {Peano-differentiable functions in O-Minimal structures}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-673}, school = {Universit{\"a}t Passau}, year = {2005}, abstract = {We discuss several aspects of Peano-differentiable functions which are definable in an o-minimal structure expanding a real closed field. After recalling some already known results about o-minimal structures we develop techniques for the intrinsic study of differentiable functions in these structures. After this we study (ordinary) differentiable functions definable in an o-minimal structure and their continuiuty properties along curves of different differentiability classes. Then we generalise (ordinary) differentiability to Peano-differentiability. We study differentiability of certain Peano-derivatives of definable functions and characterise the sets of non-continuity of these derivatives. In the end we study extendability of these functions defined on closed sets and give sufficient conditions by which we can extend functions as Peano-differentiable functions.}, subject = {Semialgebraische Menge}, language = {en} } @phdthesis{Limbeck2013, author = {Limbeck, Jan}, title = {Computation of Approximate Border Bases and Applications}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-27197}, school = {Universit{\"a}t Passau}, year = {2013}, abstract = {This thesis addresses some of the algorithmic and numerical challenges associated with the computation of approximate border bases, a generalisation of border bases, in the context of the oil and gas industry. The concept of approximate border bases was introduced by D. Heldt, M. Kreuzer, S. Pokutta and H. Poulisse in "Approximate computation of zero-dimensional polynomial ideals" as an effective mean to derive physically relevant polynomial models from measured data. The main advantages of this approach compared to alternative techniques currently in use in the (hydrocarbon) industry are its power to derive polynomial models without additional a priori knowledge about the underlying physical system and its robustness with respect to noise in the measured input data. The so-called Approximate Vanishing Ideal (AVI) algorithm which can be used to compute approximate border bases and which was also introduced by D. Heldt et al. in the paper mentioned above served as a starting point for the research which is conducted in this thesis. A central aim of this work is to broaden the applicability of the AVI algorithm to additional areas in the oil and gas industry, like seismic imaging and the compact representation of unconventional geological structures. For this purpose several new algorithms are developed, among others the so-called Approximate Buchberger M{\"o}ller (ABM) algorithm and the Extended-ABM algorithm. The numerical aspects and the runtime of the methods are analysed in detail - based on a solid foundation of the underlying mathematical and algorithmic concepts that are also provided in this thesis. It is shown that the worst case runtime of the ABM algorithm is cubic in the number of input points, which is a significant improvement over the biquadratic worst case runtime of the AVI algorithm. Furthermore, we show that the ABM algorithm allows us to exercise more direct control over the essential properties of the computed approximate border basis than the AVI algorithm. The improved runtime and the additional control turn out to be the key enablers for the new industrial applications that are proposed here. As a conclusion to the work on the computation of approximate border bases, a detailed comparison between the approach in this thesis and some other state of the art algorithms is given. Furthermore, this work also addresses one important shortcoming of approximate border bases, namely that central concepts from exact algebra such as syzygies could so far not be translated to the setting of approximate border bases. One way to mitigate this problem is to construct a "close by" exact border bases for a given approximate one. Here we present and discuss two new algorithmic approaches that allow us to compute such close by exact border bases. In the first one, we establish a link between this task, referred to as the rational recovery problem, and the problem of simultaneously quasi-diagonalising a set of complex matrices. As simultaneous quasi-diagonalisation is not a standard topic in numerical linear algebra there are hardly any off-the-shelf algorithms and implementations available that are both fast and numerically adequate for our purposes. To bridge this gap we introduce and study a new algorithm that is based on a variant of the classical Jacobi eigenvalue algorithm, which also works for non-symmetric matrices. As a second solution of the rational recovery problem, we motivate and discuss how to compute a close by exact border basis via the minimisation of a sum of squares expression, that is formed from the polynomials in the given approximate border basis. Finally, several applications of the newly developed algorithms are presented. Those include production modelling of oil and gas fields, reconstruction of the subsurface velocities for simple subsurface geometries, the compact representation of unconventional oil and gas bodies via algebraic surfaces and the stable numerical approximation of the roots of zero-dimensional polynomial ideals.}, subject = {Computeralgebra}, language = {en} } @phdthesis{Capco2010, author = {Capco, Jose}, title = {Real Closed * Rings}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-25915}, school = {Universit{\"a}t Passau}, year = {2010}, abstract = {In this dissertation I examine a definition of real closure of commutative unitary reduced rings. I also give a characterization of rings that are real closed in this context and how one is able to arrive to such a real closure. There are sufficient examples to help the reader get a feel for real closed * rings and the real closure * of commutative unitary rings.}, language = {en} } @unpublished{KreitmeierLinder2011, author = {Kreitmeier, Wolfgang and Linder, Tamas}, title = {Entropy Density and Mismatch in High-Rate Scalar Quantization with R{\´e}nyi Entropy Constraint}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-26132}, year = {2011}, abstract = {Properties of scalar quantization with \$r\$th power distortion and constrained R\'enyi entropy of order \$\alpha\in (0,1)\$ are investigated. For an asymptotically (high-rate) optimal sequence of quantizers, the contribution to the R\'enyi entropy due to source values in a fixed interval is identified in terms of the "entropy density" of the quantizer sequence. This extends results related to the well-known point density concept in optimal fixed-rate quantization. A dual of the entropy density result quantifies the distortion contribution of a given interval to the overall distortion. The distortion loss resulting from a mismatch of source densities in the design of an asymptotically optimal sequence of quantizers is also determined. This extends Bucklew's fixed-rate (\$\alpha=0\$) and Gray \emph{et al.}'s variable-rate (\$\alpha=1\$)mismatch results to general values of the entropy order parameter \$\alpha\$}, subject = {Maßtheorie}, language = {de} } @phdthesis{Ullah2012, author = {Ullah, Ehsan}, title = {New Techniques for Polynomial System Solving}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-26815}, school = {Universit{\"a}t Passau}, year = {2012}, abstract = {Since any encryption map may be viewed as a polynomial map between finite dimensional vector spaces over finite fields, the security of a cryptosystem can be examined by studying the difficulty of solving large systems of multivariate polynomial equations. Therefore, algebraic attacks lead to the task of solving polynomial systems over finite fields. In this thesis, we study several new algebraic techniques for polynomial system solving over finite fields, especially over the finite field with two elements. Instead of using traditional Gr{\"o}bner basis techniques we focus on highly developed methods from several other areas like linear algebra, discrete optimization, numerical analysis and number theory. We study some techniques from combinatorial optimization to transform a polynomial system solving problem into a (sparse) linear algebra problem. We highlight two new kinds of hybrid techniques. The first kind combines the concept of transforming combinatorial infeasibility proofs to large systems of linear equations and the concept of mutants (finding special lower degree polynomials). The second kind uses the concept of mutants to optimize the Border Basis Algorithm. We study recent suggestions of transferring a system of polynomial equations over the finite field with two elements into a system of polynomial equalities and inequalities over the set of integers (respectively over the set of reals). In particular, we develop several techniques and strategies for converting the polynomial system of equations over the field with two elements to a polynomial system of equalities and inequalities over the reals (respectively over the set of integers). This enables us to make use of several algorithms in the field of discrete optimization and number theory. Furthermore, this also enables us to investigate the use of numerical analysis techniques such as the homotopy continuation methods and Newton's method. In each case several conversion techniques have been developed, optimized and implemented. Finally, the efficiency of the developed techniques and strategies is examined using standard cryptographic examples such as CTC and HFE. Our experimental results show that most of the techniques developed are highly competitive to state-of-the-art algebraic techniques.}, subject = {Polynoml{\"o}sung}, language = {en} } @phdthesis{Xiu2012, author = {Xiu, Xingqiang}, title = {Non-commutative Gr{\"o}bner Bases and Applications}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-26827}, school = {Universit{\"a}t Passau}, year = {2012}, abstract = {Commutative Gr{\"o}bner bases have a lot of applications in theory and practice, because they have many nice properties, they are computable, and there exist many efficient improvements of their computations. Non-commutative Gr{\"o}bner bases also have many useful properties. However, applications of non-commutative Gr{\"o}bner bases are rarely considered due to high complexity of computations. The purpose of this study was to improve the computation of non-commutative Gr{\"o}bner bases and investigate the applications of non-commutative Gr{\"o}bner bases. Gr{\"o}bner basis theory in free monoid rings was carefully revised and Gr{\"o}bner bases were precisely characterized in great detail. For the computations of Gr{\"o}bner bases, the Buchberger Procedure was formulated. Three methods, say interreduction on obstructions, Gebauer-M{\"o}ller criteria, and detecting redundant generators, were developed for efficiently improving the Buchberger Procedure. Further, the same approach was applied to study Gr{\"o}bner basis theory in free bimodules over free monoid rings. The Buchberger Procedure was also formulated and improved in this setting. Moreover, J.-C. Faugere's F4 algorithm was generalized to this setting. Finally, many meaningful applications of non-commutative Gr{\"o}bner bases were developed. Enumerating procedures were proposed to semi-decide some interesting undecidable problems. All the examples in the thesis were computed using the package gbmr of the computer algebra system ApCoCoA. The package was developed by the author. It contains dozens of functions for Gr{\"o}bner basis computations and many concrete applications. The package gbmr and a collection of interesting examples are available at http://www.apcocoa.org/.}, subject = {Gr{\"o}bner-Basis}, language = {en} } @unpublished{Kreitmeier2012, author = {Kreitmeier, Wolfgang}, title = {Asymptotic optimality of scalar Gersho quantizers}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-27080}, year = {2012}, abstract = {In his famous paper Gersho stressed that the codecells of optimal quantizers asymptotically make an equal contribution to the distortion of the quantizer. Motivated by this fact, we investigate in this paper quantizers in the scalar case, where each codecell contributes with exactly the same portion to the quantization error. We show that such quantizers of Gersho type - or Gersho quantizers for short - exist for non-atomic scalar distributions. As a main result we prove that Gersho quantizers are asymptotically optimal.}, subject = {Maßtheorie}, language = {en} } @phdthesis{Sonnleitner2022, author = {Sonnleitner, Mathias}, title = {The power of random information for numerical approximation and integration}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-11305}, school = {Universit{\"a}t Passau}, pages = {x, 165 Seiten}, year = {2022}, abstract = {This thesis investigates the quality of randomly collected data by employing a framework built on information-based complexity, a field related to the numerical analysis of abstract problems. The quality or power of gathered information is measured by its radius which is the uniform error obtainable by the best possible algorithm using it. The main aim is to present progress towards understanding the power of random information for approximation and integration problems. In the first problem considered, information given by linear functionals is used to recover vectors, in particular from generalized ellipsoids. This is related to the approximation of diagonal operators which are important objects of study in the theory of function spaces. We obtain upper bounds on the radius of random information both in a convex and a quasi-normed setting, which extend and, in some cases, improve existing results. We conjecture and partially establish that the power of random information is subject to a dichotomy determined by the decay of the length of the semiaxes of the generalized ellipsoid. Second, we study multivariate approximation and integration using information given by function values at sampling point sets. We obtain an asymptotic characterization of the radius of information in terms of a geometric measure of equidistribution, the distortion, which is well known in the theory of quantization of measures. This holds for isotropic Sobolev as well as H{\"o}lder and Triebel-Lizorkin spaces on bounded convex domains. We obtain that for these spaces, depending on the parameters involved, typical point sets are either asymptotically optimal or worse by a logarithmic factor, again extending and improving existing results. Further, we study isotropic discrepancy which is related to numerical integration using linear algorithms with equal weights. In particular, we analyze the quality of lattice point sets with respect to this criterion and obtain that they are suboptimal compared to uniform random points. This is in contrast to the approximation of Sobolev functions and resolves an open question raised in the context of a possible low discrepancy construction on the two-dimensional sphere.}, subject = {Komplexit{\"a}t / Algorithmus}, language = {en} } @phdthesis{Bachl2003, author = {Bachl, Walter}, title = {Interaktives orthogonales Zeichnen von planaren Graphen}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-392}, school = {Universit{\"a}t Passau}, year = {2003}, abstract = {Die Arbeit besch{\"a}ftigt sich mit dem automatischen Zeichnen von Graphen. Hier wird ein interaktiver Ansatz untersucht, bei dem der Graph mit einer Menge von Operationen Schritt f{\"u}r Schritt aufgebaut wird. Der Zielgraph und die Einf{\"u}gereihenfolge sind dabei nicht fest vorgegeben, sondern werden vom Benutzer bestimmt. In der Arbeit wird vor allem ein Szenario f{\"u}r zweifach zusammenh{\"a}ngende Graphen untersucht und ein f{\"u}r diese Zwecke passendes Zeichenmodell entwickelt. Dieser Ansatz wird dann um verschiedene Varianten erweitert. Außerdem wird gezeigt, dass das fl{\"a}chenminimale Zeichnen in dem neu entwickelten Zeichenmodell NP-vollst{\"a}ndig ist.}, subject = {Graphenzeichnen}, language = {de} } @phdthesis{Jovanovic2015, author = {Jovanovic, Philipp}, title = {Analysis and Design of Symmetric Cryptographic Algorithms}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-3319}, school = {Universit{\"a}t Passau}, pages = {216}, year = {2015}, abstract = {This doctoral thesis is dedicated to the analysis and the design of symmetric cryptographic algorithms. In the first part of the dissertation, we deal with fault-based attacks on cryptographic circuits which belong to the field of active implementation attacks and aim to retrieve secret keys stored on such chips. Our main focus lies on the cryptanalytic aspects of those attacks. In particular, we target block ciphers with a lightweight and (often) non-bijective key schedule where the derived subkeys are (almost) independent from each other. An attacker who is able to reconstruct one of the subkeys is thus not necessarily able to directly retrieve other subkeys or even the secret master key by simply reversing the key schedule. We introduce a framework based on differential fault analysis that allows to attack block ciphers with an arbitrary number of independent subkeys and which rely on a substitution-permutation network. These methods are then applied to the lightweight block ciphers LED and PRINCE and we show in both cases how to recover the secret master key requiring only a small number of fault injections. Moreover, we investigate approaches that utilize algebraic instead of differential techniques for the fault analysis and discuss advantages and drawbacks. At the end of the first part of the dissertation, we explore fault-based attacks on the block cipher Bel-T which also has a lightweight key schedule but is not based on a substitution-permutation network but instead on the so-called Lai-Massey scheme. The framework mentioned above is thus not usable against Bel-T. Nevertheless, we also present techniques for the case of Bel-T that enable full recovery of the secret key in a very efficient way using differential fault analysis. In the second part of the thesis, we focus on authenticated encryption schemes. While regular ciphers only protect privacy of processed data, authenticated encryption schemes also secure its authenticity and integrity. Many of these ciphers are additionally able to protect authenticity and integrity of so-called associated data. This type of data is transmitted unencrypted but nevertheless must be protected from being tampered with during transmission. Authenticated encryption is nowadays the standard technique to protect in-transit data. However, most of the currently deployed schemes have deficits and there are many leverage points for improvements. With NORX we introduce a novel authenticated encryption scheme supporting associated data. This algorithm was designed with high security, efficiency in both hardware and software, simplicity, and robustness against side-channel attacks in mind. Next to its specification, we present special features, security goals, implementation details, extensive performance measurements and discuss advantages over currently deployed standards. Finally, we describe our preliminary security analysis where we investigate differential and rotational properties of NORX. Noteworthy are in particular the newly developed techniques for differential cryptanalysis of NORX which exploit the power of SAT- and SMT-solvers and have the potential to be easily adaptable to other encryption schemes as well.}, subject = {Kryptologie}, language = {en} } @phdthesis{Le2015, author = {Le, Ngoc Long}, title = {Various Differents for 0-Dimensional Schemes and Applications}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-3386}, school = {Universit{\"a}t Passau}, pages = {205}, year = {2015}, abstract = {This thesis attempts to investigate the Noether, Dedekind, and K{\"a}hler differents for a 0-dimensional scheme X in the projective n-space P^n_K over an arbitrary field K. In particular, we focus on studying the relations between the algebraic structure of these differents and geometric properties of the scheme X. In Chapter 1 we give an outline to the problems this thesis is concerned with, a brief literature review for each problem, and the main results regarding these problems. Chapter 2 contains background results that we will need in the subsequent chapters. We introduce the concept of maximal p_j-subschemes of a 0-dimensional scheme X and give some descriptions of them and their Hilbert functions. Furthermore, we generalize the notion of a separator of a subscheme of X of degree deg(X)-1 to a set of separators of a maximal p_j-subscheme of X. In Chapter 3 we explore the Noether, Dedekind, and K{\"a}hler differents for 0-dimensional schemes X. First we define these differents for X, and take a look at how to compute these differents and examine their relations. Then we give an answer to the question "What are the Hilbert functions of these differents?" in some cases. In Chapter 4 we use the differents to investigate the Cayley-Bacharach property of 0-dimensional schemes over an arbitrary field K. The principal results of this chapter are characterizations of CB-schemes and of arithmetically Gorenstein schemes in terms of their Dedekind differents and a criterion for a 0-dimensional smooth scheme to be a complete intersection. We also generalize some results such as Dedekind's formula and the characterization of the Cayley-Bacharach property by using Liaison theory. In addition, several propositions on the uniformities are proven. In Chapter 5 we are interested in studying the Noether, Dedekind, and K{\"a}hler differents for finite special classes of schemes and finding out some applications of these differents. First, we investigate these differents for reduced 0-dimensional almost complete intersections X in P^n_K over a perfect field K. Then we investigate the relationships between these differents and the i-th Fitting ideals of the module of K{\"a}hler differentials of the homogeneous coordinate ring of X. Finally, we look more closely at the Hilbert functions and the regularity indices of these differents for fat point schemes.}, subject = {Kommutativer Ring}, language = {en} } @phdthesis{Lehner2016, author = {Lehner, Sabrina}, title = {The Asymptotic Behaviour of the Riemann Mapping Function at Analytic Cusps}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-3587}, school = {Universit{\"a}t Passau}, pages = {97}, year = {2016}, abstract = {The well-known Riemann Mapping Theorem states the existence of a conformal map of a simply connected proper domain of the complex plane onto the upper half plane. One of the main topics in geometric function theory is to investigate the behaviour of the mapping functions at the boundary of such domains. In this work, we always assume that a piecewise analytic boundary is given. Hereby, we have to distinguish regular and singular boundary points. While the asymptotic behaviour for regular boundary points can be investigated by using the Schwarz Reflection at analytic arcs, the situation for singular boundary points is far more complicated. In the latter scenario two cases have to be differentiated: analytic corners and analytic cusps. The first part of the thesis deals with the asymptotic behaviour at analytic corners where the opening angle is greater than 0. The results of Lichtenstein and Warschawski on the asymptotic behaviour of the Riemann map and its derivatives at an analytic corner are presented as well as the much stronger result of Lehman that the mapping function can be developed in a certain generalised power series which in turn enables to examine the o-minimal content of the Riemann Mapping Theorem. To obtain a similar statement for domains with analytic cusps, it is necessary to investigate the asymptotic behaviour of a Riemann map at the cusp and based on this result to determine the asymptotic power series expansion. Therefore, the aim of the second part of this work is to investigate the asymptotic behaviour of a Riemann map at an analytic cusp. A simply connected domain has an analytic cusp if the boundary is locally given by two analytic arcs such that the interior angle vanishes. Besides the asymptotic behaviour of the mapping function, the behaviour of its derivatives, its inverse, and the derivatives of the inverse are analysed. Finally, we present a conjecture on the asymptotic power series expansion of the mapping function at an analytic cusp.}, subject = {Geometrische Funktionentheorie}, language = {en} } @phdthesis{Hatzesberger2020, author = {Hatzesberger, Simon}, title = {Strongly Asymptotically Optimal Methods for the Pathwise Global Approximation of Stochastic Differential Equations with Coefficients of Super-linear Growth}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-8100}, school = {Universit{\"a}t Passau}, pages = {ii, 116 Seiten}, year = {2020}, abstract = {Our subject of study is strong approximation of stochastic differential equations (SDEs) with respect to the supremum and the L_p error criteria, and we seek approximations that are strongly asymptotically optimal in specific classes of approximations. For the supremum error, we prove strong asymptotic optimality for specific tamed Euler schemes relating to certain adaptive and to equidistant time discretizations. For the L_p error, we prove strong asymptotic optimality for specific tamed Milstein schemes relating to certain adaptive and to equidistant time discretizations. To illustrate our findings, we numerically analyze the SDE associated with the Heston-3/2-model originating from mathematical finance.}, subject = {Stochastische Differentialgleichung}, language = {en} } @phdthesis{Horaček2020, author = {Hor{\´a}ček, Jan}, title = {Algebraic and Logic Solving Methods for Cryptanalysis}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-7731}, school = {Universit{\"a}t Passau}, pages = {v, 154 Seiten}, year = {2020}, abstract = {Algebraic solving of polynomial systems and satisfiability of propositional logic formulas are not two completely separate research areas, as it may appear at first sight. In fact, many problems coming from cryptanalysis, such as algebraic fault attacks, can be rephrased as solving a set of Boolean polynomials or as deciding the satisfiability of a propositional logic formula. Thus one can analyze the security of cryptosystems by applying standard solving methods from computer algebra and SAT solving. This doctoral thesis is dedicated to studying solvers that are based on logic and algebra separately as well as integrating them into one such that the combined solvers become more powerful tools for cryptanalysis. This disseration is divided into three parts. In this first part, we recall some theory and basic techniques for algebraic and logic solving. We focus mainly on DPLL-based SAT solving and techniques that are related to border bases and Gr{\"o}bner bases. In particular, we describe in detail the Border Basis Algorithm and discuss its specialized version for Boolean polynomials called the Boolean Border Basis Algorithm. In the second part of the thesis, we deal with connecting solvers based on algebra and logic. The ultimate goal is to combine the strength of different solvers into one. Namely, we fuse the XOR reasoning from algebraic solvers with the light, efficient design of SAT solvers. As a first step in this direction, we design various conversions from sets of clauses to sets of Boolean polynomials, and vice versa, such that solutions and models are preserved via the conversions. In particular, based on a block-building mechanism, we design a new blockwise algorithm for the CNF to ANF conversion which is geared towards producing fewer and lower degree polynomials. The above conversions allow usto integrate both solvers via a communication interface. To reach an even tighter integration, we consider proof systems that combine resolution and polynomial calculus, i.e. the two most used proof systems in logic and algebraic solving. Based on such a proof system, which we call SRES, we introduce new types of solving algorithms that demostrate the synergy between Gr{\"o}bner-like and DPLL-like solving. At the end of the second part of the dissertation, we provide some experiments based on a new benchmark which illustrate that the our new method based on DPLL has the potential to outperform CDCL SAT solvers. In the third part of the thesis, we focus on practical attacks on various cryptograhic primitives. For instance, we apply SAT solvers in the case of algebraic fault attacks on the symmetric ciphers LED and derivatives of the block cipher AES. The main goal there is to derive so-called fault equations automatically from the hardware description of the cryptosystem and thus automatizate the attack. To give some extra power to a SAT solver that inverts the hash functions SHA-1 and SHA-2, we describe how to tweak the SAT solver using a programmatic interface such that the propagation of the solver and thus the attack itself is improved.}, subject = {Kryptoanalyse}, language = {en} } @phdthesis{Fink2019, author = {Fink, Thomas}, title = {Curvature Detection by Integral Transforms}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-7684}, school = {Universit{\"a}t Passau}, pages = {viii, 194 Seiten}, year = {2019}, abstract = {In various fields of image analysis, determining the precise geometry of occurrent edges, e.g. the contour of an object, is a crucial task. Especially the curvature of an edge is of great practical relevance. In this thesis, we develop different methods to detect a variety of edge features, among them the curvature. We first examine the properties of the parabolic Radon transform and show that it can be used to detect the edge curvature, as the smoothness of the parabolic Radon transform changes when the parabola is tangential to an edge and also, when additionally the curvature of the parabola coincides with the edge curvature. By subsequently introducing a parabolic Fourier transform and establishing a precise relation between the smoothness of a certain class of functions and the decay of the Fourier transform, we show that the smoothness result for the parabolic Radon transform can be translated into a change of the decay rate of the parabolic Fourier transform. Furthermore, we introduce an extension of the continuous shearlet transform which additionally utilizes shears of higher order. This extension, called the Taylorlet transform, allows for a detection of the position and orientation, as well as the curvature and other higher order geometric information of edges. We introduce novel vanishing moment conditions which enable a more robust detection of the geometric edge features and examine two different constructions for Taylorlets. Lastly, we translate the results of the Taylorlet transform in R^2 into R^3 and thereby allow for the analysis of the geometry of object surfaces.}, subject = {Kr{\"u}mmung}, language = {en} } @phdthesis{Lorenz2018, author = {Lorenz, Florian}, title = {Analyse und Erzeugung von glatten Fl{\"a}chen{\"u}berg{\"a}ngen f{\"u}r das CNC-Fr{\"a}sen}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-5166}, school = {Universit{\"a}t Passau}, pages = {i, 149 Seiten}, year = {2018}, abstract = {In dieser Arbeit werden numerisch stabile Methoden zur Pr{\"u}fung von Stetigkeiten an Fl{\"a}chen{\"u}berg{\"a}ngen vorgestellt und Algorithmen zur Erzeugung von G^2-stetigen Fl{\"a}chen{\"u}berg{\"a}ngen hergeleitet.}, subject = {Differentialgeometrie}, language = {de} } @phdthesis{Apfler2018, author = {Apfler, Sabine}, title = {Erwerb mathematischer Kompetenzen in der Regelvolksschule}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-5593}, school = {Universit{\"a}t Passau}, pages = {447 Seiten}, year = {2018}, abstract = {Durch die Einf{\"u}hrung der Bildungsstandards{\"u}berpr{\"u}fungen erh{\"a}lt die Frage nach der Kompetenzentwicklung von Kindern einen zentralen Stellenwert in Bildungsangelegenheiten. Lehrkr{\"a}fte stehen dadurch vor der Aufgabe, ihren Unterricht diesbez{\"u}glich zu ver{\"a}ndern und L{\"o}sungen zu finden. Die Frage, ob der Einsatz der Montessorip{\"a}dagogik die Entwicklung mathematischer Kompetenzen positiv beeinflusst, wurde im Rahmen einer Dissertation diskutiert und empirisch erforscht werden. Der Arbeit liegt folgende Fragestellung zugrunde: Kann die Montessorip{\"a}dagogik dazu beitragen, dass Sch{\"u}lerinnen und Sch{\"u}ler in {\"o}sterreichischen Regelvolksschulen ein hohes Kompetenzniveau in Mathematik erreichen? Wie unterscheidet sich die Kompetenzentwicklung in Klassen, die von Lehrpersonen mit beziehungsweise ohne Montessoriausbildung unterrichtet werden? Bei der vorliegenden Studie handelt es sich um eine L{\"a}ngsschnittuntersuchung mit zwei Testzeitpunkten. Im Sinne einer summativen Evaluation wurden zu Beginn der Untersuchung die Basiskompetenzen mit dem „Entwicklungsorientierten Test zur Erfassung mathematischer Basiskompetenzen ab Schuleintritt (MBK 1+)" analysiert. Am Ende der dritten Schulstufe wurde eine abschließende Bewertung im Rahmen der IKM-Testung des BIFIE vorgenommen, um die Wirksamkeit des Einsatzes der Montessorimethode zu ermitteln. Untersucht wurden 14 Volksschulklassen, die entweder einer Untersuchungsgruppe oder einer Kontrollgruppe zugeordnet wurden. Die Klassen der Untersuchungsgruppe wurden von Lehrpersonen mit Montessori-Diplomausbildung unterrichtet, die Klassen der Kontrollgruppe von Lehrpersonen, die keine Montessoriausbildung absolviert haben. An der Studie nahmen 248 Sch{\"u}lerinnen und Sch{\"u}ler teil. Der Untersuchungszeitraum erstreckte sich {\"u}ber insgesamt drei Schuljahre. Die Ergebnisse der Studie zeigen Tendenzen, dass sich der Einsatz der Montessorip{\"a}dagogik positiv auf die Kompetenzentwicklung der Kinder im Bereich der Mathematik auswirkt.}, subject = {{\"O}sterreich}, language = {de} } @phdthesis{Klaus2019, author = {Klaus, Tina}, title = {Complexity Analysis of Quantizations of Multidimensional Stochastic Differential Equations}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-7665}, school = {Universit{\"a}t Passau}, pages = {iv, 166 Seiten}, year = {2019}, abstract = {The dissertation is located in the field of quantizations of certain stochastic processes, namely a solution X of a multidimensional stochastic differential equation (SDE). The quantization problem for X consists in approximating X by a a random element which takes only finitely many values. Our main interest lies in the investigation of the asymptotic behavior of the Nth minimal quantization error of X as N tends to infinity, which incorporates the determination of both the sharp rate of convergence and explicit asymptotic constants. Especially explicit asymptotic constants have been so far unknown in the context of multidimensional SDEs. Furthermore, as part of our analysis, we provide a method which yields a strongly asymptotically optimal sequence of N-quantization of X. In certain special cases our method is fully constructive and the algorithm is easy to implement.}, subject = {Stochastische Differentialgleichung}, language = {en} } @phdthesis{Stadler2015, author = {Stadler, Thomas}, title = {Eine Anwendung der Invariantentheorie auf das Korrespondenzproblem lokaler Bildmerkmale}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-4026}, school = {Universit{\"a}t Passau}, pages = {XII, 324 S.}, year = {2015}, abstract = {Als sich in der ersten H{\"a}lfte des 19. Jahrhunderts zunehmend mehr bedeutende Mathematiker mit der Suche nach Invarianten besch{\"a}ftigten, konnte nat{\"u}rlich noch niemand vorhersehen, dass die Invariantentheorie mit Beginn des Computerzeitalters in der Bildverarbeitung bzw. dem Rechnersehen ein {\"a}ußerst fruchtbares Anwendungsgebiet finden wird. In dieser Arbeit wird eine neue Anwendungsm{\"o}glichkeit der Invariantentheorie in der Bildverarbeitung vorgestellt. Dazu werden lokale Bildmerkmale betrachtet. Dabei handelt es sich um die Koordinaten einer Polynomfunktion bzgl. einer geeigneten Orthonormalbasis von P_n(R^2,R), die die zeitintegrierte Sensorinputfunktion auf lokalen Pixelfenstern bestm{\"o}glich approximiert. Diese Bildmerkmale werden in vielen Anwendungen eingesetzt, um Objekte in Bildern zu erkennen und zu lokalisieren. Beispiele hierf{\"u}r sind die Detektion von Werkst{\"u}cken an einem Fließband oder die Verfolgung von Fahrbahnmarkierungen in Fahrerassistenzsystemen. Modellieren l{\"a}sst sich die Suche nach einem Muster in einem Suchbild als Paar von Stereobildern, auf denen lokal die affin-lineare Gruppe AGL(R) operiert. Will man also feststellen, ob zwei lokale Pixelfenster in etwa Bilder eines bestimmten dreidimensionalen Oberfl{\"a}chenausschnitts sind, ist zu kl{\"a}ren, ob die Bildausschnitte durch eine Operation der Gruppe AGL(R) n{\"a}herungsweise ineinander {\"u}bergef{\"u}hrt werden k{\"o}nnen. Je nach Anwendung gen{\"u}gt es bereits, passende Untergruppen G von AGL(R) zu betrachten. Dank der lokalen Approximation durch Polynomfunktionen induziert die Operation einer Untergruppe G eine Operation auf dem reellen Vektorraum P_n(R^2,R). Damit l{\"a}sst sich das Korrespondenzproblem auf die Frage reduzieren, ob es eine Transformation T in G gibt so, dass p ungef{\"a}hr mit der Komposition von q und T f{\"u}r die zugeh{\"o}rigen Approximationspolynome p,q in P_n(R^2,R) gilt. Mit anderen Worten, es ist zu kl{\"a}ren, ob sich p und q n{\"a}herungsweise in einer G-Bahn befinden, eine typische Fragestellung der Invariantentheorie. Da nur lokale Bildausschnitte betrachtet werden, gen{\"u}gt es weiter, Untergruppen G von GL_2(R) zu betrachten. Dann erh{\"a}lt man sofort auch die Antwort f{\"u}r das semidirekte Produkt von R^2 mit G. Besonders interessant f{\"u}r Anwendungen ist hierbei die spezielle orthogonale Gruppe G=SO_2(R) und damit insgesamt die eigentliche Euklidische Gruppe. F{\"u}r diese Gruppe und spezielle Pixelfenster ist das Korrespondenzproblem bereits gel{\"o}st. In dieser Arbeit wird das Problem in eben dieser Konstellation ebenfalls gel{\"o}st, allerdings auf elegante Weise mit Methoden der Invariantentheorie. Der Ansatz, der hier vorgestellt wird, ist aber nicht auf diese Gruppe und spezielle Pixelfenster begrenzt, sondern leicht auf weitere F{\"a}lle erweiterbar. Dazu ist insbesondere zu kl{\"a}ren, wie sich sogenannte fundamentale Invarianten von lokalen Bildmerkmalen, also letztendlich Invarianten von Polynomfunktionen, berechnen lassen, d.h. Erzeugendensysteme der entsprechenden Invariantenringe. Mit deren Hilfe l{\"a}sst sich die Zugeh{\"o}rigkeit einer Polynomfunktion zur Bahn einer anderen Funktion auf einfache Weise untersuchen. Neben der Vorstellung des Verfahrens zur Korrespondenzfindung und der daf{\"u}r notwendigen Theorie werden in dieser Arbeit Erzeugendensysteme von Invariantenringen untersucht, die besonders "sch{\"o}ne" Eigenschaften besitzen. Diese sch{\"o}nen Erzeugendensysteme von Unteralgebren werden, analog zu Gr{\"o}bner-Basen als Erzeugendensysteme von Idealen, SAGBI-Basen genannt ("Subalgebra Analogs to Gr{\"o}bner Bases for Ideals"). SAGBI-Basen werden hier insbesondere aus algorithmischer Sicht behandelt, d.h. die Berechnung von SAGBI-Basen steht im Vordergrund. Dazu werden verschiedene Algorithmen erarbeitet, deren Korrektheit bewiesen und implementiert. Daraus resultiert ein Software-Paket zu SAGBI-Basen f{\"u}r das Computeralgebrasystem ApCoCoA, dessen Funktionalit{\"a}t in diesem Umfang in keinem Computeralgebrasystem zu finden sein wird. Im Zuge der Umsetzung der einzelnen Algorithmen konnte außerdem die Theorie der SAGBI-Basen an zahlreichen Stellen erweitert werden.}, language = {de} } @phdthesis{Sipal2017, author = {Sipal, Bilge}, title = {Border Basis Schemes}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-4702}, school = {Universit{\"a}t Passau}, year = {2017}, abstract = {The basic idea of border basis theory is to describe a zero-dimensional ring P/I by an order ideal of terms whose residue classes form a K-vector space basis of P/I. The O-border basis scheme is a scheme that parametrizes all zero-dimensional ideals that have an O-border basis. In general, the O-border basis scheme is not an affine space. Subsequently, in [Huib09] it is proved that if an order ideal with "d" elements is defined in a two-dimensional polynomial ring and it is of some special shapes, then the O-border basis scheme is isomorphic to the affine space of dimension 2d. This thesis is dedicated to find a more general condition for an O-border basis scheme to be isomorphic to an affine space of dimension "nd" that is independent of the shape of the order ideal with "d" elements and "n" is the dimension of the polynomial ring that the order ideal is defined in. We accomplish this in 6 Chapters. In Chapters 2 and 3 we develop the concepts and properties of border basis schemes. In Chapter 4 we transfer the smoothness criterion (see [Huib05]) for the point (0,...,0) in a Hilbert scheme of points to the monomial point of the border basis scheme by employing the tools from border basis theory. In Chapter 5 we explain trace and Jacobi identity syzygies of the defining equations of a O-border basis scheme and characterize them by the arrow grading. In Chapter 6 we give a criterion for the isomorphism between 2d dimensional affine space and O-border basis scheme by using the results from Chapters 3 and Chapter 4. The techniques from other chapters are applied in Chapter 6.1 to segment border basis schemes and in Chapter 6.2 to O-border basis schemes for which O is of the sawtooth form.}, subject = {Polynomring}, language = {en} } @phdthesis{Handeck2016, author = {Handeck, J{\"o}rg}, title = {Analyse und Korrektur von Teileprogrammen f{\"u}r numerisch gesteuerte Werkzeugmaschinen}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-4546}, school = {Universit{\"a}t Passau}, pages = {102 S.}, year = {2016}, abstract = {Splinekurven sind oft das erste Mittel der Wahl, wenn Daten interpoliert oder approximiert werden sollen. Sie spielen in vielen praktischen Anwendungsbereichen eine wichtige Rolle und sind in Bereichen des CAD/CAM nicht mehr weg zu denken. In der vorliegenden Arbeit werden in diesem Kontext Bahnpunkte zur Steuerung von Werkzeugmaschinen untersucht. Die Analyse wird mit Hilfe eines Multiresolution (MRA) Ansatzes f{\"u}r Splinekurven mit adaptiven Knotenfolgen realisiert. Dieser MRA Ansatz basiert auf einer Least-Squares-Projektion zum Knotenentfernen und unterscheidet sich somit zu bekannten Ans{\"a}tzen, die auf orthogonalen Komplementen aufbauen. Des Weiteren wird ein Konzept zur Approximation von Orientierungsdaten mittels homogenen Quaternionensplines vorgestellt. Diese Splines leben auf der Sph{\"a}re und lassen sich mittels Knotenentfernen bzw. einf{\"u}gen verfeinern. Somit l{\"a}sst sich das vorgestellte MRA-Analyseverfahren ebenfalls auf diese Kurven anwenden. Weiter konnte f{\"u}r diese Kurven eine konvexe H{\"u}lle-Eigenschaft nachgewiesen werden.}, subject = {Spline}, language = {de} } @phdthesis{Pfeffer2017, author = {Pfeffer, Wolfgang}, title = {Qualitative Entwicklung der Begriffsbildung im Fach Mathematik in der Studieneingangsphase}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-4948}, school = {Universit{\"a}t Passau}, pages = {x, 331 Seiten}, year = {2017}, abstract = {Der {\"U}bergang vom sekund{\"a}ren zum terti{\"a}ren Bildungsbereich im Fach Mathematik stellt in den vergangenen Jahren ein zentrales Forschungsinteresse der mathematikdidaktischen Forschung dar. Das Forschungsfeld macht hierbei drei grundlegende Bedingungsfaktoren aus: epistemologische und kognitive, soziologische und kulturelle sowie didaktische Schwierigkeiten. Der Schwerpunkt der vorliegenden Arbeit liegt auf dem ersten Bereich, der den sich wandelnden Charakter der Mathematik inkludiert. F{\"u}r viele Studienanf{\"a}ngerinnen und -anf{\"a}nger ist der Wechsel von der Schule zur Universit{\"a}t "traumatisch", da sich das Anforderungsprofil an der Hochschule doch deutlich von dem bisher Gewohnten abhebt. Gerade die Studieneingangsphase ist f{\"u}r den sp{\"a}teren Studienerfolg als wichtigster Abschnitt anzusehen; werden die vielfach vorhandenen fachlichen Defizite sowie falschen Vorstellungen nicht beseitigt, f{\"u}hrt dies oft zu einem vorzeitigen Studienabbruch. Untersuchungen zur mathematischen Begriffsbildung {\"u}ber einen l{\"a}ngeren Zeitraum im Verlauf eines Hochschulstudiums fehlen bislang. Hieraus ergibt sich die Motivation f{\"u}r das in dieser Arbeit beschriebene Forschungsprojekt, das sich in drei Teile gliedert. Der erste Teil fasst den Stand der Forschung zum {\"U}bergang Schule -- Hochschule im Fach Mathematik zusammen. Der Fokus richtet sich dabei auf den sich wandelnden Charakter der Mathematik sowie die unterschiedlichen Anforderungen in Bezug auf die Begriffsbildung. Der zweite Teil stellt mathematisches Vorwissen als m{\"o}glichen Bedingungsfaktor f{\"u}r den Studienerfolg dar und beschreibt anschließend Konzeption, Auswertung sowie die Diskussion der Ergebnisse eines Fragebogens zum Hintergrundwissen Mathematik. Der dritte Teil der Arbeit beschreibt eine qualitative und l{\"a}ngsschnittlich durchgef{\"u}hrte, leitfadengest{\"u}tzte Interviewstudie, in deren Rahmen die gleiche Stichprobe im Laufe der ersten beiden Semester zu drei unterschiedlichen Zeitpunkten befragt wurde. Im Hinblick auf die praktische Relevanz f{\"u}r die Lehre wurden anhand der {\"A}ußerungen der Studierenden Fehlvorstellungen hinsichtlich der mathematischen Konzepte identifiziert und kategorisiert. Weiter wird eine Klassifikation der studentischen Vorstellungen hinsichtlich deren wissenschaftlichen Qualit{\"a}t vorgenommen sowie die Entwicklung dieser {\"u}ber die drei Interviewzeitpunkte hinweg beschrieben. Die Ergebnisse der Arbeit zeigen einerseits massive Defizite der Studienanf{\"a}ngerinnen und -anf{\"a}nger in Kenntnissen und Fertigkeiten mathematischen Grundwissens. Dar{\"u}ber hinaus erfolgt auch die Begriffsbildung resp. -entwicklung hinsichtlich zentraler mathematischer Konzepte der Hochschulmathematik auf sehr niedrigem Niveau. Als Indiz hierf{\"u}r zeugen die vielf{\"a}ltig identifizierten Fehlvorstellungen, die sich {\"u}ber alle Interviewzeitpunkte hinweg zeigten. Hieraus resultiert eine verst{\"a}rkte Notwendigkeit der F{\"o}rderung der Begriffsbildung sowie -entwicklung in der Studieneingangsphase.}, subject = {Begriffsbildung}, language = {de} } @phdthesis{Ruppert2017, author = {Ruppert, Julia}, title = {Asymptotic Expansion for the Time Evolution of the Probability Distribution Given by the Brownian Motion on Semialgebraic Sets}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-5069}, school = {Universit{\"a}t Passau}, pages = {vi, 174 S.}, year = {2017}, abstract = {In this thesis, we examine whether the probability distribution given by the Brownian Motion on a semialgebraic set is definable in an o-minimal structure and we establish asymptotic expansions for the time evolution. We study the probability distribution as an example for the occurrence of special parameterized integrals of a globally subanalytic function and the exponential function of a globally subanalytic function. This work is motivated by the work of Comte, Lion and Rolin, which considered parameterized integrals of globally subanalytic functions, of Cluckers and Miller, which examined parameterized integrals of constructible functions, and by the work of Cluckers, Comte, Miller, Rolin and Servi, which treated oscillatory integrals of globally subanalytic functions. In the one dimensional case we show that the probability distribution on a family of sets, which are definable in an o-minimal structure, are definable in the Pfaffian closure. In the two-dimensional case we investigate asymptotic expansions for the time evolution. As time t approaches zero, we show that the integrals behave like a Puiseux series, which is not necessarily convergent. As t tends towards infinity, we show that the probability distribution is definable in the expansion of the real ordered field by all restricted analytic functions if the semialgebraic set is bounded. For this purpose, we apply results for parameterized integrals of globally subanalytic functions of Lion and Rolin. By establishing the asymptotic expansion of the integrals over an unbounded set, we demonstrate that this expansion has the form of convergent Puiseux series with negative exponents and their logarithm. Subsequently, we get that the asymptotic expansion is definable in an o-minimal structure. Finally, we study the three-dimensional case and give the proof that the probability distribution given by the Brownian Motion behaves like a Puiseux series as time t tends towards zero. As t approaches infinity and the semialgebraic set is bounded, it can be ascertained that the probability distribution has the form of a constructible function by results of Cluckers and Miller and therefore it is definable in an o-minimal structure. If the semialgebraic set is unbounded, we establish the asymptotic expansions and prove that the probability distribution given by the Brownian Motion on unbounded sets has an asymptotic expansion of the form of a constructible function. In consequence of that, the asymptotic expansion is definable in an o-minimal structure.}, subject = {Brownsche Bewegung}, language = {en} } @phdthesis{Guetschow2018, author = {G{\"u}tschow, Silja}, title = {Roulets - Eine Integraltransformation zur Bestimmung gerichteter Singularit{\"a}ten}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-5929}, school = {Universit{\"a}t Passau}, pages = {vii, 104 Seiten}, year = {2018}, abstract = {In dieser Arbeit wird eine neue Integraltransformation, die Roulettransformation, eingef{\"u}hrt. Diese arbeitet mit anisotropen Skalierungen und Rotationen. Es wird gezeigt, dass die Roulettransformation allgemeine gerichtete Singularit{\"a}ten im Sinne von temperierten Distributionen aufl{\"o}st. Die Abklingraten an Punkt- sowie Liniensingularit{\"a}ten werden explizit angegeben.}, subject = {Integraltransformation}, language = {de} } @phdthesis{Kell2019, author = {Kell, Christian}, title = {A Structure-based Attack on the Linearized Braid Group-based Diffie-Hellman Conjugacy Problem in Combination with an Attack using Polynomial Interpolation and the Chinese Remainder Theorem}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-6476}, school = {Universit{\"a}t Passau}, pages = {xi, 209 Seiten}, year = {2019}, abstract = {This doctoral thesis is dedicated to improve a linear algebra attack on the so-called braid group-based Diffie-Hellman conjugacy problem (BDHCP). The general procedure of the attack is to transform a BDHCP to the problem of solving several simultaneous matrix equations. A first improvement is achieved by reducing the solution space of the matrix equations to matrices that have a specific structure, which we call here the left braid structure. Using the left braid structure the number of matrix equations to be solved reduces to one. Based on the left braid structure we are further able to formulate a structure-based attack on the BDHCP. That is to transform the matrix equation to a system of linear equations and exploiting the structure of the corresponding extended coefficient matrix, which is induced by the left braid structure of the solution space. The structure-based attack then has an empirically high probability to solve the BDHCP with significantly less arithmetic operations than the original attack. A third improvement of the original linear algebra attack is to use an algorithm that combines Gaussian elimination with integer polynomial interpolation and the Chinese remainder theorem (CRT), instead of fast matrix multiplication as suggested by others. The major idea here is to distribute the task of solving a system of linear equations over a giant finite field to several much smaller finite fields. Based on our empirically measured bounds for the degree of the polynomials to be interpolated and the bit size of the coefficients and integers to be recovered via the CRT, we conclude an improvement of the run time complexity of the original algorithm by a factor of n^8 bit operations in the best case, and still n^6 in the worst case.}, subject = {Kryptologie}, language = {en} } @phdthesis{Tueno2020, author = {Tueno, Anselme}, title = {Multiparty Protocols for Tree Classifiers}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-8251}, school = {Universit{\"a}t Passau}, pages = {xvii, 171 Seiten}, year = {2020}, abstract = {Cryptography is the scientific study of techniques for securing information and communication against adversaries. It is about designing and analyzing encryption schemes and protocols that protect data from unauthorized reading. However, in our modern information-driven society with highly complex and interconnected information systems, encryption alone is no longer enough as it makes the data unintelligible, preventing any meaningful computation without decryption. On the one hand, data owners want to maintain control over their sensitive data. On the other hand, there is a high business incentive for collaborating with an untrusted external party. Modern cryptography encompasses different techniques, such as secure multiparty computation, homomorphic encryption or order-preserving encryption, that enable cloud users to encrypt their data before outsourcing it to the cloud while still being able to process and search on the outsourced and encrypted data without decrypting it. In this thesis, we rely on these cryptographic techniques for computing on encrypted data to propose efficient multiparty protocols for order-preserving encryption, decision tree evaluation and kth-ranked element computation. We start with Order-preserving encryption (OPE) which allows encrypting data, while still enabling efficient range queries on the encrypted data. However, OPE is symmetric limiting, the use case to one client and one server. Imagine a scenario where a Data Owner (DO) outsources encrypted data to the Cloud Service Provider (CSP) and a Data Analyst (DA) wants to execute private range queries on this data. Then either the DO must reveal its encryption key or the DA must reveal the private queries. We overcome this limitation by allowing the equivalent of a public-key OPE. Decision trees are common and very popular classifiers because they are explainable. The problem of evaluating a private decision tree on private data consists of a server holding a private decision tree and a client holding a private attribute vector. The goal is to classify the client's input using the server's model such that the client learns only the result of the classification, and the server learns nothing. In a first approach, we represent the tree as an array and execute only d interactive comparisons (instead of 2 d as in existing solutions), where d denotes the depth of the tree. In a second approach, we delegate the complete tree evaluation to the server using somewhat or fully homomorphic encryption where the ciphertexts are encrypted under the client's public key. A generalization of a decision tree is a random forest that consists of many decision trees. A classification with a random forest evaluates each decision tree in the forest and outputs the classification label which occurs most often. Hence, the classification labels are ranked by their number of occurrences and the final result is the best ranked one. The best ranked element is a special case of the kth-ranked element. In this thesis, we consider the secure computation of the kth-ranked element in a distributed setting with applications in benchmarking and auctions. We propose different approaches for privately computing the kth-ranked element in a star network, using either garbled circuits or threshold homomorphic encryption.}, subject = {Mathematik}, language = {en} } @phdthesis{Tran2015, author = {Tran, Nguyen Khanh Linh}, title = {Kaehler Differential Algebras for 0-Dimensional Schemes and Applications}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-3290}, school = {Universit{\"a}t Passau}, pages = {158}, year = {2015}, abstract = {The aim of this dissertation is to investigate Kaehler differential algebras and their Hilbert functions for 0-dimensional schemes in P^n. First we give relations between Kaehler differential 1-forms of fat point schemes and another fat point schemes. Then we determine the Hilbert polynomial and give a sharp bound for the regularity index of the module of Kaehler differential m-forms, for 0