Unité pédagogique

Graphes et Optimisation

Derniere édition le: 26/09/2022

Modifier

Responsable:

ABSI Nabil

Description générale :

L’objectif de ce cours est d’introduire les élèves à la théorie des graphes et à l’optimisation combinatoire :

• 3 séances de cours en amphi permettent aux élèves d’acquérir les bases ;
• 6 séances de travaux dirigés permettent un approfondissement des différentes notions vues en cours à travers l’étude de divers problèmes d’optimisation classiques.

Mots-clés:

Théorie des graphes Optimisation

Nombre d’heures à l’emploi du temps:

29

Domaine(s) ou champs disciplinaires:

Langue d’enseignement:

Français Anglais

Objectifs d’apprentissage:

A la fin de l’unité pédagogique, l’élève sera capable de :	Niveau de taxonomie	Priorité
Acquérir les notions de base en théorie des graphes et optimisation	1. Connaître	Essentiel
Comprendre et appliquer les méthodes de résolution classiques en optimisaton discrète	3. Appliquer	Essentiel

Modalités d’évaluation des apprentissages:

Part de l'évaluation individuelle			Part de l'évaluation collective
Examen sur table :	100	%	Livrable(s) de projet :		%
Examen oral individuel :		%	Exposé collectif :		%
Exposé individuel :		%	Exercice pratique collectif :		%
Exercice pratique individuel :		%	Rapport collectif :		%
Rapport individuel :		%
Autre(s) : %

Programme et contenus:

Type d’activité pédagogique :	Contenu, séquencement et organisation
Séance 1 (Cours)	Introduction à la théorie des graphes
Séance 2 (Cours)	Problème d'arbre couvrant de poids minimum, problème du plus court chemin
Séance 3 (Cours)	Introduction à la programme linéaire en nombres entiers : modélisation, simplexe, branch-and-bound
Séance 4 (TD)	Travaux dirigés de la séance de Cours 1
Séance 5 (TD)	Travaux dirigés de la séance de Cours 2
Séance 6 (TD)	Travaux dirigés de la séance de Cours 3
Séance 7	Problème du sac-à-dos
Séance 8	Problème du voyageur de commerce
Séance 9	Problème de tournées de véhicules