Vorträge Bachelor: Abstracts

Viskoelastische Fluide vom Oldroyd-Typ

André Eikmeier

In der heutigen Technik kommen immer öfter komplexe Materialien zum Einsatz, unter ihnen die viskoelastischen Fluide. Sie finden Anwendung als Trägerstoff für Salben, in Matratzen oder auch als sogenannte Compliant Walls, die in der Seefahrt zur Verringerung des Treibstoffverbrauchs eingesetzt werden. Während gewöhnliche Newtonsche Fluide mit den Navier-Stokes-Gleichungen modelliert werden, betrachtet man bei viskoelastischen Fluiden ähnliche Gleichungen, die aber einen sogenannten Gedächtnisterm aufweisen.

In diesem Vortrag werden wir uns insbesondere mit den Oldroyd-Fluiden beschäftigen. Nach einer kurzen Erläuterung der bei der Modellierung auftretenden nichtlinearen partiellen Differentialgleichungen werden Existenz- und Eindeutigkeitsaussagen vorgestellt. Schließlich werden der auftretende Gedächtnisterm und die damit in Zusammenhang stehenden mathematischen Schwierigkeiten erläutert.

Die Highway Dimension:
Von Berlin nach München in Millisekunden

Jan Macdonald

Moderne Algorithmen zum Lösen des Kürzeste-Wege-Problems berechnen optimale Reiserouten in oftmals wenigen Millisekunden, auch auf riesigen Straßennetz-Graphen, wie zum Beispiel dem von ganz West-Europa. Dieser Graph hat ungefähr 20 Millionen Knoten und 40 Millionen Kanten. Der bekannte Algorithmus von Dijkstra benötigt auf Graphen dieser Größenordnung im Schnitt mehrere Sekunden. Welche Tricks werden also verwendet, um die Berechnungen derart zu beschleunigen? Die Grundidee ist, dass während einer Preprocessing-Phase einige geschickt gewählte Hilfsdaten im Voraus berechnet und gespeichert werden. Die so gewonnenen Zusatzinformationen können dann während der Anfragen-Phase verwendet werden, um beliebige Routen beschleunigt zu berechnen. In diesem Vortrag wird beispielhaft eine Version des Transit Node Algorithmus näher erläutert. Außerdem werden Bedingungen an den Graphen formuliert, unter welchen für die Anfrage-Phase dieses Algorithmus eine sublineare Laufzeit beweisbar ist. Das zentrale Konzept hierfür ist die sogenannte Highway Dimension.

Non-Holonomic Dynamical Systems and Their Discretization, on the Example of the Chaplygin Sleigh

Pedro Maristany de las Casas

Man stelle sich einen befahrenen Schlittschuh vor. Dieses System ist zwangsweise einer Einschränkung in der Bewegung unterlegen: Die Kufe erlaubt nicht, dass man senkrecht zur aktuellen Richtung abbiegt. Nur gerade Linien und Kreisbögen können gefahren werden und eine Zusammensetzung aus solchen Abschnitten beschreibt die Trajektorie. Der russische Mathematiker Sergey Chaplygin führte dieses System 1911 als ein Beispiel eines nichtholonomen dynamischen Systems ein. Solche sind dynamische Systeme, deren Bewegung durch Bedingungen an die Geschwindigkeit beschränkt wird. In meiner Bachelorarbeit befasste ich mich mit der Diskretisierung dieses Systems, wie sie im Paper Dynamics of the Discrete Chaplygin Sleigh von Yuri N. Fedorov und Dmitry V. Zenkov vorgestellt wird. Kern der Arbeit ist die Untersuchung der Übertragbarkeit der Eigenschaften des kontinuierlichen Systems auf die diskrete Variante: Bleiben sie erhalten? Es stellt sich heraus, dass die passende Wahl der Koordinaten bei der Diskretisierung zu bemerkenswerten Ergebnissen, die konkret für dieses System sehr natürlich erscheinen, führt. Die Grundlagen hierfür werden Bestandteil meines Vortrags sein.

Das div-curl-Lemma und kompensierte Kompaktheit

