Introduction à lalgorithmique et la complexité (et un peu de
Problème de rendu de Monnaie (formalisation) Formaliser (Décrire mathématiquement)un problème concret fait partie d’une des tâches les plus importantes (et souvent difficiles) des chercheurs Prenons l’exemple du problème de rendu de monnaie Entrée 1: Un montant M 2R à rendre (en euro) (M =200 127:36 dans l’ex précédent)
Guide des problèmes de rendu CADSOFT Concepts
Au moment de lancer le rendu ou bien d'effectuer une sauvegarde de votre travail, le logiciel affiche un message d'erreur qui varie en fonction du problème rencontré En général, les erreurs correspondent à des situations particulières d'objets présents dans votre
Le principe Rendu de monnaie Tilloloy
Rendu de monnaie Tilloloy Un algorithme glouton Une solution r´ecursive Mise en place d’une solution dynamique Dans cette partie, on cherche a r` ealiser un programme de´ rendu de monnaie On souhaite que l’automate rende l’appoint de maniere optimale, dans le sens ou` il minimise le nombre de` pieces rendues (ou billets) `
MALADIE DE RENDU-OSLER
Un des 10 axes de travail des centres de référence, attribués lors du plan maladies rares, est de promouvoir les connaissances nécessaires sur la maladie de Rendu-Osler afin de sensibiliser les malades comme les acteurs médicaux, au diagnostic précoce et aux mesures préventives ou théra-peutiques qui en découlent
Problème aux limite / Eléments finis - univ-tlnfr
place su l’élément de éféence [,] donc : Les points impairs correspondent aux points extrémaux de chaque élément et les points pairs aux points milieux On a comme pas On numérote les éléments de 1 à n-1 (il y a n-1 éléments), on va donc écrire une subroutine ui va associe à chacun des éléments l’ensemble de ses nœuds
Fichier d’aide à la résolution de problèmes en cycle 3
chacune d’elles Toutefois, l’écriture de nombreux énoncés doit également permettre à chaque élève de construire ses propres types de situations problèmes Remerciements Ce fichier est le résultat de trois années d’expérimentation dans les écoles du Réseau Ambition Réussite du Collège de Terre Sainte à Saint Pierre
Algorithmes gloutons - Education
tition optimale de tâches suivant des critères précis, le problème du rendu de monnaie, le problème du sac à dos, la recherche d’un plus court chemin dans un graphe, le problème du voyageur de commerce De nombreuses techniques informatiques sont susceptibles d’apporter une solution exacte ou approchée à ces problèmes
Compte rendu hebdomadaire du travail réalisé en STAGE
PROBLEME : La tentative de transfert de sessions n'a pas fonctionné Création manuelle des 6 sessions sur les 4 PC = Perte de temps Solution envisagée en cas de futur manipulation du même types Scripts Repérage de la baie de brassages général pour accueillies des nouveaux câbles Rédaction du compte rendue hebdomadaire
COMPTE RENDU COMMISSION DE RESTAURATION
La direction de l’ISC fait le même constat concernant les quantités servies et demande à la société de restauration de veiller au respect, à minima, des recommandations en terme de grammages pour des élèves collégiens (notamment an fonction de leurs âges et corpulences)
Compte-Rendu de TP du module EDP 1
Compte-Rendu de TP du module EDP 1 Résolution numérique de l’équation de la chaleur en 2D WALLACE Ranveig CATTOEN Céline GMM 4ème année, 2002-2003
[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;36edemarchandise. 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/21Rendu 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 solutionoptimaleM=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 solutionoptimaleM=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 solutionoptimaleM=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=1Rendu 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=1Rendu 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=1Rendu 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=1Rendu 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=1Rendu 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=1Rendu 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=1ValeurOpt(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
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 doncValeur
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 servantdu 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éesInitialisation :
mise à jour de Valeur_opt(i,1)=i pour tout i<=mCas où
Valeur_opt(i,j)=1+Valeur_opt(i-xj,j)
{Terminaison :doub leboucles imbr iquéesCorrection :
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/21Rendu 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 programmationdynamique. 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 toutmN. 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=1ValeurOpt(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(kj1;;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 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 (il semble plus simple à écrire que l"algorithme précédent, mais notons que nous ne gardons queCorrection :
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é :