Hoja de repaso: Algorithmes Probabilistes et Garanties

📋 Plan du Cours

1. Contexte DataSmart et problématique
2. Algorithmes déterministes et probabilistes
3. Temps d’exécution borné et en espérance
4. Algorithmes Las Vegas et garanties
5. Algorithmes Monte Carlo et probabilité d’erreur
6. Quicksort randomisé et complexité attendue
7. Patterns algorithmiques et rôle de l’aléatoire
8. Quickselect Las Vegas et sélection du k-ième
9. Miller-Rabin Monte Carlo et contrôle d’erreur
10. Amplification de probabilité et loi géométrique
11. Choix entre Las Vegas et Monte Carlo
12. Validation des pistes et compromis performance fiabilité

📖 1. Contexte DataSmart et problématique

🔑 Notions clés & Définitions

• DataSmart Cameroun : Entreprise de traitement de données confrontée à une hausse de volume qui dégrade la performance des algorithmes existants.
• Algorithmes déterministes : Algorithmes qui suivent un déroulement fixé, sans aléa, et qui cherchent une réponse exacte à chaque exécution.
• Algorithmes probabilistes : Famille d’algorithmes qui intègrent une part d’aléatoire pour améliorer les performances, notamment sur de grandes masses de données.
• Algorithmes Las Vegas : Algorithmes probabilistes qui garantissent un résultat correct, tout en ayant un temps d’exécution aléatoire.
• Algorithmes Monte Carlo : Autre catégorie d’algorithmes probabilistes étudiée pour comparer performance et fiabilité face aux contraintes de calcul.

📝 Points essentiels

• DataSmart observe que l’augmentation du volume de données rend les algorithmes actuels inefficaces, voire inutilisables au-delà d’un seuil.
• Éric signale que les algorithmes actuels sont déterministes et visent systématiquement l’exactitude, ce qui peut faire exploser le temps d’exécution dans les cas défavorables.
• Nadia propose d’introduire des algorithmes probabilistes pour mieux gérer les grandes masses de données.
• Les algorithmes Las Vegas sont conçus pour toujours produire une réponse correcte, mais avec un temps d’exécution variable.
• La problématique centrale est le compromis entre performance (temps) et fiabilité (correction), motivant la comparaison Las Vegas vs Monte Carlo.
• Le prosit vise à formaliser ensuite la notion de temps d’exécution en espérance et la probabilité d’erreur pour justifier un choix d’algorithme selon le contexte.

💡 Astuce mémo

Déterministe = exact mais parfois lent; Probabiliste = plus rapide en moyenne, avec un risque ou une variabilité de temps (Las Vegas : correct toujours, Monte Carlo : compromis fiabilité).

📖 2. Algorithmes déterministes et probabilistes

🔑 Notions clés & Définitions

• Algorithmes probabilistes : Famille d’algorithmes qui intègrent de l’aléatoire pour améliorer les performances, notamment sur de grandes masses de données.
• Algorithmes Las Vegas : Type d’algorithme probabiliste qui produit toujours un résultat correct, mais dont le temps d’exécution varie et s’analyse en espérance.
• Algorithmes Monte Carlo : Type d’algorithme probabiliste qui garantit un temps d’exécution borné, mais autorise une erreur avec une probabilité quantifiable et contrôlable.
• Algorithmes déterministes : Algorithmes dont le comportement ne dépend pas du hasard, avec une exécution et un résultat fixés par l’entrée.

📝 Points essentiels

• Les algorithmes probabilistes visent un meilleur compromis performance–fiabilité sur des traitements à grande échelle.
• Las Vegas : la correction est garantie, tandis que le temps d’exécution est aléatoire et évalué par son espérance.
• Monte Carlo : le temps d’exécution est borné, tandis que le risque d’erreur est mesuré par une probabilité contrôlable.
• Le choix entre Las Vegas et Monte Carlo dépend de la nature du traitement et du niveau de fiabilité exigé.
• Mots-clés à maîtriser : temps d’exécution en espérance et temps d’exécution borné pour distinguer les deux familles.
• Le Quicksort randomisé fait partie des exemples/termes associés à l’approche probabiliste dans le cours.

💡 Astuce mémo

Las Vegas = Toujours Correct, Temps en Espérance ; Monte Carlo = Temps Borné, Erreur Contrôlée.

📖 3. Temps d’exécution borné et en espérance

🔑 Notions clés & Définitions