Martin Plonka

Für eine gegen eine Funktion f stark in L²(Ω) konvergierende Folge (f_n) konvergiert die Folge (f_n²) der Quadrate stark in L¹(Ω) gegen f². Diese Aussage gilt für schwach konvergente Folgen im Allgemeinen nicht. Unter geeigneten Voraussetzung erlaubt das div-curl-Lemma dennoch, auch Aussagen über die Konvergenz des Produkts von nur schwach konvergenten Folgen zu treffen. Eine Verallgemeinerung dieses auf Luc Tartar und François Murat zurückgehenden Resultats ist die Methode der kompensierten Kompaktheit. Mit dieser gelingt es, Aussagen über die Verträglichkeit von schwacher Konvergenz und allgemeiner Nichtlinearität selbst dann zu treffen, wenn klassische Konvexitäts-, Monotonie- oder Kompaktheitsargumente nicht zur Verfügung stehen. Die Methode findet insbesondere bei der Untersuchung nichtlinearer partieller Differentialgleichungen Anwendung: Unter geeigneten Voraussetzungen kann so der Nachweis der Konvergenz von Näherungslösungen gegen eine Lösung der Differentialgleichung und damit der Beweis der Existenz von Lösungen geführt werden.

Die Regeln der Naturkatastrophen

Jonas Schubert

Die Frage nach Rekorden stillt nicht nur unsere Neugier, sondern sie ist auch essenziell wichtig für unser Überleben. Häufig geht es dabei um ausgesprochen unbeständige und in höchstem Maße unvorhersehbare Phänomene wie zum Beispiel Naturkatastrophen – von Hochwasser bis hin zu Vulkanausbrüchen. Es ist daher lebensnotwendig, anhand historischer Aufzeichnungen eine Idee zu bekommen, was man in der Zukunft erwarten und wie man sich darauf vorbereiten kann.

Diese Daten richten sich zumeist nicht nach offensichtlichen Regeln, sondern sehen eher „zufällig“ aus, sodass man sie mit einem stochastischen Prozess modelliert.

In diesem Vortrag wird eine Folge von stationären Zufallsvariablen als Modell gewählt und untersucht, unter welchen sogenannten Mischbedingungen man eine Konvergenz ihrer Maxima gegen eine Verteilung erhält und somit den unabhängig identischen Fall verallgemeinern kann.

Es wird außerdem auf dieser Basis ein Resultat von Anderson und Turkman zur gemeinsamen Extremwertverteilung von Summen und Maxima stationärer Prozesse diskutiert.

Quilted Gabor Frames und Fusion Frames – oder, wie du mehr Songs auf deinem Smartphone speichern kannst

Laura Terhaar

Möchtest du auch alle deine Lieblingslieder immer auf dem Smartphone verfügbar haben? Hast du ständig neue Lieder und möchtest trotzdem auch mal die alten hören? Dann ist es für dich wichtig, dass die Methoden der Datenkompression ständig verbessert werden. Seit langer Zeit spielen Gabor Frames eine große Rolle in der Analyse von Audiosignalen. Diese analysieren die Signale sowohl in der Frequenz als auch in der Zeit. Dabei muss jedoch immer ein Kompromiss zwischen der genauen Analyse in der Zeit und der Frequenz geschlossen werden. Es ist nicht möglich, beide Komponenten exakt zu analysieren. Deshalb wurde 2011 die Theorie von Quilted Gabor Frames eingeführt, welche es erlaubt, mehrere Gabor Frames in der Zeit-Frequenz-Ebene zu nutzen. Dadurch wird die Analyse verbessert, jedoch ist die Sicherstellung der Framebedingung erschwert und damit die sinnvolle Rekonstruktion. Durch die Einordnung von Quilted Gabor Frames in die bereits gut erforschte Theorie von Fusion Frames ist es möglich, Ergebnisse aus der Theorie der Fusion Frames zu übertragen. Damit erhalten wir eine größere Klasse von Quilted Gabor Frames mit den gewünschten Eigenschaften. In diesem Vortrag werden zunächst die Probleme der Gabor Frames am Beispiel dargestellt. Danach werden Quilted Gabor Frames betrachtet und diese in Beziehung zu Fusion Frames gesetzt. Zum Schluss werden Resultate aus der Einordnung gezeigt und wie Quilted Gabor Frames die Analyse verbessern. Dies führt dazu, dass du weißt, warum du auf keines deiner Lieblingslieder verzichten musst!

