Formation et introduction Algorithmes avances

Formation et introduction Algorithmes avancés avec exemples

...

2 PRINCIPE D’ALGORITHMES EFFICACES

2.1 DIVISER POUR REGNER

Le principe consiste à résoudre un problème en résolvant deux ou plusieurs problèmes du même type, en simplifiant le problème premier par des sous-problèmes identiques, mais simplifiés.

Attention, ce n’est pas la même chose que la programmation structurée. Ici, c’est le programme qui divise le problème et non le programmeur.

Cette méthode donne souvent des algorithmes efficaces et élégants, mais il peut parfois y avoir des conflits.

2.2 QUELQUES EXEMPLES  2.2.1 Algorithme de Tri rapide

Dans un tableau, on choisit un élément pivot (dans la méthode de base, cela consiste à prendre la premier élément du tableau).

On divise le tableau en trois parties :

Ø Les éléments plus petits que le pivot,

Ø Les éléments égaux au pivot,

Ø Les éléments plus grands que le pivot.

On recommence cette méthode, récursivement pour les premières (inférieur au pivot) et troisièmes (supérieur au pivot) parties.

2.2.2 Algorithme de Tri par fusion

Méthode récursive consistant à diviser les éléments en deux parties (équilibrées), trier chaque partie, puis fusionner les parties élémentaires.

2.2.3 Algorithme Min-Max

L’algorithme Min-Max consiste à trouver le minimum et le maximum d’un tableau. S’il n’y a que deux éléments dans le tableau, il suffit de les comparer.

Sinon, on divise le tableau en deux parties (identiques et paires... ce qui implique que le tableau est de longueur n avec n pair. Voir TD 1 pour n impair) et on recommence l’algorithme (récursif). Lorsqu’on a le maximum et le minimum de deux parties, on les compare.

Cette méthode fait approximativement 3n/2 comparaisons.

 3 ALGORITHMES GLOUTONS

3.1 PRINCIPE

Les algorithmes gloutons sont ceux qui trouvent une solution parmi plusieurs possibles, comparables selon un critère global. A chaque fin d’étape de l’algorithme, on choisit l’étape suivante en fonction des informations locales. La méthode gloutonne ne trouve pas forcément la meilleure solution.

3.2 EXEMPLES

3.2.1 Arbre recouvrant de poids minimum

Cet algorithme permet, dans un graphe ou les arêtes ont un poids, de trouver l’arbre qui relie tous les sommets avec une somme des poids minimale.

On peut considérer deux méthodes :

Algorithme très glouton non optimal : on commence avec un arbre d’un seul sommet et on choisit toujours l’arête de poids minimum pour rejoindre le sommet suivant.

Algorithme glouton et optimal: on commence avec n arbres (n correspondant au nombre de sommet du graphe) d’un seul sommet et on choisit toujours l’arête de poids minimum qui relie deux arbres.

3.2.2 Sac à dos continu

Le problème consiste à remplir un containeur avec une charge la plus grande possible étant donné plusieurs matériaux, chacun avec une valeur/kilo et une quantité disponible.

Il s’agit d’un algorithme glouton : il faut toujours chercher et choisir le matériau avec le meilleur rapport valeur/poids.

3.3 CAS OU LA METHODE GLOUTONNE N’EST PAS OPTIMALE

3.3.1 Exemples

On peut retenir trois exemples :

Ø Sac à dos discret : avec des objets que l’on ne peut découper.

Ø Coloration de graphe : on veut colorier les sommets d’un graphe avec le plus petit nombre couleurs possible sachant que deux sommets voisins (reliés par une arrête) doivent avoir des couleurs différentes.

Ø Commis voyageur : étant donnée une carte des distances entre des paires de villes, trouver le chemin le moins coûteux qui passe par chaque ville une seule fois (et retourne au point de départ).

3.3.2 Commentaires sur la non existence d’algorithmes efficaces (connus) pour ces trois exemples

Ces trois problèmes sont des variantes des problèmes NP-complets. Personne ne connaît des algorithmes garantis de trouver une solution optimale en temps raisonnable (borné par un polynôme), mais il n’est pas dit que ce soit impossible.

Donc, il est utile de considérer des algorithmes qui ont une garantie de trouver une solution proche de l’optimale. Un premier essai à un tel algorithme pourrait être un algorithme glouton simple. Un deuxième essai serait d’améliorer le résultat du premier par des modifications locales gloutonnes.

