Suchprobleme PDF

Zur Navigation springen Zur Suche springen Monte-Carlo-Algorithmen sind suchprobleme PDF Algorithmen, die mit einer nichttrivial nach oben beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern dürfen. Bei Monte-Carlo-Algorithmen für Entscheidungsprobleme unterscheidet man zwischen ein- und zweiseitigen Fehlern. Wenn die korrekte Ausgabe Nein lautet, beträgt die Wahrscheinlichkeit, dass der Algorithmus Nein ausgibt, 1. Obwohl BPP und RP Mengen von Problemen sind, werden im allgemeinen Sprachgebrauch häufig Begriffe wie BPP-Algorithmen oder RP-Algorithmen benutzt, um Algorithmen mit den oben definierten Eigenschaften zu bezeichnen.


Författare: Rudolf Ahlswede.

In den vergangenen drei Jahrzehnten findet man sowohl in theo­ retisch ausgerichteten als auch in anwendungsorientierten Zeit­ schriften in zunehmendem Maße Beiträge zum Thema "Suchen". Dabei ist auffallend, daß sehr verschiedenartige Probleme als Suchpro­ bleme klassifiziert werden und daß Forscher der verschiedenen Fach­ richtungen häufig sehr wenig über Ergebnisse, die in ihnen nicht vertrauten Gebieten erzielt wurden, informiert sind. Mit diesem Buch wird ein Versuch unternommen, das umfangreiche Material so darzustellen, daß dem Leser ein schneller Einstieg in den Fragenkreis und ein möglichst umfassender Uberblick ermöglicht wird. Es war unser Ziel, die wesentlichen Arbeiten auf dem Gebiet nach neuestem Stand zu behandeln, aber wir erheben keinen Anspruch auf Vollständigkeit in irgendeinem Sinne, da schon der Rahmen dieses Buches einem solchen Verlangen nicht gerecht werden kann. Bei einigen Arbeiten, die es an sich verdient hätten, ausführlich dargestellt zu werden, haben wir uns deshalb auf die Angabe ihrer Ergebnisse beschränkt. Der interessierte Forscher wird so in den Stand versetzt, sich seinen Weg durch die Literatur selbst zu bahnen. Das Buch dürfte für den Experten als Nachschlagewerk nütz­ lich sein. Aber unser Hauptanliegen ist es, jedem Leser mit der Bereit­ schaft und der Fähigkeit zu abstraktem, formalen Denken einen Zu­ gang zu den grundlegenden Ideen, Methoden und Resultaten des Ge­ bietes zu ermöglichen, die noch nicht in Büchern erschienen sind, aber von ihrer Bedeutung her eine weitere Verbreitung verdienen.

Ein Beispiel für einen Monte-Carlo-Algorithmus ist der Miller-Rabin-Test, bei dem probabilistisch bestimmt wird, ob eine natürliche Zahl prim ist oder nicht. Numerische Integration mit Monte Carlo: Die Stützstellen werden zufällig gleichverteilt auf dem Integrationsintervall gewählt. Neue Stützstellen sind dunkelblau, die alten hellblau eingezeichnet. Der Wert des Integrals nähert sich 3,32 an. Das obige Beispiel zur Bestimmung von Pi bildet praktisch das Flächenintegral einer Viertelkreisfläche. Entsprechend kann man das Flächenintegral allgemeiner, auch höherdimensionaler Funktionen nach dieser Methode berechnen.

Im allgemeineren Fall von höherdimensionalen Funktionen ist das Vorgehen ähnlich. Multiprocessing mit vielen tausend Einzelprozessoren, die parallel arbeiten. Diese Gegebenheiten lassen sich besonders gut mit solchen probabilistischen Lösungsverfahren ausnutzen. Cambridge University Press, Cambridge 1995, ISBN 0-521-47465-5. Thomas Müller-Gronbach, Erich Novak, Klaus Ritter: Monte Carlo-Algorithmen.

18: So lassen sich probabilistische Lösungsverfahren zumeist weitaus besser parallelisieren als die heute üblichen deterministischen. Diese Seite wurde zuletzt am 12. November 2018 um 19:52 Uhr bearbeitet. Regelfall durch Anklicken dieser abgerufen werden.