Place de l'UV dans le programme

Il s'agit de la première UV liée à l'option COPSI. Elle se situe à la racine des problématiques de la
recherche opérationnelle. Elle permet aux étudiants de comprendre la complexité des problèmes, c'est à
dire de différencier les problèmes "faciles" ou polynomiaux, des problèmes NP-complet ou difficiles.


Objectifs Généraux (Quels sont les objectifs de l'enseignant ?)

L'objectif général de cette UV est de considérer la notion de graphe depuis la théorie jusqu'à la pratique
opérationnelle sur différents problèmes que cette structure mathématique permet de modéliser. Le
graphe est une structure de données classique utilisée pour modéliser beaucoup de problèmes
d'optimisation combinatoire. Il s'agit d'une structure simple de compréhension mais particulièrement
riche à manipuler. Cette UV met l'accent sur l'utilité opérationnelle de cette structure de données
avancée. Lors de cette UV, les élèves apprennent à maîtriser le vocabulaire et les concepts
fondamentaux des graphes, leur codage informatique et les problématiques liées à l'identification de
structures singulières dans les graphes (parcours, connexité, cheminement...)


Noms des modules de l'UV et en quoi ils y contribuent

- Graphe et Algorithmique (30h) Gilles Simonin et Oussama Ben Ammar

Complexité (10h)

PLNE (5h)


Prérequis (Formations, Parcours, UVs, autres...)

Les notions de programmation (programmation linéaire) et de structure (algorithme de base), d'algèbre
linéaire et d'analyse vus en année 1 sont nécessaires à cette UV.