Ein Zusammenhang zwischen Dominanz, Maximalgrad und Packungen. - 31 S. : Ilmenau, Techn. Univ., Bachelor-Arbeit, 2011
Henning, Löwenstein und Rautenbach zeigten, dass zwischen der Dominanzzahl $\gamma(G)$, der Packungszahl $\rho(G)$ und dem Maximalgrad $\Delta(G)$ eines Graphen $G$ die Beziehung $\gamma(G)\leq \Delta(G)\rho(G)$ besteht. Für $\Delta(G)\leq3$ können sie diese Ungleichung zu $\gamma(G)\leq 2\rho(G)$ verschärfen, sofern $G$ keinen $K_{1,3}$ als induzierten Teilgraphen hat. Wir zeigen, dass auch Graphen G mit $\Delta(G)\leq3$ und $\gamma(G)\in[\frac{n(G)}{4}, \frac{2}{7}n(G)]\cup[\frac{4}{9}n(G), \frac{n(G)}{2}]$ diese Verschärfung erfüllen. Ferner beweisen wir für $\Delta(G)=\Delta\in\N$, dass $\gamma(G)\leq f(\Delta)\rho(G)$ für Graphen $G$ mit $\gamma(G)\in [\frac{n(G)}{\Delta+1}, \frac{f(\Delta)}{f(\Delta)\Delta+1}n(G)]$ und einer Funktion $f:\N\rightarrow\N$, die $f(\Delta)<\Delta$ für alle $\Delta\in\N$ erfüllt, gilt.
Die Hadwiger Vermutung. - 104 S. Ilmenau : Techn. Univ., Diplomarbeit, 2011
Hadwiger stellte 1943 eine Vermutung über die Beziehung zwischen der chromatischen Zahl und der Existenz von vollständigen Minoren in Graphen auf: Ein zusammenhängender Graph mit chromatischer Zahl k lässt sich auf einen vollständigen Graphen K_k kontrahieren. Für k kleiner als 7 ist die Vermutung bewiesen, für alle anderen Fälle ist sie noch offen. Die Vermutung ist im Rahmen von Beweisversuchen zum Vierfarbenproblem entstanden. Diese Diplomarbeit liefert einen Überblick über die bisher erzielten Teilergebnisse und Beweisversuche zur Hadwiger Vermutung.
Ein Lösungsverfahren für Stochastic Dynamic Distance Optimal Partitioning (SDDP) : Probleme mit MATLAB. - 107 S. Ilmenau : Techn. Univ., Masterarbeit, 2011
Das Ziel dieser Masterarbeit besteht darin, eine Software zu entwickeln, welche in der Lage ist Stochastic Dynamic Distance Optimal Partitioning (SDDP) Probleme zu lösen. Zu diesem Zweck werden nach einer kurzen Vorstellung des zugrundeliegenden markovschen Entscheidungsmodelles die benötigten Parameter für ein SDDP-Modell nach HILDENBRANDT (2010) eingeführt. Zum Auffinden einer optimalen Strategie wird das Strategieiterationsverfahren von Howard benutzt und dessen wesentliche Schritte vorgestellt. Nach einigen kurzen Erklärungen zur Implementation wird die Software an einigen Beispielen untersucht. Dafür werden mit leichten Modifikationen der vorliegenden Software Untersuchungen zur Struktur der verwendeten Beispiele vorgenommen. Desweiteren wird die Größenordnung der vorgestellten Beispiele deutlich. Die Leistungsfähigkeit der Software, welche mit MATLAB entwickelt wurde, ist in Anbetracht der Komplexität der verwendeten Beispiele beachtlich, so dass sich die Software für weitergehende Forschung als wertvolles Hilfsmittel darstellt. In diesem Sinne wird abschließend eine Vermutung aus HILDENBRANDT (2010) zu spezielleren SDDP-Modellen mit einheitlichen Basiskosten und unabhängig, gleichverteilten Bedarfskomponenten widerlegt. Dazu wird ein kleines Gegenbeispiel genauer untersucht und eine Vielzahl weiterer Beispiel-Daten angegeben.
Orthogonalreihenschätzer. - 74 S. Ilmenau : Techn. Univ., Diplomarbeit, 2011
Orthogonalreihenschätzer werden verwendet um verauschte Funktionen (Regressionsmodell) oder Wahrscheinlichkeitsdichte von einen gegebenen Satz an Zufallszahlen auf eine nichtparametrische Art zu schätzen. Deren Erwartungstreue und Konsistenz wird gezeigt. Die optimale Anzahl an Orthogonalfunktionen, der sogenannte Glättungsparameter, hängt von der Funktion oder Dichte ab, welche geschätzt werden soll. Dieser Parameter kann durch Verwendung von Kriterien bestimmt werden, welche ebenfalls in dieser Arbeit behandelt werden. Beispiele demonstrieren Schätzungen mit verschiedenen Basen, Glättungsparamtern, sowie Kriterien. Das verwendete Code-Paket wurde für MATLAB geschrieben und ist dieser Arbeit angehangen. Es enthält Schätzer, Kriterien und Orthonormalsysteme, welche alle in dieser Arbeit vorgestellt wurden. Weiterhin wird die Verwandtschaft zwischen Orthogonalreihenschätzern und Kernschätzern gezeigt.
Optimization of imaging optical systems. - 48 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2011
In the design of optical systems, after creating a starting system, choosing the values of the remaining free parameters in order to maximize image quality is a problem of mathematical optimization. The (objective) function used to assess image quality typically requires ray tracing. We implement a ray tracing procedure for conventional optical systems that allows extension with free-form surfaces and show it to work correctly and sufficiently fast. We compare the performance of optimization algorithms from a freely available package to a commercial optical design software. Optimization algorithms often require derivatives of the objective function and numerical differentiation is commonly used to obtain these derivatives. We implement automatic differentiation and provide evidence that it is preferable to numerical differentiation also in the optimization of optical systems.
Hamiltonkreiserzwingende Mengen in planaren Graphen. - 29 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2011
In der Arbeit wird erklärt was man unter einer Hamiltonkreiserzwingenden Menge und der Hamiltonkreiserzwingenden Zahl versteht. Es werden einige Sätze angegeben, welche klären wie man Hamiltonkreiserzwingende Mengen in Graphen findet und die Hamiltonkreiserzwingende Zahl eines Graphen bestimmt. Desweiteren werden Beweise geführt welche die Hamiltonkreiserzwingenden Zahl in Polyedergraphen, Triangulationen und bestimmten Ringgraphen bestimmen.
Konfidenzmengen für Shortfall Constraints. - 33 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2011
Die Behandlung des Themas "Konfidenzmengen für Shortfall Constraints" stellt eine Verbindung zwischen der stochastischen Optimierung und deren wirtschaftlicher Anwendung dar. Dazu betrachte ich eine in der Portolio-Optimierung auftretende Nebenbedingung zur Risikoregulierung, die Shortfall Constraint genannt wird. Im ersten Teil meiner Arbeit beschreibe ich ein Vorgehen zur Herleitung von Konfidenzmengen für allgemeine Restriktionsmengen. Im zweiten Teil gehe ich näher auf die Shortfall-Restriktionsmenge ein und wende die Theorie an, um zu einem vorgegebenen Stichprobenumfang eine Konfidenzmenge zu bestimmen.
Einfluß der Anzahl großer vollständiger Teilgraphen auf die Unabhängigkeitszahl von Graphen . - 34 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2011
Thomas Hofmeister und Hanno Lefmann haben gezeigt, dass für einen Graphen G ein Algorithmus existiert, der eine unabhängige Menge findet, die mindestens die Mächtigkeit c(n/d)ln(\beta*d) hat. Dabei ist \beta=min{1,\sqrt(n/s)}, c eine positive Konstante und s die Anzahl der Dreiecke, die G enthält. Dieser Algorithmus wird aufgegriffen und auf Graphen, welche vollständige Teilgraphen der Ordnung k, k>=3, enthalten, erweitert. Im zweiten Teil beschäftigen wir uns mit der Arbeit "On the Independence number of sparse graphs" von James B. Shearer und arbeiten diese Stück für Stück durch.
Lokale optimale Färbungen. - 20 S. Ilmenau : Techn. Univ., Bachlor-Arbeit, 2011
Sucht man zu einer Färbung eines Graphen eine alternative Färbung die weniger Farben verwendet, so steht man oft vor algorithmisch schwierigen Problemen. Vorallem über die Menge der umzufärbenden Ecken hat man keine Kontrolle. Um dies zu umgehen, besteht die Möglichkeit sich auf alternative Färbungen einzuschränken, die durch Anwendung lokaler Operationen hervorgehen. Diese Arbeit beschäftigt sich mit solchen Operationen und ihren Färbungsparametern.
Modellierung der Boltzmanngleichung auf diskreten Geschwindigkeitsgittern, numerische Umsetzung und Parallelisierung mithilfe von CUDA. - 116 S. Ilmenau : Techn. Univ., Masterarbeit, 2010
Im ersten Teil dieser Arbeit wurden die wichtigsten Eigenschaften der Boltzmanngleichung zusammengetragen. Daraufhin wurde die Boltzmanngleichung auf einem diskreten Geschwindigkeitsgitter modelliert und gezeigt, dass die modellierte Gleichung die gleichen Eigenschaften besitzt wie die originale Gleichung. In der zweiten Hälfte entwickelten wir einfache Algorithmen um die modellierte (diskrete) Boltzmanngleichung numerisch zu lösen. Diese Algorithmen wurden in C++ zur Berechnung auf einem CPU und parallelisiert in CUDA zur Berechnung auf einem GPU umgesetzt. Abschließend wurden einige Modellprobleme numerisch mithilfe der beiden Implementierungen gelöst und überprüft, ob eine parallelisierte Implementierung dieses Problems auf einem GPU sinnvoll ist.