• Complexité en pire cas : La complexité en pire cas mesure le coût maximal d’un algorithme sur toutes les entrées possibles, ce qui donne une garantie même dans le scénario le plus défavorable.
• Complexité en espérance : La complexité en espérance est l’analyse moyenne du temps d’exécution, obtenue en prenant la valeur moyenne sur toutes les exécutions aléatoires possibles.
• Algorithme Las Vegas : Un algorithme Las Vegas est un algorithme probabiliste qui garantit toujours la correction du résultat, tandis que l’aléatoire ne concerne que le temps d’exécution.
• Algorithme Monte Carlo : Un algorithme Monte Carlo est un algorithme probabiliste où l’aléatoire peut affecter la correction, et où l’on contrôle la probabilité d’erreur par répétition.

📝 Points essentiels

• Pour un algorithme déterministe, la complexité est classiquement étudiée en pire cas car le comportement ne varie pas d’une exécution à l’autre.
• Pour un algorithme probabiliste, l’analyse se fait en espérance ou en probabilité car le comportement dépend d’un générateur aléatoire.
• Dans un algorithme Las Vegas, la correction est garantie à chaque exécution, mais le temps d’exécution peut varier et n’est donc pas borné de façon stricte à chaque run.
• Le temps d’exécution d’un Las Vegas se caractérise par une borne en espérance, ce qui donne une garantie moyenne malgré des exécutions potentiellement très longues.
• La répétition d’un algorithme Monte Carlo réduit la probabilité d’erreur en la rendant négligeable si on combine suffisamment d’exécutions.
• On privilégie Monte Carlo plutôt que Las Vegas quand on accepte une petite probabilité d’erreur pour obtenir un temps d’exécution plus maîtrisé en pratique.

💡 Astuce mémo

Las Vegas = Toujours juste, variable en durée (on parle d’espérance) ; Monte Carlo = Durée plus “rapide”, mais erreur contrôlée par répétitions.

📖 4. Algorithmes Las Vegas et garanties

🔑 Notions clés & Définitions

• Algorithme Las Vegas : Algorithme probabiliste qui garantit toujours la correction, l’aléatoire ne change que le temps d’exécution, analysé en espérance.
• Algorithme Monte Carlo : Algorithme probabiliste dont le temps d’exécution est garanti borné, mais dont le résultat peut être faux avec une probabilité d’erreur.
• Temps d'exécution borné : Propriété où l’on peut garantir une borne supérieure sur la durée d’exécution, indépendamment des choix aléatoires.
• Temps d'exécution en espérance : Moyenne du temps d’exécution sur toutes les exécutions possibles pour une même entrée, notée E[T] quand T est la durée.
• Amplification de probabilité : Technique consistant à répéter un algorithme Monte Carlo pour rendre la probabilité d’erreur aussi petite que souhaitée.

📝 Points essentiels

• Dans un algorithme Las Vegas, le résultat est toujours correct, mais le temps peut varier et n’est pas borné dans le pire cas.
• Le temps d’exécution d’un Las Vegas se caractérise par son espérance E[T], car l’analyse porte sur la moyenne des durées.
• Un algorithme Las Vegas peut potentiellement tourner très longtemps, mais il finit toujours par produire la bonne réponse.
• Dans un algorithme Monte Carlo, le temps d’exécution est borné (garanti), mais le résultat peut être incorrect avec une probabilité non nulle.
• La probabilité d’erreur d’un Monte Carlo peut être réduite arbitrairement en répétant l’algorithme suffisamment de fois (amplification de probabilité).
• En notation asymptotique, un temps d’exécution borné correspond à une complexité en O(f(n)) dans tous les cas, indépendamment des aléas.

💡 Astuce mémo

Las Vegas : « Correct toujours, temps inconnu » ; Monte Carlo : « Temps garanti, parfois faux ».

📖 5. Algorithmes Monte Carlo et probabilité d’erreur

🔑 Notions clés & Définitions

• Espérance du temps : L’espérance du temps est la moyenne du nombre d’opérations $E[T]$ sur toutes les exécutions aléatoires possibles pour une entrée donnée.
• Complexité en espérance : La complexité en espérance mesure le coût moyen d’un algorithme probabiliste via l’espérance de sa variable de temps.
• Algorithme Las Vegas : Un algorithme Las Vegas est probabiliste et garantit la correction, mais son temps d’exécution peut varier selon les tirages aléatoires.
• Algorithme Monte Carlo : Un algorithme Monte Carlo est probabiliste et peut se tromper, avec une probabilité d’erreur contrôlée, tout en ayant un temps borné en pratique.
• Quicksort randomisé : Le Quicksort randomisé est une variante de Quicksort où le pivot est choisi aléatoirement, ce qui rend l’analyse en moyenne favorable.

