Quelques exemples et exercices de programmation dynamique

Support de cours quelques exemples et exercices de programmation dynamique, tutoriel & guide de travaux pratiques algorithmes en pdf.

Soit k le nombre de balles rangÉes en Þle sur lÕÉtag•re telles que deux balles consécutives nÕaient jamais la m•me couleur, alors le nombre de balles dÕun m•me couleur est toujours k.
Preuve précise : utiliser le lemme des tiroirs, cÕest ˆ dire Òsi M chaussettes sont rangÉes parmi m tiroirs avec M > m, alors il existe un tiroir avec au moins deux chaussettesÓ. Ici dÉcouper lÕÉtag•re en k tiroirs disjoints qui sont des paires dÕemplacements consÉcutifs sur lÕÉtag•re. SÕ il y a plus de k balles dÕune m•me couleur, il en existe deux dans un m•me tiroir, cÕest ˆ dire   ici adjacentes sur lÕÉtag•re.
 Correction de l’algorithme : on montre des invariants (propriÉtÉs restants vraies pendant une phase de lÕalgorithme).
– Phase 1 –
Invariant 1 : si la corbeille nÕest pas vide, toutes les balles dans la corbeille ont la m•me couleur que la derni•re ballle sur lÕÉtag•re.
Preuve : montrer que si la prop. est vraie ˆ un instant donnÉ, elle reste vraie ˆ lÕÉtape suivante. Plusieurs cas peuvent se produire ici, vÉriÞer la conservation de la propriÉtÉ dans chaque cas (ˆ faire) :
Ð ajout dÕune balle diffÉrente de la derni•re et corbeille pleine …
Ð ajout dÕune balle diffÉrente de la derni•re et corbeille vide …
Ð ajout dÕune balle identique ˆ la derni•re …
Invariant 2 : sur lÕÉtag•re, il nÕy a jamais deux balles de m•me couleur c™te ˆ c™te.
Preuve : idem au cas par cas.
Fin de Phase 1 : soit C la couleur de la derni•re balle sur lÕÉtag•re. Les balles dÕautres couleurs sont dans les k 1 premi•res balles de lÕÉtag•re, o• k est le nombre de balles sur lÕÉtag•re et
k n. Comme il nÕy a pas deux balles adjacentes de m•me couleur, dÕapr•s la question 1,
le nombre de balles dÕune couleur diffÉrente de C est n 1 = n . Donc la seule couleur candidate pour •tre majoritaire est C.
– Phase 2 – vÉriÞe si C est bien majoritaire :
Ð Quand on retire une paire de balles, on en a toujours une de couleur C et lÕautre diffÉrente, donc C est majoritaire si et seulement si une majoritÉ de balles ˆ la Þn (Étag•re + corbeille) est de couleur C.
Ð Deux cas de Þn se prÉsentent :
Ð La phase 2 sÕarr•te car on a besoin dÕune balle de la corbeille mais la corbeille est vide. Dans ce cas, la derni•re balle sur lÕÉtag•re nÕest pas de couleur C et dÕapr•s la question 1, au plus la moitiÉ des balles restant sur lÕÉtag•re sont de couleur C, il nÕy a pas de majoritaire. Ok, cÕest bien ce que rÉpond lÕalgorithme.
Ð LÕalgorithme va jusquÕau bout de lÕÉtag•re, les balles restantes (sÕil en reste) sont dans la corbeille, elles sont toutes de couleur C. Donc C est majoritaire si et seulement si la corbeille est non vide, cÕest bien le test effectuÉ par lÕalgorithme.
Complexité :
Phase 1 : (n 1) comparaisons ( 1 car la premi•re balle est directement posÉe sur lÕÉtag•re).
Phase 2 : une comparaison par paire de balles ÉliminÉes, plus Éventuellement une comparaison
avec C pour la derni•re balle de lÕÉtag•re sÕil en reste une unique, soit n comparaisons ( 1 car au dÉbut de la phase 2, on sait que la derni•re balle sur lÕÉtag•re est de couleur C).
ComplexitÉ totale 3n comparaisons.
Optimalité
Tous les cas possibles sont bien reprÉsentÉs. Au dÉpart d = n et tous les troupeaux sont des singletons. Quels cas modiÞent d ?
Cas 1 : non.
Cas 2 : non (car -1 bin™me, +1 dans les troupeaux).
Cas 3 : non.
Cas 4(a) : oui, d diminue de 1 (mais les troupeaux restent des singletons).
Cas 4(b) : non.
Conclusion :
Ð Invariant d m (si d change, cÕest que d > m avec le cas 4(a) et alors d 1 m).
Ð d > m implique que tous les troupeaux sont des singletons.
Consistence des réponses de lÕadversaire ˆ tout moment.
Coloration (i) : correspond bien aux rÉponses donnÉes, car respecte les bin™mes (comparaisons inÉgales) et les troupeaux (comparaisons Égales). De plus les balles envoyÉes dans les gradins ont toujours engendrÉ la rÉponse NON aux comparaisons, ce qui fonctionne si leurs couleurs sont toutes diffÉrentes et diffÉrentes des couleurs des balles dans lÕar•ne.
Coloration (ii) : idem avec de plus le fait quÕune balle dans un bin™me nÕa jamais ÉtÉ comparÉe
ˆ quelquÕun dÕautre que son bin™me (donc pas de risque de contradiction avec les choix des couleurs ailleurs).
Un algorithme correct ne peut sÕarr•ter que si lÕar•ne ne contient quÕune composante connexe qui sera un troupeau de taille m.
Preuve par lÕabsurde : supposons que lÕar•ne contienne au moins deux composantes (ce qui implique n 2 et m 2). Par dÉÞnition de d, chaque troupeau contient < d balles. Chaque troupeau contient donc < m balles, car soit d = m, soit d > m et dÕapr•s la question 1 chaque troupeau est un singleton. La coloration (i) nÕa pas dÕÉlÉment majoritaire, mais la coloration (ii) a un ÉlÉment majoritaire (car d m). Donc aucun algorithme correct ne peut sÕarr•ter ˆ cet instant.
Conclusion : ˆ la Þn, il y a nÉcessairement une unique composante, nÉcessairement de taille d = m (par dÉÞnition de d et dÕapr•s la question 1 qui implique que d > m).
A tout moment, on a eu jusquà présent :
Ð Nombre de comparaisons inÉgales 2g + B, car il faut 2 comparaisons inÉgales pour mettre une balle dans les gradins (entrÉe dans un bin™me puis sortie du bin™me) et il y a B comparaisons inÉgales qui ont construit les bin™mes en place.
Ð Nombre de comparaisons Égales t T , car un troupeau i avec ti balles est connexe donc il a ti 1 ar•tes, soit ici ti 1 comparaisons Égales.
En Þn dÕalgorithme, dÕapr•s la question 3, g = n m, B = 0, t = m et T = 1. Donc, avec la question 4, il y a eu 2(n m) = 2 n 2 comparaisons inÉgales et m 1 = n  comparaisons Égales, soit au total 2  3n comparaisons.
Références bibliographiques
La prÉsentation du cours, et lÕexercice Matrices de Toeplitz, sÕinspirent du Cormen [2]. LÕexer-cice Recherche dÕun ÉlÉment majoritaire est tirÉ de Darte et Vaudenay [4].

