General Engineering Program
General Data
Academic program General Engineering Program :
Type d'EC Classes (LIIAem08ERechOp)
Lectures : 12h00
Tutorials : 4h00
Total duration : 24h00
Status :
Period :
ACADEMIC SEMESTER
Education language :
French
Learning Outcomes
This course introduces Operations research as an optimization process on the particular context of graph theory. In this course, we will explain well-known problems of operations research as the shortest path, minimum spanning tree, and maximum flow. We will study how to modeling into graph and which algorithms solve that kind of problem.

Five competences will be evaluated in relation to:
- Vocabulary and mathematical concepts
- Problem modeling
- Application of algorithms
- Adaptation of a known algorithm
- Interpretation of a result
Content
Course outline:
- Graphs: definitions
- Connectivity
- Path problem
- Hamitonians paths and heuristic
- Minimum spanning tree
- Graphs coloration
- Maximum flow
- Problems raised with large graphs
Pre-requisites / co-requisites
Fundamentals of algorithms: conditions, loops, arrays, lists, trees
Bibliography
- Roseaux, "Exercices et problèmes résolus de recherche opérationnelle", Tome 1, Dunod, Paris 2002, 296p.
- M. Gondran, M. Minoux, "Graphes et Algorithmes", Eyrolles, Paris 1995, 588p.
- R. Faure, B. Lemaire, C. Picouleau, "Précis de recherche opérationnelle", Dunod, 2000, 520p.

Assessment(s)
Nature Coefficient Observable objectives
1General assessment on the entire course.
- Vocabulary and mathematical concepts
- Problem modeling
- Application of algorithms
- Adaptation of a known algorithm
- Interpretation of a result
1Written exam