Zerlegungen von Knesergraphen in hochzusammenhängende Teile. - Ilmenau. - 33 Seiten
Technische Universität Ilmenau, Masterarbeit 2024
In der vorliegenden Masterarbeit wird eine Vermutung Thomassens anhand von Knesergraphen überprüft. Thomassen hatte vermutet, dass jeder (s+t+1)-zusammenhängende Graph eine Zerlegung in einen s-zusammenhängenden und einen t-zusammenhängenden Teil besitzt. Dabei besteht eine Zerlegung aus zwei disjunkten Teilgraphen, sodass jede Ecke des Graphen in genau einem der beiden Teile enthalten ist. Ein Knesergraph K(n,k) ist definiert auf den k-elementigen Teilmengen der ersten n natürlichen Zahlen als Ecken, wobei zwei Ecken genau dann zueinander benachbart sind, falls sie disjunkt sind. Dazu wurden im ersten Teil der Arbeit disjunkte Teilgraphen betrachtet, die zu einer Zerlegung erweitert werden können. Damit konnte für den 7-zusammenhängenden Knesergraph K(13,6) eine Zerlegung in zwei 3-zusammenhängende Teile konstruiert werden. Weiter wurde dies für alle 7-zusammenhängenden Knesergraphen gezeigt. Außerdem konnte für allgemeine (s+t+1)-zusammenhängende Knesergraphen K(2k+1,k) die Vermutung bestätigt werden. Im zweiten Teil der Arbeit wurde die Struktur der trennenden Eckenmengen von Knesergraphen analysiert. Anschließend wurde ein Teilgraph gelöscht und der Zusammenhang des übrigen Graphen untersucht. Damit konnte für (t+4)-zusammenhängende Knesergraphen gezeigt werden, dass es immer eine Zerlegung in einen 3-zusammenhängenden und einen t-zusammenhängenden Teil gibt. Schließlich konnte für bliebige s und t für unendlich viele Knesergraphen die gewünschte Zerlegung nachgewiesen werden.
Data Augmentation für verallgemeinerte lineare Zustandsraummodelle. - Ilmenau. - 53 Seiten
Technische Universität Ilmenau, Masterarbeit 2024
Zeitabhängige nicht-negative ganzzahlige Beobachtungen lassen sich oft durch ein verallgemeinertes lineares Zustandsraummodell beschreiben. Dabei lässt sich eine geschlossene Form der bedingten Verteilung der Zustände gegeben den Beobachtungen nicht immer analytisch bestimmen. Die Berechnung von Integralen bezüglich dieser Verteilung ist dann nur approximativ möglich, zum Beispiel mithilfe von Markov Chain Monte Carlo Methoden, wie der Data Augmentation. Das Hauptergebnis dieser Masterarbeit ist die Herleitung eines Data Augmentation Algorithmus für Zustandsraummodelle mit bedingt binomial- oder negativ-binomialverteilten Beobachtungen und gaußschen Zustände, die einen autoregressiven Prozess bilden. Die Konstruktion und Simulation des Markovprozesses basiert auf der Pólya-Gammaverteilung (Polson et al. 2013) und dem Algorithmus zur Simulation aus dieser sowie dem forward filter, backwards sampling Algorithmus (Frühwirth-Schnatter 1994). Der resultierende Algorithmus eignet sich aufgrund seiner Effizienz auch für hochdimensionale Zeitreihen. Anhand mehrerer Beispiele wird die Anwendung auf reale Daten diskutiert und die numerischen Ergebnisse mit denen des Importance Samplings verglichen.
Kalmanfilter auf Graphen. - Ilmenau. - 49 Seiten
Technische Universität Ilmenau, Masterarbeit 2024
Der Kalmanfilter ist ein beliebtes statistisches Hilfsmittel zur Vorhersage in zahlreichen Modellen verschiedenster Anwendungsgebiete. Ziel dieser Arbeit ist es, den Kalmanfilter auf einem Graphenmodell anzuwenden. Hierzu wird ein Zustandsraummodell auf einem gerichteten azyklischen Graphen definiert. Die Ecken werden univariaten Zuständen und Beobachtungen entsprechen, die Kanten Übergängen zwischen diesen. Es wird ein Algorithmus zur Vorhersage dieser Zustände, bedingt auf die Beobachtungen vorgestellt, welcher auf den Ecken des Graphen iteriert. Seine Vorgehensweise entspricht der des Kalmanfilters. Hierbei wird die vorteilhafte inverse Wurzelform ausgenutzt. Weiterhin wird auf den Zusammenhang der bedingten Unabhängigkeiten in Graphenmodellen auf gerichteten azyklischen Graphen mit der Besetztheit der Wurzel der inversen Kovarianzmatrix eingegangen. Es wird vorgestellt, wie sich diese innerhalb des Algorithmus verhält, um ein Ausnutzen in der Anwendung zu ermöglichen. Oft ist es möglich, Gaußsche lineare Zustandsraummodelle in ein solches Graphenmodell zu überführen. Inwieweit die Anwendung des in dieser Arbeit vorgestellten Algorithmus darauf möglich und sinnvoll ist, wird diskutiert.
Ein Fourier-Schätzer für die multivariate Volatilität von Handelsobjekten. - Ilmenau. - 93 Seiten
Technische Universität Ilmenau, Masterarbeit 2024
Die Volatilität von Handelsobjekten ist ein zentraler Parameter in der Finanzmathematik und Ökonometrie. Wir untersuchen den Schätzer von Malliavin und Mancino (2009) für die multivariate instantane Volatilität von Preisprozessen, die als stetige Semimartingale modelliert werden. Das Verfahren basiert auf Fourier-Methoden und baut auf einer Identität zwischen den Fourier-Koeffizienten der Volatilität und den Fourier-Stieltjes-Koeffizienten der Preisprozesse auf. Die Volatilität wird aus ihren geschätzten Fourier-Koeffizienten als stochastische Funktion auf der gesamten Zeitmenge rekonstruiert. Der resultierende nichtparametrische Kurvenschätzer kann durch zwei Eingabegrößen angepasst werden und ist auf diskrete ungleichmäßig beabstandete, asynchrone Beobachtungen der Preisprozesse anwendbar. Unter gewissen Bedingungen wird seine Konsistenz bewiesen, wobei das Resultat von Malliavin und Mancino auf den Fall nicht periodischer Volatilität ausgedehnt wird. In einer Simulationsstudie wird der Einfluss der Eingabegrößen für verschiedenartige Volatilitätsfunktionen untersucht und ein Bias für gewisse Parameterwahlen unter asynchronen Beobachtungen festgestellt.
The cut cover problem in acyclic digraphs. - Ilmenau. - 27 Seiten
Technische Universität Ilmenau, Masterarbeit 2024
Die Arbeit untersucht Überdeckungen der Kantenmenge eines Digraphen mit k Schnitten (im Folgenden als k-Cut Cover bezeichnet). Eine äquivalente Eigenschaft ist die k-Färbbarkeit der Kanten so, dass keine zwei aufeinanderfolgenden Kanten uv, vw dieselbe Farbe erhalten. Eine Eckenfärbung mit höchstens M(k) Farben ist hinreichend für die Existenz eines k-Cut Covers, wobei M(k) der zentrale Binomialkoeffizient „k über [k/2]“ ist. Für symmetrische Digraphen erweisen sich diese beiden Eigenschaften als äquivalent. Hieraus folgt, dass das Problem zu entscheiden, ob ein (symmetrischer) Digraph ein k-Cut Cover besitzt, für k ≥ 3 NP-vollständig ist. Insbesondere untersucht diese Arbeit minimale Cut Covers in azyklischen Digraphen. Jeder azyklische Digraph mit maximalem Eingrad M(k)-1 hat ein k-Cut Cover, da er eine Eckenfärbung mit M(k) Farben besitzt. Es wird gezeigt, dass diese Schranke bestmögliche ist, und dies löst ein von Alon, Bollobás, Gyárfás, Lehel und Scott gestelltes Problem. Für die abgeänderte Bedingung, dass für jeden Knoten entweder sein Eingrad oder Ausgrad nach oben beschränkt ist, wird das minimale k, welches ein k-Cut Cover im Allgemeinen garantiert, bis auf höchstens zwei mögliche Werte bestimmt. Außerdem werden Cut Covers in Potenzen von gerichteten Pfaden betrachtet. Es wird gezeigt, dass ein k-Cut Cover in der d-ten Potenz beliebig langer gerichteter Pfade genau dann existiert, wenn d ≤ (c-o(1)) 2^k, für eine Konstante c ∈ [1/e, 1/2]. Ein Cut Cover in einem Digraphen kann auf alle Digraphen übertragen werden, die homomorph zu ihm sind. Die Existenz eines Homomorphismus zu einer Potenz eines gerichteten Pfades ist in polynomialer Zeit überprüfbar und äquivalent zu einer Gleichgewichtsbedingung für die Anzahl der Vorwärts- und Rückwärtskanten von ungerichteten Kantenzügen. Das Problem, zu entscheiden, ob ein azyklischer Digraph ein 3-Cut Cover besitzt, ist NP-vollständig, sogar für planare Digraphen mit maximalem Ein- und Ausgrad 3, die einen Homomorphismus zur dritten Potenz des gerichteten Pfades auf 12 Ecken besitzen.
Numerical solutions ased on the ADI iteration for large-scale control problems: the Lyapunov, Riccati, and Lur’e equations. - Ilmenau. - 55 Seiten
Technische Universität Ilmenau, Masterarbeit 2024
Wir stellen eine Reihe von Methoden vor, die auf der ADI-Iteration basieren, für die numerische Lösung der Lyapunov-Gleichungen, der algebraischen Riccati-Gleichungen und der Lur'e-Gleichungen. Diese Matrixgleichungen spielen eine wichtige Rolle in der Kontrolltheorie, und wir konzentrieren uns auf großskalige, spärliche Probleme. Die LRCF-ADI-Iteration, welche die Eigenschaften sowohl des ADI-Modells als auch der niedrigrangigen Cholesky-Faktoren integriert, wird zur Lösung der Lyapunov-Gleichung verwendet. Die LRCF-NM, welche die Kleinman-Newton-Iteration und die LRCF-ADI-Iteration kombiniert, wird zur Lösung der algebraischen Riccati-Gleichung verwendet. Die stabilisierende Lösung dieser Gleichung kann das entsprechende LQR-Problem lösen. Der Störungsansatz, der die LRCF-NM anwendet, wird zur Lösung der Lur'e-Gleichungen im Falle von Singularität verwendet. Die maximale Lösung dieser Gleichungen kann das entsprechende linear-quadratische optimale Steuerungsproblem lösen. In dieser Arbeit demonstrieren wir durch zwei Beispiele, wie diese Methoden die entsprechenden Matrixgleichungen numerisch lösen.
Path following and obstacle avoidance algorithms for underactuated unmanned surface vessel. - Ilmenau. - 29 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2024
Die Entwicklung von autonomen Steuerungen von unbemannten Schiffen in flachen Gewässern ist ein wichtiges Forschungsgebiet im Bereich der Binnenschiffahrt. Ein übliches Szenario in dem sich ein solches unbemanntes Schiff befinden könnte, ist die Fahrt entlang eines Pfades, welcher durch Koordinatenpunkte vorgegeben ist. Nun befinden sich entlang des Pfades noch Hindernisse, welche es zu vermeiden gilt und gleichzeitig herrscht noch eine Strömung mit konstanter Richtung und Stärke, wie zum Beispiel auf einem Fluss. Das Ziel ist es nun, einen Algorithmus mit Sicherheitsgarantien zu entwickeln, welcher das Schiff erfolgreich entlang des Pfades steuert. Zuerst wird das 3-Freiheitsgrade Kinematikmodell und das Konzept von Lyapunov Stabilität dynamischer Systeme eingeführt. Anschließend beschäftigt sich diese Arbeit mit der Vorstellung von LOS und ILOS, 2 gängigen Algorithmen zur Pfadverfolgung, welche auch bezüglich ihres Verhaltens bei Strömung untersucht werden. Des Weiteren wird ein bestehender Stabilitätsbeweis für LOS mitgeliefert. Daraufhin wird ein Algorithmus zur Hindernisvermeidung, sowie ein zugehöriger Stabilitätsbeweis vorgestellt. Anschließend wird ein hybrider Algorithmus entwickelt, welcher sowohl Pfadverfolgung, als auch Hindernisvermeidung gewährleisten kann, für welchen wir mithilfe der vorangegangenen Resultate auch Sicherheitsgarantien beweisen konnten. Dieser Algorithmus wird dann mithilfe von Matlab implementiert, und in verschiedenen simulierten Szenarien werden bestehende und gelöste Probleme des Algorithmus aufgezeigt. Schlussendlich wird dadurch ein Algorithmus für autonome Schiffahrt unter vereinfachten Bedingungen entwickelt.
An algebraic framework for time-varying linear systems. - Ilmenau. - 22 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2023
Diese Arbeit untersucht lineare differentiell-algebraische Gleichungen mit zeitabhängigen Koeffizienten. Lösungen sind Vektoren von glatten reellen Funktionen, definiert auf den reellen Zahlen, mit Ausnahme einer diskreten Teilmenge. Zwei Lösungen werden identifiziert, wenn sie fast überall bezüglich des Lebesgue-Maßes übereinstimmen. Wir zeigen in der vorliegenden Arbeit, dass dieser Ansatz die notwendige algebraische Struktur für unsere Untersuchungen liefert und die Fehler eines früheren Ansatzes korrigiert. Darüber hinaus deckt dieser Ansatz den Spezialfall von reellen meromorphen Koeffizienten ab, in welchem die Teichmüller-Nakayama-Form zur Vereinfachung der Systemanalyse verwendet werden kann. Des Weiteren beschäftigen wir uns mit der Steuerbarkeit des zeitabhängigen Systems, was zum Hauptergebnis der Arbeit führt – einer algebraischen Charakterisierung von Steuerbarkeit. Dieser Satz ist bekannt, wir liefern jedoch einen überarbeiteten Beweis in unserem Framework.
Die skalare und multikriterielle Rundungseigenschaft. - Ilmenau. - 35 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2023
Die vorliegende Arbeit beschäftigt sich mit der Rundungseigenschaft, welche eine Methode zum Lösen ganzzahliger skalarwertiger Optimierungsprobleme liefert. Diese Arbeit verwendet dabei vorrangig den Levelmengenansatz von Hübner, 2013, um für verschiedene Klassen von Optimierungsproblemen diese Eigenschaft nachzuweisen. Weiterhin werden diese Ideen teilweise auf multikriterielle Optimierungsprobleme ausgeweitet.
Charakterisierung der Baumweite eines Graphen durch Graphsuche. - Ilmenau. - 21 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2023
Das Konzept der Baumweite ist eines der weniger intuitiven Konzepte in der Graphentheorie. Deswegen ist es durchaus nützlich, sich alternative Charakterisierungen dieser Größe anzusehen. Zu diesem Zweck soll das Suchen auf Graphen mit bestimmten Voraussetzungen dienen. Ziel dieser Arbeit ist es, einen kurzen Überblick über die Geschichte der Graphsuche zu geben, die Voraussetzungen für die Graphsuche zu definieren, so dass ein Zusammenhang zur Baumweite hergestellt wird, und einen Beweis für diesen Zusammenhang darzustellen.