http://www.tu-ilmenau.de

Logo TU Ilmenau



Foto des Ansprechpartners
Ansprechpartner

Univ.-Prof. Dr. rer. nat. habil. Matthias Kriesell

Fachgebietsleiter

Telefon +49 3677 69-3633

E-Mail senden


Ihre Position

INHALTE

Studienabschlussarbeiten

Anzahl der Treffer: 52
Erstellt: Tue, 04 Aug 2020 23:07:53 +0200 in 0.0469 sec


Alder, Sascha;
Engineering von Algorithmen zur Berechnung eines minimalen Schnittes in Graphen. - Ilmenau. - 90 Seiten.
Technische Universität Ilmenau, Masterarbeit 2020

In dieser Masterarbeit wird mittels Algorithm Engineering eine möglichst schnelle Implementation des Algorithmus von Nagamochi-Ibaraki für das Open Graph Drawing Framework erarbeitet, die ebenfalls auf großen Graphen schnell ist. Zusätzlich soll die Berechnung einer Maximum Adjacency Ordering ( MAO ) und der Algorithmus von Nagamochi-Ibaraki im praktischen Einsatz beschleunigt werden. Hierbei ist eine MAO eine Totalordnung über die Knotenmenge des Graphen. Zuerst wurden verschiedene Implementationen für die MAO Berechnung erstellt. Ein Ergebnis dieser Implementationen ist die BoundedList, in der maximal B Elemente in einer Liste enthalten sein dürfen, um Lösch- und Einfügeoperationen einzusparen. Bei dem Vergleich der MAO Berechnungen auf verschiedenen Problemfamilien ist ein Ergebnis, dass die BoundedList in der Praxis schneller ist als die Priority-Queue Variante, die von anderen experimentellen Auswertungen verwendet wurde. Daraufhin wurde die BoundedList in Nagamochi-Ibaraki zusammen mit den Padberg-Rinaldi Heuristiken eingearbeitet. Hierbei existieren ebenfalls verschiedene Varianten der Implementation. Eine dieser verwendet eine kompakte Kontraktion um Knoten zu kontrahieren. Dagegen erfolgt die Umsetzung einer anderen Variante mittels Union-Find, um zusammengehörige Knotenmengen zu bilden, die die zu kontrahierenden Knoten repräsentieren. Unter den getesteten Graphen befinden sich ebenfalls Graphen, die realen Netzwerken nachempfunden wurden. Hierbei ist ein Ergebnis, dass das Abbrechen der MAO Berechnung und das Kontrahieren von kontrahierbaren Knotenmengen innerhalb einer Runde von Nagamochi-Ibaraki vorteilhaft bei Graphen mit Clusterkoeffizienten unter 10 Prozent ist. Ansonsten ist die vollständige Berechnung der MAO zu empfehlen. Des weiteren ist während der Masterarbeit aufgefallen, dass die Implementation einer schnellen Kontraktion erheblich ist.



Eckenpartitionszahlen. - Ilmenau. - 46 Seiten.
Technische Universität Ilmenau, Masterarbeit 2020

Ein wichtiger Teil der Graphentheorie sind bis heute Färbungsprobleme. Das klassische Färbungsproblem ist ein kombinatorisches Optimierungsproblem. Im Mittelpunkt steht dabei die Untersuchung der chromatische Zahl. Erweitern wir dieses Konzept und fordern, dass jede Farbklasse streng-t-degeneriert ist, so nennen wir die minimale Anzahl benötigter Farben die Eckenpartitionszahl. Wir zeigen grundlegende Eigenschaften kritischer Graphen bezüglich der Eckenpartitionszahl und untersuchen, wann ein Graph in zwei disjunkte Teilgraphen zerlegt werden kann, wobei jede Ecke des ersten Teilgraphen mit jeder Ecke des zweiten Teilgraphen durch genau t Kanten verbunden wird. Des Weiteren untersuchen wir die minimale Anzahl Kanten eines kritischen Graphen bezüglich der Eckenpartitionszahl. Außerdem erweitern wir das Strong Perfect Graph Theorem auf die Eckenpartitionszahl mit t=2.



Fanselow, Niklas;
Paths in a ball. - Ilmenau. - 40 Seiten.
Technische Universität Ilmenau, Masterarbeit 2019

