Extrait du cours algorithmes avancés

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.
Pour ne pas faciliter le problème, on peut, à chaque coup, choisir de lancer un ou deux dés (de façon à maximiser la probabilité de réussite).
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) :
Si on lance un dé : probabilité =i=16P(pi,c+1)/6
Si on lance deux dés: probabilité =P(pi,c+1)×Prob[i points des 2 dés] Et on prend le maximum des deux comme valeur de P(p,c).
i=212 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
Il se peut que quelques éléments du tableau ne soient pas utilisés dans le calcul final qui nous intéresse (c’est-à dire ni directement ni indirectement) mais que la structure du problème soit trop irrégulière pour savoir à l’avance lesquels (par exemple dans le cas de la chaîne de Markov, il est inutile de calculer la probabilité de réussir en 90 transitions à partir de l’état j s’il n’est pas possible d’arriver à cet état en 10 transitions de l’état initial).
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…n n-1
– Mais tous les entiers ne correspondent pas à une permutation (nn entiers mais n! permutations)
– Interpréter suite a1, a2, …, n avec 1 <=ai <=i: échanger les éléments n et a n, ensuite n-1 et a -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 EXEMPLE SUR LES ARBRES
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)=
– Programmation dynamique!
……..

Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)
Algorithmes avancés (228 KO) (Cours PDF)