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.
Dans un dernier temps, 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, éventuellement appliqués dans un contexte industriel.
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.2 : Dimensionner un produit, procédé, processus
1.3 : Modéliser un produit, procédé, processus
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.3 : Gérer les flux internes
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.1 : Analyser les performances d'un produit, procédé, processus
3.3 : Modéliser un produit, procédé, processus
Objectifs pédagogiques
A l’issue du module, les étudiants seront capables de :
- Modéliser des problèmes réels sous forme de problèmes de graphes
- Identifier et appliquer les algorithmes adaptés à la résolution de problèmes de graphes
- Analyser la complexité de problèmes d’optimisation discrète en formalisant une réduction polynomiale et exhibant des certificats polynomiaux
- Démontrer des propriétés fondamentales dans des graphes
- Faire le lien entre les différentes méthodes d’optimisation discrète abordées
Pour les élèves du diplômeDiplôme d'Ingénieur IMT Mines Albi
- Éléments de raisonnement (preuves par récurrence, par l’absurde, etc.)
- Logique de premier ordre
- Algorithmique et programmation
- Optimisation linéaire
Format des notes
Numérique sur 20Pour les élèves du diplômeDiplôme d'Ingénieur IMT Mines Albi
Vos modalités d'acquisition :
Devoir écrit en fin de semestre + notes éventuelles au cours du semestre
Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)
Le coefficient de l'enseignement est : 1