Notwendige und hinreichende Bedingungen für Nachbarschaftshypergraphen. - 28 S. Ilmenau : Techn. Univ., Masterarbeit, 2015
Ein Nachbarschaftshypergraph ist ein Hypergraph H, der aus einem schlichten Graphen G entsteht, indem die Nachbarschaft jeder Ecke von G einen Block von H bildet. Der Graph G wird dabei Ursprungsgraph von H genannt. Wir betrachten in dieser Arbeit, unter welchen Bedingungen ein Hypergraph ein Nachbarschaftshypergraph ist. In Kapitel 2 zeigen wir notwendige Bedingungen, die alle Nachbarschaftshypergraphen erfüllen. Insbesondere beweisen wir mit Satz 2.7, dass sie selbstdual sind. Außerdem stellen wir mit Satz 2.10 den Zusammenhang zwischen einer Adjazenzmatrix eines Graphen und der Inzidenzmatrix des zugehörigen Nachbarschaftshypergraphen vor. In Kapitel 3 beschäftigen wir uns mit der Klasse der 2-Designs. Dabei zeigen wir mit Lemma 3.3, welche Eigenschaften die Ursprungsgraphen von 2-Designs haben und darauf aufbauend beweisen wir mit algebraischen Methoden in Satz 3.4 notwendige Bedingungen für die Parameter der 2-Designs, die Nachbarschaftshypergraphen sind. Auswirkungen der Eigenschaften Bipartitheit und Zusammenhang der Ursprungsgraphen auf ihre Nachbarschaftshypergraphen betrachten wir in Kapitel 4. Die Sätze 4.5 und 4.6 zeigen, welche Beziehungen zwischen den Zusammenhangskomponenten eines Hypergraphen genau dann bestehen, wenn es einen bipartiten Ursprungsgraphen gibt. Beispiel 4.9 beweist, dass ein Hypergraph verschiedene, nicht bipartite Ursprungsgraphen haben kann. Dahingegen ist ein bipartiter Ursprungsgraph immer bis auf Isomorphie eindeutig, was aus Satz 4.8 folgt. Für die Hypergraphen in Kapitel 5 setzen wir Kreisfreiheit voraus. Daraus folgt, dass gegebenenfalls Ursprungsgraphen Wälder sind, wo durch wir auf den Ergebnissen aus Kapitel 4 aufbauen können. Wir greifen einen Algorithmus zur Überprüfung, ob Bäume isomorph sind, auf, der von Hochstättler in dem Buch Algorithmische Mathematik vorgestellt wird. Diesen nutzen wir, um einen Algorithmus anzugeben, mit dem getestet werden kann, ob die Zusammenhangskomponenten eines Hyperwaldes die notwendigen und hinreichenden Bedingungen für die Existenz eines bipartiten Ursprungsgraphen erfüllen. Dieser Algorithmus arbeitet in Polynomialzeit.
Differentialoperatoren zweiter Ordnung mit komplexwertigen Koeffizienten. - 46 S. Ilmenau : Techn. Univ., Masterarbeit, 2015
Diese Masterarbeit befasst sich mit Differentialausdrücken zweiter Ordnung der Form $\tau[y]=\frac{1}{w}[-(py')'+qy]$. Hier sind $p^{-1}$, $q$ und $w$ lokal summierbare Funktionen, welche auf einem halboffenen, nicht notwendigerweise beschränktem, Intervall [a,b) erklärt sind. Das dazugehörige Eigenwertproblem $\tau[y]=\lambda y$ heißt Sturm-Liouville'sches Eigenwertproblem. Diese Differentialgleichung besitzt zwei linear unabhängige Lösungen, die aber nicht unbedingt im Hilbertraum $$L^2(a,b,w\, dx):= \left{u:(a,b)\rightarrow \mathbb{C}:\int_a^bw|u|^2\, dx <\infty \right}$$ liegen. Ein berühmtes Ergebnis von H. Weyl besagt, dass entweder für jedes $\lambda$ alle Lösungen des Eigenwertproblems in $L^2(a,b,w\, dx$ liegen oder nur eine Lösung (und ihre Vielfache) in $L^2(a,b,w\, dx$ liegt. Im ersten Fall spricht man vom Grenzkreisfall, sonst vom Grenzpunktfall. Es werden die Ergebnisse der Arbeit "On the spectrum of second-order differential operators with complex coefficients" von B.M. Brown, D.K.R. McCormack, W.D. Evans und M. Plum (Proc. R. Soc. Lond. 455 (1999), 1235-1257) vorgestellt. Diese behandelt das Sturm-Liouville'sche Eigenwertproblem mit komplexwertigen $p$ und $q$. Auch in diesem Fall lassen sich die Ergebnisse von H.Weyl zumindest teilweise übertragen. Die Charakterisierung führt dann auf zwei Grenzpunktfälle und einen Grenzkreisfall. Außerdem werden Eigenschaften der Weylschen $m$-Funktion untersucht und eine Operatorrealisierung von $\tau$ angegeben. Für diesen Operator bestimmen wir Mengen, in denen das Spektrum des Operators nur aus Eigenwerten mit endlicher algebraischer Vielfachheit besteht.
Stellvertreterspiele. - 35 S. Ilmenau : Techn. Univ., Masterarbeit, 2015
In der vorliegenden Arbeit werden 2-Personen Normalformspiele untersucht. Jedem solchen Spiel kann ein so genanntes Stellvertreterspiel zugeordnet werden. Die Idee dabei ist, dass die Spieler ihre Aktionen nicht selbst auswählen, sondern Stellvertreter benennen, welche das Spiel in ihrem Auftrag spielen. Die Nutzenfunktionen der Stellvertreter stimmen nicht notwendig mit denen der Spieler überein. Es wird angenommen, dass die Stellvertreter rational im Sinne der Spieltheorie sind und sowohl die eigene Nutzenfunktion als auch die Nutzenfunktion des jeweils anderen Stellvertreters kennen. Rationalität impliziert, dass die Stellvertreter ein Nash Equilibrium in dem durch ihre Nutzenfunktionen induzierten Spiel spielen. Die Spieler erhalten die Auszahlung, welche sich aus diesem Nash Equilibrium ergibt. Da das sich ergebende Spiel mehr als ein Nash Equilibrium haben kann, muss eine Auswahlfunktion Phi fixiert werden, welche das Nash Equilibrium auswählt. Damit wird ein neues Spiel definiert, in welchem die Strategien der Spieler die Stellvertreter sind und die Auszahlungen die Auszahlungen in den durch Phi ausgewählten Nash Equilibria in dem durch die Nutzenfunktionen der Stellvertreter induzierten Spiel sind. Das Studium der Nash Equilibria dieses neuen Spiels bildet den Inhalt der vorliegenden Arbeit.
Algorithmen zur Berechnung des Volumens beschränkter nicht notwendig konvexer Polyeder im R 3. - 41 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2015
Die effiziente Volumenberechnung allgemeiner beschränkter Polyeder hat große Bedeutung in geometrischen und computergrafischen Bereichen. In dieser Arbeit wird dazu unter Benutzung geeigneter Datenstrukturen eine Methode aus der Literatur zur Berechnung von Geradenschnittpunkten aufgegriffen. Mithilfe dieser wird eine Struktur verwaltet, die das Problem zerlegt und sukzessive Teilvolumen aufaddiert. Damit ergibt sich für einen gegebenen Polyeder mit n berandenden Polygonen und höchstens m Ecken für jedes Polygon eine Laufzeit von O((nm + s) log(nm) + n 2 m 2 log n) mit s <= n 2 m 2. Die Schranke, insbesondere der Wert s, bietet Verbesserungsmöglichkeiten in der Abschätzung. Nach Konstruktion sind Verallgemeinerungen des gegeben Algorithmus für Polyederschnitte möglich. Dem gegenüber wird eine Methode mit Laufzeit O(nm) beschrieben, die eine konsistente Orientierung der Polygone fordert.
Banachräume mit reproduzierenden Kernen. - 43 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2015
Diese Arbeit ist in sechs Kapitel unterteilt. Die Einleitung gibt einen kurzen Überblick über die Theorie der reproduzierenden Kerne für Hilberträume und motiviert zugleich die Verallgemeinerung auf Banachräume. Im zweiten Kapitel sind die theoretischen Grundlagen zusammengestellt, welche notwendig sind um spezielle Banachräume zu entwickeln, welche reproduzierende Kerne besitzen können. Kapitel 3 befasst sich schließlich mit Banachräumen mit reproduzierenden Kernen (RKBS), welche aufgrund der Theorie des zweiten Kapitels definiert werden können. Insbesondere werden hier grundlegende Resultate aus der Hilbertraumtheorie analog auf RKBS verallgemeinert. In Kapitel 4 wird erläutert, wie sich RKBS zur Lösung von Interpolationsproblemen einsetzen lassen. In Kapitel 5 wird die Theorie der letzten beiden Kapitel an zwei ausführlichen Beispielen erläutert. Im letzten Kapitel werden die Ergebnisse diskutiert und es gibt einen Ausblick auf mögliche weitere Forschung.
Baumweite endlicher Graphen und Separatortheoreme. - 21 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2014
Die Ergebnisse dieser Bachelorarbeit sind Aussagen über den Zusammenhang zwischen Baumweite und Zerlegbarkeit eines Graphen.
Quadratic forms on graphs and maximum weighted induced subgraphs. - 35, 29 S. : Ilmenau, Techn. Univ., Bachelor-Arbeit, 2014
Gegeben sei ein einfacher, endlicher, ungerichteter Graph G = (V, E) mit Eckenmenge V (G) und Kantenmenge E(G). Eine unabhängige Menge von G ist eine Teilmenge von V (G), in der je zwei Ecken nicht adjazent in G sind. Ein oft untersuchtes kombinatorisches Optimierungsproblem ist die Frage nach einer unabhängigen Menge maximaler Kardinalität. Angenommen, den Ecken sind Gewichte zugewiesen, dann ist ein weiteres Problem, eine unabhängige Menge maximalen Gewichtes zu finden. Es ist bekannt, dass die Entscheidungsversion dieser Probleme NP-vollständig ist, wodurch Untersuchungen von Schranken für das maximale Gewicht unabhängiger Mengen gerechtfertigt sind. Eine bekannte Schranke, auf dem diese Arbeit aufbaut, ist eine Veröffentlichung von Gibbons, Hearn, Pardalos und Ramana [1]. Diese Bachelorarbeit untersucht quadratische Formen auf Graphen, welche durch eine Arbeit von Motzkin und Straus [2] motiviert sind. Mit den Ergebnissen kann die Schranke von Gibbons und andere verbessert werden. Des Weiteren wird eine Verallgemeinerung der gewichteten Unabhängigkeit zu maximal gewichteten induzierten Untergraphen untersucht.
Chromatische Zahl und Spektrum von Graphen. - 51 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2014
In dieser Bachelorarbeit wird der Zusammenhang zwischen den Eigenwerten und der chromatischen Zahl eines Graphen erarbeitet. Außerdem wird ein Zusammenhang zwischen den Eigenwerten eines Graphen und der Erdös-Faber Lovasz Vermutung hergestellt und eine stärkere Vermutung über die Eigenwerte und seine chromatische Zahl formuliert.
Modifikation der alphaBB-Methode für die inverse Kinematik von Roboterarmen. - 92 S. Ilmenau : Techn. Univ., Masterarbeit, 2014
In dieser Arbeit wurde das Problem der inversen Kinematik für Roboterarme als Optimierungsproblem formuliert. Es ergibt sich ein globales Optimierungsproblem, welches mehrere oder sogar unendlich viele globale Minimalstellen hat. Unendlich viele globale Minimalstellen treten bei Roboterarmen mit redundanter Struktur und an singulären Stellungen auf. Für die Anwendung ist es sinnvoll, alle globalen Minimalstellen zu kennen. Zur Lösung dieses Optimierungsproblems wurde die aus der Literatur bekannte alphaBB-Methode erweitert. Mit Hilfe dieses modifizierten Optimierungsverfahrens können von box-restringierten, zweimal stetig differenzierbaren Optimierungsproblemen alle globalen Minimalstellen approximiert werden, unabhängig davon, ob es endlich oder unendlich viele globale Minimalstellen gibt. Es wurde die Korrektheit und Endlichkeit des entwickelten Verfahrens bewiesen.
Analyse eines MINLP-Problems in der Kraftwerkseinsatzplanung. - 35 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2014
In der Kraftwerkseinsatzplanung gibt es nach der Liberalisierung der Energiemärkte viel zu beachten, wodurch die Optimierungsprobleme in diesem Bereich an Komplexität gewinnen. Somit ist es von Nöten die vielen Facetten der Kraftwerkseinsatzplanung in ein gemischt-ganzzahliges nichtlineares Optimierungsproblem umzuwandeln, um dies mit entsprechenden Solvern lösen zu können. In dieser Bachelorarbeit haben wir nun ein konkretes Beispiel aus der Kraftwerkseinsatzplanung betrachtet. Wie haben aus den vorhandenen Rahmenbedingungen ein Optimierungsproblem erstellt und dieses anschließend auf zwei verschiedene Arten gelöst. Anhand dieser Ergebnisse haben wir einen Vergleich zwischen dem kommerziellen Solver LINDO und dem in Matlab implementierten SQP-Verfahren angestellt. Des Weiteren haben wir untersucht welche Eigenschaften die einzelnen nichtlinearen Teilfunktionen der Zielfunktion besitzen und wie sich Veränderungen an verschiedenen Variablen auf das Gesamtsystem auswirken um zu analysieren wie stabil das gesamte System ist.