Dynamic Bin Packing – Theory And Computational Experiments

Fabian Wegscheider

Given a set of items with sizes between 0 and 1, the (one-dimensional) Bin Packing Problem is to store these items in as few bins of unit-capacity as possible. Since the early 70’s a lot of approaches to solve the BPP have been studied, as it models a number of problems in computer science and industry. A generalization of it, called the Dynamic Bin Packing Problem, allows for some items to be unpacked during the packing process. In other words, in the dynamic version, a list of stations has to be dealt with at each of which some already packed items are to be unloaded while new items have to be added to the bins.

While the classical Bin Packing Problem has been well studied in the past, not quite as much attention has been paid to its dynamic variant, with a particular lack of computational experiments. In this talk I will briefly summarize the content of my bachelor thesis, which includes an overview of important theoretic results for both of the problems and a presentation of the results obtained by computational experiments with algorithms for the dynamic version.

Der Wächter-Biegler-Effekt im Kontext affiner Kovarianz

Marc-Steffen Zwisele

In dieser Arbeit wird auf das Gegenbeispiel von Wächter und Biegler zur globalen Konvergenz von innere-Punkt-Methoden für nicht-lineare Optimierungsprobleme eingegangen und eine Modifikation des Composite-Step-Verfahrens nach Vardi vorgestellt. Diese affin kovariante Modifikation behebt den Wächter-Biegler-Effekt durch Projektion der Slackvariablen.

Vorträge Master: Abstracts

Zur Kopplung atomistischer und kontinuierlicher Modelle

Clemens Bartsch

Seit einigen Jahren kommt dem Konzept der Multiskalenmodellierung in der mathematischen Modellierung physikalischer Vorgänge einiges an Aufmerksamkeit zu. Eine in der Elastizitätstheorie anzutreffende Klasse solcher Multiskalenmodelle koppelt eine atomistische und eine kontinuierliche Beschreibung der Materie. Ein stark vereinfachtes Modell dieses Typs wurde 2007 von X. Blanc, C. Le Bris und F. Legoll untersucht. Das Modell ist eindimensional und nutzt ein konvexes Potenzial. Im Vortrag nehmen wir uns der Frage der Wohlgestelltheit dieses gekoppelten Modells als Variationsproblem und der Konvergenz der Lösung gegen die Lösung eines rein atomistischen Modells an. Dies wird den Schwerpunkt des Vortrags bilden. Des Weiteren stellen wir eine Anwendung der Multiskalenmodellierung vor, die erfolgreiche „Quasi-Continuum Method“. Mit dieser Methode können Verformungen von kristallinen Feststoffen genau und wenig rechenaufwändig simuliert werden. Dabei konzentrieren wir uns auf eine statische Version, zeigen aber in einem Ausblick auch eine dynamische Variante.

Verallgemeinerungen des Wright-Fisher-Modells

Eugenio Buzzoni

Die theoretische Populationsgenetik ist ein Thema, das zwischen Mathematik und Biologie liegt und als Ziel hat, die Fluktuation genetischer Typen innerhalb einer Bevölkerung zu erklären. Zu Beginn des 20. Jahrhunderts begann man, die Populationsgenetik auf mathematischer Basis (z.B. mit Hilfe von stochastischen Prozessen) zu formulieren; ein Meilenstein dafür stellen die Werke von Fisher (1922) und Wright (1931) dar. Das Hauptthema meines Vortrags ist das klassische Wright-Fisher-Modell – das grundlegende stochastische Modell, das von diesen zwei Wissenschaftlern stammt – sowie einiger seiner (z.T. sehr aktuellen) Verallgemeinerungen.

