Algorithmique des graphes et complexité

ECTS

6.0

Présentation

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.

Objectifs

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.

Volume horaire

TD30
CM20

Compétences visées

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.

Diplômes intégrant cette UE

Composante

Etudiants internationaux

Ouvert aux étudiants en échange

Logo

Nous contacter

15, rue de l'Hôtel Dieu
TSA 71117
86073 POITIERS Cedex 9 - France
Tél : (33) (0)5 49 45 30 00
Fax: (33) (0)5 49 45 30 50

Suivez-nous