FR
EN
Modélisation et Théorie des graphesDéveloppement et Mathématiques pour l'ingénieur (STI)
Modélisation et Théorie des graphes
Unité d'enseignement Développement et Mathématiques pour l'ingénieur · S06T_SMI2 | Code EC S06T_SMI2-1
10ECTS (UE)
1Coefficient
21:20Heures
Séquencement
↳ Amraoui Mohammed
↳ Berthome Pascal
↳ Clemente Patrice
Bloc incomplet : le nombre de séances planifiées ne correspond pas à la fiche.
Objectifs pédagogiques
Apporter les clés de la modélisation des problèmes informatiques au travers deux grands systèmes de modélisation : la théorie des graphes et la programmation linéaire.
Pré-requis
| Module | Unité d'enseignement | Semestre |
|---|---|---|
| Algorithmique et Complexité | Principes de la programmation | S5 |
Programme
-
Théorie des graphes :
-
Introduction aux graphes, paramètres de graphes
-
Degré, diamètre
-
Eulérien, Hamiltonien
-
Algorithmes classiques sur les graphes
-
Exploration de graphes (BFS, DFS et applications)
-
Plus courts chemins (Dikstra, Bellman-Ford)
-
Arbres couvrants (Prim, Kruskal)
-
Flot Maximal
-
Programmation linéaire :
-
Modélisation d'un problème sous forme de PL
-
Formes canonique et standard d’un PL
-
Méthodes de résolution (graphique, simplexe, …)
-
Outils
Modalités d'évaluation
- Examen final
Références bibliographiques
- Jacques Teghem : Programmation Linéaire, édition de l'université de Bruxelles, Ellipsis
- J.A. Bondy, U.S.R. Murty : Graph Theory, Graduate Texts in Mathematics, Springer, 2008
- Cormen, Thomas H. ; Leiserson, Charles Eric ; Rivest, Ronald L ; Cazin, Xavier, "Introduction à l'algorithmique", Dunod
Compétences
3| Réf. | Verbe | Description | Niveau |
|---|---|---|---|
| C2_1 | choisir | Connaître et Utiliser les algorithmes fondamentaux de la théorie des graphes | 2 |
| C2_1 | reconnaître | Connaître les principes de la programmation linéaire | 1 |
| C2_3 | analyser | Savoir modéliser un problème grâce à différentes méthodes | 2 |