A. Malapert

Recherche Opérationnelle

Ce cours est une introduction à la recherche opérationnelle à travers la théorie des graphes, 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.

MIASHS 3 ECTS 30h L3 OPT arnaud.malapert@univ-cotedazur.fr

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.

Calendrier

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 ; Merch Time !.

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 (2h)
  • Contrôle Terminal (3h)

La seconde session est aussi une épreuve écrite (2h).