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

- Non défini -

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

- Non défini -

Responsable de l'unité d'enseignement

Pierre Pesneau

Enseignants

- Non défini -