Chapitre 7 : exemples d’algorithmes gloutons
Mary Allen Wilkes est une programmeuse et conceptrice de logiciel, connue pour son travail avec l'ordinateur LINC (Laboratory INstrument Computer), considéré comme le premier ordinateur personnel. En janvier 1963, le groupe LINC quitte le laboratoire Lincoln pour créer le Centre de technologie informatique en sciences biomédicales sur le campus de Cambridge, dans le Massachusetts.
En informatique, on rencontre souvent des problèmes d’optimisation, c’est-à-dire des problèmes pour lesquels on cherche la meilleure solution possible satisfaisant un certain nombre de contraintes.
En pratique, on cherche à trouver une solution algorithmique pour résoudre de tels problèmes lorsque :
- le problème possède un très grand nombre de solutions ;
- on sait évaluer la qualité de chacune des solutions (et donc dire quelle solution est meilleure parmi plusieurs).
Le but de ce chapitre est de présenter une classe d'algorithmes très importante pour la résolution de problèmes d'optimisation : les algorithmes gloutons.
On propose le déroulé suivant :
- lecture interactive du cours et résolution des exercices qui y sont intégrés. On aborde en particulier les problèmes d'optimisation classiques suivants :
- le problème du voyageur de commerce ;
- un problème d'organisation ;
- le problème du rendu de monnaie.
- des exercices d'entraînement sur les algorithmes gloutons.
Afficher le cours
Afficher les exercices
Il n'y a pas de ressources à télécharger.