Kompetitivitätsanalyse von Online-Algorithmen für das verallgemeinerte Paging-Problem. - Ilmenau. - 71 Seiten
Technische Universität Ilmenau, Diplomarbeit 2022
Im Gebiet Online-Optimierung werden Probleme betrachtet, bei denen Anfragefolgen mit minimalem Kostenaufwand bearbeitet werden sollen. Eine Anfrage wird dabei erst gestellt, wenn die vorhergehende bereits fertig beantwortet worden ist. Für die Gruppe der Paging-Probleme gibt es einige Algorithmen, die mögliche Antwortvorschriften liefern. In dieser Arbeit wird eine Verallgemeinerung des Paging-Problems vorgestellt. Hier werden Mehrfachbelegungen auf einem Punkt und Mehrfachforderungen in einer Anfrage zugelassen; die Abstände zwischen je zwei Punkten sind jedoch immer gleich. Dann wird der optimale Paging-Algorithmus LFD für das verallgemeinerte Paging-Problem erweitert und seine Optimalität nachgewiesen. Die Algorithmen LRU und MARK, die ebenfalls eigentlich für das Paging-Problem verfasst wurden, werden für das verallgemeinerte Paging-Problem angepasst. Danach wird ihre Kompetitivität nachgewiesen, indem für beide ein Vergleich mit einem optimalen Offline-Algorithmus durchgeführt wird.
Relative genericity with applications to linear differential-algebraic systems. - Ilmenau. - 63 Seiten
Technische Universität Ilmenau, Masterarbeit 2022
Das vor kurzem eingeführte Konzept der Generizität relativ zu einer Referenzmenge wird untersucht. Es wird gezeigt, dass relative generische Mengen viele Eigenschaften des von Wonham verwendeten klassischen Generizitätskonzepts aufweisen, nämlich dass sie unter Vereinigung, Schnittmenge und Obermengen geschlossen sind und ihr Komplement nirgends dicht ist. Unter Verwendung dieser Eigenschaften wird dann gezeigt, dass der Rang von Polynom-Blockmatrizen mit beschränktem Grad sowohl über dem Körper der rationalen Funktionen als auch auf der gesamten komplexen Ebene (wenn die Matrix nicht quadratisch ist) generisch voll ist, unter der Bedingung, dass der Rang eines Blocks von oben beschränkt ist. Diese Ergebnisse werden dann auf die algebraischen Charakterisierungen verschiedener Konzepte der Steuerbarkeit und Stabilisierbarkeit für lineare differential-algebraische Systeme der Form Ex' = Ax + Bu angewandt und notwendige und hinreichende Bedingungen für die Dimensionen von E, A und B abgeleitet, unter denen diese Systeme mit festem Rang von E steuerbar und stabilisierbar sind.
Betrachtung der Gradientenbestimmung für den Adam Algorithmus. - Ilmenau. - 80 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2022
In dieser Arbeit werden verschiedene Abstiegsverfahren dargestellt. Speziell wird auf das Gradientenverfahren eingegangen und am Beispiel von Empirical Risk Minimization eine Entwicklung bis hin zu adaptiven Verfahren wie dem Adam-Algorithmus beschrieben. Anschließend wird das CLUE-Verfahren erklärt, welches den Adam-Algorithmus zum Lösen einer gewichteten Summe verwendet. Das CLUE-Verfahren verwendet ein Bayesches neuronales Netz und einen Variational Autoencoder, um eine Zielfunktion zu definieren. Diese beiden neuronalen Netze werden beschrieben und es wird erklärt, wie solche trainiert werden können. Für die Zielfunktion wird der Einfluss von verschiedenen Batch-Größen untersucht. Außerdem wird eine modifizierte Abbruchbedingung betrachtet.
Minimalgradzerlegungen von Kreispotenzen. - Ilmenau. - 35 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2022
Das Ziel dieser Arbeit ist es, herauszufinden für welche s und t es unendlich viele (s+t)-zusammenhängende Graphen gibt, die keine (s,t)-Zerlegung besitzen. Zu diesem Zweck wurden Potenzen von Kreisen auf Existenz solcher Zerlegungen untersucht. Dabei ist eine Zerlegung hier ein Tupel induzierter, disjunkter Teilgraphen, sodass jede Ecke des Graphen in einem der beiden Teile enthalten ist und eine (s,t)-Zerlegung eine solche Zerlegung, sodass der eine Teil Minimalgrad s und der andere Minimalgrad t hat. Dabei wurden die Fälle s = t, s = 1, s = 2 sowie s = 3 vollständig analysiert. Für allgemeine s und t konnten hinreichende Kriterien für die Existenz von (s,t)-Zerlegungen von Kreispotenzen hergeleitet werden, welche nicht immer erfüllt seien können. Dadurch wurden unendlich viele (s+t)-zusammenhängende Graphen ohne eine (s,t)-Zerlegung gefunden. Zusätzlich wurden auch notwendige Kriterien gefunden.
Diskrete Geschwindigkeitsmodelle und ihr Bezug zu den Navier-Stokes-Gleichungen. - Ilmenau. - 105 Seiten
Technische Universität Ilmenau, Masterarbeit 2022
Das Ziel dieser Arbeit ist die Herleitung von Parametern der Strömungstheorie, dem Viskositäts- und Wärmeleitkoeffizienten sowie der Prandtl-Zahl, aus der Lösung der räumlich homogenen Boltzmann-Gleichung mit Korrekturterm. Um dies zu erreichen, beschäftigen wir uns zuerst mit der Boltzmann-Gleichung, einer mesoskopischen Gleichung der Gastheorie für verdünnte Gase. Diese wird auf einem diskreten Geschwindigkeitsmodell betrachtet, um die Lösung numerisch berechnen zu können. In diesem Zusammenhang interessieren wir uns auch für die Möglichkeit der Beeinflussung der Prandtl-Zahl durch die Wahl der Stoßgewichte des Stoßoperators der Boltzmann-Gleichung. Dafür wird zuerst die Theorie erarbeitet, die der Arbeit mit der Boltzmann-Gleichung zugrunde liegt und ein diskretes Geschwindigkeitsmodell definiert. Dazu gehört die Arbeit mit elastischen Stößen und dem allgemeinen und linearisierten Stoßoperator. Die Anfangsbedingung und gewisse Korrekturterme werden anschließend bestimmt, um die homogene Boltzmann-Gleichung aufstellen zu können. Dann werden wir uns mit dem Begriff des Orbits auseinandersetzen, der die Arbeit mit dem komplexen Geschwindigkeitsmodell etwas vereinfacht. Wir können anschließend feststellen, dass die Gewichte in den Stoßoperatoren die Lösung der Boltzmann-Gleichung tatsächlich beeinflussen können. Es werden gewisse Kriterien erstellt, nach denen die Gewichte, zusammengefasst in Gewichtsvektoren, aufgestellt werden können. Mit diesen Gewichtsvektoren kann nun die Boltzmann-Gleichung gelöst werden und diese Lösungen können zusammen mit den Prandtl-Zahlen für jedes der verwendeten Gewichte ausgewertet werden. Dies wird für zwei unterschiedliche Gittermodelle ausgetestet und die Ergebnisse werden dokumentiert. Schließlich wird die Herleitung der Euler- und Navier-Stokes-Gleichungen aus der Boltzmann-Gleichung erarbeitet und das Vorgehen skizziert. Somit wird auch die Entstehung der Prandtl-Zahl, die eine Kennzahl der Navier-Stokes-Gleichungen ist, sowie ihre Verbindung zu der Boltzmann-Gleichung, erklärt.
Verbundene perfekte Matchings in Graphen mit spezieller Kempe-Färbung. - Ilmenau. - 21 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2022
In dieser Arbeit wird eine Verschärfung eines Spezialfalls der Hadwiger-Vermutung gelöst. Es werden Graphen mit einer Kempe-Färbung, das ist eine Färbung, in der der von je zwei Farbklassen induzierte Teilgraph zusammenhängend ist, betrachtet und unter diesen solche, in denen alle Farbklassen die Größe zwei haben. Unter dieser Voraussetzung konnte gezeigt werden, dass, wenn der Graph nicht allzu viele nicht verbundene Kanten besitzt, er ein perfektes Matching, in dem die Kanten paarweise verbunden sind, haben muss. Dieses verbundene perfekte Matching stellt dann einen vollständigen Minor dar, der so viele Taschen hat, wie die Färbung Farbklassen.
Analyse der Varianz der Aktivierungen in Convolutional Neural Networks zum Verzicht auf Batch Normalization. - Ilmenau. - 105 Seiten
Technische Universität Ilmenau, Masterarbeit 2021
Im Rahmen der Bildverarbeitung werden künstliche Intelligenzen zur Klassifikation eingesetzt. Ein sehr verbreitetes Modell in Bezug auf diese Problemstellung ist das in dieser Masterarbeit vorgestellte ResNet. In ResNets ist die Batch Normalization ein wesentlicher Bestandteil und trägt erheblich zum Trainingsprozess dieser Netzwerke bei. Nichtsdestotrotz bringt sie auch einige Nachteile mit sich, weshalb es in den letzten Jahren viele Bestrebungen gab, Batch Normalization zu ersetzen. Allerdings führt ein bloßes Entfernen der Batch Normalization in ResNets zu explodierenden Varianzen, welche mit dem Exploding Gradient Problem einhergehen, das zum frühen Abbruch des Trainings eines Netzwerks führt. Im Fokus dieser Masterarbeit steht deshalb die Analyse der Entwicklung der Varianzen innerhalb von ResNets und ResNet-ähnlichen Architekturen ohne Normierung, wie dem RescaleNet. Auf Basis ausführlicher Varianzanalysen ergründen wir, welche Effekte in modifizierten preactivation ResNet-Varianten ohne Batch Normalization auftreten. Dabei wird in dieser Masterarbeit erstmals aufgezeigt, inwiefern das Padding im Residuum-Zweig Einfluss auf die Varianzentwicklung ausübt. Außerdem arbeiten wir Unterschiede zwischen den Entwicklungen der Varianzen im pre- und postactivation RescaleNet heraus und trainieren das preactivation RescaleNet erstmals erfolgreich sowohl auf dem CIFAR-10- als auch auf dem ImageNet-Datensatz.
Entwicklung und Implementierung eines numerischen Verfahrens zur Lösung eines unvollständigen Anfangswertproblems mit Nebenbedingung. - Ilmenau. - 41 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2021
In der vorliegenden Arbeit wurde ein numerisches Verfahren entwickelt, um ein unvollständiges Anfangswertproblem mit Nebenbedingung zu lösen. Dieses wird durch die aus der Physik bekannte Boltzmanngleichung motiviert. Da man häufig nur an stationären, also zeitunabhängigen Lösungen in einer Raumdimension interessiert ist, genügt es die Gleichung im eindimensionalen Fall zu betrachten, wo sie durch ein Randwertproblem gegeben ist. In der Praxis wird das zeitabhängige Problem so lange numerisch gelöst, bis der asymptotisch stationäre Zustand erreicht ist. Da diese Methode sehr rechenintensiv ist, wurde in der vorliegenden Arbeit anhand eines einfachen Modells des Stoßoperators eine alternative Berechnungsmethode entwickelt. Hierbei wird ausgehend von einer bekannten Lösung eine Homotopiemethode in Verbindung mit einem einfachen Schießverfahren genutzt, um die stationäre Lösung zu erhalten. Die dafür benötigten Schritte wurden in Matlab implementiert. Abschließend wurden numerische Berechnungen durchgeführt, um zu sehen, wie sich verschiedene Störungen der Anfangswerte auf die Lösung des Problems auswirken.
Zur Zerlegung von Ordnungen mit totalen Ordnungserweiterungen. - Ilmenau. - 51 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2021
Mit der Ordnungsdimension haben Dushnik und Miller 1941 ein Konzept entwickelt, das es ermöglicht, die Komplexität endlicher partieller Ordnungen abzuschätzen. In dieser Arbeit entwickeln wir eine alternative Methode zur Darstellung derartiger Ordnungen durch totale Ordnungserweiterungen, die - im Unterschied zum vorherigen Ansatz - zusätzliche Informationen über die Minima beliebiger Teilmengen erhalten. Wir beschäftigen uns dabei zunächst mit der Frage, wie groß derartige Zerlegungen wenigstens sein müssen und leiten anschließend konstruktive Zerlegungsalgorithmen her, die wir an geeigneten Beispielen testen.
Klassifikation von Merkmalsvektoren mit vorheriger Dimensionsreduktion mittels Hauptkomponentenanalyse am Beispiel der Pflanzenbestimmung. - Ilmenau. - 80 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2021
In dieser Bachelorarbeit befassen wir uns mit der Klassifikation von Merkmalsvektoren nach einer Dimensionsreduktion. Zu diesem Zweck wurde uns ein Datensatz aus Merkmalsvektoren zur Verfügung gestellt, der aus Fotos von Blumen entstanden ist. Auf die Bestimmung eines Merkmalsvektors auf der Grundlage eines Fotos werden wir nicht eingehen. Unser Ziel ist es herauszufinden, ob eine Dimensionsreduktion mittels Hauptkomponentenanalyse vor der Klassifikation auf diesem Datensatz nennenswerte Vorteile bringt, ohne große Nachteile in der Genauigkeit der Klassifikation zu verursachen. Der Schwerpunkt der Theorie liegt dabei auf der Hauptkomponentenanalyse. Diese werden wir aus statistischer Sicht heraus erklären. Im Kontext der Eigenwertzerlegung bei der Hauptkomponentenanalyse gehen wir zudem auf deren Zusammenhang mit der Singulärwertzerlegung ein und geben ein Beispiel, wie sie numerisch berechnet werden kann. Zur Klassifikation von Merkmalsvektoren verwenden wir Support Vector Machines. Hier betrachten wir Vektoren zweier Klassen, die sich durch eine Hyperebene trennen lassen, um die Funktionsweise exemplarisch anzudeuten. Anschließend haben wir in der Programmiersprache python Programme erstellt, die es uns erlauben, Vorzüge und Nachteile der Dimensionsreduktion vor der Klassifikation auf unseren Daten zu untersuchen. Das Ergebnis dieser Untersuchung wird sein, dass für unseren Datensatz eine Reduktion auf Dimension vierzig vor der Klassifikation sinnvoll scheint. Die Laufzeit wird hier, zumindest für unsere Implementierung, stark verkürzt, während die Präzision der Klassifikation in etwa erhalten bleibt.