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