THEORIE DES AUTOMATES ET DES LANGAGES, THEORIE DES GRAPHES

  • See this page in english

    En bref

  • Crédits ECTS : 5
  • Code : N7EN10

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

Contact(s)

MORIN GÉRALDINE

Contactez l’ENSEEIHT

L’École Nationale Supérieure d'Électrotechnique, d'Électronique, d'Informatique, d'Hydraulique et des Télécommunications

2, rue Charles Camichel - BP 7122
31071 Toulouse Cedex 7, France

+33 (0)5 34 32 20 00

Certifications

  • Logo MENESR
  • Logo UTFTMP
  • Logo INP
  • Logo INPT
  • Logo Mines télécoms
  • Logo CTI
  • Logo CDEFI
  • Logo midisup