• Votre sélection est vide.

    Enregistrez les diplômes, parcours ou enseignements de votre choix.

Algorithmique des graphes et complexité

  • ECTS

    6 crédits

  • Composante

    Sciences Fondamentales et Appliquées

Description

Cet enseignement comporte quatre parties :

1. Cycles et cocycles dans un graphe : exemples, algorithmes et applications.

2. Théorie des graphes appliquée à la recherche opérationnelle : réseaux de transport, graphes et réseaux de transport canalisés ; théorèmes de Ford-Fulkerson et de Hoffman ; algorithmes de Ford-Fulkerson et d'Edmonds-Karp ; applications.

3. Couplages et recouvrements : algorithmes dans le cas général et dans le cas de graphes bipartis.

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

Lire plus

Objectifs

Cette UE vise à étudier, comprendre et utiliser des algorithmes issus de la théorie des graphes, très utiles en recherche opérationnelle. Ceci doit permettre de mettre en évidence divers types de complexité, notamment les classes de problèmes NP et P, que l'étudiant doit être capable d'identifier et pour lequel il doit savoir mettre en oeuvre quelques techniques d'attaque.

Lire plus

Heures d'enseignement

  • Algorithmique des graphes et complexité - CMCM20h
  • Algorithmique des graphes et complexité - TDTD30h

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.

Lire plus

Liste des enseignements