Studienabschlussarbeiten am Institut

Ein adiabatischer Quantencomputer kann quadratische unrestringierte binäre Optimierungsprobleme (QUBO-Probleme) effizient lösen, unter bestimmten Voraussetzungen sogar schneller als herkömmliche Computer. Das Ziel dieser Arbeit ist es herauszufinden, welche Optimierungsprobleme als QUBO-Problem modelliert werden können und in welcher Form dies möglich ist. Es stellt sich heraus, dass beliebige ganzzahlige Optimierungsprobleme als QUBO-Pro- bleme modelliert werden können, sofern geeignete Straffunktionen existieren und alle Variablen beschränkt sind. Für die nötigen Umformungsschritten werden die Voraussetzungen diskutiert. Dies umfasst Binärdarstellungen von beschränkten ganzzahligen Variablen, die Reduzierung des Grades multilinearer binärer Polynome und das Aufnehmen von Nebenbedingungen in die Zielfunktion. Des Weiteren werden für multilineare binäre Gleichungs- und Ungleichungsnebenbedingungen geeignete Straffunktionen aufgestellt und verschiedene Möglichkeiten der Wahl der Straffunktionen diskutiert. Zudem wird analysiert, wie mit Betragsfunktionen in Nebenbedingungen und in Zielfunktionen verfahren werden kann.

Das Ziel dieser Masterarbeit ist es, ausgewählte Arbeiten aus der Spieltheorie, neu darzustellen, weiter zu untersuchen und neue Erkenntnisse zu generieren. Dazu wird folgende Forschungsfrage gestellt: Welche neuen Aussagen können ergänzend zur vorgestellten Literatur bewiesen werden? Um die Frage zu beantworten, werden verschiedene wissenschaftliche Publikationen ausgewertet und ergänzendes Hintergrundwissen zusammengetragen. In Abschnitt 3 sehen wir, dass eine abzählbar unendliche Spielermenge nötig ist, damit ein sogenanntes Wasserfallspiel existiert. Dem Autor ist es gelungen zu beweisen, dass dies für eine beliebige abzählbar unendliche Menge erfüllt ist. Wenn wir beim Austausch der i-ten Aktion durch H bzw. S Gleichheit der Auszahlungsfunktion zulassen, dann können wir zeigen, dass dieses Spiel leicht für eine beliebige abzählbar unendliche Menge konstruierbar ist. Anhand des Untreue-Ehemänner-Problems untersuchen wir in Abschnitt 4 die Auswirkungen der Kommunikationsform. Hierbei stellen wir fest, dass untreue Ehemänner frühestens nach drei Nächten hingerichtet werden können, wenn sich die Frauen nicht über die Treue ihrer Männer unterhalten dürfen. Insgesamt erkennen wir, dass die Anzahl der untreuen Ehemänner für die Argumentation entscheidend ist. Aus diesem Kommunikationsdilemma lernen wir, dass die Wirkung einer Aussage maßgeblich von der Beschaffenheit des Informationskanals abhängt. Dabei nimmt der derzeitige Allgemeinwissensstand eine zentrale Rolle ein. Abschließend können wir mithilfe der evolutionären Spieltheorie feststellen, wie stabil Strategien sind. Dabei erkennen wir, dass das Nash-Gleichgewicht im Urlauberdilemma instabil ist, wenn es zulässig ist, dass sehr große Zahlen notiert werden. Daher ist es, entgegen der klassischen Spieltheorie, sinnvoll von Nash-Gleichgewichten abzuweichen.

In der vorliegenden Masterarbeit wird ein Monte Carlo-Algorithmus zur numerischen Simulation von Gelationsphänomenen entworfen und getestet. Gelation beschreibt den Vorgang, bei dem Partikel endlicher Masse in endlicher Zeit zu Partikeln unendlicher Masse heranwachsen. Die Basis dafür bilden Koagulationsprozesse, welche mittels der Smoluchowski -Gleichung abgebildet werden. Beim Entwurf eines entsprechenden Algorithmus liegt die Schwierigkeit in der numerischen Erfassung der Gelation. Diese erfordert das Konzept einer geeigneten Schwelle, welche in der Arbeit entsprechend hergeleitet und eigeführt wird. Weiterhin werden Maßnahmen zur effizienten Gestaltung des Algorithmus vorgestellt und auf die Aussagekraft und Grenzen des Algorithmus eingegangen. Der Basisalgorithmus zur Simulation von Gelationsphänomenen wurde mittels Operatorensplitting erweitert. In diesem Zusammenhang werden Koagulationsprozesse unter Berücksichtigung von räumlicher Diffusion und deren Auswirkung auf das Gelationsverhalten des betrachteten Systems untersucht.

Der Zustandsraum von Markovketten lässt sich durch die Doob-Martin-Kompaktifizierung um den Martin-Rand erweitern, sodass diese fast sicher konvergieren. In dieser Arbeit werden die Doob-Martin-Kompaktifizierungen verschiedener kombinatorischer Markovketten und kombinatorischer Familien betrachtet. Hierbei wird nachgewiesen, dass der Martin-Rand kombinatorischer Familien bestehend aus Permutationen S* und schlichter Graphen G bezüglich einer Vielzahl kombinatorischer Markovketten der Menge der Permutons beziehungsweise Graphons entspricht. Allgemeiner werden für beliebige kombinatorische Familien mit geeignetem Einbettungsbegriff kombinatorische Markovketten konstruiert. Diese Markovketten sind eng mit den Einbettungsbegriffen verknüpft und die über sie definierten Doob-Martin-Kompaktifizierungen können als natürliche Kompaktifizierung der kombinatorischen Familie aufgefasst werden. Die Annahmen über die Einbettungsbegriffe der kombinatorischen Familien sind hierbei so schwach gewählt, dass neben den G und S* viele der bisher in der Literatur betrachteten kombinatorischen Familien als Spezialfälle dieses neuen generischen Ansatzes betrachtet werden können.

In dieser Arbeit werden simultane Konfidenzintervalle mithilfe der Bonferroni-Methode und der Scheffé-Methode für den Wahrscheinlichkeitenvektor einer Multinomialverteilung hergeleitet. Diese werden dann auf eigens erhobene Daten eines Galtonbrettes angewendet, um die Nutzbarkeit dieser Apparatur zu Lehrzwecken zu beurteilen. Dabei wird untersucht, welche der beiden Methoden für diese Anwendung zu kleineren Konfidenzintervallen führt. Es zeigt sich, dass die Bonferroni-Methode, die im Gegensatz zur Scheffé-Methode die linearen Abhängigkeiten in den Komponenten des Wahrscheinlichkeitenvektors ignoriert, die kleineren Intervalle erzeugt. Die Anwendung der simultanen Konfidenzintervalle an dem Galtonbrett führt zu der Erkenntnis, dass dieses für zwei der insgesamt drei Einstellungen seinen Lehrzweck erfüllt.