[PDF] [PDF] Programmation Dynamique - Inria

[PDF] Programmation Dynamique - Inria

Problèmes de Décision / d'Optimisation 3 Rendu de Monnaie : Algorithme Glouton 4 Rendu de Monnaie : Algorithme Optimal 1 5 Programmation dynamique

[PDF] Rendu de monnaie

28 jui 2013 · Le problème du rendu de monnaie consiste, étant donné s, à calculer m(s) On cherche d'abord un algorithme simple et efficace capable 

[PDF] corrigé, pdf - DIU-EIL

programmation dynamique consiste à résoudre un problème en le un algorithme glouton pour résoudre le problème du rendu de pièces de monnaie

[PDF] A 1 Problème du rendu de monnaie

1 Problème du rendu de monnaie 1 1 Distributeur de boissons Dans un distributeur de boissons, le monnayeur utilise des pièces de valeurs faciales : 0, 01 €, 0 

[PDF] programmation dynamique

Problème du sac à dos (8 4) 10 5 que possible à Trois Rivières, on risque de tomber en panne d'essence Analogue à l'algorithme pour rendre la monnaie

[PDF] 1 Rendre la monnaie

1 Rendre la monnaie On se propose d'écrire un algorithme permettant d'obtenir la suite des billets totalisant une somme donnée (dont on suppose qu'elle est 

[PDF] Algorithmes gloutons

III- Le problème du rendu de monnaie : 1 Position du problème : On considère un système de pièces de monnaie La question est la suivante : quel est le nombre 

[PDF] Programmation dynamique - NUMERICABLE

Adapter enfin l'algorithme pour permettre de construire un x une fois f(x) calculé 1 Le problème du rendu de monnaie Les problèmes de combinatoire ont une 

[PDF] Programmation dynamique - mediaeduscoleducationfr - Ministère

Le problème du rendu de monnaie 1 1 Retour sur l'algorithme glouton On a déjà vu en classe de première qu'un algorithme glouton pouvait donner une 

[PDF] fragment 128 questions

[PDF] feuillet d'hypnos 128 analyse

[PDF] brevet blanc fragment 128 des feuillets d'hypnos

[PDF] feuillets d'hypnos texte intégral

[PDF] poésie dimanche rené de obaldia

[PDF] poésie dimanche jacques prévert

[PDF] la cromagnonne et le cosmonaute (poésie)

[PDF] otto dix la tranchée lieu de conservation

[PDF] poésie de rené de obaldia moi j'irai dans la lune

[PDF] poesie dimanche charlotte fait de la compote

[PDF] rené de obaldia innocentines

[PDF] gestion des conflits interpersonnels

[PDF] gestion des conflits ppt

[PDF] gestion de conflits au travail

[PDF] rené descartes biographie pdf

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Introduction à l"algorithmique

et la complexité(et un peu de CAML)

Programmation Dynamique

Nicolas Nisse

Université Côte d"Azur, Inria, CNRS, I3S, France Cours dispensés en MPSI (option Info) au CIV, depuis 2011-

N. Nisse

Programmation Dynamique1/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Outline1Problème de rendu de Monnaie

2Problèmes de Décision / d"Optimisation

3Rendu de Monnaie : Algorithme Glouton

4Rendu de Monnaie : Algorithme Optimal 1

5Programmation dynamique

6Rendu de Monnaie : Algorithme Optimal 2

7Problème du Sac-à-Dos

N. NisseProgrammation Dynamique2/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Problème de rendu de Monnaie

Supposons que vous êtes un commerçant. Un client vous achête pour 127;36ede

marchandise. Il vous tend un billet de 200e.Pour lui rendre la monnaie, vous disposez de pièces de 1;5;10;20;50 centimes d"euros, de

pièces de 1 et 2eet de billets de 5;10;20;50 et 100e.Pour ne pas déplaire au client (en surchargeant ses poches avec 7264 pièces de 0:01e) :

Vous voulez lui rendre le moins de pièces/billets que possible.Que lui rendez vous ?

N. NisseProgrammation Dynamique3/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Problème de rendu de Monnaie (formalisation)Formaliser (Décrire mathématiquement)un prob lèmeconcret f aitpar tied "unedes tâches les

plus importantes (et souvent difficiles) des chercheurs.Prenons l"exemple du problème de rendu de monnaie.

Entrée1:Un montantM2Rà rendre (en euro)(M=200127:36 dans l"ex. précédent) Entrée2:Un système de monnaie(x1 xr)2Rr(les "types" de pièces/billets dont on dispose, e.g., 1;2;5;10;20 euros) Sortie :Décider de ce que l"on rend au client : pour chaque typeide pièces/billets (1ir), quel est le nombrekide pièces/billets de typei(de valeurxi) rendus on au client ? Contrainte :Il faut rendre au client ce qu"on lui doit : la somme des pièces/billets qu"on lui rend doit être égale àM:å 1irk ixi=M.

Optimisation :On veut minimiser le nombreå

1irk ide pièces/billets rendus.Problème de rendu de Monnaie

Étant donnésM2Ret(x1;;xr)2Rr

Calculer(k1;;kr)2Nrtels queå

1irk isoit minimum sous réserve queå 1irk ixi=M.N. NisseProgrammation Dynamique4/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Outline1Problème de rendu de Monnaie

2Problèmes de Décision / d"Optimisation

3Rendu de Monnaie : Algorithme Glouton

4Rendu de Monnaie : Algorithme Optimal 1

5Programmation dynamique

6Rendu de Monnaie : Algorithme Optimal 2

7Problème du Sac-à-Dos

N. NisseProgrammation Dynamique5/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Problèmes de Décision / d"OptimisationProblème de rendu de Monnaie

Étant donnésM2R+et(x1;;xr)2(R+)r

Calculer(k1;;kr)2Nrtels queå

1irk isoit minimum sous réserve queå 1irk ixi=M.Exercices :trouver une (des) solutions aux problèmes suivants M=13 et(x1=1;x2=2;x3=3;x4=7;x5=9)(k1) = (13)(13 pièces de 1e)(solutionvalidemais pasoptimale)

(k3;k4) = (2;1)(2 pièces de 3eet 1 de 7e)(solutionoptimale, i.e., minimisant le nombre de pièces)

(k2;k5) = (2;1)(2 pièces de 2eet 1 de 9e)Prouvez que c"est une solutionoptimale

M=73 et(x1=4;x2=12).Toute combinaison linéaire de pièces de valeurx1etx2donne une valeur paire. Il n"y a

donc pas de solution valide (satisfaisant la contrainte

åkixi=M).Contrairement aux problèmes étudiés précédement (tri d"un tableau, calcul dexc...), où il y avait

toujours une unique solution, dans les problèmes d"optimisation, il peut y avoir des solutions valides (satisf aisantles contr aintes)non optimales , une ou plusieurs solutio ns(v alides) optimales (minimisant/maximisant une cer tainemesure), v oire pas du tou tde solution v alide

.Décidersi un problème admet une solution (valide) peut être "difficile" (voire "non-décidable").

Dans la suite, nous nous assurerons qu"il en existe toujours (à vous de le vérifier). Pour le problème du rendu de Monnaie, il est suffisant de supposer que M2Net

(x1=1;x2;;xn)2Nnpour qu"il y ait toujours (au moins) une solution valide( prouvez le !).N. NisseProgrammation Dynamique6/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Problèmes de Décision / d"OptimisationProblème de rendu de Monnaie

Étant donnésM2R+et(x1;;xr)2(R+)r

Calculer(k1;;kr)2Nrtels queå

1irk isoit minimum sous réserve queå 1irk ixi=M.Exercices :trouver une (des) solutions aux problèmes suivants M=13 et(x1=1;x2=2;x3=3;x4=7;x5=9)(k1) = (13)(13 pièces de 1e)(solutionvalidemais pasoptimale)

(k3;k4) = (2;1)(2 pièces de 3eet 1 de 7e)(solutionoptimale, i.e., minimisant le nombre de pièces)

(k2;k5) = (2;1)(2 pièces de 2eet 1 de 9e)Prouvez que c"est une solutionoptimale

M=73 et(x1=4;x2=12).Toute combinaison linéaire de pièces de valeurx1etx2donne une valeur paire. Il n"y a

donc pas de solution valide (satisfaisant la contrainte

åkixi=M).Contrairement aux problèmes étudiés précédement (tri d"un tableau, calcul dexc...), où il y avait

toujours une unique solution, dans les problèmes d"optimisation, il peut y avoir des solutions valides (satisf aisantles contr aintes)non optimales , une ou plusieurs solutio ns(v alides) optimales (minimisant/maximisant une cer tainemesure), v oire pas du tou tde solution v alide

.Décidersi un problème admet une solution (valide) peut être "difficile" (voire "non-décidable").

Dans la suite, nous nous assurerons qu"il en existe toujours (à vous de le vérifier). Pour le problème du rendu de Monnaie, il est suffisant de supposer que M2Net

(x1=1;x2;;xn)2Nnpour qu"il y ait toujours (au moins) une solution valide( prouvez le !).N. NisseProgrammation Dynamique6/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Problèmes de Décision / d"OptimisationProblème de rendu de Monnaie

Étant donnésM2R+et(x1;;xr)2(R+)r

Calculer(k1;;kr)2Nrtels queå

1irk isoit minimum sous réserve queå 1irk ixi=M.Exercices :trouver une (des) solutions aux problèmes suivants M=13 et(x1=1;x2=2;x3=3;x4=7;x5=9)(k1) = (13)(13 pièces de 1e)(solutionvalidemais pasoptimale)

(k3;k4) = (2;1)(2 pièces de 3eet 1 de 7e)(solutionoptimale, i.e., minimisant le nombre de pièces)

(k2;k5) = (2;1)(2 pièces de 2eet 1 de 9e)Prouvez que c"est une solutionoptimale

M=73 et(x1=4;x2=12).Toute combinaison linéaire de pièces de valeurx1etx2donne une valeur paire. Il n"y a

donc pas de solution valide (satisfaisant la contrainte

åkixi=M).Contrairement aux problèmes étudiés précédement (tri d"un tableau, calcul dexc...), où il y avait

toujours une unique solution, dans les problèmes d"optimisation, il peut y avoir des solutions valides (satisf aisantles contr aintes)non optimales , une ou plusieurs solutio ns(v alides) optimales (minimisant/maximisant une cer tainemesure), v oire pas du tou tde solution v alide

.Décidersi un problème admet une solution (valide) peut être "difficile" (voire "non-décidable").

Dans la suite, nous nous assurerons qu"il en existe toujours (à vous de le vérifier). Pour le problème du rendu de Monnaie, il est suffisant de supposer que M2Net

(x1=1;x2;;xn)2Nnpour qu"il y ait toujours (au moins) une solution valide( prouvez le !).N. NisseProgrammation Dynamique6/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Outline1Problème de rendu de Monnaie

2Problèmes de Décision / d"Optimisation

3Rendu de Monnaie : Algorithme Glouton

4Rendu de Monnaie : Algorithme Optimal 1

5Programmation dynamique

6Rendu de Monnaie : Algorithme Optimal 2

7Problème du Sac-à-Dos

N. NisseProgrammation Dynamique7/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Rendu de Monnaie : Algorithme Glouton (1/2)

Résolvez l"exemple suivant :M=78 et(x1;;x5) = (1;2;5;10;50). La solution que vous avez (probablement) proposée est(k1;;k5) = (1;1;1;2;1), i.e., une piéce de 1;2;5 et 50eet 2 pièces de 10e.Cette solution (avec 6 pièces) est-elle optimale ?

Toute solution sans pièce de valeurx5utilise au moinsdM=x4e=8 pièces (prouvez le). Donc, toute solution utilisant moins que

8 pièces doit utiliser une pièce de typex5. Ainsi, le nombre minimum de pièce pour rendreMvaut 1 plus le nombre minimum de

pièce pour rendreMx5. En répétant récursivement cet argument, prouvez qu"il s"agit d"une solution optimale.Quel algorithme avez vous (probablement) utilisé ?

Rendre la pièce de plus grande valeurxiM. Il resteMxià rendre. SiMxi=0 alors, c"est fini, sinon, recommencer avec la nouvelle valeurMxi>0 à rendre.Il s"agit d"un algorithmeglouton ("g reedy"en anglais). À chaque étape (ici, à chaque fois qu"on rend une pièce), on choisit la solution qui semble localement (à cette étape) la meilleure (ici, on rend la pièce qui dimin uela somme à rendre au maximum).L"algorithme gloutontrouv et"il toujours une solution optimale pour le problème de rendu de monnaie ?Correction : sim2Net(x1=1MonnaieGreedydonne une solution valide !! Complexité :O(n+m)N. NisseProgrammation Dynamique8/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Rendu de Monnaie : Algorithme Glouton (1/2)

Résolvez l"exemple suivant :M=78 et(x1;;x5) = (1;2;5;10;50).La solution que vous avez (probablement) proposée est(k1;;k5) = (1;1;1;2;1), i.e., une

piéce de 1;2;5 et 50eet 2 pièces de 10e.Cette solution (avec 6 pièces) est-elle optimale ?

Toute solution sans pièce de valeurx5utilise au moinsdM=x4e=8 pièces (prouvez le). Donc, toute solution utilisant moins que

8 pièces doit utiliser une pièce de typex5. Ainsi, le nombre minimum de pièce pour rendreMvaut 1 plus le nombre minimum de

pièce pour rendreMx5. En répétant récursivement cet argument, prouvez qu"il s"agit d"une solution optimale.Quel algorithme avez vous (probablement) utilisé ?

Rendre la pièce de plus grande valeurxiM. Il resteMxià rendre. SiMxi=0 alors, c"est fini, sinon, recommencer avec la nouvelle valeurMxi>0 à rendre.Il s"agit d"un algorithmeglouton ("g reedy"en anglais). À chaque étape (ici, à chaque fois qu"on rend une pièce), on choisit la solution qui semble localement (à cette étape) la meilleure (ici, on rend la pièce qui dimin uela somme à rendre au maximum).L"algorithme gloutontrouv et"il toujours une solution optimale pour le problème de rendu de monnaie ?Correction : sim2Net(x1=1MonnaieGreedydonne une solution valide !! Complexité :O(n+m)N. NisseProgrammation Dynamique8/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Rendu de Monnaie : Algorithme Glouton (1/2)

Résolvez l"exemple suivant :M=78 et(x1;;x5) = (1;2;5;10;50).La solution que vous avez (probablement) proposée est(k1;;k5) = (1;1;1;2;1), i.e., une

piéce de 1;2;5 et 50eet 2 pièces de 10e.Cette solution (avec 6 pièces) est-elle optimale ?

Toute solution sans pièce de valeurx5utilise au moinsdM=x4e=8 pièces (prouvez le). Donc, toute solution utilisant moins que

8 pièces doit utiliser une pièce de typex5. Ainsi, le nombre minimum de pièce pour rendreMvaut 1 plus le nombre minimum de

pièce pour rendreMx5. En répétant récursivement cet argument, prouvez qu"il s"agit d"une solution optimale.Quel algorithme avez vous (probablement) utilisé ?

Rendre la pièce de plus grande valeurxiM. Il resteMxià rendre. SiMxi=0 alors, c"est fini, sinon, recommencer avec la nouvelle valeurMxi>0 à rendre.Il s"agit d"un algorithmeglouton ("g reedy"en anglais). À chaque étape (ici, à chaque fois qu"on rend une pièce), on choisit la solution qui semble localement (à cette étape) la meilleure (ici, on rend la pièce qui dimin uela somme à rendre au maximum).L"algorithme gloutontrouv et"il toujours une solution optimale pour le problème de rendu de monnaie ?Correction : sim2Net(x1=1MonnaieGreedydonne une solution valide !! Complexité :O(n+m)N. NisseProgrammation Dynamique8/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Rendu de Monnaie : Algorithme Glouton (1/2)

Résolvez l"exemple suivant :M=78 et(x1;;x5) = (1;2;5;10;50).La solution que vous avez (probablement) proposée est(k1;;k5) = (1;1;1;2;1), i.e., une

piéce de 1;2;5 et 50eet 2 pièces de 10e.Cette solution (avec 6 pièces) est-elle optimale ?

Toute solution sans pièce de valeurx5utilise au moinsdM=x4e=8 pièces (prouvez le). Donc, toute solution utilisant moins que

8 pièces doit utiliser une pièce de typex5. Ainsi, le nombre minimum de pièce pour rendreMvaut 1 plus le nombre minimum de

pièce pour rendreMx5. En répétant récursivement cet argument, prouvez qu"il s"agit d"une solution optimale.Quel algorithme avez vous (probablement) utilisé ?

Rendre la pièce de plus grande valeurxiM. Il resteMxià rendre. SiMxi=0 alors, c"est fini, sinon, recommencer avec la nouvelle valeurMxi>0 à rendre.Il s"agit d"un algorithmeglouton ("g reedy"en anglais). À chaque étape (ici, à chaque fois qu"on rend une pièce), on choisit la solution qui semble localement (à cette étape) la meilleure (ici, on rend la pièce qui dimin uela somme à rendre au maximum).L"algorithme gloutontrouv et"il toujours une solution optimale pour le problème de rendu de monnaie ?Correction : sim2Net(x1=1MonnaieGreedydonne une solution valide !! Complexité :O(n+m)N. NisseProgrammation Dynamique8/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Rendu de Monnaie : Algorithme Glouton (1/2)

Résolvez l"exemple suivant :M=78 et(x1;;x5) = (1;2;5;10;50).La solution que vous avez (probablement) proposée est(k1;;k5) = (1;1;1;2;1), i.e., une

piéce de 1;2;5 et 50eet 2 pièces de 10e.Cette solution (avec 6 pièces) est-elle optimale ?

Toute solution sans pièce de valeurx5utilise au moinsdM=x4e=8 pièces (prouvez le). Donc, toute solution utilisant moins que

8 pièces doit utiliser une pièce de typex5. Ainsi, le nombre minimum de pièce pour rendreMvaut 1 plus le nombre minimum de

pièce pour rendreMx5. En répétant récursivement cet argument, prouvez qu"il s"agit d"une solution optimale.Quel algorithme avez vous (probablement) utilisé ?

Rendre la pièce de plus grande valeurxiM. Il resteMxià rendre. SiMxi=0 alors, c"est fini, sinon, recommencer avec la nouvelle valeurMxi>0 à rendre.Il s"agit d"un algorithmeglouton ("g reedy"en anglais). À chaque étape (ici, à chaque fois qu"on rend une pièce), on choisit la solution qui semble localement (à cette étape) la meilleure (ici, on rend la pièce qui dimin uela somme à rendre au maximum).L"algorithme gloutontrouv et"il toujours une solution optimale pour le problème de rendu de monnaie ?Correction : sim2Net(x1=1MonnaieGreedydonne une solution valide !! Complexité :O(n+m)N. NisseProgrammation Dynamique8/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Rendu de Monnaie : Algorithme Glouton (1/2)

Résolvez l"exemple suivant :M=78 et(x1;;x5) = (1;2;5;10;50).La solution que vous avez (probablement) proposée est(k1;;k5) = (1;1;1;2;1), i.e., une

piéce de 1;2;5 et 50eet 2 pièces de 10e.Cette solution (avec 6 pièces) est-elle optimale ?

Toute solution sans pièce de valeurx5utilise au moinsdM=x4e=8 pièces (prouvez le). Donc, toute solution utilisant moins que

8 pièces doit utiliser une pièce de typex5. Ainsi, le nombre minimum de pièce pour rendreMvaut 1 plus le nombre minimum de

pièce pour rendreMx5. En répétant récursivement cet argument, prouvez qu"il s"agit d"une solution optimale.Quel algorithme avez vous (probablement) utilisé ?

Rendre la pièce de plus grande valeurxiM. Il resteMxià rendre. SiMxi=0 alors, c"est fini, sinon, recommencer avec la nouvelle valeurMxi>0 à rendre.Il s"agit d"un algorithmeglouton ("g reedy"en anglais). À chaque étape (ici, à chaque fois qu"on rend une pièce), on choisit la solution qui semble localement (à cette étape) la meilleure (ici, on rend la pièce qui dimin uela somme à rendre au maximum).L"algorithme gloutontrouv et"il toujours une solution optimale pour le problème de rendu de monnaie ?Correction : sim2Net(x1=1MonnaieGreedydonne une solution valide !! Complexité :O(n+m)N. NisseProgrammation Dynamique8/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Rendu de Monnaie : Algorithme Glouton (2/2)

Nouvel exemple :M=6 et(x1;x2;x3) = (1;3;4).Donnez le résultat obtenu par l"algorithme glouton (du slide précédent) :

Donnez une solution optimale :Remarque :Un systèmeS= (x1;;xn)est ditcanoniquesi l"algorithme glouton produit

toujours (pour toutM) une solution optimale pourS. Prouvez que, tout système avec 2 éléments (n=2) est canonique. Pourn3, on ne sait pas déterminer "simplement" (en gros, sans tester toutes les possibilités)

si un système avecnéléments est canonique.Puisque l"algorithme glouton n"est pas forcément optimal, nous allons décrire dans la suite 2

algorithmes, basés sur la programmation dynamique, qui donnent toujours une solution optimale pour le problème de rendu de monnaie.

N. NisseProgrammation Dynamique9/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Rendu de Monnaie : Algorithme Glouton (2/2)

Nouvel exemple :M=6 et(x1;x2;x3) = (1;3;4).Donnez le résultat obtenu par l"algorithme glouton (du slide précédent) :(k1;k2;k3) = (2;0;1)

Donnez une solution optimale :(k1;k2;k3) =( 0;2;0)L"algorithme glouton ne donne donc pas toujours une solution optimale !!

Remarque :Un systèmeS= (x1;;xn)est ditcanoniquesi l"algorithme glouton produit toujours (pour toutM) une solution optimale pourS. Prouvez que, tout système avec 2 éléments (n=2) est canonique. Pourn3, on ne sait pas déterminer "simplement" (en gros, sans tester toutes les possibilités)

si un système avecnéléments est canonique.Puisque l"algorithme glouton n"est pas forcément optimal, nous allons décrire dans la suite 2

algorithmes, basés sur la programmation dynamique, qui donnent toujours une solution optimale pour le problème de rendu de monnaie.

N. NisseProgrammation Dynamique9/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Rendu de Monnaie : Algorithme Glouton (2/2)

Nouvel exemple :M=6 et(x1;x2;x3) = (1;3;4).Donnez le résultat obtenu par l"algorithme glouton (du slide précédent) :(k1;k2;k3) = (2;0;1)

Donnez une solution optimale :(k1;k2;k3) =( 0;2;0)L"algorithme glouton ne donne donc pas toujours une solution optimale !!

Remarque :Un systèmeS= (x1;;xn)est ditcanoniquesi l"algorithme glouton produit toujours (pour toutM) une solution optimale pourS. Prouvez que, tout système avec 2 éléments (n=2) est canonique. Pourn3, on ne sait pas déterminer "simplement" (en gros, sans tester toutes les possibilités)

si un système avecnéléments est canonique.Puisque l"algorithme glouton n"est pas forcément optimal, nous allons décrire dans la suite 2

algorithmes, basés sur la programmation dynamique, qui donnent toujours une solution optimale pour le problème de rendu de monnaie.

N. NisseProgrammation Dynamique9/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Rendu de Monnaie : Algorithme Glouton (2/2)

Nouvel exemple :M=6 et(x1;x2;x3) = (1;3;4).Donnez le résultat obtenu par l"algorithme glouton (du slide précédent) :(k1;k2;k3) = (2;0;1)

Donnez une solution optimale :(k1;k2;k3) =( 0;2;0)L"algorithme glouton ne donne donc pas toujours une solution optimale !!

Remarque :Un systèmeS= (x1;;xn)est ditcanoniquesi l"algorithme glouton produit toujours (pour toutM) une solution optimale pourS. Prouvez que, tout système avec 2 éléments (n=2) est canonique. Pourn3, on ne sait pas déterminer "simplement" (en gros, sans tester toutes les possibilités)

si un système avecnéléments est canonique.Puisque l"algorithme glouton n"est pas forcément optimal, nous allons décrire dans la suite 2

algorithmes, basés sur la programmation dynamique, qui donnent toujours une solution optimale pour le problème de rendu de monnaie.

N. NisseProgrammation Dynamique9/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Outline1Problème de rendu de Monnaie

2Problèmes de Décision / d"Optimisation

3Rendu de Monnaie : Algorithme Glouton

4Rendu de Monnaie : Algorithme Optimal 1

5Programmation dynamique

6Rendu de Monnaie : Algorithme Optimal 2

7Problème du Sac-à-Dos

N. NisseProgrammation Dynamique10/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Rendu de Monnaie : Algorithme Optimal 1

SoitM;n2NetSn= (x1=1On noteValeurOpt(M;n)= min(k1;;kn)2Nnfå 1ink ijå 1ink ixi=Mgla valeur (nombre de pièces) d"une solution optimale pour l"instance(M;Sn).Théorème :

ValeurOpt(M;1) =M;

8n>1, sixn>MalorsValeurOpt(M;n) =ValeurOpt(M;n1), sinon

ValeurOpt(M;n) =minfValeurOpt(M;n1);1+ValeurOpt(Mxn;n)gPreuve :Les 2 premiers points sont évidents, donc supposons quen>1 etMxn.

Le 3 mepoint se prouve pardoub leinégalité . Toute solution(k1;;kn1)valide pour(M;Sn1)(i.e.,å

1i DoncValeurOpt(M;n)ValeurOpt(M;n1). Par ailleurs, toute solution(k1;;kn)valide pour(Mxn;Sn)(telle que

1inkixi=Mxn) permet d"obtenir une solution(k1;;kn1;kn+1)valide pour(M;Sn)en ajoutant une pièce de valeur

x n. DoncValeurOpt(M;n)1+ValeurOpt(Mxn;n). On en déduit queValeurOpt(M;n)minfValeurOpt(M;n1);1+ValeurOpt(Mxn;n)g. (on utilise le fait que si (acetbc) alors minfa;bg c). Soit(k1;;kn)une solution optimale pour(M;Sn). Sikn=0, c"est une solution valide pour(M;Sn1)et donc

Valeur

Opt(M;n1)ValeurOpt(M;n). Sinon (sikn>0),(k1;;kn1;kn1)est une solution valide pour(Mxn;Sn)et doncValeurOpt(Mxn;n)ValeurOpt(M;n)1.

Ainsi,

min fValeurOpt(M;n1);1+ValeurOpt(Mxn;n)g ValeurOpt(M;n). (pour la dernière étape, on utilise le fait que si (acoubc) alors minfa;bg c).

N. Nisse

Programmation Dynamique11/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Rendu de Monnaie : Algorithme Optimal 1

Pour tout 1mMet 1n0n, calculons récursivementValeurOpt(m;n0)en nous servant

du théorème précédent pour calculer un terme en fonction des précédents.Création d'un tableau res_value qui contiendra les valeurs optimales :

res_value.(m).(n-1) = Valeur_opt(m,n) (attention au décalage d'indice pour n) Création d'un tableau res_vector qui contiendra les solutions optimales : res_vector.(m).(n-1) = [|k1,...kn|] tel que sum(k_i)= Valeur_opt(m,n) (attention au décalage d'indice pour n)}

Cas où

Valeur_opt(i,j)=Valeur_opt(i,j-1)

calcul de Valeur_opt(i,j) (et d'un vecteur correspondant) pour tout 2<=i<=m et 1<=j<=n-1 en utilisant les valeurs précédentes (dans l'ordre lexicographique) déjà calculées

Initialisation :

mise à jour de Valeur_opt(i,1)=i pour tout i<=m

Cas où

Valeur_opt(i,j)=1+Valeur_opt(i-xj,j)

{Terminaison :doub leboucles imbr iquées

Correction :

preuv epar récurrence sur (i;j)(en se servant du théorème précédent) qu"après l"itération(i;j), res_value:(i):(j) =ValeurOpt(i;j+1).

Complexité :

doub leboucles imbr iquéesO(nM).N. NisseProgrammation Dynamique12/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Outline1Problème de rendu de Monnaie

2Problèmes de Décision / d"Optimisation

3Rendu de Monnaie : Algorithme Glouton

4Rendu de Monnaie : Algorithme Optimal 1

5Programmation dynamique

6Rendu de Monnaie : Algorithme Optimal 2

7Problème du Sac-à-Dos

N. NisseProgrammation Dynamique13/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Programmation dynamiqueProgrammation dynamique(def. de Wikipedia)Méthode algorithmique pour résoudre des problèmes d"optimisation. Elle consiste à résoudre un

problème en le décomposant en sous-problèmes, puis à résoudre les sous-problèmes, des plus

petits aux plus grands en stockant ( mémoïsation

) les résultats intermédiaires.Remarque 1 :"programmation" signifie ici "planification" ou "ordonnancement" (pas du tout

"implémentation") : la programmation dynamique cherche à organiser les calculs d"une f açon "efficace". Remarque 2 :la technique de "Diviser pour régner" fait partie des méthodes par programmation

dynamique. Une différence est que dans "Diviser pour régner", les sous-problèmes sont résolus

indépendamment les uns des autres. La programmation dynamique présente l"avantage de ne résoudre qu"une seule fois chaque sous-problème , ce qui n"est pas forcément le cas dans "Diviser pour régner". Par exemple, pour trier le tableau[j4;3;5;7;13;2;4;3j], l"algorithme tri-fusion triera deux fois le tableau[j4;3j]. Exemple :Dans le problème duRendu de Monnaie , pour calculerValeurOpt(M;n), nous avons calculéValeurOpt(m;n0)pour toutmValeur

Opt(M;n)à partir des valeurs préalablement calculées et stoquées. Notez que chaque sous-problèmeValeurOpt(m;n0)n"est calculé qu"une fois.

N. Nisse

Programmation Dynamique14/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Outline1Problème de rendu de Monnaie

2Problèmes de Décision / d"Optimisation

3Rendu de Monnaie : Algorithme Glouton

4Rendu de Monnaie : Algorithme Optimal 1

5Programmation dynamique

6Rendu de Monnaie : Algorithme Optimal 2

7Problème du Sac-à-Dos

N. NisseProgrammation Dynamique15/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Rendu de Monnaie : Algorithme Optimal 2

SoitM;n2NetSn= (x1=1On noteValeurOpt(M;n)= min(k1;;kn)2Nnfå 1ink ijå 1ink ixi=Mgla valeur (nombre de pièces) d"une solution optimale pour l"instance(M;Sn).Théorème :

ValeurOpt(0;n) =0;

8M>0,ValeurOpt(M;n) =1+min1in;Mxi0ValeurOpt(Mxi;n)Preuve 1 :Application récursive de la preuve du Slide 11.

Preuve 2 :Le 1erpoint est évident, donc supposons queM>0. Le 2ndpoint se prouve pardoub leinégalité .

Toute solution(k1;;kn)optimale pour(M;n)(en particulier,å

1i0 (pour 1jnavecMxj) ,

donne une solution valide(k1;;kj1;kj1;kj+1;;kn1)pour(Mxj;n). Donc

Valeur

Opt(M;n)1+min1jn;Mxj0ValeurOpt(Mxj;n).

Par ailleurs, pour tout 1jntel queMxj0, toute solution(kj

1;;kjn)valide pour(Mxj;n)(telle que

1inkj ixi=Mxj) permet d"obtenir une solution(kj 1;;kj j1;kj j+1;kj j+1;;kj n1)valide pour(M;n)en ajoutant une pièce de valeurxj. DoncValeurOpt(M;n)1+min1jn;Mxj0ValeurOpt(Mxj;n).

N. Nisse

Programmation Dynamique16/21

Rendu de monnaieDécision / Optimisation Alg. Glouton Alg. 1 Prog. Dyn. Alg. 2 Sac-à-Dos (a vec/sansremise)

Rendu de Monnaie : Algorithme Optimal 2

Pour tout 1mMetn2N, calculons récursivementValeurOpt(m;n)en nous servant du théorème précédent:ValeurOpt(M;n) =1+min1in;Mxi0ValeurOpt(Mxi;n)

pour calculer un terme en fonction des précédentsValeurOpt(m0;n)pourm0

Correction :

preuv epar récurrence sur (k;j)(en se servant du théorème précédent) qu"après l"itération(k;j),sol:(k) =

1+min1ij;kxi0ValeurOpt(kxi;n).

Complexité :

doub leboucles imbr iquéesO(nM).Cet algorithme a l"avantage, par rapport à l"algorithme précédent, de n"utiliser qu"un tableau de

tailleM+1 (alors que l"algorithme précédent utilisait une matrice(M+1)n). Sacomple xitéen espace est donc meilleure ,pour une comple xitéen temps similaire .

(il semble plus simple à écrire que l"algorithme précédent, mais notons que nous ne gardons que

le nombre minimum de pièces et non une combinaison optimale de pièces)quotesdbs_dbs7.pdfusesText_13