Programmation dynamique

Pièces de Monnaies
On dispose de pi•ces en nombre illimitÉ, de valeurs 10, 5, 2 et 1. On veut arriver a une somme S avec le minimum de pi•ces.
Algorithme Glouton : Trier les types de pi•ces par valeurs dÉcroissantes. Pour chaque valeur de pi•ce, maximiser le nombre de pi•ces choisies. Plus formellement, soit R la somme restante, initialisÉe ˆ S. Pour chaque valeur vi , prendre ci = R pi•ces, et poser R R ci á vi .
Pour prouver lÕoptimalitÉ de lÕalgorithme glouton avec les valeurs 10, 5, 2 et 1 :
Ð Au plus une pi•ce de 5 (sinon une de 10)
Ð Au plus une pi•ce de 1 (sinon une de 2)
Ð Au plus deux pi•ces de 2 (sinon une de 5 et une de 1)
Ð Au plus quatre pi•ces qui ne sont pas des pi•ces de 10 (1 5 + 2 2 + 1 = 1 10), pour un
Ð total infÉrieur ou Égal ˆ 9
Le nombre de pi•ces de 10 est donc 10
Ð Conclure avec ce qui prÉc•de
Remarque : lÕalgorithme glouton nÕest pas optimal pour le jeu de pi•ces de valeurs (6, 4, 1) :
pour S = 8, le glouton renvoie 8 = 6 + 1 + 1 alors quÕon a 8 = 4 + 4.
Dans le cas gÉnÉral, on cherche m(S), le nombre minimum de pi•ces pour faire S avec des pi•ces de valeur (a1, a2, . . . , an ). Pour cela on introduit la fonction z telle que :
Ð z(T, i) = nombre minimum de pi•ces choisies parmi les i premi•res (a1, …, ai ) pour faire T
Ð on remarque que z(S, n) = m(S), on rÉsout un probl•me apparemment plus compliquÉ que le probl•me de dÉpart
Mais on a une relation de rÉcurrence :
z(T, i) = min z(T, i 1) i-•me pi•ce non utilisÉe
z(T vi , i) + 1 on a utilisÉ une fois (au moins) la i-•me pi•ce
Il faut initialiser la rÉcurrence correctement, par exemple en posant z(T, i) = 0 pour T 0 ou i = 0.
Comment calculer toutes les Sán valeurs de z dont on a besoin ? Un algorithme qui calcule par colonnes (boucle sur i externe, boucle sur T interne) permet de respecter les dÉpendances, i.e. de toujours avoir en membre droit des valeurs prÉcÉdemment obtenues. On obtient une complexitÉ en O(n S)., alors que lÕalgorithme glouton avait une complexitÉ en O(n log n) (lÕexÉcution est linÉaire, mais il faut auparavant trier les valeurs).
Remarque CaractÉriser les jeux de pi•ces pour lesquels lÕalgorithme glouton est optimal est un probl•me ouvert. Il est facile de trouver des catÉgories qui marchent (par exemple des pi•ces 1, B, B2, B3, . . . pour B 2) mais le cas gÉnÉral rÉsiste !
Le problème du sac à dos
On se donne n objets ayant pour valeurs c1, . . . , cn et pour poids (ou volume) w1, . . . , wn . Le but est de remplir le sac ˆ dos en maximisant i I ci , sous la contrainte i I wi W , o• W est la contenance maximale du sac
 En glouton
