Optimisation dans les graphes

Informations

Langue d'enseignement : Français
Crédits ECTS: 6

Programme

  • Heures d'enseignement dispensées à l'étudiant : 48 heures
  • Temps de travail personnel : 102 heures

Objectifs et compétences

Objectifs :
Donner les outils standards de modélisation et d'optimisation dans les graphes.

- Définitions des notions de base de théorie des graphes (graphes orientés et non-orientés, degrés, connexité, ...)

- Structures de bases (arbres, stables, cliques, ...)

- Représentation informatique des graphes

- Algorithmes combinatoires (arbres couvrants minimum, parcours de graphes, ordre topologiques, ...)

- Notions de réseaux et de flots dans les réseaux

- Algorithmes de plus courts chemins

- Algorithmes de flots maximum

- Algorithmes de flot de coût minimum

Compétences :
  • Être autonome dans le travail
  • Maitriser les concepts fondamentaux en mathématiques et en probabilité
  • Maitriser les bases scientifiques de la modélisation et les outils modernes du langage scientifique : mathématiques, statistiques, méthodes numériques
  • Posséder une rigueur méthodologique
  • Maîtriser le raisonnement logique

  • Connaître et mettre en application les principaux modèles mathématiques intervenant dans les différentes disciplines connexes du domaine Sciences et Technologies mais aussi des autres domaines
  • Construire et rédiger une démonstration mathématique synthétique et rigoureuse.
  • Être capable de traduire un problème simple en langage mathématique.

Organisation pédagogique

le mode de fonctionnement de l'UE est présenté au début des enseignements

Contrôle des connaissances

Session 1 : Contrôle continu - coef. 1/3 + Examen final (3 heures) - coef. 2/3

Session 2 : Note contrôle continu session 1 - coef. 1/3 + Examen final (3 heures) - coef. 2/3. L'examen final pourra se faire à l'oral en cas d'effectif faible.

La règle du max est appliquée pour la deuxième session

Note éliminatoire : 5

Lectures recommandées

l'ensemble des références bibliographiques est communiqué au début des enseignements

Responsable de l'unité d'enseignement

Pierre Pesneau

Enseignants

la composition de l'ensemble de l'équipe pédagogique est communiquée au début des enseignements