PD Dr. Sascha Kurz

Lehrstuhl für Wirtschaftsmathematik
Mathematisches Institut, Fakultät für Mathematik, Physik und Informatik

Abschlussarbeiten

• Kontakt
• Forschung
• Lehre
• Projekte

• Kommende Veranstaltungen
• Aktuelle Veranstaltungen
• Übersicht Veranstaltungen
• Abschlussarbeiten

Betreute Abschlussarbeiten

• Nikolas Tautenhahn (Dissertation): Enumeration und Optimierung einfacher vollständiger Spiele (vorläufiger Arbeitstitel),

• "Minimale Anzahl von Hinweisen bei Sudoku" (Details)
• "K-Server Problem und der Arbeitsfunktionenalgorithmus" (Details)
• "Selbstorganisierende Datenstrukturen" (Details)
• "Eine effiziente Implementierung der Score-Fix-Adjust-Heuristik" (Details)
• "Preisoptimierung und Nachfrageschätzung bei zensierten Daten" (Details)
• "Die Score-Fix-Adjust-Heuristik" (Details)
• "Fairness-Optimierung bei der Zuweisung von Stimmgewichten"
• "Minimal orientierter Durchmesser" (Details)
• "Monotone Boolsche Funktionen in der Qualtätssicherung"
• "Polyominos mit minimalem Umfang"
• "Polyominos mit maximalem Flächeninhalt der konvexen Hülle"
• "Palindrome"
• "Punktmengen mit wenigen Abständen"
• "Ganzzahlige Punktmengen in höherdimensionalen Euklidischen Räumen"
• "Ganzzahlige Punktmengen über \mathbb{Z}_n^m"
• "Ganzzahlige lineare Programme in der Diskreten Geometrie" (Details)
• "Unvermeidbare Polyominos" (Details)
• Weitere Themen auf Anfrage, sind aber in Vorbereitung. Eigene Vorschläge sind natürlich auch möglich. Anregungen kann man weiter in meinem Skript zur Diskreten Geometrie finden.

• Stefan Müller (Bachelorarbeit): Gewichtete Mediane -- Wieviel Einfluss hat der einzelne Bürger? In der Praxis werden recht häufig zweistufige Abstimmungsverfahren benutzt, d.h. die breite Bevölkerungsmasse bestimmt in einer ersten Stufe zunächst Repräsentaten. Dies geschieht in der Regel in grösseren Zeitabständen. Das regelmässige Tagesgeschäft wird dann von den Repräsentanten in der zweiten Stufe entschieden. Den Einfluß den der einzelne Bürger auf die Wahl seines Repräsentanten hat, wird gewöhnlich mit Hilfe der Wahrscheinlichkeit, der Medianwähler zu sein, gemessen. In der zweiten Stufe werden oft Gewichte für die einzelnen Repräsentanten verwendet, so dass der Einfluss eines Repräsentanten als Wahrscheinlichkeit der gewichtete Median der zweiten Stufe zu sein, gemessen werden kann. Das Verständnis von Zusammenhängen, die diese Einflüsse, sowohl die direkten innerhalb einer Stufe, als auch die indirekten über beide Stufen hinweg, beeinflussen, ist z.B. wichtig für das Design von fairen Abstimmungsverfahren.
  Bearbeitungszeitraum: 01.05.2012–31.07.2012 (16.04.2012-16.07.2012) (01.05.2012-31.07.2012)
