Refine
Document Type
- Part of a Book (2)
- diplomthesis (1)
Language
- German (3) (remove)
Has Fulltext
- yes (3) (remove)
Is part of the Bibliography
- no (3)
Keywords
- Algorithmus (3) (remove)
Institute
- Mathematik (1)
Der in seinen mannigfachen Referenzen nahezu opake Film "Contra-Internet: Jubilee 2033" von Zach Blas (2018) steht im Zentrum der Frage, welches Internet wir uns aus einer queer-theoretischen und queer-ästhetischen Perspektive vorstellen können. Was ist eine queere Vision des Internets? Wie lässt sich eine Zukunft des Internets prophezeien, die den von Technologieunternehmen herbeigeführten Nexus von Mystik und Mathematik hintertreibt? Am Beispiel der im Film verhandelten Symbole, Objekte und Materialien beschäftigt sich dieser Beitrag mit der queeren Ästhetik des Algorithmischen.
Im Rahmen dieser Arbeit wird der aktuelle Stand auf dem Gebiet des Lokalen Lovász Lemmas (LLL) beschrieben und ein Überblick über die Arbeiten zu konstruktiven Beweisen und Anwendungen gegeben. Ausgehend von Jószef Becks Arbeit zu einer algorithmischen Herangehensweise, haben sich in den letzten Jahren im Umfeld von Moser und Tardos und ihren Arbeiten zu einem konstruktiven Beweis des LLL eine erneute starke Beschäftigung mit dem Thema und eine Fülle von Verbesserungen entwickelt.
In Kapitel 1 wird als Motivation eine kurze Einführung in die probabilistische Methode gegeben. Mit der First- und Second Moment Method werden zwei einfache Vorgehensweisen vorgestellt, die die Grundidee dieses Beweisprinzips klar werden lassen. Von Paul Erdős eröffnet, beschreibt es Wege, Existenzbeweise in nicht-stochastischen Teilgebieten der Mathematik mithilfe stochastischer Überlegungen zu führen. Das Lokale Lemma als eine solche Überlegung entstammt dieser Idee.
In Kapitel 2 werden verschiedene Formen des LLL vorgestellt und bewiesen, außerdem wird anhand einiger Anwendungsbeispiele die Vorgehensweise bei der Verwendung des LLL veranschaulicht.
In Kapitel 3 werden algorithmische Herangehensweisen beschrieben, die geeignet sind, von der (mithilfe des LLL gezeigten) Existenz gewisser Objekte zur tatsächlichen Konstruktion derselben zu gelangen.
In Kapitel 4 wird anhand von Beispielen aus dem reichen Schatz neuerer Veröffentlichungen gezeigt, welche Bewegung nach der Arbeit von Moser und Tardos entstanden ist. Dabei beleuchtet die Arbeit nicht nur einen anwendungsorientierten Beitrag von Haeupler, Saha und Srinivasan, sondern auch einen Beitrag Terence Taos, der die Beweistechnik Mosers aus einem anderen Blickwinkel beleuchtet.