Bachelor Theses and Master Theses

Diese Masterarbeit beschäftigt sich mit der semidefiniten Optimierung und deren Anwendung in der Magnetresonanztomographie. Dazu führen wir zuerst die Grundlagen der semidefiniten Optimierung ein. Anschließend werden die Ideen zur Datenreduzierung von Beobachtungspunkten bei der Magenetresonanztomographie aus der Arbeit von G. Eichfelder und M. Gebhardt mathematisch aufgearbeitet. Wir betrachten dann das in dieser Arbeit hergeleitete semidefinite Optimierungsproblem, für das zwei Matrixnormen als (nichtlineare) Zielfunktion gewählt werden können. Diese Optimierungsprobleme formulieren wir zu Problemen mit linearen Zielfunktionen um. Ebenfalls leiten wir die zugehörigen dualen Optimierungsprobleme her und erbringen den Nachweis über die starke Dualität. Zum Schluss lösen wir die oben erwähnten Optimierungsprobleme, die anhand von Zufallsdaten und Daten aus der Anwendung gebildet wurden, mit Hilfe verschiedener Software-Pakete für MATLAB und diskutieren die gewonnenen Ergebnisse.

Für einen Graph G mit der Eckenmenge V und der Kantenmenge E wird das klassische Eckenfärbungskonzept verallgemeinert. Hierbei weist man zunächst jeder Ecke v des Graphen eine Menge S(v) zu, welche lediglich eine Teilmenge von V \cup E sein muss. Des Weiteren wählt man eine Gewichtsfunktion w : V \cup E -> {1,2,..,k}, wobei k eine natürliche Zahl ist. Nun wird für jede Ecke v mittels c(v) = sum_{x \in S(v)} w(x) eine Farbe definiert. Die so entstandene Färbung soll zulässig sein, d.h. benachbarte Ecken sollen stets verschieden gefärbt sein. Unter dieser Bedingung soll die Zahl k minimiert werden. Wie obere Schranken für dieses minimale k aussehen können, wird für verschiedene Färbungskonzepte, also verschiedene Mengen S(v), angewendet auf einige Graphenklassen untersucht. Genauer werden die Färbungskonzepte S(v) = N(v) = {x \in V | xv \in E} und S(v) = N[v] = N(v) \cup {v} für Kreise, Bäume, bipartite und vollständige r-partite Graphen betrachtet. Zusätzlich werden die Färbungskonzepte S(v) = N_E(v) = {uv \in E | u \in V} , S(v) = N[v] \cup N_E(v) und S(v) = N(v) \cup N_E(v) für Bäume betrachtet.

Diese Arbeit ist in sechs Kapitel unterteilt. Die Einleitung dient einerseits der Erläuterung der praktischen Problemstellung am Beispiel der Computertomographie und andererseits bereits der Einführung einiger grundlegender Objekte, welche vor allem im zweiten Teil eine übergeordnete Rolle spielen werden. Weiterhin die Methode der gefilterten Rückprojektionen zur Invertierung der Radontransformation vorgestellt und deren Vor- und Nachteile beleuchtet. Das zweite Kapitel legt zunächst alle theoretischen Grundlagen für die Entwicklung der Theorie und erläutert die mathematische Seite des neuen Verfahrens zur Invertierung der Radontransformation. Im Zuge dessen ergibt sich auch ein neues Ergebnis über lineare stetige Funktionale in Hilberträumen mit reproduzierenden Kernen. Kapitel 2 endet mit dem Invertierungstheorem, welches den Mittelpunkt dieser Arbeit darstellt. Es erlaubt eine Approximation der inversen Radontransformation, die viel weniger Anforderungen an die Messdaten stellt, als beispielsweise die gefilterte Rückprojektion. Die hier entwickelte Methode wird im Folgenden der Einfachheit halber Kernmethode genannt werden. Kapitel 3 befasst sich damit, ein konkretes Beispiel von Kernfunktionen im Sinne der entwickelten Theorie aufzubereiten, um diese in einer praktischen Problemstellung verwenden zu können. Weiterhin wird der Einfluss von einigen weiteren Parametern erläutert, welche bei der Approximation eine Rolle spielen. In den letzten Kapiteln wird zunächst eine kurze Erklärung der benutzten Numerik gegeben. Dann wird die Kernmethode mit verschiedenen Datensätzen getestet und untersucht. Schlussendlich werden die Ergebnisse der Kernmethode mit denen der gefilterten Rückprojektion verglichen. Der Schluss beinhaltet einige weiterführende Aspekte und gibt mögliche Anhaltspunkte für weitere Untersuchungen der Kernmethode.

Im Katasteramt ist es nötig, verschiedene Grundstücksgrenzen zu markieren. Vor allem spielt die Unterteilung dieser Flächen in Nutz- und Grundstücksflächen eine zentrale Rolle. In dieser Arbeit wird ein Algorithmus entwickelt, welcher die Flächen von ebenen polygonalberandeten Objekten und deren Schnitten berechnet. Um mit zweidimensionalen Objekten handhaben zu können, besteht die Möglichkeit deren Ränder durch einfach geschlossene Polygonzüge zu approximieren. Zunächst wird die Flächenberechnung affiner Funktionen auf endlichen Intervallen betrachtet. Anschließend steigert man sich mittels Vereinigungen von Trapezflächen auf die Berechnung der Flächeninhalte polygonalberandeter Objekte. Hierbei werden diese Objekte in endlich viele Trapeze mittels Schnittgeraden zerlegt. Dafür müssen die Schnittpunkte zwischen den verschiedenen einfach geschlossenen Polygonzügen ausfindig gemacht werden. Am Schluss wurde dieser Algorithmus zur Flächenberechnung in einem C++-Programm umgesetzt.

Zu jeder natürlichen Zahl $\ell \geq 3$ und jedem beliebigen Graphen $G$ derart, dass $G$ keine zwei eckendisjunkte Kreise der Länge mindestens $\ell$ enthält, exisitert eine Eckenmenge $X$ von höchstens $\frac{5}{3}\ell+\frac{13}{3}$ Elementen derart, dass $G - X$ keinen Kreis der Länge mindestens $\ell$ mehr enthält. Dies ist eine Verbesserung der oberen Schranke $2\ell+3$ von Birmelé, Bondy und Reed (The Erdös-Pósa property for long circuits, {Combinatorica} {27} (2007), 135-145).