1. Accueil
  2. TUTORIELS
  3. LES ALGORITHMES GLOUTONS

LES ALGORITHMES GLOUTONS

Au marché Mokolo, une vendeuse rend la monnaie en deux secondes sans réfléchir. Un transporteur charge son car en commençant par la marchandise la plus rentable. Tous deux appliquent un algorithme glouton, et l'un des deux se trompe. Ce cours explique lequel, et pourquoi.

Ce que vous saurez faire à la fin

  • Reconnaître un problème d'optimisation et formuler son objectif sans ambiguïté.
  • Concevoir un critère glouton, et surtout : le mettre en défaut avant d'écrire du code.
  • Écrire les gloutons classiques : rendu de monnaie, sac à dos, choix d'activités.
  • Démontrer qu'un glouton est optimal par argument d'échange.
  • Savoir quand passer à la programmation dynamique.

Le principe, en une image

Les quatre etapes d'un algorithme glouton : ce qui reste a choisir, le meilleur du moment, on le prend definitivement, au suivant. Une fleche de retour en arriere est barree.

Prendre le meilleur du moment, et ne jamais revenir dessus. C'est ce qui rend le glouton rapide ; c'est aussi ce qui peut lui faire rater la meilleure solution.

A qui s'adresse ce cours

A tout étudiant qui sait écrire une boucle et trier une liste. Les exemples sont situés au Cameroun : une vendeuse de Mokolo, un transporteur de la ligne Yaoundé-Douala, une responsable de foyer à Bafoussam. Les montants sont en francs CFA.

Les chiffres annoncés ont tous été vérifiés par le calcul, contre-exemples compris.

Les six chapitres

Chapitre 1Le réflexe du marchéQu'est-ce qu'un algorithme glouton ? Le principe expliqué par la façon dont une vendeuse de Mokolo rend la monnaie : prendre le meilleur du moment, et ne jamais revenir en arrière.Chapitre 2Rendre la monnaieLe rendu de monnaie en francs CFA : l'algorithme glouton, son code, et la démonstration qu'il donne bien le nombre minimal de coupures, avec le système monétaire où il échoue.Chapitre 3Quand le glouton se trompeLe problème du sac à dos : Tonton Émile charge son car pour Douala et perd 10 000 FCFA en suivant son intuition. Pourquoi le meilleur choix immédiat n'est pas toujours le bon.Chapitre 4Couper les sacs : le glouton redevient optimalLe sac à dos fractionnaire : en autorisant les demi-sacs, le même algorithme glouton devient exact. Pourquoi une seule règle du jeu change tout, avec la démonstration.Chapitre 5La salle du foyer : caser le plus d'activitésLe problème du choix d'activités : une seule salle, beaucoup de demandes. Trois critères gloutons possibles, un seul qui marche, et la preuve qu'il est optimal.Chapitre 6Les deux conditions, et comment le prouverCe qui distingue un problème où le glouton est exact d'un problème où il échoue : la propriété du choix glouton et la sous-structure optimale. Avec la méthode de démonstration et la comparaison aux autres approches.

Pour aller plus loin

Pour prolonger ce cours : Algorithmes de graphes : parcours, chemins, arbres couvrants et flots, avec dix chapitres et des exercices corrigés.

Questions / Réponses

Aucune question. Soyez le premier à poser une question.
★ ★ ★ ★ ★
2 votes. Moyenne 5 sur 5.

Ajouter un commentaire

Anti-spam