• 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. 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.

Lire plus

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.

Lire plus

Heures d'enseignement

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

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