• Jonas Hoffmeister (Bachelorarbeit): Das inverse Machtindexproblem für den Nucleolus Wenn ein neues Land der Europäischen Union oder einem anderen Verbund beitritt, kommt es häufig zu politischen Diskussionen über die Verteilung der Stimmgewichte. Über den Zusammenhang zwischen Bevölkerungsgröße und einem angemessenen Machtanteil ist man sich mehr oder weniger einig und sieht eine Machtzuteilung, die proportional zur Quadratwurzel der Bevölkerung ist, als "fair" an. Aber dass Macht nicht proportional zum Stimmgewicht ist, sieht man an folgendem kleinen Beispiel. Wir betrachten drei Länder A, B und C mit Stimmgewichten 6, 3 und 2. Obwohl Land B immerhin noch die Hälfte der Stimmen von Land A hat, haben bei einer 50%-Mehrheitsregelung die Länder B und C keinerlei Macht. Land A kann alle Entscheidungen alleine treffen. Für verwickeltere Situationen gibt es mehrere sogenannte Machtindizes, mit denen man eine reelle Zahl als Maß für die Macht eines Landes ausrechnen kann. Hat man sich einmal auf einen geeigneten Machtindex geeinigt, so kann man die offensichtliche Frage nach einer gerechten Verteilung der Stimmgewichte als mathematisches Optimierungsproblem formulieren. Im Rahmen dieser Bachelorarbeit soll der Stand der Dinge des inversen Machtindexproblems für den Penrose-Banzhafindex (PBI) beschrieben und für den Nucleolus als weiteres, robusteres, Machtmass übertragen werden.
  Bearbeitungszeitraum: 06.04.2012–16.07.2012 (16.04.2012-16.07.2012)
• Maria Juraschik (Bachelorarbeit): Dispositionsoptimierung bei einem Internetbuchhändler Ein Online-Händler verkauft einen großen Artikelkatalog in mehreren Online Shops. Das Lagern der Artikel und Versenden der Bestellungen wird von verschiedenen Fullfillment Dienstleistern durchgeführt. Bei der Zuordnung von Bestllungen zu den einzelnen Dienstleistern sind einige Restriktionen zu beachten. Nicht jeder Artikel wird von jedem Dienstleister angeboten bzw. ist nicht aktuell verfügbar; wobei die Verfügbarkeitsinformationen von unterschiedlicher Güte sind. Für bestimmte Artikel gibt es Rabattverträge, die an monatliche Mindestabnahmemengen gekoppelt sind. Wie kann man unter diesen Nebenbedingungen bzw. Unsicherheiten eine erlösmaximale Aufteilung von Bestellungen auf die verschiedenen Dienstleister bestimmen?
  Bearbeitungszeitraum: 01.04.2012–30.06.2012
• Marcus Hassa (Diplomarbeit): Symmetrische ganzzahlige lineare Programme mit Anwendungen in der Kodierungstheorie Bei vielen kombinatorischen motivierten Modellierungen in der Sprache der ganzzahlig-linearen Programmierung gibt es vielfältige Symmetrien in der Formulierung. Das heißt, dass es zu jeder zulässigen Lösung eine ganze Menge an äquivalenten zulässigen Lösungen mit demselben Zielfunktionswert gibt. Diese Eigenschaft ist für die Standard-ILP-Löser wie beispielsweise CPLEX oder Gurobi sehr schlecht, weil sie immer wieder dieselben Schranken berechnen.
  Der optimale Ausweg wäre sich die Symmetrie beim Branch-and-Bound-Baum zu Nutze zu machen. Zu eben diesem Thema gibt es ein paar Arbeiten, die im Rahmen dieser Diplomarbeit anhand zweier spezifischer Anwendungsprobleme aus der Kodierungstheorie beschrieben und implementiert werden sollen.
  Bearbeitungszeitraum: 01.01.2012–30.06.2012
