Algorithmes probabilistes Flashcards
Explorer les points clés de la matière survolée (18 cards)
Quel est l’utilité globale de l’algorithme Las Vegas - Type 1 ?
Quand un algo déterministe existe pour un type de problème qui est :
- Bon en moyenne
- Mauvais dans le pire cas
Que permet de faire l’algorithme Las Vegas - Type 1 sur un problème qui répond à ses critères d’utilisation (utilité globale) ?
- Éliminer les instances pire cas
- Uniformiser les instance
- Maintenir un bon temps espéré
Solution exacte garantie : s’arrête uniquement quand une solution valide est trouvée (aucune sortie erronée).
• Temps d’exécution aléatoire : durée variable, caractérisée par sa distribution, avec une espérance polynomialle (si le problème est dans ZPP).
• Mécanisme : génère aléatoirement des candidats, vérifie en temps polynomial, et recommence tant que la vérification échoue.
• Condition d’usage : la validité de toute solution doit pouvoir être vérifiée en temps polynomial.
Différencie les 3 types d’algorithme Monte-Carlo (vrai-biaisé, faux-biaisé, non-biaisé).
Vrai-biaisé : s’il répond “vrai”, il ne se trompe jamais
Faux-biaisé : s’il répond “faux”, il ne se trompe jamais
Non-biaisé : il peut se trompé entre soit “vrai”, soit “faux” dans ses réponses
V/F : Un algorithme probabiliste de Las Vegas peut se tromper des fois, mais seulement lorsque la réponse est “faux”.
FAUX. Il ne se trompe jamais. Dans le pire cas, il répond “je ne sais pas”.
V/F : L’algorithme de tri rapide randomisé permet d’éliminer certains pire cas pour le tri rapide déterministe tel une liste déjà triée.
VRAI. Grâce à l’algorithme Las Vegas - Type 1.
V/F : On peut tester la primalité d’un nombre très efficacement et avec une grande précision grâce aux algorithmes probabilistes.
VRAI. Grâce aux algorithmes Monte-Carlo, on peut construire des tests de primalité pour le Petit théorême de Fermat.
V/F : Pour pouvoir faire des choix aléatoires, on génère des suites de nombre pseudo-aléatoires qui ont des propriétés mathématiques similaires aux vrais nombres aléatoires.
VRAI. Grâce aux méthodes d’échantillonage numériques comme celle de Monte-Carlo (à ne pas confondre avec l’algorithme de Monte-Carlo).
V/F : Les algorithmes probabilistes numériques permettent d’estimer des solutions à des problèmes numériques
tels des intégrales difficiles ou des simulations.
VRAI. Grâce à un échantillonage uniforme aléatoire.
V/F : Les algorithmes probabilistes peuvent résoudre certains problèmes plus rapidement en temps espéré que des algorithmes déterministes.
VRAI. C’est l’objectif principal des algorithmes probabilistes.
V/F : Il n’y a pas d’utilité à répéter un algorithme probabiliste de Monte Carlo.
FAUXVR. Au contraire, il est recommandé de répéter un algorithme probabiliste de Monte Carlo afin de diminuer l’erreur.
V/F : L’algorithme de Karger permet de trouver rapidement en temps espéré un Arbre Couvrant Minimal (ACM).
FAUX. L’algorithme de Karger permet plutôt de trouver la coupe minimale d’un graphe non-orienté. La probabilité associée sans répétition est ~ 2/pi^2.
Différencie les 3 types d’algorithmes probabilistes vus en classe (donne une définition courte).
Probabiliste numérique (avec la méthode de Monte-Carlo) : retourne une solution approximative à un problème numérique
Monte-Carlo : retourne toujours une réponse mais peut se tromper
Las Vegas : ne retourne jamais une réponse inexacte mais, peut parfois prendre plus de temps OU ne pas trouver un réponse du tout
Quelle est la différence principale entre Las Vegas - Type 1 et Las Vegas - Type 2 ?
Tous les deux utilisent le hasard mais
- Type 1 : l’utilise pour GUIDER ses choix et arrive à résoudre en tout temps
- Type 2 : l’utilise pour TENTER de résoudre le problème, même s’il doit échoué
Liste 1 problème typique pour
1. Las Vegas - Type 1
2. Las Vegas - Type 2
- Tri rapide randomisé
- 8 reines
Avec quel autre classe d’algorithmes vu en classe est-ce que l’algorithme Las Vegas vorace peut-il être hybridé (pour 8 reines) ?
Retour en arrière. Las Vegas commence sur les “k” premières positions, puis ensuite Retour en arrière.
Dans l’algorithme probabiliste numérique Aiguille de Buffon, quel est la probabilité qu’une aiguille tombe au travers d’une craque ?
A. 1/pi
B. 2/pi^2
C. pi
D. 1/2
A. 1/pi
Dans la définition de l’algorithme de Monte-Carlo, que signifie un algorithme qui est p-correct ?
S’il retourne une solution correcte avec une probabilité SUPÉRIEURE à p, pour 0 < p < 1 et ce, peut importe l’instance.
L’algorithme Miller-Rabin (Monte-Carlo) est-il vrai-biaisé, faux-biaisé ou non-biaisé ? Que vaut son “p” ? Peut-on le répéter plusieurs fois pour diminuer le taux d’erreur ?
Faux-biaisé. Sa probabilité est de p = 3/4. Oui, on peut le répéter plusieurs fois.
