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.
Objectifs pédagogiques
- 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 surveillé
Oral de projets
Le coefficient de l'enseignement est : 1