FR
EN
Modélisation et Théorie des graphesDéveloppement et Mathématiques pour l'ingénieur (STI)
Modeling and Graph Theory
Teaching unit Development and Mathematics for Engineers · S06T_SMI2 | EC Code S06T_SMI2-1
10ECTS (EU)
1Coefficient
21:20Hours
Séquencement
↳ Amraoui Mohammed
↳ Berthome Pascal
↳ Clemente Patrice
Bloc incomplet : le nombre de séances planifiées ne correspond pas à la fiche.
Learning objectives
Bringing the keys to computer problem modelling through two major modelling systems: graph theory and linear programming.
Prerequisites
| Module | Teaching unit | Semester |
|---|---|---|
| Algorithms and Complexity | Programming Principles | S5 |
Program
-
Graph theory :
-
Introduction to graphs, graph parameters
-
Degree, diameter
-
Eulerian, Hamiltonian
-
Classical algorithms on graphs
-
Graph exploration (BFS, DFS and applications)
-
Shorter paths (Dikstra, Bellman-Ford)
-
Cover trees (Prim, Kruskal)
-
Maximal Flot
-
Linear programming :
-
Modeling a problem as a PL
-
Canonical and standard forms of a PL
-
Resolution methods (graphic, simplex, ...)
-
Tools
Assessment
- Final review
References
- Jacques Teghem : Linear Programming, University of Brussels edition, 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 to algorithmics", Dunod
Skills
3| Ref. | Verb | Description | Level |
|---|---|---|---|
| C2_1 | choose | Know and Use Basic Algorithms of Graph Theory | 2 |
| C2_1 | recognize | Know the principles of linear programming | 1 |
| C2_3 | analyze | Know how to model a problem using different methods | 2 |