NSI · Première · Algorithmique et programmation
Algorithmes gloutons
Le meilleur choix, sans jamais revenir.
En bref
Un algorithme glouton construit une solution par étapes, en faisant à chaque fois le choix qui paraît le meilleur sur le moment, sans jamais revenir en arrière.
Le schéma
| L'étape | Ce qu'on fait |
|---|---|
| 1 | Trier ou évaluer les candidats selon un critère |
| 2 | Prendre le meilleur candidat encore admissible |
| 3 | L'ajouter à la solution, définitivement |
| 4 | Recommencer jusqu'à épuisement |
Ses deux qualités : rapide — souvent n log n, tri compris — et simple à écrire.
Le rendu de monnaie
On prend à chaque étape la plus grosse pièce qui n'excède pas ce qui reste à rendre.
| Le système de pièces | Pour rendre 6 | Le glouton donne | L'optimal est |
|---|---|---|---|
| Européen (1, 2, 5…) | — | Optimal | Le même |
| Fabriqué exprès : 1, 3, 4 | 6 | 4 + 1 + 1, soit 3 pièces | 3 + 3, soit 2 pièces |
Point capital du chapitre : le glouton donne toujours une solution, rarement la garantie que c'est la meilleure. Que cela marche pour les euros est une propriété du système de pièces, pas de l'algorithme.
Trois autres problèmes
| Le problème | Le critère glouton | Le résultat |
|---|---|---|
| Sac à dos | Le rapport valeur sur poids | Excellent, souvent non optimal |
| Choix d'activités | Celle qui finit le plus tôt | Prouvé optimal |
| Plus court chemin (Dijkstra) | Le sommet le plus proche | Optimal tant que les poids sont positifs |
Quand l'employer
| La situation | Le glouton convient-il |
|---|---|
| Une solution approchée suffit | Oui |
| Le temps de calcul compte | Oui |
| La structure du problème garantit l'optimalité | Oui, et c'est démontrable |
| Il faut l'optimum garanti sans cette garantie | Non : il faut une méthode exacte, bien plus coûteuse |
Teste-toi
6 questions pour vérifier
Touche une réponse : la correction s’affiche tout de suite.
1.Qu’est-ce qu’un algorithme glouton ?
2.Un algorithme glouton donne-t-il toujours la solution optimale ?
3.Avec des pièces de 1, 3 et 4, combien de pièces le glouton rend-il pour 6 ?
4.Que le glouton fonctionne pour le rendu de monnaie en euros est une propriété…
5.Quel critère glouton donne un bon résultat au problème du sac à dos ?
6.L’algorithme de Dijkstra est glouton et optimal si les poids sont positifs.
0 / 6 questions
Dans l’app, ce chapitre a son quiz complet, chronométré, et tes erreurs reviennent au bon moment pour ne plus les refaire.
La fiche de révision, sur une page
Tout « Algorithmes gloutons » sur une seule page A4 illustrée : l’essentiel, les pièges et un mini-test. Elle se débloque dans l’app avec des gemmes — et ton compte gratuit en offre assez pour tes trois premières fiches.