Die empirische Analyse von Lösungsphasen bei Gemischt-Ganzzahliger Programmierung

Gregor Christian Hendel

Für viele Entscheidungsprobleme aus Wirtschaft und Industrie stellt die Gemischt-Ganzzahlige Programmierung (Mixed Integer Programming, MIP) aufgrund ihrer enormen Modellierungsmöglichkeiten das Werkzeug der Wahl dar. Dieses kommerzielle Interesse motiviert die Entwicklung von anwendungsübergreifender Lösungssoftware. Derzeit verfügbare Löser verwenden das globale Branch-and-Bound-Verfahren, dessen Lösungsverlauf sich in drei Phasen einteilen lässt. Deren exakte Erkennung würde eine verbesserte Steuerung der Suche sowie zahlreicher Hilfsalgorithmen wie Primalheuristiken und Schnittebenenverfahren für die jeweilige Phase ermöglichen, ist jedoch im Allgemeinen NP-schwer.

In diesem Vortrag stellen wir einerseits Komponenten für jede Phase vor, durch deren Kombination wir im CIP-Framework SCIP eine Zeiteinsparung von bis zu 50 % in den einzelnen Phasen erzielen. Anschließend entwickeln wir Kriterien für einen heuristischen Phasenübergang. Insgesamt drei verschiedene solcher Ansätze werden in dieser Arbeit vorgestellt. Das erste Kriterium nutzt eine stetige Approximation des diskreten primalen Lösungsverlaufs mit Hilfe einer logarithmischen Regressionskurve. Die anderen beiden Kriterien benutzen globale Informationen über den Zustand des Suchbaumes. Abschließend zeigen wir anhand von experimentellen Daten den Einfluss unseres so konstruierten dynamischen Lösers auf die Gesamtlaufzeit von SCIP.

A Configuration Model for the Line Planning Problem

Heide Hoppmann

Das Linienplanungsproblem ist ein wichtiges Teilproblem der Angebotsplanung im öffentlichen Nahverkehr. Dabei werden Routen und Betriebsfrequenzen von Linien in einem gegebenen Infrastrukturnetzwerk gesucht, sodass ein gegebener Beförderungsbedarf gedeckt wird und die Kosten minimal sind.

Praktische Ansätze zum Lösen dieser Probleme beruhen auf ganzzahliger Programmierung. Ein Schwachpunkt klassischer Modelle ist es, dass schon kleine Änderungen der Eingabeparameter eine Vergrößerung oder Verkleinerung der Menge der zulässigen fraktionalen Lösungen bewirken können, auch wenn die Menge der ganzzahligen Lösungen unverändert bleibt. Wir betrachten in dieser Arbeit einen neuen kombinatorischen Ansatz, welcher die Möglichkeiten, den Bedarf auf einer Verbindung im Netzwerk mit Frequenzen zu überdecken, mit Hilfe von diskreten „Konfigurationen“ beschreibt und dieses Problem eliminiert.

Um die Vorteile dieses Konfigurationsmodells aufzuzeigen, vergleichen wir es mit einem klassischen Ansatz, den wir Standardmodell nennen. Wir zeigen, dass das Konfigurationsmodell mehrere facettendefinierende Ungleichungen des Standardmodells impliziert: Setcover-, symmetrische Band-, Multicover- und MIR-Ungleichungen. Diese theoretischen Ergebnisse können wir mit Rechenergebnissen bestätigen. Um die Anzahl dieser Variablen auch für große Instanzen zu beschränken, schlagen wir ein weiteres Modell vor, welches nur eine Teilmenge der Konfigurationsvariablen enthält. Dieses stellt sich als ein sehr guter Kompromiss zwischen der Größe und der Stärke des Modells heraus. Da das Linienplanungsproblem eine Spezialisierung des Netzwerkdesignproblems ist, können unsere Methoden auch auf andere Problemklassen übertragen werden.

Das Standortentscheidungsproblem mit strikten Kapazitäten

Antje Lehmann

