Mathematik
Refine
Year of publication
Document Type
- diplomthesis (33) (remove)
Language
- German (33) (remove)
Has Fulltext
- yes (33)
Is part of the Bibliography
- no (33)
Keywords
- Stochastik (2)
- Stochastischer Prozess (2)
- Yule-Prozess (2)
- Algorithmus (1)
- Assignment Problem (1)
- Ausreißer <Statistik> (1)
- Bolthausen-Sznitman (1)
- Bootstrap-Statistik (1)
- CIR-1 (1)
- China-Restaurant-Prozess (1)
Institute
- Mathematik (33)
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.
In der vorliegenden Arbeit werden Aspekte autonomer und nichtautonomer dynamischer Systeme behandelt, wobei Attraktoren und verwandte Objekte eine wichtige Rolle spielen werden. Zunächst findet man in einem Kapitel über dynamische Systeme die Definition der grundlegenden Begriffe Attraktor, Repeller und Schiefproduktfluss, gefolgt von zwei hinreichenden Bedingungen für die Existenz von Attraktoren. Mit den Attraktoren und Repellern können dann im nächsten Kapitel Morsemengen eingeführt werden. Dadurch kann das Verhalten eines dynamischen Systems qualitativ beschrieben werden. Des weiteren wird auf die Bedeutung der Kettenrekurrenzmenge für die Morsemengen eingegangen. Im Kapitel über Kontrolltheorie wird, nach einer kurzen Einführung in dieses Gebiet, gezeigt, dass der dort definierte Lift einer Kettenkontrollmenge unter gewissen Voraussetzungen eine Morsemenge ist. Im letzten Kapitel geht es um Pullback-Attraktoren, die unter den angegebenen Bedingungen als Attraktoren für den Schiefproduktfluss interpretiert werden können.
Diese Arbeit beschäaftigt sich mit den Eigenschaften dynamischer Systeme, die in Form von autonomen Differentialgleichungen vorliegen. Genauer: Das Langzeitverhalten dieser dynamischen Systeme soll untersucht werden. Es läßtt sich beschreiben durch für das jeweilige System charakteristische Mengen, die attrahierenden Mengen und deren Einzugsbereiche. Attrahierende Mengen sind bezüglich eines dynamischen Systems invariante Mengen, die Trajektorien des dynamischen Systems, die in ihrer Umgebung starten, anziehen. Der Einzugsbereich einer attrahierenden Menge ist die Menge aller Punkte, die von der attrahierenden Menge angezogen werden. Betrachtet werden Systeme, die von einer Eingangsfunktion abhängen. Diese Eingangsfunktion kann je nach Zusammenhang eine Störung des dynamischen Systems oder eine Kontrolle desselben darstellen. Werden Störungen betrachtet, so sind Eigenschaften des dynamischen Systems, die für alle Eingangsfunktionen gelten, zu untersuchen. Diese werden in dieser Arbeit als starke Eigenschaften bezeichnet. Werden Kontrollen betrachtet, sind Eigenschaften des dynamischen Systems, die nur für mindestens eine Eingangsfunktion erfüllt sind, zu untersuchen. Sie werden hier als schwache Eigenschaften bezeichnet. Man betrachte beispielsweise einen Punkt, der zu einer invarianten Menge gehört. Zu jeder Eingangsfunktion gibt es eine zugehörige Trajektorie, die an diesem Punkt startet. Starke Invarianz bedeutet, daß keine dieser Trajektorien jemals die invariante Menge verläßt, schwache Invarianz, da mindestens eine dieser Trajektorien niemals die invariante Menge verläßt. Der Schwerpunkt dieser Arbeit liegt auf der Untersuchung der schwachen Einzugsbereiche. Sie lassen sich nur in Ausnahmefällen durch theoretische Überlegungen finden. Daher ist es von Nutzen, diese Mengen numerisch zu berechnen. Hier soll deshalb die benötigte Theorie bereitgestellt werden, um schwache Einzugsbereiche mit einem Unterteilungsalgorithmus anzunähern. Ein Unterteilungsalgorithmus dient allgemein dazu, innerhalb einer vorgegebenen Grundmenge eine Menge, die eine bestimmte Eigenschaft hat, zu finden. Die Idee eines solchen Algorithmus ist es einfach, die Grundmenge in "Zellen" zu unterteilen und für jede dieser Zellen zu prüfen, ob sie ganz, gar nicht oder teilweise zur gesuchten Menge gehört. Gehört eine Zelle nur teilweise zur gesuchten Menge, so wird sie weiter unterteilt und für die "Teilzellen" erneut entschieden, ob sie zur gesuchten Menge gehören. Für die Berechnung eines schwachen Einzugsbereiches bedeutet dies, daß für jede Zelle überprüft werden muß, ob es eine Kontrollfunktion gibt, mit deren Hilfe Trajektorien der betrachteten Differentialgleichung, die innerhalb der Zelle starten, in eine gegebene schwach attrahierende Menge (bzw. eine passend gewählte Umgebung dieser Menge) gesteuert werden können.
Das Assignment Problem ist ein bekanntes kombinatorisches Optimierungsproblem, bei dem es darum geht, in einem gewichteten bipartiten Graphen ein Matching mit minimalem Gewicht zu finden. In dieser Arbeit sind die Kantengewichte exponentialverteilt zu speziell gewählten Raten. Damit sind Erwartungswert und Varianz des minimalen Gewichts von besonderem Interesse. Zunächst wird ein Beweis der Parisi Formel und der Coppersmith-Sorkin Formel erläutert. Die Formeln beschreiben den Erwartungswert des minimalen Gewichts im Fall, dass die Raten alle dem Wert 1 entsprechen. Im zweiten Teil wird die Herleitung einer expliziten Formel zur Berechnung der Varianz des zufälligen minimalen Gewichts erklärt, wobei die Raten immer noch mit 1 übereinstimmen. Gleichzeitig wird eine Formel für die höheren Momente geliefert, aus der die Parisi Formel und Coppersmith-Sorkin Formel aus dem ersten Teil folgen und die sogar das bisherige Modell bezüglich der Parameter erweitert. Schließlich kann man das Ergebnis des zweiten Teils zur Beschreibung des asymptotischen Verhaltens der Varianz benutzen.
Der Begriff der editierfreundlichen Kryptographie wurde von Mihir Bellare, Oded Goldreich und Shafi Goldwasser 1994 bzw. 1995 eingeführt. Mit einem editierfreundlicher Verschlüsselungs- oder Unterschriftenverfahren kann man aus einer Verschlüsselung bzw. Unterschrift zu einer Nachricht schnell eine Verschlüsselung oder Unterschrift zu einer ähnlichen Nachricht erstellen. Wir geben eine Übersicht über die bekannten editierfreundlichen Verfahren und entwickeln sowohl ein symmetrisches als auch ein asymmetrisches editierfreundliches Unterschriftenverfahren (IncXMACC und IncHSig). Wir zeigen, wie man mit editierfreundlichen Schemata überprüfen kann, ob die Implementierung einer Datenstruktur korrekt arbeitet. Basierend auf den Ideen der editierfreundlichen Kryptographie entwickeln wir effiziente Verfahren für spezielle Datenstrukturen. Diese Ergebnisse sind in zwei Arbeiten [F97a, F97b] zusammengefaßt worden.
In der vorliegenden Diplomarbeit beschäftigen wir uns mit kryptographisch sicheren Pseudozufallsgeneratoren. Diese e±zienten Algorithmen erzeugen zu zufälliger Eingabe deterministisch eine längere Bitfolge, die praktisch von einer Folge zufälliger Münzwürfe nicht unterscheidbar ist. Wir geben die Definitionen von A. Yao sowie M. Blum und S. Micali, beweisen die Äquivalenz und charakterisieren den Unterschied zur klassischen Sichtweise von Zufallsgeneratoren. Mit der Blum-Micali-Konstruktion zeigen wir, wie man aus einer Oneway-Permutation und zugehörigem Hardcore-Prädikat einen kryptographisch sicheren Pseudozufallsgenerator konstruiert: Man wendet auf einen zufälligen Startwert iterativ die Oneway-Funktion an und gibt jeweils das Hardcore-Prädikat des Urbilds aus. Wir stellen das allgemeine Hardcore- Prädikat inneres Produkt modulo 2 von L.A. Levin und O. Goldreich vor und beweisen mit Hilfe des XOR-Lemmas von U.V. Vazirani und V.V. Vazirani die Verallgemeinerung zu einer Hardcore-Funktion, die statt eines Prädikats mehrere Bits ausgibt. Man geht davon aus, daß die Verschlüsselungsfunktionen des RSA- und des Rabin-Public- Key-Kryptosystems Oneway-Permutationen sind. Basierend auf dem Rabin-System haben L. Blum, M. Blum und M. Shub den x2-mod-N-Generator aufgebaut, W. Alexi, B. Chor, O. Goldreich und C.P. Schnorr haben den RSA-Generator konstruiert und den Sicherheitsbeweis zum x2-mod-N-Generator verbessert. Diese Generatoren basieren auf der Blum-Micali-Konstruktion mit dem Hardcore-Prädikat des untersten Bits. Durch neue Ideen können wir die beweisbare Sicherheit der Generatoren deutlich erhöhen, so daß in der Praxis kleinere Schlüssellängen genügen. Bisher war zum Beispiel für den x2-mod-N-Generator bekannt, daß man mit einem Algorithmus A, der das unterste Bit der Wurzel modulo einer n-Bit- Blumzahl mit Wahrscheinlichkeit 1 2 + ² in Zeit |A| = ¡n3¢ berechnet, den Modul in Zeit O¡n3² 9|A|¢ mit Wahrscheinlichkeit ²2 64 faktorisieren kann. Wir verbessern die Laufzeit zu O¡n² 4 log2(n² 1)|A|¢ und Wahrscheinlichkeit 1 9 . Diese neuen Resultate wurden auf der Eurocrypt-Konferenz im Mai 1997 in Konstanz vorgestellt, D.E. Knuth hat sie bereits in die neue Auflage seines Standardwerks The Art of Computer Programming aufgenommen.
Der Bolthausen-Sznitman Koaleszent ist ein zeitstetiger Markovprozess mit Werten in der Menge der Partitionen der natürlichen Zahlen. Der Prozess startet in Singletons und seine Dynamik erlaubt lediglich Übergänge in gröbere Partitionen. In dieser Arbeit wird der Bolthausen-Sznitman Koaleszent zum Zeitpunkt seines letzten Übergangs analysiert. Das Hauptresultat ist ein Grenzwertsatz, welcher eine gemeinsame Aussage sowohl über die Blockanzahl als auch über die Blockgrößen des Koaleszenten zu diesem Zeitpunkt macht. Dafür wird der Koaleszent durch ein gewisses Abholzverfahren zufälliger rekursiver Bäume modelliert, wobei diese Bäume wiederum anhand von Yule-Prozessen generiert werden.
Ein universeller zentraler Grenzwertsatz für den Abstand zweier Kugeln in zufälligen Splitbäumen
(2008)
In der vorliegenden Arbeit wird ein Modell des zufälligen Splitbaumes untersucht. Dies ist ein verallgemeinertes Modell, das bei passender Wahl der zugehörigenParameter viele konkrete Suchbäume umfasst. Das Modell ist in der Arbeit von L. Devroye beschrieben: Nach einem zufallsbasierten Algorithmus werden den Knoten des Baumes Daten in Form von Kugeln hinzugefügt. Tiefe und Höhe sind dabei grundlegende Größen, die die Komplexität von Suchoperationen beschreiben, wenn das Suchbaummodell als Datenstruktur verwendet wird. Das Augenmerk der Arbeit richtet sich auf eine weitere entscheidende Größe: Den Abstand zweier rein zufällig gewählter Kugeln im Baum. Aufbauend auf Devroyes Erkenntnissen zum asymptotischen Verhalten der Tiefe der zuletzt eingefügten Kugel im Splitbaum, wird ein neues Resultat erzielt: Ein universeller Zentraler Grenzwertsatz für den Abstand der Kugeln. Als Anwendungsbeispiel werden zwei vom allgemeinen Modell abgedeckte Suchbäume betrachtet und der jeweilige Grenzwertsatz für die Abstände aus dem universellen Satz abgeleitet.
Kieferorthopäden beschreiben die Anordnung der Zähne und die Stellung der Kiefer üblicherweise mittels Winkel und Strecken in der sagittalen Gesichtsebene. Im vorliegenden Fall werden fünf Winkel betrachtet und jedes Individuum lässt sich als Punkt in einem 5-dimensionalen Raum darstellen. Individuen, die laut Experten ein gut funktionierendes Gebiss und ein harmonisches Äußeres besitzen, formen eine Punktwolke, die im Folgenden als die Norm Population bezeichnet wird. Individuen fern von der Wolke benötigen kieferorthopädische Behandlung. Welche Form sollte dieser Eingriff annehmen? Durch Hilfsmittel der modernen Kieferorthopädie lassen sich die beschriebenen Winkel nahezu nach Belieben ändern. Dies ist natürlich verbunden mit einer unterschiedlichen Menge an Problemen, Arbeitsaufwand und Unannehmlichkeiten, abhängig vom individuellen Patienten. Diese Arbeit präsentiert eine Methode, die auf jedem Computer leicht implementierbar und auf k Variablen verallgemeinerbar ist. Sie ermöglicht Kieferorthopäden eine Visualisierung, wie verschiedene denkbare Anpassungen der Winkel eines Patienten dessen relative Position zur Norm Population verändern. Damit unterstützt sie Kieferorthopäden bei der Entscheidung für einen Behandlungsplan, der die besten Ergebnisse verspricht.