Publicité R▼
⇨ voir la définition de Wikipedia
Publicité ▼
Wikipedia
Monte-Carlo-Algorithmen sind randomisierte Algorithmen, die mit einer nach oben beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern dürfen. Dafür sind sie im Vergleich zu deterministischen Algorithmen häufig effizienter. Ihr Nachteil besteht darin, dass das berechnete Ergebnis falsch sein kann. Durch Wiederholen des Algorithmus mit unabhängigen Zufallsbits kann jedoch die Fehlerwahrscheinlichkeit gesenkt werden (Probability Amplification, weitere Einzelheiten im Artikel Randomisierter Algorithmus). Im Gegensatz zu Monte-Carlo-Algorithmen dürfen Las-Vegas-Algorithmen nur korrekte Lösungen berechnen.
Inhaltsverzeichnis |
Monte-Carlo-Algorithmen gibt es für Suchprobleme (Probleme, bei denen eine Lösung zu berechnen ist) und Entscheidungsprobleme (Probleme, bei denen eine Ja/Nein-Frage zu beantworten ist). Bei Monte-Carlo-Algorithmen für Entscheidungsprobleme unterscheidet man ein- und zweiseitigen Fehler. Bei zweiseitigem Fehler darf ein Monte-Carlo-Algorithmus sowohl false Positives liefern (also die Ausgabe Ja, obwohl Nein richtig wäre), als auch false Negatives (also die Ausgabe Nein, obwohl Ja richtig wäre). Bei einseitigem Fehler ist nur eine der beiden Fehlermöglichkeiten erlaubt. Eine häufige Vereinbarung besteht darin, von einseitigem Fehler zu sprechen und damit false Negatives zu meinen. Diese Konzepte werden im folgenden Abschnitt verdeutlicht, wo Komplexitätsklassen für Probleme mit Monte-Carlo-Algorithmen definiert werden.
Die angegebenen Schranken für die Wahrscheinlichkeiten müssen jeweils für alle Eingaben gelten; die Wahrscheinlichkeiten beziehen sich jeweils nur auf die vom Algorithmus verwendeten Zufallsbits (und nicht auf die Eingabe, die Eingabe wird also nicht als zufällig aufgefasst). Mit Hilfe von Probability Amplification kann man zeigen, dass die Konstante 2/3 aus der Definition von BPP durch jede andere Konstante aus dem Intervall (1/2,1) ersetzt werden kann, ohne die Menge BPP zu ändern; ebenso kann in den Definitionen von RP und co-RP die Konstante 1/2 durch jede Konstante aus dem Intervall (0,1) ersetzt werden.
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.
Zur Verdeutlichung der Definition von RP: Wenn ein RP-Algorithmus die Ausgabe Ja liefert, wissen wir mit Sicherheit, dass die Ausgabe Ja korrekt ist (da die Definition sicherstellt, dass bei korrekter Ausgabe Nein dies auf jeden Fall auch ausgegeben wird). Wenn dagegen ein RP-Algorithmus die Ausgabe Nein liefert, wissen wir nichts über die korrekte Ausgabe (da nach der Definition die Ausgabe Nein möglich ist, wenn Ja oder Nein korrekt wäre).
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. Die Ausgabe des Tests lautet entweder „sicher zusammengesetzt“ oder „wahrscheinlich prim“. Die Wahrscheinlichkeit, dass eine zusammengesetzte Zahl als „wahrscheinlich prim“ klassifiziert wird, liegt pro Durchgang unter 25 % und kann durch mehrfache Ausführung weiter gesenkt werden. Der Miller-Rabin-Test liefert keine Aussage über die Faktoren einer zusammengesetzten Zahl, ist also kein Faktorisierungsverfahren.
Man wählt hierzu zufällige Punkte aus und überprüft, ob diese innerhalb des Einheitskreises liegen. Die sich ergebende Wahrscheinlichkeitsverteilung P(Im Kreis) stellt die Fläche eines Viertels des Einheitskreises dar. Pi kann nun mit folgender Formel berechnet werden:
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. Soll das Integral
einer Funktion berechnet werden, dann wählt man unabhängige im Intervall gleichverteilte Punkte und approximiert durch
Im allgemeineren Fall von höherdimensionalen Funktionen ist das Vorgehen ähnlich. Sei eine beliebige -dimensionale Menge und eine integrierbare Funktion. Um den Wert
näherungsweise zu berechnen, wählt man zufällig in der Menge gleichverteilte Punkte für . Dann approximiert
den Wert in Abhängigkeit von beliebig genau. Um wie oben vorgestellt Pi zu berechnen, muss man und als charakteristische Funktion des Einheitskreises wählen. Hier ist gerade die Fläche des Einheitskreises.
Heutige Supercomputer (HPC) basieren auf massivem Multiprocessing mit vielen tausend Einzelprozessoren, die parallel arbeiten. Diese Gegebenheiten lassen sich besonders gut mit solchen probabilistischen Lösungsverfahren ausnutzen.[1]
Contenu de sensagent
dictionnaire et traducteur pour sites web
Alexandria
Une fenêtre (pop-into) d'information (contenu principal de Sensagent) est invoquée un double-clic sur n'importe quel mot de votre page web. LA fenêtre fournit des explications et des traductions contextuelles, c'est-à-dire sans obliger votre visiteur à quitter votre page web !
Essayer ici, télécharger le code;
SensagentBox
Avec la boîte de recherches Sensagent, les visiteurs de votre site peuvent également accéder à une information de référence pertinente parmi plus de 5 millions de pages web indexées sur Sensagent.com. Vous pouvez Choisir la taille qui convient le mieux à votre site et adapter la charte graphique.
Solution commerce électronique
Augmenter le contenu de votre site
Ajouter de nouveaux contenus Add à votre site depuis Sensagent par XML.
Parcourir les produits et les annonces
Obtenir des informations en XML pour filtrer le meilleur contenu.
Indexer des images et définir des méta-données
Fixer la signification de chaque méta-donnée (multilingue).
Renseignements suite à un email de description de votre projet.
Jeux de lettres
Les jeux de lettre français sont :
○ Anagrammes
○ jokers, mots-croisés
○ Lettris
○ Boggle.
Lettris
Lettris est un jeu de lettres gravitationnelles proche de Tetris. Chaque lettre qui apparaît descend ; il faut placer les lettres de telle manière que des mots se forment (gauche, droit, haut et bas) et que de la place soit libérée.
boggle
Il s'agit en 3 minutes de trouver le plus grand nombre de mots possibles de trois lettres et plus dans une grille de 16 lettres. Il est aussi possible de jouer avec la grille de 25 cases. Les lettres doivent être adjacentes et les mots les plus longs sont les meilleurs. Participer au concours et enregistrer votre nom dans la liste de meilleurs joueurs ! Jouer
Dictionnaire de la langue française
Principales Références
La plupart des définitions du français sont proposées par SenseGates et comportent un approfondissement avec Littré et plusieurs auteurs techniques spécialisés.
Le dictionnaire des synonymes est surtout dérivé du dictionnaire intégral (TID).
L'encyclopédie française bénéficie de la licence Wikipedia (GNU).
Copyright
Les jeux de lettres anagramme, mot-croisé, joker, Lettris et Boggle sont proposés par Memodata.
Le service web Alexandria est motorisé par Memodata pour faciliter les recherches sur Ebay.
La SensagentBox est offerte par sensAgent.
Traduction
Changer la langue cible pour obtenir des traductions.
Astuce: parcourir les champs sémantiques du dictionnaire analogique en plusieurs langues pour mieux apprendre avec sensagent.
calculé en 0,047s