Modélisation et Théorie des graphesDéveloppement et Mathématiques pour l'ingénieur (STI)

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.

• 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

• Examen final

• 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