• Madeline Lips (Diplomarbeit): Windenergieprognosen -- Potenzial stochastischer Optimierung. An der European Energy Exchange (EEX) Energiebörse mit Sitz in Leipzig werden tagtäglich Preise für Energie ausgehandelt. Durch das Erneuerbare-Energien-Gesetz besitzen Windkraft und andere erneuerbare Energien gegenüber fossilen Brennstoffen und Kernkraft eine Vorrangstellung. In Folge dessen hängt der Strompreis an der EEX sehr stark von der aktuellen Leistung von Kraftwerken erneuerbarer Energien wie Windkraftwerken ab. Eine möglichst genaue Prognose der zukünftig produzierten Leistung ist somit u.a. für Stromnetzbetreiber essentiell. Hat man mehrere Prognosen zur Verfügung, so stellt sich die Frage, wie man aufgrund dessen optimal (z.B. über Ankaufs- und Verkaufsmengen) entscheiden soll. Eine Möglichkeit ist es, die Prognosen zu einer einzigen (z.B. als gewichtete Summe) Prognose zusammenzufassen und anschließend optimal zu entscheiden. Anhand historischer Daten kann man versuchen die vorhandenen Freiheitsgrade möglichst effektiv zu nutzen. Ein anderer Ansatz mit dieser mehrdeutigen Information umzugehen, ist die unsichere Information in die Optimierung mit einzubeziehen anstatt sie vorab zu eliminieren -- sogennante stochastische Optimierung. Bearbeitungszeitraum: 16.05.2011–12.12.2011
• Bianca Lindner (Diplomarbeit): Optimalsteuerung von Meinungsbildungsdynamiken. Viele Prozesse unserer Welt unterliegen einer Meinungsdynamik. Dies bedeutet, dass jedes einzelne Individuum eine Meinung zu einem gegebenen Thema hat, sich diese aber durch Kommunikation mit anderen Individuen im Laufe der Zeit ändert. Ein theoretisches Modell Meinungsbildungsdynamiken zu beschreiben ist das sogennannte Bounded Confidence-Modell. Hierbei wird die eigene Meinung nur von anderen Meinungen beeinflusst, die nicht zu stark hiervon abweichen. Anhand dieses Modells lassen sich schon ein paar Phänomene von Meinungsbildungsdynamiken analysieren. Richtig spannend wird es allerdings, wenn man versucht die Meinungsbildungsdynamik zu beeinflussen.
  Bearbeitungszeitraum: 08.04.2011–07.10.2011
• Maria Gundermann (Diplomarbeit): Das Inverse Machtindexproblem. Tritt neues Land der Europäischen Union oder einem anderen Verbund bei, so kommt es häufig zu politischen Diskussionen über die Verteilung der Stimmgewichte. Allgemein anerkannt ist, dass bevölkerungsreiche Länder mehr Macht haben sollen als bevölkerungsarme Länder. Auch über den Zusammenhang zwischen Bevölkerungsgröße und einem angemessenen Machtanteil ist man sich mehr oder weniger einig und sieht eine Machtzuteilung, die proportional zur Quadratwurzel der Bevölkerung ist, als fair an.
  Um Machtanteile zu messen gibt es mehrere sogenannte Machtindizes. Hat man sich einmal auf einen geeigneten Machtindex geeinigt, so kann man die offensichtliche Frage nach einer gerechten Verteilung der Stimmgewichte als mathematisches Optimierungsproblem formulieren. Es gilt, die Abweichung zwischen dem sich aus der Bevölkerungsanzahl ergebenden, gerechten Machtanteil und der sich aus den Stimmgewichten ergebenden, tatsächlichen Macht zu minimieren.
  Im Rahmen dieser Diplomarbeit sollen fortgeschrittene Methoden der Ganzzahligen Linearen Optimierung auf eine ILP-Formulierung des Problems angewendet werden, mit dem Ziel beispielhaft eine faire (inkl. Gütegarantien) Stimmgewichtsverteilung der EU27 zu berechnen bzw. die aktuellen Rechengrenzen weiter zu verschieben. Bearbeitungszeitraum: 01.02.2011–31.07.2011
