Exercices corrigés — Algorithmes gloutons (informatique (MP2I/MPI))
15 exercices avec corrigé rédigé, du plus simple au plus exigeant.
- Le glouton n'échoue pas au hasard
- Les deux mauvais critères de la sélection d'activités
- Le codage de Huffman quand toutes les fréquences sont égales
- Pourquoi « au plus tard » et non « au plus tôt »
- La 2-approximation est-elle serrée ? et le glouton « degré maximal » a-t-il une garantie ?
- Le sac à dos fractionnaire : le même glouton, mais exact
- Une parade qui vaut 2, et pourquoi elle vaut 2
- Un glouton exact que le cours ne traite pas : minimiser la somme des temps d'attente
- Ce qui casse quand les activités sont pondérées
- Huffman sur un alphabet d'un seul caractère
- Probleme – Huffman de bout en bout : coder, décoder, mesurer
- Probleme – Tâches unitaires : quels ensembles sont réalisables, et pourquoi le glouton les trouve
- Probleme – La couverture par ensembles : un glouton qui perd un facteur logarithmique
- Probleme – Le rendu de monnaie : quand le glouton est-il optimal ?
- Probleme – Trois gloutons pour un même ordonnancement, et un seul qui répond à la question posée