📝 Points essentiels

• Pour un algorithme probabiliste, l’analyse de complexité se fait en considérant toutes les exécutions possibles et la variable aléatoire $T$ des opérations.
• Pour les algorithmes Las Vegas, on ne garantit pas le temps dans le pire cas, mais on obtient un bon comportement moyen via $E[T]$.
• Le Quicksort randomisé choisit le pivot au hasard parmi les éléments, au lieu d’un choix déterministe (premier, dernier, médian fixe).
• Le choix aléatoire du pivot évite le cas pathologique $O(n^2)$ qui apparaît sur des tableaux déjà triés avec un pivot déterministe.
• La complexité attendue du Quicksort randomisé est $O(n\log n)$.
• Un algorithme Monte Carlo peut produire une erreur, contrairement à un algorithme Las Vegas qui reste correct mais variable en temps.

💡 Astuce mémo

Las Vegas = Correct mais temps variable (moyenne via $E[T]$) ; Monte Carlo = Temps plus “stable” mais risque d’erreur (probabilité d’échec).

📖 6. Quicksort randomisé et complexité attendue

🔑 Notions clés & Définitions

• Algorithme probabiliste : Un algorithme probabiliste utilise des tirages aléatoires pour améliorer le comportement moyen et éviter les pires cas déterministes.
• Complexité attendue : La complexité attendue est la valeur moyenne du temps d’exécution sur tous les tirages aléatoires possibles.
• Quicksort randomisé : Le quicksort randomisé choisit le pivot de façon aléatoire pour casser les configurations adversariales et obtenir de bonnes performances en moyenne.
• Pivot aléatoire : Un pivot aléatoire est un élément choisi au hasard qui rend la partition moins sensible aux entrées construites pour piéger le déterministe.
• Las Vegas : Un algorithme Las Vegas garantit la correction du résultat, tandis que le temps d’exécution varie selon les tirages.

📝 Points essentiels

• Le temps d’exécution d’un algorithme probabiliste est variable car il dépend des tirages aléatoires.
• La performance est analysée en espérance ou en probabilité plutôt qu’en pire cas déterministe.
• Le randomisé casse les configurations adversariales qui provoquent un pire cas catastrophique en déterministe.
• Quicksort randomisé utilise un pivot aléatoire pour obtenir, en moyenne, des partitions proches de l’équilibre.
• Le résultat est toujours exact pour les algorithmes de type Las Vegas, mais le temps peut être plus ou moins long selon les tirages.

💡 Astuce mémo

Pivot au hasard = partitions “moins piégées” → bon temps moyen (espérance).

📖 7. Patterns algorithmiques et rôle de l’aléatoire

🔑 Notions clés & Définitions

• Pivot aléatoire : Un pivot aléatoire est un choix de pivot tiré au hasard pour éviter des configurations adversariales et obtenir, en moyenne, une séparation plus équilibrée.
• Test de primalité de Miller-Rabin : Le test de primalité de Miller-Rabin est un algorithme probabiliste qui décide si un entier est premier en répétant des tests avec des témoins aléatoires.
• Algorithme Monte Carlo : Un algorithme Monte Carlo est un algorithme probabiliste qui peut échouer, mais dont la probabilité d’erreur peut être rendue très faible par répétitions indépendantes.
• Algorithme Las Vegas : Un algorithme Las Vegas est un algorithme probabiliste qui garantit la correction quand il termine, avec un temps (nombre d’itérations) aléatoire.
• Amplification de probabilité : L’amplification de probabilité est la technique qui répète un algorithme Monte Carlo indépendant pour augmenter la probabilité d’obtenir au moins un succès.

📝 Points essentiels