• Andreea Giurgiu (Diplomarbeit): Effizientes Lernen monotoner boolscher Funktionen. In komplexen Systemen (mit Ressourcenbeschränkungen) und vielen Einzelkomponenten kann es zu Fehlern kommen, wenn bestimmte Kombinationen von Einzelkomponenten gleichzeit aktiv sind. Als anschauliches Beispiel kann man sich einen Computer vorstellen, auf dem unterschiedliche Programme ausgeführt werden können, beispielsweise ein Textverarbeitsprogramm, ein Internetbrowser, ein Tabellenkalkulationsprogramm und ein Graphikprogramm. Nehmen wir einmal an, dass der Computer abstürzt, wenn alle vier Programme gleichzeitig ausgeführt werden, so sind wir daran interessiert herauszufinden, bei welchen Kombinationen der Computer abstürzt und bei welchen er stabil weiter läuft.
  Bei N verschiedenen Programmen gibt es theoretisch 2^N Kombinationen, in denen der Computer entweder abstürzen oder stabil weiter laufen kann. Es ist aber nicht unrealistisch eine gewisse Monotonie anzunehmen: Läuft der Computer bei gleichzeitiger Ausführung der Textverarbeitung und der Tabellenkalkulation weiter, so ist davon auszugehen, dass er auch bei alleiniger Ausführung eines der beiden Programme stabil weiter läuft. Führen dagegen bereits die Programme Textverarbeitung, Tabellenkalkulation und der Internetbrowser zu einem Absturz, so wird das System auch bei gleichzeitiger Verwendung aller vier Programm abstürzen. Mathematisch lässt sich das Fehlerverhalten eines solchen Systems als monotone boolsche Funktion beschreiben.
  Ziel ist es, die monotone boolsche Funktion eines Systems durch Auswertungen an Stützpunkten vollständig zu bestimmen. Hier kann man sich vorstellen, dass man beispielsweise ein Experiment durchführt (die Programme in der gewählten Kombination auf dem Rechner laufen lassen und beobachten, was passiert) oder Experten befragt. Da eine solche Auswertung in der Regel teuer ist, soll die Anzahl der notwendigen Auswertungen minimiert werden. Bearbeitungszeitraum: 01.01.2011–30.06.2011
• Peter Hoffmann (Diplomarbeit): Approximationsalgorithmen für das Lottyp-Designproblem Viele praktisch bedeutsame Optimierungsprobleme sind NP-schwer. Dies bedeutet für die Praxis, dass es, zumindest falls P!=NP gilt, keine Lösungsalgorithmen mit polynomialer Laufzeit in der Eingabegröße für sie geben kann. Ein pragmatischer Ausweg sind sogenannte Approximationsalgorithmen.
  Eine Klasse von Optimierungsproblemen sind die sogenannten Facility Location- und K-Median-Probleme, welche bei einem aktuellen Industrieprojekt des Lehrstuhls in der Praxis auftreten. Konkret geht es um einen Textildiscounter mit über tausend Filialen in Deutschland und Österreich. Um die Logistikkosten gering zu halten, finden Einmalbelieferungen der Filialen in Lotpaketen statt. Jede Filiale bekommt ggf. mehrere Pakete eines Lottyps geliefert. Um Komplexität in der Logistik zu vermeiden, ist die Anzahl der insgesamt verwendeten Lottypen bei einer Artikellieferung durch eine kleine Zahl, wie z.B. 4 beschränkt.
  Bei gegebenen größen- und filialgenauen Bedarfen stellt sich nun die Frage, wie man mithilfe von Lotpaketen den Bedarf bestmöglich approximiert. Da dieses Optimierungsproblem im Allgemeinen NP-schwer ist, müssen hier Heuristiken und Approximationsalgorithmen in Anschlag gebracht werden.
  Bearbeitungszeitraum: 01.03.2010–31.10.2010
• Stefan Baier (Zulassungsarbeit): Kombinatorik, Wahrscheinlichkeitsrechnung und Spieltheorie in der gymnasialen Mittelstufe anhand von Poker. Das Kartenspiel Poker erfreut sich seit einiger Zeit einer immer stärkeren Beliebtheit. Mittlerweile gibt es eine Reihe von Leuten, die von Siegprämien bei Pokertunieren leben können. Offensichtlich kann man Poker mehr oder weniger geschickt spielen. Dass Poker trotz Glücks- und Zufallskomponenten ein sehr strategisches Spiel ist, kann man u.a. daran sehen, wie viele Schachspieler sich mittlerweile, und sei es auch nur nebenbei, mit Poker beschäftigen. Der Schachgroß meister Matthias Wahls betreibt beispielsweise die Internetseite www.pokerstrategy.de.
  Abgabe: 01.04.2010
