A. Malapert, MCF

Graphes et programmation dynamique

La théorie des graphes est une théorie informatique et mathématique. La théorie des graphes a de nombreuses applications dans tous les domaines liés à la notion de réseau (réseau social, réseau informatique, télécommunications, etc.) et dans bien d'autres domaines (par exemple génétique) tant le concept de graphe, à peu près équivalent à celui de relation binaire (à ne pas confondre donc avec graphe d'une fonction), est général.

Nous allons étudier des notions, problèmes, et algorithmes fondamentaux de la théorie des graphes. La programmation dynamique, une méthode algorithmique pour résoudre des problèmes d’optimisation, sera introduite grâce aux graphes, avant d’être appliquée à d’autres problèmes classiques.

Contenu

Les diapositives du cours de théorie des graphes sont disponibles : 1 diapositive par page ; 4 diapositives par page ; 8 diapositives par page.

Les diapositives du cours de programmation dynamique sont disponibles : suite de Fibonacci ; problème du sac-à-dos.

Le plan des cours est le suivant :

  • Généralités et définitions sur les graphes.
  • Graphes eulériens et hamiltoniens.
  • Connexité, arbres, et cheminement.
  • Recherche de connexité et applications
  • Problèmes de plus courts chemins
  • Contrôle continu
  • Généralités et définitions sur la programmation dynamique.
  • Applications algorithmiques de la programmation dynamique.

Ressources

BU

Électroniques

Modalités de contrôle des connaissances

Le contrôle des connaissances comprendra 2 épreuves écrites :

  • Contrôle Continu (1h)
  • Contrôle Terminal (2h)
  • Épreuve orale en seconde session