Algorithmique des graphes et complexité

Cet enseignement comporte quatre parties :

1. Algorithmes élémentaires sur les graphes : parcours de graphes, arbres recouvrants, plus courts chemins. Théorie des graphes appliquée à la recherche opérationnelle : espaces des flots et et des tensions, Ford-Fulkerson.

2. Introduction à la théorie de la complexité : problèmes de décision, classes de problèmes (P et NP), réduction polynomiale, problèmes NP-complets et problèmes NP-durs, classe co-NP, attaque de problèmes NP-durs (solutions approchées).

3. Algorithmes géométriques.

4. Approfondissement d'un aspect de la théorie ou de l'algorithmique des graphes au choix.

Ce module vise à approfondir les algorithmes de manipulation des graphes afin de mettre en évidence la notion des problèmes NP-complets. Les divers types de complexité seront présentés.

Connaître les concepts de base de théorie des graphes et savoir mettre en oeuvre les algorithmes élémentaires correspondants.

Connaître et savoir mettre en oeuvre quelques techniques de la recherche opérationnelle.

Maitriser des connaissances de base en théorie de la complexité.

Etre capable d'identifier un problème NP-complet et savoir mettre en oeuvre quelques techniques d'attaque.