4 ARBRES

4.1 ARBRES BINAIRES DE RECHERCHE

Les arbres binaires sont des structures utiles. Exemples :

Ø La structure représente la structure logique des données (arbre syntaxique, arbre généalogique)

Ø La structure est utilisée pour permettre les opérations nécessaires sur une structure abstraite (arbre binaire de recherche, additions, suppressions d’éléments plus efficacement qu’avec un tableau ou liste avec pointeurs).

4.1.1 Insertion, recherche, annulation dans un arbre binaire de recherche

4.1.1.1 La recherche dans un arbre binaire

On commence la recherche à la racine, on parcours à gauche ou à droite selon la comparaison avec la valeur à chaque nœud (échec si sous arbre vide).

4.1.1.2 Insertion d’une valeur dans un arbre binaire

Idem que pour la recherche, en remplaçant le sous-arbre vide par un nouveau sous arbre contenant la valeur à insérer.

4.1.1.3 Suppression dans un arbre binaire

La suppression est facile au niveau d’une feuille ou si le nœud n’a qu’un seul fils. S’il y a deux fils, on remplace par exemple le nœud supprimé par le sous arbre.

4.1.1.4 Remarque

Les traitements dans la hauteur de l’arbre ont toujours un nombre d’opération linéaire. Il s’agit de quelques manipulations de pointeurs

4.1.2 Les ordres de parcours

Il existe trois ordres de parcours (souvent utiles) permettant de visiter tous les nœuds d’un arbre (binaire) :

Ø Ordre infixe : (par exemple, afficher les éléments d’un arbre binaire de recherche en ordre). On parcourt tous le sous arbre gauche (en parcourant les sous arbre du sous arbre dans le même ordre... récursivement), ensuite la racine, puis tout le sous arbre droit.

Ø Ordre préfixe : (utile pour calculer la profondeur de chaque nœud) on traite d’abord la racine, puis le sous arbre gauche et enfin le sous arbre droit.

4.2 ARBRES EQUILIBRES

Un arbre binaire de recherche peut avoir une hauteur près de son nombre de nœud (n), en revanche, la moyenne est O(log n). C’est cette hauteur qui détermine le temps des opérations de base.

Il existe un grand nombre possible d’arbres avec n nœuds, on en obtient un selon l’ordre des insertions.

L’idée, pour obtenir un arbre équilibré, consiste à faire un peu plus de travail (à chaque insertion) afin de garder une hauteur plus raisonnable (de préférence O(log n)).

4.2.1 Arbre AVL

Un arbre AVL est un arbre dont la différence entre les hauteurs des deux sous arbres est au maximum 1. Ce type d’arbre nécessite le stockage d’une petite information cachée à chaque nœud : la différence entre les deux hauteurs des sous-arbres (-1, 0, 1).

Dans ce type d’arbre, la suppression d’un élément devient donc un peu plus compliquée.

4.2.2 Arbres 2-3

Un arbre 2-3 est un arbre pour lequel chaque nœud a soit une valeur et un fils, soit deux valeurs et trois fils. L’ordre est: sous-arbre, valeur, sous-arbre [, valeur, sous-arbre].

Dans un tel arbre, toutes les feuilles sont à la même profondeur.

Ø Pour ajouter une valeur dans un nœud qui n’en contient qu’un : trivial.

Ø S’il yen a déjà deux: insérer le deuxième dans le nœud père et diviser ce nœud en deux (avec peut-être une réaction en chaîne vers la racine).

 5 RECURSIVITE 5.1 IDEE

une fonction peut s’appeler elle-même exactement comme un appel d'une autre fonction. Dès l'appel récursif achevé l'exécution du programme continue (et sans effet sur les variables etparamètres de l'appel initial).

Cette méthode est valable pour les fonctions et procédures (fonctions void).

On parle aussi de récursivité mutuelle lorsque deux ou plusieurs fonctions s'appellent entre elles (donc appel avant déclaration pour quelques unes).

5.2 EXEMPLES FAVORIS  5.2.1 Calcul de factorielle

Fonction fact(n) : entier

Début

Si (n=0) retourner (1)

Fin

5.2.2 Fibonacci

Fonction Fb(n) : entier

Début

Si (n2) retourner 1

Sinon retourner (Fb(n-1)+Fb(n-2))