Die vorliegende Abschlussarbeit befasst sich mit einem Problem, welches durch einen Vortrag von P. Braun über die wissenschaftliche Arbeit "Unsafe Point Avoidance in Linear State Feedback". Um die Nichtexistenz einer stetigen Zustandsrückführung als Lösung eines linearen, zeitinvarianten, stabilisierbaren Systems mit der Eigenschaft, dass eine vorgegebene Menge von nicht sicheren Punkten durch die Lösungen des Systems vermieden wird, zu erklären, wurde im genannten Vortrag die folgende Behauptung aufgestellt. Betrachten wir eine Familie von Wegen im Einheitsball, welche stetig von ihrem Anfangspunkt auf der Einheitssphäre abhängen und in den Ursprung laufen, so gibt es für jeden Punkt des Einheitsballs einen Weg, der diesen Punkt in seinem Bild enthält. Diese Fragestellung, formuliert für den endlich-dimensionalen euklidischen Raum, wird in vorliegender Abschlussarbeit untersucht. Zunächst wird eine Funktion F konstruiert, welche ermöglicht, alle diese Wege zugleich zu betrachten. Unter der zusätzlichen Voraussetzung der Injektivität von F, stellt das Bild von F für einen festgehaltenen Zeitparameter topologische Sphären da. Basierend auf dem Jordan-Brouwer Separationssatz und der Gebietsinvarianz von Brouwer wird für diese Voraussetzungen ein Beweis der Surjektivität von F geführt. Allerdings konnte die zugrundeliegende Fragestellung in vorliegender Arbeit nicht beantwortet werden. Ein weiteres Hauptresultat dieser Arbeit stellt eine äquivalente Beziehung zwischen der Sujektivität von F und der Separationseigenschaft dar. Abschließend wird gezeigt, dass die Homöomorphie-Eigenschaft der Innen- und Außengebiete der durch F erhaltenen topologischen Sphären in diesem Spezialfall erhalten bleibt, während der Satz von Jordan-Schoenflies nicht auf höhere Dimensionen verallgemeinert werden kann, wie beispielsweise Alexander mittels der Konstruktion der Alexanderschen gehörnten Sphären bewies.



Erweitertes Online GNSS-Matching - Verbesserung der Abgleichsmechanismen zwischen digitalen Karten und per GNSS erfassten Positionsdaten. - Ilmenau. - 95 Seiten.
Technische Universität Ilmenau, Masterarbeit 2018

In dieser Arbeit wird ein kurzer Überblick über die Funktionsweise von globalen Navigationssystemen (GNSS) und den verwendeten Positionsangaben gegeben. Mittels der GNSS kann ein GNSS-Empfänger seinen Standort in Relation zur Erde bestimmen. Ein Map Matching Verfahren bringt diese fehlerbehafteten Standortdaten in Relation zu einem gegebenen Straßennetz (Straßenkarte) und versucht die korrekte Position des Empfängers darauf zu ermitteln. Map Matching Algorithmen, welche sofort die aktuelle Position bestimmen ohne zukünftige GNSS-Werte zu haben, werden als online Map Matching Algorithmen bezeichnet. In dieser Arbeit wurde gezeigt, inwiefern sich Hidden Markov Modelle als Basis für ein solchen online Map Matching Algorithmus eignen. Hierfür wurde ein einfaches Straßenmodell erstellt, auf welches fehlerbehaftete Standortdaten simuliert wurden. Für dieses Modell wurde ein einfacher Map Matching Algorithmus erstellt. Dieser hat den Viterbi-Algorithmus als Grundlage. Anhand von eigenen Simulationen erfolgte eine Beurteilung, inwiefern sich das Hidden Markov Modell tatsächlich für einen Map Matching Algorithmus eignet.



Storch, Patrick;
Proxy games. - Ilmenau. - 48 Seiten.
Technische Universität Ilmenau, Masterarbeit 2018

Obgleich Nashgleichgewichte das wohl bekannteste Lösungskonzept der Spieltheorie darstellen, sind sie doch eher theoretischer Natur. Damit ist gemeint, dass sich Personen in tatsächlichen Spielsituationen gar nicht, oder nur selten nach dem Nachgleichgewicht richten. Um diese Diskrepanz zwischen mathematischer Vorhersage und tatsächlichem Spielverhalten zu überbrücken, führen wir Stellvertreterspiele als eine weitere Ebene in Normalformspielen ein. Die Hauptidee hierbei ist es, zwischen der Auszahlung die ein Spieler erhält, und seinem/ihrem tatsächlichen Nutzen zu unterscheiden. In dieser Masterarbeit, welche auf den Ergebnissen von Stefan Zeuner und dessen Masterarbeit aufbaut, konnten wir zeigen, dass N-Personen-Spiele mit reinem Nashgleichgewicht stets auch ein reines Stellvertretergleichgewicht haben. Dies stellt eine Verallgemeinerung von Zeuners Resultat über 2-Personen-Spiele dar. Ebenfalls wird eine vollständige Charakterisierung von 2x2-Normalformspielen angegeben und gezeigt, dass diese stets ein reines Stellvertretergleichgewicht besitzen (unter der Voraussetzung, dass die Auswahlfunktion Phi pareto-optimale Ausgänge bevorzugt). Ebenso konnte gezeigt werden, dass die Auszahlungsfunktion des Stellvertreterspiels niemals stetig sein kann, was unsere Möglichkeiten bestehende Resultate bezüglich der Existenz von Nashgleichgewichten zu nutzen, erheblich einschränkt; Und wir konnten zeigen, dass das Konzept von Vertreterspielen (unter gewissen Voraussetzungen) einige grundlegende Probleme mit sich bringt, welche dem Satz von Gibbard-Satterthwaite, sowie Arrows Unmöglichkeitstheorem zuzuschreiben sind. Trotz dieser beiden vorhergehenden Ergebnisse konnte ein reines Stellvertretergleichgewicht (mit Beweis) für ein Spiel angegeben werden, welches mit keiner der vorher bekannten Methoden behandelt werden konnte. Ein möglicher Grund warum diese Art Lösung funktioniert und wie man sie gegebenenfalls auch auf andere Spiele ausweiten kann, wird ebenfalls angedeutet.



