Search Log in FR EN

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

FISEFISA STI Semester 7 Common Core Machine translation

Modeling and Graph Theory

Teaching unit Fundamental Computer Science · AS07_IF1  |  EC Code AS07_IF1-1
Course on Celene
7ECTS (EU)
1Coefficient
21:20Hours

Séquencement

C TD C TD C TD C TD C TD C TD C TD C TD

Learning objectives

Bringing the keys to computer problem modelling through two major modelling systems: graph theory and linear programming.

Prerequisites

ModuleTeaching unitSemester
Algorithms and ComplexityProgramming PrinciplesS5

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.VerbDescriptionLevel
C2_1chooseKnow and Use Basic Algorithms of Graph Theory2
C2_1recognizeKnow the principles of linear programming1
C2_3analyzeKnow how to model a problem using different methods2