• Katrin Dietrich (Zulassungsarbeit): Strukturisomere der Alkane. Chemische Verbindungen, welche die gleiche Summenformel aber unterschiedliche Verknüpfungen besitzen, werden Strukturisomere genannt. Eine Andersartigkeit in der Anordnung bzw. Verknüpfung führt teilweise zu abweichenden chemischen, physikalischen oder biologischen Eigenschaften. Ein Beispiel für eine Klasse chemischer Verbindungen sind die sogenannten Alkane (früher Paraffine). Dies sind gesättigte Kohlenwasserstoffe mit Summenformel C_nH_2n+2.
  In vielen Chemiebüchern findet man Tabellen über die Anzahl der Strukturisomere von Alkanen aus n C-Atomen, siehe ggf. diese ausführliche Tabelle für bis zu 100 C-Atomen. Wie man auf diese Zahlen kommt wird dagegen nicht erwähnt.
  Da die Verbindung der C-Atome bei Alkanen eine Baumstruktur besitzt, ist es hier noch relativ einfach die Anzahl der Strukturisomere zu berechnen bzw. die Strukturisomere computergeneriert zu erzeugen. Im Rahmen dieser Zulassungsarbeit sollten die notwendigen mathematischen und algorithmischen Grundlagen dargestellt werden.
  Bearbeitungszeitraum: 22.06.2009–29.09.2009
• Matthias Lippert (Diplomarbeit): Approximationsalgorithmen für Facility Location und K-Median. Viele praktisch bedeutsame Optimierungsprobleme sind NP-schwer. Dies bedeutet für die Praxis, dass es, zumindest falls P!=NP gilt, keine Lösungsalgorithmen mit polynomialer Laufzeit in der Eingabegröße für sie geben kann. Ein pragmatischer Ausweg sind sogenannte Approximationsalgorithmen.
  Eine Klasse von Optimierungsproblemen sind die sogenannten Facility Location- und K-Median-Probleme, welche bei einem aktuellen Industrieprojekt des Lehrstuhls in der Praxis auftreten. Konkret geht es um einen Textildiscounter mit über tausend Filialen in Deutschland und Österreich. Um die Logistikkosten gering zu halten, finden Einmalbelieferungen der Filialen in Lotpaketen statt. Jede Filiale bekommt ggf. mehrere Pakete eines Lottyps geliefert. Um Komplexität in der Logistik zu vermeiden, ist die Anzahl der insgesamt verwendeten Lottypen bei einer Artikellieferung durch eine kleine Zahl, wie z.B. 4 beschränkt.
  Bei gegebenen größen- und filialgenauen Bedarfen stellt sich nun die Frage, wie man mithilfe von Lotpaketen den Bedarf bestmöglich approximiert. Da dieses Optimierungsproblem im Allgemeinen NP-schwer ist, müssen hier Heuristiken und Approximationsalgorithmen in Anschlag gebracht werden.
  Bearbeitungszeitraum: 01.02.2009–31.07.2009
• Achim Hildenbrandt (Diplomarbeit): Graphen mit Einheitsabständen. In der geometrischen Graphentheorie beschäftigt man sich mit Einbettungen von Graphen in die euklidische Ebene mit vorgegebenen Kantenlängen. Ein Spezialfall hiervon ist, dass alle Kanten Länge 1 besitzen. Anschulich können diese Graphen auch mit Streichhölzern gelegt werden. Im Rahmen dieser Diplomarbeit sollen z.B. Methoden entwickelt werden, mit denen man in vielen Fällen algorithmisch schnell zeigen kann, dass es für einen gegebenen Graphen keine Einbettung in die euklidische Ebene mit Einheitsabständen geben kann. Eine recht spezielle Frage ist, ob der sogennante Harborth-Graph der kleinste vierreguläre planare Graph mit Einheitskanten ist.
  Bearbeitungszeitraum: 01.01.2009–31.07.2009
