THEORIE DES AUTOMATES ET DES LANGAGES, THEORIE DES GRAPHES

Objectifs

L’objectif de l’UE est double. D’une part, l’étudiant doit maitriser le formalisme des automates finis, des automates à piles et des machines de Turing, pour la modélisation de systèmes à états et l’implantation d’analyseurs lexicaux et syntaxiques. Il doit de plus être familiarisé avec la théorie de la calculabilité et de la complexité.
D’autre part, l’étudiant doit maîtriser les concepts et les principaux résultats de la théorie des graphes et est capable de les appliquer à des situations et problèmes de la vie courante. Il est capable de programmer et de tester des algorithmes classiques de la théorie des graphes, tels que les circuits d’Euler, le plus court chemin de Diskjstra, le coloriage de Welsh-Powell, etc.

Bibliographie

• Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, 2008 (ISBN 978-2-7117-2077-4)
• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2013). Introduction
to Automata Theory, Languages, and Computation(3rd ed.). Pearson. ISBN 1292039051.
• Ferdinand Wagner, Ruedi Schmuki,Thomas Wagner et Peter Wolstenholme,
Modeling Software with Finite State Machines : A Practical Approach,
Auerbach Publications, 2006, 392 p. (ISBN 9780849380860).
* Gondran, Michel, and Michel Minoux. Graphs and algorithms. Wiley, 1984

Organisation

• Automates (Coefficient 50 )
• Graphes (Coefficient 50 )