Kanzler, Kai;
Konvexe Einbettung und k-Zusammenhang. - Ilmenau. - 19 Seiten.
Technische Universität Ilmenau, Bachelorarbeit 2018

In der Arbeit habe ich auf Basis der Arbeit "Rubber bands, convex embeddings and graph connectivity" den Zusammenhang zwischen der konvexen X-Einbettung eines Graphen (Graphentheorie) und dessen k-Zusammenhang aufgezeigt, eine kurze algorithmische Betrachtung durchgeführt und auf den Nutzen eines solchen Algorithmus hingewiesen.



Fischer, Steffen;
A new separator theorem, metric properties and crossing numbers. - Ilmenau. - 34 Seiten.
Technische Universität Ilmenau, Masterarbeit 2017

Gegeben sei ein einfacher, endlicher, ungerichteter Graph G = (V,E) mit Eckenmenge V (G) und Kantenmenge E(G). Die Kreuzungszahl eines Graphen G, die mit cr(G) bezeichnet wird, ist das Minimum aller Kantenkreuzungen über alle Zeichnungen von G in der Ebene. Diese ist eine wichtige Messgröße für die Charakterisierung der Nichtplanarität eines Graphen. Aufgrund der schweren Berechenbarkeit des dazugehörigen Entscheidungsproblems ist es gerechtfertigt, sich mit Schranken zu beschäftigen. Diese Masterarbeit liefert einen Beweis für eine obere Schranke für Graphen, die mit beschränkter Verzerrung eingebettet werden können. Unabhängig davon wird ein neues Separator-Theorem angegeben, das ein konstantes Größenverhältnis bei den Komponenten eines Graphen G erzeugt, die durch den Trenner S entstehen. Trenner von Graphen sind mächtige Werkzeuge, die durch den Teile-und-herrsche-Algorithmus motiviert sind.



Postel, Justus; von
Hadwigers Vermutung : eine Auswahl der bisherigen Ergebnisse. - Ilmenau. - 38 Seiten.
Technische Universität Ilmenau, Bachelorarbeit 2017

Ein wichtiges Thema der Graphentheorie ist das Färben von Graphen und in diesem Zusammenhang die chromatische Zahl. Der wohl bekannteste Satz zu diesem Thema ist der 4-Farben-Satz, der sich ursprünglich mit dem Färben von Landkarten bschäftigte. Mit einer Verallgemeinerung dieses Themas und einer Verbindung der Färbungszahl mit gewissen Unterstruktren beschäftigte sich der Schweizer Hugo Hadwiger und stellte eine sehr weitreichende Vermutung auf.



Fabel, Marc;
Ein alternatives Lösungskonzept für 2-Personen Normalformspiele. - 60 Seiten.
Technische Universität Ilmenau, Masterarbeit 2016

In der nicht kooperativen Spieltheorie existiert kein komplett zufriedenstellendes Lösungskonzept. Selbst das häufig verwendete Nash-Gleichgewicht liefert nicht immer plausible Ergebnisse, sodass in der aktuellen Forschung nach neuen besseren Lösungskonzepten gesucht wird. In dieser Arbeit wird ein neues Lösungsverfahren für 2-Personen Normalformspiele vorgestellt, welches iterativ vorgeht. Nach der Definition werden erste Eigenschaften gezeigt, bevor es auf verschiedene bekannte Beispiele der Spieltheorie angewendet wird. Anhand dieser Spiele wird untersucht, ob das Verfahren plausible Lösungen liefert. Des Weiteren dienen die Beispiele um Vergleiche zu anderen bekannten Lösungskonzepten der Spieltheorie durchzuführen.



Mohr, Samuel;
Über untere Schranken zur Unabhängigkeit in Graphen. - 57 Seiten.
Technische Universität Ilmenau, Masterarbeit 2016

Gegeben sei ein einfacher, endlicher, ungerichteter Graph G = (V, E) mit Eckenmenge V(G) und Kantenmenge E(G). Eine unabhängige Menge in G ist eine Teilmenge der Eckenmenge 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. Aufgrund der schweren Berechenbarkeit des dazugehörigen Entscheidungsproblems ist es gerechtfertigt, sich mit Schranken, überwiegend unteren Schranken, zu beschäftigen. Der Beitrag dieser Masterarbeit ist eine neue untere Schranke, die als Verbesserung der bekannten Caro-Wei-Schranke aufgefasst werden kann. Hierbei sind insbesondere Spezialisierungen von Interesse, die zu einfachen und leicht berechenbaren Schranken führen. Neben Vergleichen mit klassischen unteren Schranken von O. Murphy und S. M. Selkow wird das Resultat genutzt, um eine Schranke zu entwickeln, die einer Vermutung von E. Bertram und P. Horak nahe kommt.