Résolution de problèmes d'optimisation

Master 1 informatique WeDSci et I2L - 2023/2024

Annales

Retrouver l'année 2022-2023.

Questions ?

Contacter l'équipe enseignante

But

S'initier à la démarche de modélisation d'un problème pour le résoudre de manière informatique. Cet enseignement présente de nombreuses méthodes de résolution de problèmes et s'appuie sur des exemples pratiques.

haut

Evaluation

L'évaluation comprend :

  • Projets, 50%,
  • 2 écrits intermédiaires, 50%, les 17/04/2024 (I2L) de 45 minutes, et le xx/xx/2024.

L'énoncé du projet est ici pdf et le code accompagnant ici zip.


Cette UE compte pour 5 crédits ECTS.

haut

Équipe d'enseignants

Sébastien Verel et Alexandre Chotard.

Pour contacter un des intervenants : contacts. Vous pouvez contacter l'équipe pour tout ce qui concerne cet enseignement et votre orientation.

haut

Objectifs

Ils sont mis à jour régulièrement :

  1. Savoir définir un problème d'optimisation combinatoire
  2. Connaitre des exemples de problème d'optimisation (maxSAT, TSP, QAP, knapsack, etc.)
  3. Savoir modéliser un problème en un problème d'optimisation.
  4. Connaitre le principe d'une recherche locale à solution unique.
  5. Connaitre la recherche aléatoire
  6. Savoir comparer statistiquement deux algorithmes de recherche stochastiques.
  7. Savoir définir une marche aléatoire
  8. Connaitre les heuristiques "Hill-Climbing"
  9. Connaitre la notion d'optimum local
  10. Connaitre le dilemme exploration / exploitation
  11. Savoir définir les métaheuristiques classiques (recuit simulé, recherche taboue, iterated local search)
  12. Savoir définir les principes des algorithmes évolutionnaires
  13. Connaitre les différents types d'algorithmes évolutionnaires
  14. Savoir coder dans un langage les algorithmes d'optimisation précédents
  15. ...

haut

Supports de Cours et de TP

Voici l'ensemble des supports de cours et des émoncés des TP.

Séance Titre cours TP/TD Cor.
01 Introduction à l'optimisation cours td ks5 ks1000
02 Modélisation: exemples discrets cours td chr12a bur26a cor
03 Algorithmes de recherche locale cours notes R td codeR R-hc cor
04 Metaheuristiques cours td
05 Algorithmes évolutionnaires cours td cor
06 Optimisation numérique cours
99 Projet cours énoncé code zip

haut

Bibliographie

Quelques repères bibliographiques :

haut

Horaires

13h de CM, 13h de TD, et 13h de TP.


Consulter l'emploi du master : edt

haut

dernière modification : 7 février 2024