Descriptif

Ce module introduit les fondements de la théorie des graphes et les notions de complexité des problèmes.

La première partie sera consacrée à la découverte de problèmes combinatoires, qui seront en premier lieu abordés via la théorie des graphes Les concepts fondamentaux (connexité, arbres, chemins, flots, coloration, etc.) seront explorés, avec un focus sur la modélisation, les algorithmes de résolution classiques et les preuves formelles.

La deuxième partie sera consacrée aux notions de complexité des problèmes combinatoires. Les concepts essentiels en théorie de la complexité (Machine de Turing, réduction polynomiale) seront présentés. Les étudiants apprendront à formaliser une réduction polynomiale et à l’utiliser pour classifier la complexité de nouveaux problèmes.

Un lien sera établi avec d'autres techniques d’optimisation (notamment la programmation linéaire), qui pourront être comparées et confrontées sur des problèmes combinatoires, afin d’analyser leurs performances en fonction de la complexité des problèmes.

Compétences travaillées

Bloc 1 : Concevoir pour l'industrie et les services, des produits, procédés et processus respectueux d'un avenir durable
  1.3 : Modéliser un produit, procédé, processus
  1.6 : Valider une solution
  1.8 : Mobiliser des informations validées
Bloc 2 : Organiser la production dans un environnement en évolution avec une responsabilité individuelle et collective
  2.2 : Planifier la production et les ressources
  2.8 : Mobiliser des informations validées
Bloc 3 : Améliorer pour l'industrie et les services, les performances d'un produit, procédé et processus pour anticiper et accompagner les changements induits par les transition
  3.3 : Modéliser un produit, procédé, processus
  3.8 : Agir avec responsabilité environnementale et sociétale