• Un pivot aléatoire réduit l’impact des configurations adversariales et améliore l’équilibre attendu du partitionnement.
• Dans Miller-Rabin, si le test échoue alors n est certainement composé, et s’il réussit n est probablement premier.
• Après k itérations indépendantes de Miller-Rabin, la probabilité que n soit composé mais déclaré premier est ≤ (1/4)^k.
• Pour k = 40, la borne (1/4)^40 est < 10^(-24), bien plus faible que des défaillances matérielles typiques.
• Dans un Monte Carlo, si la probabilité de succès par exécution est p > 0,5, répéter N fois donne P(au moins un succès) = 1 − (1 − p)^N.
• Pour p = 0,6 et N = 10, on obtient 1 − (0,4)^10 ≈ 0,99990, soit > 99,99 % de chances d’avoir au moins un résultat correct.

💡 Astuce mémo

Monte Carlo : on répète pour gagner en probabilité (1 − (1 − p)^N) ; Las Vegas : on répète pour gagner en temps (E[X]=1/p).

📖 8. Quickselect Las Vegas et sélection du k-ième

🔑 Notions clés & Définitions

• Quickselect Las Vegas : Quickselect Las Vegas : algorithme probabiliste dont la correction est garantie, avec un temps d’exécution variable mais borné en espérance.
• Sélection du k-ième élément : Sélection du k-ième élément : problème consistant à trouver l’élément qui serait à la position k après tri, sans trier tout le tableau.
• Temps en espérance : Temps en espérance : durée moyenne de l’algorithme sur toutes les exécutions aléatoires, utilisée pour caractériser la performance probabiliste.
• Monte Carlo : Monte Carlo : algorithme probabiliste qui garantit une borne de temps, mais peut produire une réponse approximative ou erronée.

📝 Points essentiels

• Quickselect Las Vegas a une complexité $O(n)$ en espérance pour la recherche du k-ième élément.
• Le choix Las Vegas vs Monte Carlo dépend du compromis exactitude garantie vs borne temporelle assurée.
• Las Vegas : la correction est garantie (pas d’erreur), mais le temps d’exécution peut varier d’une exécution à l’autre.
• Monte Carlo : le temps est contrôlé (borne temporelle), mais la précision dépend du paramétrage et peut être insuffisante.
• Pour un estimateur de Monte Carlo, l’erreur décroît lentement : avec Chebyshev, l’ordre de grandeur requis pour 0,01 à 95% est $n\ge 700\,000$.
• Le TCL améliore l’estimation : une approximation gaussienne donne un ordre de grandeur d’environ $38\,465$ points pour le même niveau de confiance.

💡 Astuce mémo

Las Vegas = Exactitude sûre, temps moyen $O(n)$ pour Quickselect ; Monte Carlo = Temps garanti, précision à payer.

📖 9. Miller-Rabin Monte Carlo et contrôle d’erreur

🔑 Notions clés & Définitions

• Quicksort randomisé : Algorithme de tri qui choisit le pivot au hasard, ce qui évite les pires cas systématiques du pivot fixe.
• Quicksort déterministe à pivot fixe : Algorithme de tri où le pivot est choisi selon une règle fixe (ex. premier élément), pouvant conduire à un pire cas en O(n²).
• Algorithme Las Vegas : Algorithme probabiliste dont la correction est garantie, car il ne s’arrête que lorsqu’il a une réponse correcte.
• Algorithme Monte Carlo : Algorithme probabiliste qui peut se tromper, mais dont la probabilité d’erreur peut être réduite par répétition.
• Amplification de probabilité : Technique consistant à répéter un algorithme Monte Carlo pour diminuer la probabilité de produire une réponse incorrecte.

📝 Points essentiels

• Quicksort déterministe à pivot fixe peut atteindre un pire cas en O(n²) sur des entrées déjà triées ou inversement triées.
• Quicksort randomisé a une complexité attendue O(n log n) quelle que soit la distribution des données en entrée.
• L’aléatoire dans le choix du pivot empêche un adversaire de forcer systématiquement un mauvais cas.
• Dans un algorithme Las Vegas, l’aléatoire influence seulement la durée d’exécution, pas la justesse de la réponse.
• Un algorithme Las Vegas peut répéter des tentatives et rejeter celles qui n’aboutissent pas à une réponse valide.
• Si chaque tentative réussit avec probabilité p, le nombre espéré de tentatives vaut 1/p, donc le temps espéré est fini si p>0.

💡 Astuce mémo

Las Vegas = Justesse garantie (on attend le bon résultat) ; Monte Carlo = On accélère mais on contrôle l’erreur par répétition.

📖 10. Amplification de probabilité et loi géométrique

🔑 Notions clés & Définitions

