Es ist mehrfach festgestellt worden, dass schnellere Rechner nur einen geringen Einfluss auf die Aufwandsordnung haben, d.h. sie leisten nur einen begrenzten Beitrag zur schnelleren/effizienteren Verarbeitung eines Verfahrens. Die einzige Lösung besteht in dem Suchen und Finden immer besserer und schnellerer Algorithmen zur Lösung konkreter Probleme.
Eine Kategorie von immer besseren Berechnungsverfahren sind die Probabilistischen Algorithmen. Diese Algorithmen verwenden Zufallsbits um ihren Ablauf zu steuern, was soviel bedeutet, dass sie im Laufe der Berechnung, also während der Laufzeit des Algorithmuses, Zufallszahlen benutzen.
Diese Algorithmen haben mehrere Vorteile gegenüber ihren deterministischen Vettern. Sie sind in den meisten Fällen
- schneller (bezüglich Laufzeit); - benötigen weniger Speicher; - sind einfacher zu verstehen und damit ...; - ... einfacher zu implementieren als die schnellsten deterministischen Algorithmen für das selbe Problem.
Der Nachteil pobabilistischer Algorithmen ist, dass sie zufällig auch worst-case-Entscheidungen treffen können. Ebenfalls nachteilig ist die Tatsache, dass diese Algorithmen falsche Aussagen produzieren (Monte Carlo-Algorithmen) können oder erst gar nicht terminieren, weil eine ungünstige Zufallszahlenauswahl so getroffen wurde, dass die Berechnung in eine Sackgasse führt (Las Vegas-Algorithmus).
Inhaltsverzeichnis
- Einführung
- (Pseudo-) Zufallszahlen und Zufallszahlengeneratoren
- Numerische Probabilistische Algorithmen
- Las Vegas-Algorithmen
- Monte-Carlo-Algorithmen
- Äquivalenz zweier Multimengen
- Analyse des Problems
- Implementierung.
- Primzahltest nach Fermat .
- Analyse des Problems
- Implementierung.
- Primzahltest von Solovay und Strassen.
- Analyse des Problems.
- Implementierung.
- Äquivalenz zweier Multimengen
Zielsetzung und Themenschwerpunkte
Der Text beleuchtet die Bedeutung probabilistischer Algorithmen in der Informatik und deren Vorteile gegenüber deterministischen Algorithmen. Er zeigt auf, dass probabilistische Algorithmen in vielen Bereichen, wie der algorithmischen Zahlentheorie und der Kryptographie, von entscheidender Bedeutung sind.
- Vorteile probabilistischer Algorithmen
- Zufallszahlengeneratoren und Pseudozufallszahlen
- Anwendung von probabilistischen Algorithmen in verschiedenen Bereichen
- Analyse von Algorithmen
- Implementierung probabilistischer Algorithmen
Zusammenfassung der Kapitel
Einführung
Dieses Kapitel führt in das Thema der probabilistischen Algorithmen ein und beleuchtet deren Vorteile gegenüber deterministischen Algorithmen. Es werden die wichtigsten Anwendungsgebiete und die grundlegenden Konzepte erläutert.
(Pseudo-) Zufallszahlen und Zufallszahlengeneratoren
Das Kapitel behandelt die Erzeugung von Zufallszahlen, die für die Ausführung probabilistischer Algorithmen benötigt werden. Es werden verschiedene Methoden zur Generierung von Pseudozufallszahlen vorgestellt, darunter die Kongruenzmethode.
Numerische Probabilistische Algorithmen
Dieses Kapitel beschäftigt sich mit numerischen probabilistischen Algorithmen, die für die Lösung von Problemen in der numerischen Mathematik eingesetzt werden. Es werden verschiedene Algorithmen und deren Eigenschaften vorgestellt.
Las Vegas-Algorithmen
Das Kapitel behandelt Las Vegas-Algorithmen, die entweder die richtige Lösung liefern oder mit einer bestimmten Wahrscheinlichkeit scheitern. Es werden verschiedene Beispiele für Las Vegas-Algorithmen vorgestellt.
Monte-Carlo-Algorithmen
Dieses Kapitel befasst sich mit Monte-Carlo-Algorithmen, die eine Näherungslösung für ein Problem liefern. Es werden verschiedene Beispiele für Monte-Carlo-Algorithmen vorgestellt, darunter Algorithmen zur Überprüfung der Äquivalenz von Multimengen und Primzahltests.
Schlüsselwörter
Probabilistische Algorithmen, Zufallszahlengeneratoren, Pseudozufallszahlen, Las Vegas-Algorithmen, Monte-Carlo-Algorithmen, Primzahltests, Algorithmische Zahlentheorie, Kryptographie, Simulationen, Stichproben, Tests.
Häufig gestellte Fragen
Was sind probabilistische Algorithmen?
Das sind Algorithmen, die Zufallszahlen oder Zufallsbits verwenden, um ihren Ablauf zu steuern, anstatt rein deterministisch vorzugehen.
Welche Vorteile haben sie gegenüber deterministischen Algorithmen?
Sie sind oft schneller, benötigen weniger Speicherplatz und sind häufig einfacher zu verstehen und zu implementieren als vergleichbare deterministische Verfahren.
Was ist der Unterschied zwischen Las-Vegas- und Monte-Carlo-Algorithmen?
Las-Vegas-Algorithmen liefern immer das korrekte Ergebnis, aber ihre Laufzeit ist zufällig. Monte-Carlo-Algorithmen haben eine feste Laufzeit, können aber mit einer geringen Wahrscheinlichkeit ein falsches Ergebnis liefern.
Welche Nachteile können probabilistische Algorithmen haben?
Sie können theoretisch "Worst-Case"-Entscheidungen treffen, falsche Aussagen produzieren oder im Fall von Las-Vegas-Algorithmen in seltenen Fällen nicht terminieren.
Wo werden diese Algorithmen in der Praxis eingesetzt?
Häufige Einsatzgebiete sind die Kryptographie, die algorithmische Zahlentheorie (z.B. Primzahltests) und komplexe Simulationen.
Welche Primzahltests werden in der Arbeit behandelt?
Die Arbeit analysiert den Primzahltest nach Fermat sowie den Primzahltest von Solovay und Strassen.
- Citation du texte
- BSc Informatik Sebastian Rick (Auteur), Jörg Wiesner (Auteur), 2007, Probabilistische Algorithmen, Munich, GRIN Verlag, https://www.grin.com/document/118495