• Nikolas Tautenhahn (Diplomarbeit): Enumeration einfacher Spiele mit Anwendungen in der Stimmgewichtsverteilung, Mit Hilfe von sogenannten einfachen Spielen kann man Machtverhältnisse bei Abstimmungen mit Stimmgewichten beschreiben. Dass Macht nicht proportional zum Stimmgewicht ist, sieht man an folgendem kleinen Beispiel. Wir betrachten drei Länder A, B und C mit Stimmgewichten 6, 3 und 2. Obwohl Land B immerhin noch die Hälfte der Stimmen von Land A hat, haben bei einer 50%-Mehrheitsregelung die Länder B und C keinerlei Macht. Land A kann alle Entscheidungen alleine treffen. Die zugrunde liegende diskrete Struktur sind sogenannte Antiketten bzw. monotone boolsche Funktionen.
  Aufgabe dieser Diplomarbeit ist es Verfahren weiter zu entwickeln, um einfache Spiele bis auf Isomorphie vollständig zu enumerieren.
  Bearbeitungszeitraum: 01.04.2008–30.09.2008
• Anton Lastei (Diplomarbeit): Machtindizes - Optimierung von Stimmgewichten, Wenn ein neues Land der Europäischen Union oder einem anderen Verbund beitritt, kommt es häufig zu politischen Diskussionen über die Verteilung der Stimmgewichte. Sind die Stimmgewichte gegeben, so kann man den Machtanteil der einzelnen Länder über sogenannte Machtindizes ausrechnen. In der politikwissenschaftlichen Literatur lassen sich Analysen finden, wieviel Macht man einem Land in Abhängigkeit seiner Bevölkerungsgröße geben sollte, so dass kein Bewohner eines Landes übervorteilt wird. Diese Optimalverteilung gilt es mit ganzzahligen Stimmgewichten zu approximieren.
  Aufgabe dieser Diplomarbeit ist es Verfahren zu entwickeln un zu implementieren, mit denen man dieses Optimierungsproblem in angemessener Zeit optimal oder inklusive einer Gütegarantie lösen kann.
  Bearbeitungszeitraum: 01.04.2008–30.09.2008
• Shan Shan Hou (Bachelorarbeit): "Lotgrößenoptimierung bei einem Textildiscounter"
  In einem Projekt zum Revenue-Management im Saisonwareneinzelhandel wurden Techniken entwickelt für die fast 1 200 Filialen des Textildiscounters NKD Vetriebs GmbH größen- und filialgenauen Nachfragebedarf anhand historicher Daten zu schätzen. Die Belieferung der Filialen geschieht in Lots mit den Restriktionen, dass es insgesamt nur wenig verschiedene Lottypen geben darf, und dass eine einzelne Filiale sehr wenig verschiedene Lottypen bei einer Belieferung erhalten darf. Im Rahmen dieser Bachelorarbeit sollen exakte und heuristische Verfahren für die folgenden zwei Probleme untersucht und implementiert werden:
  (1) Optimale Bestellpolitik von Lots bei gegebener Gesamtmenge und Bedarfsschätzung für die Filialen.
  (2) Optimale Verteilpolitik von Lots bei gegebenen Lots und gegebener Nachfrageschätzung für die Filialen.
  Bearbeitungszeitraum: 05.06.2007–04.08.2007
• Manuela Mosburger (Zulassungsarbeit): "Spieltheorie - Eine anschauliche Einführung mit anwendungsbezogenen Beispielen aus Ökonomie und Alltag"
  Die Methoden der Spieltheorie können bei vielen praktischen Problemen auftreten. Sie gibt Antworten auf Frgane wie, "Warum ist es bei der Verkehrsplanung nicht immer besser, zusätzliche Straßen zu bauen?" oder "Warum nähern sich die großen politischen Parteien mit ihren Konzepten so stark an?". Im Rahmen einer Zulassungsarbeit soll anhand einer zu entwickelnden anschaulichen Einführung in die Spieltheorie aufgezeigt werden, dass dieses Thema auch für den Schulunterricht geeignet ist. Folgerungen aus der Anschaung heraus sollen das sonst häufig vertretene Satz-Beweis-Prinzip ersetzen. Abgerundet wird die Arbeit durch Darstellungen von Problemen aus der Praxis.
  Bearbeitungszeitraum: ?–Oktober 2006

Siehe auch die komplette Liste des Lehrstuhls für Wirtschaftsmathematik

© 2005 Lehrstuhl Wirtschaftsmathematik — Imprint
Webmaster
Letztes Update am: 1.10.2012