Fin

5.2.3 Remarques

La fonction récursive est une méthode bizarre de calculer une factorielle. Une boucle simple suffit. La fonction récursive est une très mauvaise méthode de calculer une suite de Fibonacci car le temps de calcul est exponentiel!

Donc, ne pas oublier qu’une méthode récursive est plus élégante et claire... mais il faut aussi considérer le temps de calcul, l’efficacité.

5.3 MEILLEURS EXEMPLES

5.3.1 Calcul de x n

Fonction Puissance (x, n) : réel

Début

Selon que:

N=1 : retourner x

N%2=0 : retourner carrée(puissance(x,n/2))

Défaut : retourner x*carrée(puissance(x,n/2))

Fin

Remarque : on saute de xi à x2i dans une seule multiplication, ce qui est plus difficile à gérer avec une boucle. Il s’agit donc d’un bon exemple d’utilisation de fonction récursive.

5.3.2 Tour de Hanoi

5.3.2.1 Rappel du principe

Déplacer une tour de n disques de taille différente d'une colonne à une autre en utilisant une seule colonne auxiliaire, selon la règle qu'on ne peut déplacer qu'un disque à la fois et chaque colonne a toujours ses disques en ordre décroissante de taille.

5.3.2.2 Algorithme

Procédure Hanoi(n {nombre de disques}, a, b, c {tours})

Début

Si n=0 alors exit

Hanoi(n-1,a, c, b)

Afficher(a vers b)

Hanoi (n-1, c, b, a)

Fin

L’appel initial peut être : Hanoi(64, 1, 2, 3)

5.3.3 Autres exemples

Ø Affichage en (disons) binaire : une boucle simple affiche les chiffres dans l'ordre inversé

Ø Boucles imbriquées de profondeur inconnue

Ø Algorithmes « diviser pour régner »

5.4 PARAMETRES ET VARIABLES LOCALES

Les paramètres et les variables déclarées localement dans une fonction (si elle est récursive ou non) sont créés au moment de l'appel/activation de la fonction et continuent à exister jusqu’à la sortie finale de l'appel.

Donc, quand une fonction s'appelle récursivement, à un moment de l'exécution du programme, il existe un nombre indéfini d'occurrences de ses paramètres et variables, mais, en général une seule occurrence accessible. Il y a possibilité d'échec parce que l'espace mémoire ne suffit pas pour toutes ces variables (segmentation fault en C).

5.5 EXEMPLES UTILISANT DES TABLEAUX

5.5.1 Listes multiplicatives

Procédure Suites(n, m, T) :

Début

Afficher (n, T[n], T[n-1], ...,T[1])

T[m+1]

Pour i de 1 à n/2 faire:

Si n%i=0 Suites(i, m+1, T)

Fin

5.5.2 Recherche d’un parcours de l’échiquier par un cavalier (et revenir au début)

Procédure Cavalier (i, j, n, T) {i, j : position– T tableau à double entrée – n : nombre de coups/cases parcourues}

Début

Selon que:

i:90 ou j :90 ou i>8 ou j>8 : exit

i=1 et j=1 et n=65 afficher FIN

cas T[i,j]>0 exit {Si =0 : alors la case n’a pas encore été parcourue}

Défaut: T[i, j]<-n

Cavalier (i-2, j-1, n+1, T)

...

Fin

...

7 PROGRAMMATION DYNAMIQUE

La programmation dynamique est une méthode générale de calcul de plusieurs valeurs dont la plupart dépendent d'autres. Elle est utilisée dans les cas où un algorithme simple naïf serait trop coûteux. Elle consiste à appliquer le principe évident qu'il est inutile de calculer la même chose deux (ou plusieurs) fois. Pour cela, on va stocker les résultats déjà calculés dans un tableau.

7.1 EXEMPLES

7.1.1 Un TRES petit exemple: la suite de Fibonacci

Nous avons vu que la méthode simple récursive n'est pas bonne. Une meilleure méthode consiste à stocker les résultats déjà calculés dans un tableau et ce, jusqu’à la valeur souhaitée :

1 1 2 3 5 ...

7.1.2 Les coefficients binomiaux

n !

Le nombre de façons de choisir m objets parmi n. On connaît tous la formule  . Une autre méthode

m! (n—m)!