• Amplification de probabilité : Technique de répétition d’un algorithme probabiliste qui réduit la probabilité d’erreur globale de façon exponentielle avec le nombre d’exécutions indépendantes.
• Répétition indépendante : Exécution de plusieurs itérations d’un algorithme probabiliste en supposant que les erreurs de chaque itération ne sont pas corrélées.
• Réponse majoritaire : Règle de décision qui choisit la sortie la plus fréquente parmi les exécutions indépendantes pour diminuer la probabilité d’erreur.
• Arrêt à la première réponse satisfaisante : Stratégie d’exécution où l’on s’arrête dès qu’une exécution produit une réponse jugée correcte, ce qui limite le nombre d’essais.
• Loi géométrique : Modèle probabiliste du nombre d’essais nécessaires avant le premier succès, utile quand on s’arrête dès qu’une condition de succès est atteinte.

📝 Points essentiels

• Si un Monte Carlo a une probabilité de succès p avec p>1/2, alors la probabilité d’erreur diminue exponentiellement quand on répète indépendamment et qu’on agrège (majorité ou arrêt sur succès).
• En répétant N fois et en ne gardant que le cas où toutes les itérations échouent, l’erreur globale peut s’écrire comme (1-p)^N, ce qui donne une décroissance exponentielle en N.
• Pour l’algorithme Monte Carlo de l’exercice 7 (variante max-Las-Vegas) répété k=275 fois avec probabilité d’erreur par itération 1/2, l’erreur globale vaut (1/2)^275.
• Le résultat (1/2)^275 est extrêmement petit, inférieur à 10^(-82), donc négligeable face à des défaillances physiques plausibles.
• Le choix Monte Carlo vs Las Vegas dépend des contraintes métier : Monte Carlo pour un temps de réponse garanti, Las Vegas quand l’exactitude est indispensable.

💡 Astuce mémo

p>1/2 + répétitions indépendantes ⇒ l’erreur “fond” comme (1/2)^N : plus tu répètes, plus le risque devient astronomiquement petit.

📖 11. Choix entre Las Vegas et Monte Carlo

🔑 Notions clés & Définitions

• Algorithmes Las Vegas : Les algorithmes Las Vegas garantissent la correction, mais leur temps d’exécution peut varier selon le hasard.
• Algorithmes Monte Carlo : Les algorithmes Monte Carlo garantissent un temps maîtrisé, mais autorisent une probabilité d’erreur.
• Probabilité d’erreur résiduelle : La probabilité d’erreur résiduelle mesure le risque restant après répétitions ou amplification, et sert à juger la fiabilité pratique.
• Décision d’ingénierie : La décision d’ingénierie consiste à choisir le type d’algorithme selon contraintes de temps, de correction et contexte d’application.

📝 Points essentiels

• Le choix entre Monte Carlo et Las Vegas dépend des contraintes de temps, de correction et du domaine applicatif plutôt que d’un jugement de qualité générale.
• Les algorithmes Las Vegas préservent la correction au prix d’un temps variable.
• Les algorithmes Monte Carlo préservent le temps au prix d’une correction probabiliste.
• Quand la probabilité d’erreur résiduelle est < 10^(-24), elle devient négligeable face aux risques physiques typiques.
• La distinction n’oppose pas « bon » contre « moins bon » : chaque famille est optimale dans son contexte de contraintes.

💡 Astuce mémo

Las Vegas = Correct toujours, Temps variable ; Monte Carlo = Temps fixe, Erreur possible.

📖 12. Validation des pistes et compromis performance fiabilité

🔑 Notions clés & Définitions

• Raisonnement probabiliste : Approche algorithmique qui fournit des garanties via des probabilités plutôt que par une certitude déterministe.
• Monte Carlo : Méthode probabiliste utilisée pour estimer des grandeurs par simulation à partir de tirages aléatoires.
• Quicksort randomisé : Variante de Quicksort qui choisit aléatoirement le pivot pour améliorer les performances attendues.
• Tests de primalité probabilistes : Procédures qui décident la primalité avec une probabilité d’erreur contrôlée, utiles en cryptographie.
• Correcte en espérance : Propriété où la performance ou le résultat est évalué en moyenne, ce qui peut suffire selon les contraintes.

📝 Points essentiels

