Algorithmes gloutons
Résoudre des problèmes d'optimisation à l'aide d'algorithmes gloutons, en s'appuyant sur l'exemple classique du problème du rendu de monnaie.
À propos de ce thème
Résoudre des problèmes d'optimisation à l'aide d'algorithmes gloutons, en s'appuyant sur l'exemple classique du problème du rendu de monnaie.
Questions clés
- Qu'est-ce qu'un choix glouton ?
- Un algorithme glouton donne-t-il toujours la solution optimale ?
- Comment implémenter le rendu de monnaie de manière gloutonne ?
Plus dans Algorithmique
Parcours séquentiel et recherche
Écrire des algorithmes pour parcourir un tableau à la recherche d'un élément, d'un extremum ou pour calculer une moyenne.
2 methodologies
Algorithmes de tri
Étudier et implémenter les algorithmes de tri par insertion et par sélection. Analyser leur complexité quadratique et prouver leur terminaison.
2 methodologies
Recherche dichotomique
Mettre en œuvre l'algorithme de recherche dichotomique dans un tableau trié. Comparer son efficacité logarithmique avec la recherche séquentielle.
2 methodologies