In Standortentscheidungsproblemen geht es darum, für eine feste Menge von Kunden eine Teilmenge der gegebenen, potenziellen Standorte auszuwählen, und jeden Kunden an einem der gewählten Standorte anzubinden. Ziel ist es, die Summe der Kosten für Standortanbindung und Standorteröffnung zu minimieren. Ein Beispiel hierfür ist die Frage, wie Server möglichst günstig platziert werden können, damit eine gegebene Menge von Computern gut angebunden ist. In realen Anwendungen kommt es häufig vor, dass jeder Standort nur eine begrenzte Menge von Kunden bedienen kann. Wie ist es jedoch, wenn die Kapazität jedes zu eröffnenden Standortes ausgeschöpft werden soll? Zum Beispiel um Ressourcen zu schonen, oder weil auf jedem Tennisfeld genau zwei (oder aber null) Tennisspieler sein sollen? Im Vortrag wird gezeigt, dass das Tennisfeldproblem von einem Algorithmus, welcher in polynomieller Zeit läuft, gelöst werden kann und daher in diesem Sinne leicht ist. Sobald es jedoch um Doppel geht – genauer: für mehr als strikt zwei Kunden – ist das Problem schwer, daher wird ein Approximationsalgorithmus präsentiert und analysiert.

Irrfahrt in zufälliger Umgebung

Tuan Anh Nguyen

Es sei є Z² die Menge von Gitterpunkten in der Ebene: Jeder Punkt hat 4 Nächste-Nachbarn und є ist der Abstand zwischen 2 Nächste-Nachbarn-Punkten.

Zwei Nächste-Nachbarn-Punkte x,y werden mit einer zufälligen Leitfähigkeit ω_xy≡ ω_yx∈ [0,∞) verbunden. Ein Teilchen bewegt sich in den Gitterpunkten nach der folgenden Regel: Nach jeder Zeiteinheit bewegt es sich durch eine Leitfähigkeit zu einem Nächste-Nachbarn-Punkt mit einer Wahrscheinlichkeit, die proportional zu der Leitfähigkeit ist. Wir sprechen daher von einer Irrfahrt in zufälliger Umgebung (random walk in random environment).

Trotz der Zufälligkeit der Umgebung erhalten wir (unter ein paar Bedingungen) ein Invarianzprinzip: Für є→ 0 konvergiert die Trajektorie des Teilchens gegen eine zufällige Kurve, und zwar eine brownsche Bewegung, deren Struktur nicht mehr von der zufälligen Umgebung abhängt.

Im Vortrag werden die Stichwörter Umgebung, Irrfahrt, brownsche Bewegung, Invarianzprinzip usw. schrittweise anschaulich erklärt.

Kostenverteilungen für eine bessere Welt

Daniel Schmand

Häufig suchen wir im Alltag einen optimalen Weg von unserem aktuellen Standort zu einem Ziel. Doch welches Verkehrsmittel und welche Route sollten wir wählen? Hängt diese Frage nicht auch direkt von den anderen Menschen im Netzwerk ab? Dieses und andere Probleme lassen sich gut mit sogenannten Auslastungsspielen modellieren. Hierbei sucht jedes Individuum einer Spielermenge rational und egoistisch einen kostengünstigsten Weg von einem gegebenen Startknoten zu einem Zielknoten im vorgegebenem Netzwerk. Die Kosten der Kanten des Netzwerks sind dabei aber nicht fest, sondern hängen direkt von der Menge der Spieler_innen ab, die die Kante in ihrem Weg gewählt haben und werden dann mit einer Kostenverteilungsmethode auf die Nutzenden verteilt. Damit beeinflussen die Spieler_innen mit der Wahl ihrer Strategie also direkt die Kosten der Strategien der anderen. Wir untersuchen die Güte von Gleichgewichtslösungen in diesen Spielen im Vergleich zu einem vorgegebenem Systemoptimum in Anhängigkeit von der gewählten Kostenverteilungsmethode. Dabei präsentieren wir eine Kostenverteilungsmethode, die bestmögliche Gleichgewichte unter den sogenannten uniformen Methoden garantiert.