Optimisation Combinatoire

Informations

Langue d'enseignement : Français
Crédits ECTS: 6

Programme

  • Heures d'enseignement dispensées à l'étudiant : 48 heures
  • Temps de travail personnel : 102 heures

Objectifs et compétences

Objectifs :
Parmi les problèmes que l'on souhaite pouvoir résoudre avec l'aide d'un ordinateur, on trouve de nombreux problèmes d'optimisation combinatoire. Par exemple, on pourra chercher à optimiser des transports, des emplois du temps, des répartitions de ressources... Pour résoudre ces problèmes, souvent difficiles, de nombreuses techniques ont été inventées et des outils logiciels développés.

Cet enseignement vise à initier les étudiants aux méthodes d'optimisation combinatoire et à leur utilisation. Ceci inclut les notions de programmation linéaire (éventuellement en nombre entiers) et les outils attachés, tels que l'algorithme du simplexe, la notion de dualité, la relaxation linéaire. Ceci inclut aussi la découverte des méthodes de descente, et la résolution de problème d'optimisation combinatoire (notamment dans les graphes) par des algorithmes avancés.

Compétences :
  • Comprendre et mettre en oeuvre l'intérêt et les principes de la démarche de recherche fondamentale et/ou appliquée
  • Maitriser le vocabulaire technique des différents enseignements
  • Développer une argumentation avec esprit critique

  • Connaître et mettre en application les principaux modèles mathématiques intervenant dans les différentes disciplines connexes du domaine Sciences et Technologies mais aussi des autres domaines
  • Être capable de traduire un problème simple en langage mathématique.
  • Modéliser une situation concrète en un énoncé formel au moyen d'outils (e.g., automates, langages, grammaires, graphes)
  • Concevoir des algorithmes avancés dans son domaine de spécialisation, et savoir les programmer
  • Utiliser les bibliothèques et outils logiciels usuels de son domaine de spécialisation
  • Comprendre et traduire sous forme algorithmique la spécification mathématique d'une méthode de son domaine de spécialisation
  • Implémenter et/ou comparer les méthodes de l'état de l'art dans son domaine de spécialisation
  • Ecrire une preuve de correction d'algorithme
  • Être capable de résoudre des équations (linéaires, algébriques, différentielles) de façon exacte et par des méthodes numériques.

Organisation pédagogique

- Non défini -

Contrôle des connaissances

Session 1:

Contrôle continu coefficient 0.5

Examen terminal (durée 3h, coefficient 0.5)

Seconde session:

Épreuve écrite (3h) ou orale selon effectif, coefficient 0.5

Contrôle continu, report de la note de session 1, coefficient 0.5

Note finale session 2: max(NoteEx2, 0.5*NoteEx2 + 0.5*NoteCC)

Lectures recommandées

- Non défini -

Responsable de l'unité d'enseignement

Paul Dorbec

Enseignants

- Non défini -