Classfication d'algorithmes randomisés

De Wikipedia sur les algorithmes randomisés

Il faut distinguer les algorithmes qui utilisent l'entrée aléatoire pour réduire le temps d'exécution prévu ou l'utilisation de la mémoire, mais qui se terminent toujours par un résultat correct dans un laps de temps limité, et les algorithmes probabilistes , qui, selon l'entrée aléatoire, ont une chance de produire un résultat incorrect (algorithmes de Monte Carlo) ou de ne pas produire un résultat (algorithmes de Las Vegas) soit en signalant un échec, soit en ne se terminant pas.

1. Je me demandais comment le premier type d '« algorithmes utilise l'entrée aléatoire pour réduire le temps d'exécution prévu ou l'utilisation de la mémoire, mais se termine-t-il toujours par un résultat correct dans un laps de temps limité?
2. Quelles sont les différences entre celui-ci et les algorithmes de Las Vegas qui peuvent ne pas produire de résultat?
3. Si je comprends bien, les algorithmes probabilistes et les algorithmes randomisés ne sont pas le même concept. Les algorithmes probabilistes ne sont qu'un type d'algorithmes randomisés, et l'autre type est celui qui utilise l'entrée aléatoire pour réduire le temps d'exécution prévu ou l'utilisation de la mémoire, mais se termine toujours par un résultat correct dans un laps de temps limité?

1. $O(n^{2})$$O(n\log n)$$O(n^{2})$$O(n\log n)$

2. Cela donne un sous-ensemble d'algorithmes de Las Vegas. Les algorithmes de Las Vegas permettent également la possibilité (avec une faible probabilité) de ne pas se terminer du tout - pas seulement de se terminer avec un peu plus de temps.

3. Ceux-ci à leur tour ne sont vraiment qu'un type d'algorithme de Monte Carlo, où la réponse peut être incorrecte (avec une faible probabilité), ce qui est au moins conceptuellement différent de ne pas répondre.

Il y a tout un tas de détails que j'ai omis bien sûr, vous voudrez peut-être rechercher les classes de complexité ZPP, RP et BPP, qui formalisent ces idées.

Les deux termes algorithmes randomisés et algorithmes probabilistes sont utilisés dans deux contextes différents. Les algorithmes randomisés sont des algorithmes qui utilisent l'aléatoire, contrairement aux algorithmes déterministes qui n'en utilisent pas. Les algorithmes probabilistes , par exemple les algorithmes probabilistes pour le test de primalité, sont des algorithmes qui utilisent le caractère aléatoire et pourraient faire une erreur avec une probabilité (espérons-le) faible.

Une distinction importante doit être faite entre les algorithmes de Monte Carlo et les algorithmes de Las Vegas . Les algorithmes de Las Vegas sont des algorithmes randomisés qui renvoient toujours la bonne réponse, mais leur durée de fonctionnement dépend des lancers de pièces. Un exemple est les algorithmes de factorisation des nombres entiers - ils renvoient toujours les bons facteurs, mais leur durée de fonctionnement dépend du caractère aléatoire. Lorsque nous indiquons le temps d'exécution d'un algorithme de Las Vegas (disons un algorithme d'affacturage), nous indiquons en fait le temps d' exécution prévu ; si nous n'avons pas de chance, l'algorithme pourrait fonctionner plus longtemps.

Les algorithmes de Monte-Carlo, en revanche, sont des algorithmes randomisés dont le temps d'exécution est défini à l'avance. De tels algorithmes peuvent faire une erreur, mais généralement la probabilité d'erreur est très faible. Un bon exemple est le test de primalité probabiliste. Ces algorithmes sont très rapides mais pourraient faire une erreur. Cependant, la probabilité d'erreur est lente et faible qu'en pratique, ils ne se trompent jamais.

Chaque algorithme de Las Vegas peut être converti en un algorithme de Monte Carlo en arrêtant l'exécution après un temps suffisamment long, de sorte que les algorithmes de Las Vegas sont en quelque sorte «meilleurs» que les algorithmes de Monte Carlo.