Number of hours
- Lectures 13.5
- Projects -
- Tutorials 12.0
- Internship -
- Laboratory works -
- Written tests -
ECTS
ECTS 2.5
Goal(s)
The notion of graph is a useful tool in complex modelling. It may be needed in some cases, for example for modellign some optimization problems.
After following this course, the student should be able to:
- use graphs as a modelling tool;
- design and understand graph algorithms;
- understand correctness proofs for simple graph algorithms.
Responsible(s)
Yann KIEFFER
Content(s)
Unoriented graphs:
- chains, cycles;
- binary relations; connexity;
- trees;
- minimum spanning trees.
Oriented graphs:
- paths, circuits;
- topological sorting;
- accessibility;
- shortest paths;
- certificates.
Basic algorithmic notions:
- control structures;
- Tracing an algorithm.
Test
E1: exam (1st session): 90 minutes written exam with documents and calculator
E2: exam (2nd session): 90 minutes written exam or 30 minutes oral exam
CC: homework assignment
Calendar
The course exists in the following branches:
- Curriculum - Network and computer science - Semester 6
- Curriculum - EIS - Semester 6
Additional Information
Course ID : 3AMMA351
Course language(s):
The course is attached to the following structures:
You can find this course among all other courses.
Bibliography
« Théorie des graphes et applications », Jean-Claude Fournier, Hermès, 2006.