consistant à voir si on laisse le premier objet , ou on le prend donne la relation suivante qui pourra être

7.1.3 Le nombre de partitions d'un entier

Supposons que l’on cherche le nombre de façons de diviser n objets identiques en (1 ou) plusieurs parties. Ce calcul peut paraître peu évident car il n’y a pas de récurrence directe. Mais si on ajoute un deuxième paramètre (la taille de la plus grande partie) on trouve une récurrence dont les résultats pourront être stockés : Part(n,max)=Y-i=1maxPart(n—max,i) sauf dans les cas n :5max .

7.1.4 Remarque intermédiaire

Une méthode naïve aurait été de calculer directement la récurrence (peut-être par une fonction récursive) sans utiliser de tableau. Le temps de calcul aurait été déterminé par le nombre de feuilles dans l'arbre de tous les calculs possibles. On peut arriver à des algorithmes qui mettent des siècles à calculer. La programmation dynamique peut réduire la durée de ces calculs à une fraction de seconde.

7.1.5 Un exemple (un peu) moins mathématique faire l'appoint

Je veux calculer le nombre de façons de faire un total de N centimes étant donné le nombre de types de pièces qui existent (n), le nombre que je possède et la valeur en centimes de chaque type (tableaux Nombre et Valeur indicés de 1 à n) .

Calcul de Nombre(Total,i) : le nombre de façons de faire un total de Total centimes en n'utilisant que les pièces des i premiers types :

Ù=0; // sera le nombre souhaite

u:=0; // le nombre de pieces de type i utilisees repeter

t:=t+Nom(Tot-u*Valeur[i],i-1);

u:=u+1;

jusqu'a u>Nombre[i] ou u*Valeur[i]>Tot

finrepeter;

