| dbo:abstract
|
- Algoritmus typu Monte Carlo je v teoretické informatice označení pro takový pravděpodobnostní algoritmus, který může s malou pravděpodobností vrátit špatný výsledek. Tím se na první pohled liší od algoritmů typu Las Vegas, které vždy na konci vrátí správný výsledek, ovšem s malou pravděpodobností mohou běžet velmi dlouho, než skončí. Na algoritmus typu Las Vegas lze algoritmus typu Monte Carlo do jisté míry převést, pokud máme způsob, jak určit, zda je výsledek správný. V takovém případě lze algoritmus Monte Carlo pouštět opakovaně, dokud nevrátí správný výsledek. Jméno Monte Carlo dal tomuto typu algoritmů v roce 1947 řecký fyzik , a to podle Monte Carla v Monaku, kde je slavné kasíno. Příkladem algoritmu typu Monte Carlo je Millerův–Rabinův test prvočíselnosti. (cs)
- Monte-Carlo-Algorithmen sind randomisierte Algorithmen, die mit einer nichttrivial nach oben beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern. Dafür sind sie im Vergleich zu deterministischen Algorithmen häufig effizienter. Durch Wiederholen des Algorithmus mit unabhängigen Zufallszahlen 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. Der Name Monte-Carlo hängt laut Nicholas Metropolis wie folgt mit der Methode zusammen: Stan Ulam hatte einen Onkel, der sich zum Spielen immer Geld von Verwandten geliehen hatte, denn „er musste nach Monte Carlo gehen“. Monte-Carlo-Algorithmen dienen als Basis für Monte-Carlo-Simulationen. (de)
- En algorithmique, un algorithme de Monte-Carlo est un algorithme randomisé dont le temps d'exécution est déterministe, mais dont le résultat peut être incorrect avec une certaine probabilité (généralement minime). Autrement dit un algorithme de Monte-Carlo est un algorithme qui utilise une source de hasard, dont le temps de calcul est connu dès le départ (pas de surprise sur la durée du calcul), cependant dont la sortie peut ne pas être la réponse au problème posé, mais c'est un cas très rare. L’intérêt de tels algorithmes est d'avoir une probabilité d'échec faible et d'être rapide. Deux autres types d'algorithmes probabilistes sont la famille des algorithmes de Las Vegas et la famille des algorithmes d'Atlantic City. Les algorithmes de Las Vegas prennent un temps d'exécution aléatoire, mais produisent toujours une réponse correcte. Les algorithmes d'Atlantic City donnent une réponse probablement correcte dans un temps d'exécution probablement rapide. Un algorithme de Monte-Carlo peut être transformé en un algorithme de Las Vegas quand il existe une procédure capable de vérifier la correction du résultat. En effet, il suffit d'exécuter l'algorithme de Monte-Carlo jusqu'à lui faire produire une réponse correcte. Accessoirement, le qualificatif Monte-Carlo fait référence à la Principauté de Monaco et à son célèbre casino appelé Casino de Monte-Carlo, haut lieu des jeux de hasard. (fr)
- In computing, a Monte Carlo algorithm is a randomized algorithm whose output may be incorrect with a certain (typically small) probability. Two examples of such algorithms are Karger–Stein algorithm and Monte Carlo algorithm for minimum Feedback arc set. The name refers to the grand casino in the Principality of Monaco at Monte Carlo, which is well-known around the world as an icon of gambling. The term "Monte Carlo" was first introduced in 1947 by Nicholas Metropolis. Las Vegas algorithms are a dual of Monte Carlo algorithms that never return an incorrect answer. However, they may make random choices as part of their work. As a result, the time taken might vary between runs, even with the same input. If there is a procedure for verifying whether the answer given by a Monte Carlo algorithm is correct, and the probability of a correct answer is bounded above zero, then with probability, one running the algorithm repeatedly while testing the answers will eventually give a correct answer. Whether this process is a Las Vegas algorithm depends on whether halting with probability one is considered to satisfy the definition. (en)
- ( 비슷한 이름의 몬테카를로 방법에 관해서는 해당 문서를 참조하십시오.) 컴퓨팅에서 몬테카를로 알고리즘은 항상 유한한 시간 안에 멈추지만, 특정 확률(주로 낮은 확률)로 부정확할 수도 있는 결과를 도출하는 무작위 알고리즘이다. 이러한 알고리즘의 두 가지 예로 과 에 대한 몬테카를로 알고리즘이 있다. 몬테카를로(Monte Carlo)라는 용어는 1947년 가 제안한 이름이다. 그의 동료였던 폴란드 출신 수학자 스타니스와프 울람에게는 삼촌이 있었는데, 그는 모나코의 유명한 도박의 도시 몬테카를로에서 도박을 하기 위해 친척들의 돈을 종종 빌려갔다. 몬테카를로 알고리즘 또한 무작위성이 있으므로 이로부터 이름이 유래된 것이 지금까지 이어져 내려왔다. 은 부정확할 수도 있는 결과를 절대 반환하지 않는 몬테카를로 알고리즘의 듀얼이다. 이 때문에 은 몬테카를로 알고리즘과 다르게 무작위 선택을 하지 않는다고 오해할 수 있다. 그러나 또한 시행의 일부로 무작위 선택을 할 수 있다. 그 결과, 동일한 입력을 사용하더라도 실행 간에 소요되는 시간이 다를 수 있다. 만약 몬테카를로 알고리즘에 의해 주어진 답이 정확한지 검증하는 절차가 있고 정답일 확률이 0보다 크다면, 답을 테스트하면서 알고리즘을 반복적으로 실행하는 프로세스가 결국 정답을 줄 사건은 거의 확실하게 발생한다. 이 프로세스가 인지는 의 정의에 프로세스가 중지되는 사건이 거의 확실하게 발생하는 프로세스를 포함시키는지 여부에 따라 다르다. (ko)
- Per algoritmo Monte Carlo si intende un algoritmo randomizzato il cui output può essere sbagliato in un certo numero - solitamente ridotto - di casi. Il nome deriva dal quartiere di Monaco noto per l'elevato numero di casinò ed è stato usato per la prima volta nel 1974 da Nicholas Metropolis. Un loro sottinsieme, detto , produce sempre un risultato corretto ma può impiegare un tempo variabile per la verifica del risultato. Esempi noti di tali algoritmi, solitamente di complessità ZPP, sono vari test di primalità come il , il , il e, nel campo della teoria computazionale dei gruppi, l'. (it)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 7128 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Per algoritmo Monte Carlo si intende un algoritmo randomizzato il cui output può essere sbagliato in un certo numero - solitamente ridotto - di casi. Il nome deriva dal quartiere di Monaco noto per l'elevato numero di casinò ed è stato usato per la prima volta nel 1974 da Nicholas Metropolis. Un loro sottinsieme, detto , produce sempre un risultato corretto ma può impiegare un tempo variabile per la verifica del risultato. Esempi noti di tali algoritmi, solitamente di complessità ZPP, sono vari test di primalità come il , il , il e, nel campo della teoria computazionale dei gruppi, l'. (it)
- Algoritmus typu Monte Carlo je v teoretické informatice označení pro takový pravděpodobnostní algoritmus, který může s malou pravděpodobností vrátit špatný výsledek. Tím se na první pohled liší od algoritmů typu Las Vegas, které vždy na konci vrátí správný výsledek, ovšem s malou pravděpodobností mohou běžet velmi dlouho, než skončí. Na algoritmus typu Las Vegas lze algoritmus typu Monte Carlo do jisté míry převést, pokud máme způsob, jak určit, zda je výsledek správný. V takovém případě lze algoritmus Monte Carlo pouštět opakovaně, dokud nevrátí správný výsledek. (cs)
- Monte-Carlo-Algorithmen sind randomisierte Algorithmen, die mit einer nichttrivial nach oben beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern. Dafür sind sie im Vergleich zu deterministischen Algorithmen häufig effizienter. Durch Wiederholen des Algorithmus mit unabhängigen Zufallszahlen 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. (de)
- In computing, a Monte Carlo algorithm is a randomized algorithm whose output may be incorrect with a certain (typically small) probability. Two examples of such algorithms are Karger–Stein algorithm and Monte Carlo algorithm for minimum Feedback arc set. The name refers to the grand casino in the Principality of Monaco at Monte Carlo, which is well-known around the world as an icon of gambling. The term "Monte Carlo" was first introduced in 1947 by Nicholas Metropolis. (en)
- En algorithmique, un algorithme de Monte-Carlo est un algorithme randomisé dont le temps d'exécution est déterministe, mais dont le résultat peut être incorrect avec une certaine probabilité (généralement minime). Autrement dit un algorithme de Monte-Carlo est un algorithme qui utilise une source de hasard, dont le temps de calcul est connu dès le départ (pas de surprise sur la durée du calcul), cependant dont la sortie peut ne pas être la réponse au problème posé, mais c'est un cas très rare. L’intérêt de tels algorithmes est d'avoir une probabilité d'échec faible et d'être rapide. (fr)
- ( 비슷한 이름의 몬테카를로 방법에 관해서는 해당 문서를 참조하십시오.) 컴퓨팅에서 몬테카를로 알고리즘은 항상 유한한 시간 안에 멈추지만, 특정 확률(주로 낮은 확률)로 부정확할 수도 있는 결과를 도출하는 무작위 알고리즘이다. 이러한 알고리즘의 두 가지 예로 과 에 대한 몬테카를로 알고리즘이 있다. 몬테카를로(Monte Carlo)라는 용어는 1947년 가 제안한 이름이다. 그의 동료였던 폴란드 출신 수학자 스타니스와프 울람에게는 삼촌이 있었는데, 그는 모나코의 유명한 도박의 도시 몬테카를로에서 도박을 하기 위해 친척들의 돈을 종종 빌려갔다. 몬테카를로 알고리즘 또한 무작위성이 있으므로 이로부터 이름이 유래된 것이 지금까지 이어져 내려왔다. 은 부정확할 수도 있는 결과를 절대 반환하지 않는 몬테카를로 알고리즘의 듀얼이다. 이 때문에 은 몬테카를로 알고리즘과 다르게 무작위 선택을 하지 않는다고 오해할 수 있다. 그러나 또한 시행의 일부로 무작위 선택을 할 수 있다. 그 결과, 동일한 입력을 사용하더라도 실행 간에 소요되는 시간이 다를 수 있다. (ko)
|
| rdfs:label
|
- Algoritmus typu Monte Carlo (cs)
- Monte-Carlo-Algorithmus (de)
- Algoritmo Monte Carlo (it)
- Algorithme de Monte-Carlo (fr)
- 몬테카를로 알고리즘 (ko)
- Monte Carlo algorithm (en)
|
| owl:differentFrom
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is owl:differentFrom
of | |
| is foaf:primaryTopic
of | |
