THEORIE DES AUTOMATES ET DES LANGAGES, THEORIE DES GRAPHES

The objective of the UE is twofold. The student must master the formalisms of finite automata, stack automata and Turing machine for the modeling of state based systems and the implementation of lexical and syntactic analyses. He is also introduced to the computability and complexity theories.
The student must also master the principal concepts and results of Graph Theory and is able to apply them to real life problems and situations. He can implement and test classical algorithms of graph theory, such as Euler’s circuit, Disjkstra’s shortest path, Welsh-Powell’s coloring, etc.