On va travailler sur le rapport ÒqualitÉ/prixÓ. On commence par trier les objets selon les ci wi dÉcroissants, puis on gloutonne en remplissant le sac par le plus grand ÉlÉment possible ˆ chaque tour.
Question : Est-ce optimal ? Non.
Le probl•me qui se pose est que lÕon travaille avec des ÉlÉments discrets non divisibles. Prenons un contre-exemple : si lÕon consid•re 3 objets, le 1er (ci /wi max) remplissant le sac ˆ lui seul (aucun autre objet ne rentre) et les 2•me et 3•me tels que c1 > c2, c1 > c3, mais que c2 +c3 > c1 et que les deux objets puissent rentrer ensemble dans le sac. Alors la solution donnÉe par glouton (remplissage par le premier objet) est sous-optimale, contrairement au remplissage par les objets 2 et 3. (W = 10) (w1 = 6; w2 = 5; w3 = 5) (c1 = 7; c2 = 5; c3 = 5) est un exemple dÕun tel cas de Þgure.
 Par programmation dynamique
AÞn de rÉsoudre le probl•me par une rÉcurrence, on va le compliquer. Un probl•me de remplissage plus complexe que celui de dÉpart est celui o• la taille du sac et le nombre dÕobjets ˆ employer sont arbitraires. Posons alors C(v, i) comme lÕexpression du meilleur coét pour remplir un sac de taille v avec les i premiers objets. RÉsoudre le probl•me de remplissage du sac de taille
W avec les n objets revient ˆ donner C(W, n).
La rÉcurrence : soit on a pris le dernier objet, soit on ne lÕa pas pris, dÕo•
C(v, i) = max C(v, i 1) dernier objet non considÉrÉ
C(v wi , i 1) + ci dernier objet pris
La solution optimale des sous-probl•mes va servir ˆ retrouver la solution optimale du problème global, sans que lÕon calcule jamais 2 fois la m•me valeur. Ceci implique par contre de respecter les dépendances du calcul.
Remarque Le coét de glouton est en O(n log n) (tri de n nombres) tandis que le coét du traitement en programmation dynamique est en O(nW )

1 Introduction : calcul de xn 
1.1 Énoncé du problème
1.2 Algorithme naïf
1.3 Méthode binaire
1.4 Méthode des facteurs
1.5 Arbre de Knuth
1.6 Résultats sur la complexité
1.7 Exercices
1.8 Références bibliographiques
2 Diviser pour régner 
2.1 Algorithme de Strassen
2.2 Produit de deux polynômes
2.3 Master theorem
2.4 Résolution des récurrences
2.5 Multiplication et inversion de matrices
2.6 Exercices
2.7 Références bibliographiques
3 Programmation dynamique 
3.1 Pièces de Monnaies
3.2 Le problème du sac à dos
3.3 Quelques exemples de programmation dynamique
3.4 Exercices
3.5 Références bibliographiques
4 Algorithmes gloutons 
4.1 Exemple du gymnase
4.2 Coloriage d’un graphe
4.3 Théorie des matroïdes
4.4 Ordonnancement
4.5 Exercices
4.6 Références bibliographiques
5 Tri 
5.1 Tri rapide
5.2 Tri fusion
5.3 Tri par tas : Heapsort
5.4 Complexité du tri
5.5 Exercices
5.6 Références bibliographiques
6 Graphes 
6.1 Définitions
6.2 Arbres
6.3 Structures de données pour les graphes
6.4 Accessibilité
6.5 Plus courts chemins
6.6 Parcours en largeur
6.7 Parcours en profondeur
6.8 Tri topologique
6.9 Forte connexité
6.10 Exercices
6.11 Références bibliographiques
7 Tables de hachage 
7.1 Recherche en table
7.2 Tables de hachage
7.3 Collisions séparées
7.4 Adressage ouvert
7.5 Références bibliographiques
8 Analyse amortie 
8.1 Compteur
8.2 Malloc primaire
8.3 Insertion ET suppression
8.4 Gestion des partitions
8.5 Références bibliographiques
9 NP-Complétude 
9.1 P versus NP
9.2 3-SAT
9.3 Clique
9.4 Couverture par les sommets
9.5 Circuit hamiltonien
9.6 Coloration de graphes
9.7 Exercices
9.8 Références bibliographiques
10 Algorithmes d’approximation 
10.1 Définition
10.2 Vertex cover
10.3 Voyageur de commerce : TSP
10.4 Bin Packing : BP
10.6 Exercices
10.7 Références bibliographiques

………

Télécharger le cours complet