• 40 répétitions permettent d’obtenir une probabilité d’erreur < 10^(-24), bien plus faible que toute erreur matérielle concevable.
• Le raisonnement probabiliste peut donner des garanties pratiques très solides même sans certitude absolue.
• Les algorithmes probabilistes complètent les paradigmes classiques (glouton, diviser-pour-régner, programmation dynamique) par un raisonnement probabiliste.
• Monte Carlo est central pour les simulations et le renforcement par apprentissage.
• Le Quicksort randomisé est largement implémenté dans les bibliothèques de tri.
• Les tests de primalité probabilistes sont indispensables pour générer des clés cryptographiques utilisées dans les connexions HTTPS.

💡 Astuce mémo

40 répétitions → erreur < 10^(-24) : “probabilité d’échec quasi nulle” face aux erreurs matérielles.

📊 Tableaux de synthèse

Déterministe vs probabiliste (caractéristiques)

Caractéristique	Déterministe	Probabiliste
Résultat pour une même entrée	Toujours identique	Peut varier selon l’aléa
Utilisation d’aléatoire	Aucune	Oui, par conception
Analyse de complexité	Pire cas, meilleur cas, cas moyen	En espérance ou en probabilité
Temps d’exécution	Prévisible et reproductible	Variable selon les tirages aléatoires

Las Vegas vs Monte Carlo (garanties)

Caractéristique	Las Vegas	Monte Carlo
Correction du résultat	Toujours garantie	Probabiliste (peut être faux)
Temps d’exécution	Aléatoire, analysé en espérance	Borné, garanti dans tous les cas
Probabilité d’erreur	Nulle	ε > 0, contrôlable par répétition
Amplification	Non nécessaire	Possible par répétitions indépendantes

⚠️ Pièges & confusions fréquents

1. Confondre « temps d’exécution en espérance » (moyenne E[T]) avec une borne stricte : Las Vegas n’a pas de garantie de temps dans le pire cas.
2. Croire que Monte Carlo garantit la correction : en réalité le résultat peut être faux avec une probabilité d’erreur contrôlable.
3. Mélanger les rôles de l’aléatoire : pour Las Vegas il porte sur le temps, pour Monte Carlo il peut affecter la correction.
4. Penser que l’amplification de probabilité est un mécanisme Las Vegas : elle sert surtout à réduire l’erreur d’un Monte Carlo par répétitions indépendantes.
5. Oublier la condition p>1/2 pour l’argument « erreur décroît exponentiellement » avec majorité/agrégation dans Monte Carlo.
6. Interpréter « complexité bornée » comme « complexité en espérance » : bornée signifie une garantie de temps supérieure indépendamment des aléas.
7. Se tromper sur Miller-Rabin : si le test échoue, n est certainement composé ; s’il réussit, n est seulement probablement premier.

✅ Checklist Examen

1. Définir un algorithme probabiliste et expliquer pourquoi son comportement peut varier d’une exécution à l’autre pour une même entrée.
2. Distinguer algorithmes déterministes et probabilistes en précisant au moins : résultat, rôle de l’aléatoire et mode d’analyse (pire cas vs espérance/probabilité).
3. Définir le temps d’exécution en espérance (E[T]) et expliquer pourquoi c’est l’outil d’analyse naturel pour Las Vegas.
4. Définir un algorithme Las Vegas et justifier la garantie de correction tout en précisant que le temps est aléatoire.
5. Définir un algorithme Monte Carlo et préciser : temps borné garanti mais probabilité d’erreur ε>0.
6. Expliquer la différence entre « temps d’exécution borné » et « temps d’exécution en espérance » et relier chacune aux familles Las Vegas/Monte Carlo.
7. Justifier comment la répétition indépendante et l’amplification de probabilité réduisent la probabilité d’erreur d’un Monte Carlo.
8. Calculer/exprimer la probabilité d’au moins un succès après N répétitions : P(au moins un succès)=1-(1-p)^N (ou l’erreur résiduelle via (1-p)^N selon l’agrégation).
9. Expliquer le lien entre Las Vegas et loi géométrique : si chaque itération réussit avec probabilité p, alors E[X]=1/p.
10. Décrire Quickselect Las Vegas : principe (pivot aléatoire, partition, récursion sur la partie pertinente) et complexité en espérance O(n).
11. Décrire Quicksort randomisé : pivot choisi aléatoirement, transformation en Las Vegas, et complexité attendue O(n log n) en évitant le cas pathologique O(n^2).
12. Expliquer Miller-Rabin : rôle des témoins aléatoires, conclusion en cas d’échec vs réussite, et borne (1/4)^k puis relier à k=40 et à l’usage cryptographique.