(sauf les cas i=0 (Nombre(Total,0)=1 ou 0 selon si Total=0)

7.1.6 Un exemple avec temps, probabilité et stratégie: lancer des dés pour finir avec 100 points.

On lance des dés 20 fois. A chaque coup, on gagne le nombre de points sur la face visible du dé. On veut finir avec exactement 100 points. Le calcul consiste à déterminer la probabilité de réussir.

On calcule pour chaque p (nombre de points entre 0 et 100) et chaque c (nombre de coups entre 0 et 20) la probabilité de gagner si on veut encore p points après le c-ème coup, disons P(p,c) (sauf si c=20) :

Ø Sion lance un dé : probabilité =Ei=16 P(p—i,c+1)/6

Ø Si on lance deux dés: probabilité =Ei=212 P(p—i,c+1)×Prob[ipoints des 2 dés]

Ø Et on prend le maximum des deux comme valeur de P(p,c).

Ø Avec correction pour les cas où on essaie de calculer une valeur avec p < 0 !

7.1.7 Le problème du sac à dos discret

Etant donné un sac à dos et n objets de poids et valeur différents, quel est la valeur maximale d'un ensemble d'objets qui ne dépasse pas la capacité (en poids) du sac?

Supposons que l’on considère les objets en ordre et décide, pour chacun, si on le prend ou non. Quand on considère l'objet numéro i, la valeur de ce que l’on pourrai choisir parmi (i+1, n) dépend de la partie non utilisée de la capacité. On calcule donc pour chaque i et chaque capacité (entre 0 et la capacité initiale) une valeur maximale.

7.2 REMARQUE 1 : ECONOMISER L'ESPACE

Quand la récurrence donne la valeur de la colonne i du tableau comme fonction de la colonne i+1 (ou i—1) on n'est pas obligé de garder tout le tableau. Il suffit de garder deux colonnes à chaque moment (vrai pour les algorithmes de probabilités dans le graphe et le sac-à-dos par exemple)

Si, en outre, chaque élément d'une colonne ne dépend que des éléments de l'autre colonne qui sont en dessus (ou en dessous), il suffit de garder une colonne qui, à chaque moment, peut contenir une partie de l'ancienne colonne et une partie de la nouvelle. (vrai pour le sac-à-dos).

7.3 REMARQUE 2 : EVITER LES CALCULS INUTILES

Dans ce cas, la programmation dynamique comme décrite fait des calculs inutiles qui n'auraient pas été faits par la méthode récursive citée avant. Mais il est toujours vrai que cette méthode récursive fait BEAUCOUP plus de calculs parce qu'elle fait très souvent le même calcul plusieurs fois.

Il existe une méthode mixte qui ne fait que les calculs utiles et ne les fait qu'une fois: elle consiste à utiliser la structure récursive et un tableau; la première fois qu'un résultat est calculé il est inséré dans le tableau; les fois suivants, cette valeur est récupérée du tableau.

 8 STRUCTURES COMPLEXES

8.1 EXEMPLES

Ø Sous-ensembles d'un ensemble

Ø Arbres (binaires ou autres...)

Ø Graphes

Ø Permutations

Si un programme construit et utilise une seule structure, des méthodes ad hoc suffisent. Si le programme en utilise beaucoup, il faut penser à l'efficacité des opérations nécessaires.

8.2 OPERATIONS UTILES

Ø Boucler sur toutes les structures

Ø Stocker une structure dans l'espace minimum possible (code)

Ø Récupérer une structure stockée (décode)

Ø compter les structures

Remarque : Il faut souvent choisir une taille de structure (disons n), sinon on ne peut utiliser de fonction de boucle.

8.3 SOUS-ENSEMBLES ET PERMUTATIONS

Pas de gros problème :

Ø Sous-ensemble de n objets entier en 0...2n-1

Ø Permutation? considérer une permutation comme n entiers en 0...n-1 donne une représentation par un entier en 0...nn-1

Ø Mais tous les entiers ne correspondent pas à une permutation (nn entiers mais n! permutations)

Ø Interpréter suite a1, a2, ..., an avec 1 < =ai < =i: échanger les éléments n et an, ensuite n-1 et an-1 et ainsi de suite; chaque permutation est générée une seule fois.

Ø Facile à générer la suite des a à partir d'un entier en 0...n!-1

Ø (Remarquer existence d'algorithmes plus astucieux qui génèrent toutes les permutations avec une seule transposition à chaque itération)

8.4.1 Générer tous les arbres binaires (sans valeurs aux sommets) (de taille n)

Pour toute taille i possible du sous-arbre gauche (0...n-1) générer tous les sous-arbres gauches (taille i)i générer tous les sous-arbres droits (taille n-1-i)

Ø mais complication de programmation; il faut chaque combinaison possible d'un sous-arbre gauche et droit

Ø une solution: procédures init et prochain

8.4.2 Compter les arbres (binaires)

En ce cas il existe une formule simple mais...

Ø Soit T(n) le nombre d'arbres de taille n T(0)=1

Ø Considérer le nombre avec sous-arbre gauche de taille i : T(n)=z T ( ) * ( 1 )

i T n   i

Ø Programmation dynamique!

8.4.3 Coder un arbre (de taille n, entier en 0...T(n)-1)

Ø Ordonner les arbres selon la taille de leur sous-arbre gauche, et ensuite selon son code

 Ø code(A)=sommei=0taille(A.gauche)-1T(i)*T(n-1-i)+code(A.gauche)*T(A.droite)+code(A.droite)

Ø code(arbre.vide)=0

8.4.4 Décoder un arbre

Etant donné le code c d'un arbre de taille n, trouver :

Ø La taille du sous-arbre gauche

Ø Le code du sous-arbre gauche

Ø Le code du sous-arbre droit

Ø Et continuer récursivement

8.4.5 En général

Un algorithme de génération donne des algorithmes de codage décodage:

Ø Ordonner les objets selon les choix faits par l'algorithme

Ø considérer le nombre d'objets susceptibles d'être générés par chaque choix

Ø ajouter pour coder

Ø soustraire pour décoder

8.4.6 Des cas plus compliqués

Par exemple des arbres (non binaires), par exemple : Arbre = vide ou racine + ensemble de sous-arbres. Il s’agit d’ensemble, donc il nÿa pas d’ordre.

Pour simplifier, on considère les cas de degré max 2. Un arbre peut être alors représenté par un arbre binaire mais, de plusieurs façons!

8.5 REPRESENTATIONS CANONIQUES

Pour cela, on utilise une fonction qui permet de décider si une représentation est canonique : Récurrence pour le nombre d'arbres de taille n (n > 1):

n 2

G(n) = G(n-1) + E G i G n

( ) * ( 1 )

  i + (si n impair)G((n-1)/2) + ( G((n-1)/2)/2) .

Remarques :

Ø arrondir vers le bas dans la division n/2

Ø les quatre parties sont: un seul sous-arbre (forcément de taille n-1, deux sous-arbres de taille différente, le plus petit de taille i, deux sous-arbres identiques, deux sous-arbres différents de la même taille).

Ø Mêmes principes pour codage et décodage

8.6 DES PROBLEMES DIFFICILES

Les problèmes de codage et décodage sont parfois très compliqués. On peut citer comme exemple les graphes sur n sommets de degré maximum (par exemple) 3. On peut les générer en considérant chaque sommet à son tour et ajoutant un nombre d'arêtes jusqu'à 3 - degré actuel. Mais contraintes : pas d'arête à un sommet qui a déjà comme degré 3. Donc, on se retrouve avec une multitude de possibilités de compléter?

8.7 GRAPHES ET ISOMORPHISME!

Souvent, on considère deux structures comme identiques si on peut transformer l'une dans l'autre par une permutation des composants. On veut générer (ou compter) un représentant canonique de chaque classe d'équivalence. Mais les classes ne sont pas toutes de la même taille! Il est donc difficile de savoir si une structure est canonique ou de décider si deux structures sont isomorphes (Pb NP-complet).

 9 FONCTIONS SUR LES NOMBRES

9.1 LES NOMBRES ALEATOIRES

Il est souvent utile d'avoir une fonction qui produit des nombres apparemment aléatoires. La fonction rand() prédéfini peut faire se genre d’opération. A chaque fois qu’elle est appelée, elle donne un nombre différent (normalement en [0..N]). En réalité, elle n’est pas vraiment aléatoire mais on considère statistiquement que le résultat est convenable.

9.2 GENERATION DE NOMBRES

Ø On effectue un calcul simple comme xi+1 = xi*m + c (mod N) pour m bien choisi et N une puissance de 2.

Ø On divise par N pour un réel aléatoire en [0..1]

Ø On multiplie ensuite par R pour un réel en [0..R]

Ø Et on arrondit pour un entier en [0..R?1]

Attention toutefois : prendre xi mod. R est très mauvais si R est une puissance de 2!!

9.3 GENERATION DE STRUCTURES

La génération de structure consiste :

Ø Soit à générer un entier dans un bon intervalle et le décoder

Ø Soit à générer la structure itérativement avec un entier généré chaque fois que l'algorithme doit prendre une décision. La deuxième méthode plus facile à programmer et évite problèmes d'entiers trop grands.

9.3.1 Utilisation 0: interface avec l'extérieur

Ø programme de jeu: pour ne pas toujours jouer pareil

Ø joli écran

Ø réseau: attendre un temps aléatoire avant de réessayer un transfert après une collision.

9.3.2 Utilisation 1: tester un algorithme

Ø Générer un jeu de tests sur les cas aléatoires (Ne remplace pas les tests systématiques qui utilisent chaque branche du programme) Attention, se rappeler que :

Ø « Tester ne prouve jamais qu'un programme est sans fautes »

Ø Sauf pour ceux avec un nombre fini (et petit) de données possibles

9.3.3 Utilisation 2: calcul numérique de statistiques

On peut donner plusieurs exemples d’applications dans ce domaine:

Ø Calculer la superficie moyenne du polygone défini (enveloppe convexe) par 10 points choisis aléatoirement dans le carré [0,1][0,1].

Ø Générer, disons 1000, cas aléatoires et calculer la superficie de chacun Attention, cette utilisation peut être :

Ø dangereuse : car très faible probabilité qu’on soit loin du vrai moyen.

Ø très dangereuse : si la distribution est très bizarre (écart type très grand), presque certain d'être loin du vrai moyen.

9.3.4 Utilisation 3: Simulation de processus (naturels ...)

Exemples:

Ø Propagation d'une maladie

 Ø Résilience d'un réseau à des pannes

Ø Comportement d'une bourse où des commandes de ventes ou d'achats sont générées par des logiciels En fait, cette technique peut être utilisé partout où la complexité des interactions entre les composants d'un système exclut tout calcul direct.

9.3.5 Utilisation 4: algorithmes probabilistes

Quelques exemples :

Ø Algorithmes de calcul exact qui utilisent des choix aléatoires

Ø Algorithmes calculant une probabilité d'échec (mais, souvent, ils reconnaissent qu'un échec est arrivé). Donc, répéter plusieurs fois un évènement (avec choix différents) réduit exponentiellement la probabilité d'échec