Skip to content

3 1 6 1 Problème d'optimisation

Algorithmes gloutons. ⅕ : Problème d'optimisation

  1. Problème d'optimisation
  2. Allocation
  3. Preuve d'algorithme
  4. Problème des choix d'activité
  5. Résumé

Dans cette séquence, on s'intéresse aux algorithmes gloutons, qui sont un schéma algorithmique qui permet de résoudre des problèmes en particulier d’optimisation. Nous allons voir un exemple autour de l’allocation et des points d'entrée c'est à dire le point clé de tout ce qui définit les algorithmes glouton : la preuve de l’optimalité. On va toucher à un invariant pour la preuve qui est un invariant pas commun puisque c’est un invariant qui n’est pas constructif au niveau des objets manipulés, pas vérifiable par exemple par un assert dans un code python.

Problèmes d’optimisation : on cherche la meilleure solution d’un problème et cela va consister à sélectionner un sous-ensemble d’objets, dans un grand ensemble d’objets qui permette de réaliser quelquechose. Par exemple, pour les enseignants, on chercherait à construire un algorithme qui va trouver une solution pour faire les emplois du temps...

Vidéo 1 B3-M1-S6

Supports de présentation (diapos)

Support des vidéos de la séquence Algorithmes gloutons