AccueilLicence généraleInformatiqueEnseignementsAutomates finis

Licence InformatiqueUE Automates finis

Contenu

Ce cours permet d'appréhender les bases théoriques de l'informatique en définissant la notion d'automate.

  • Automates finis déterministes et non-déterministes (AFD-AFN) et leur utilisation en modélisation.
  • Produit cartésien d'automates
  • Déterminisation d'automates finis non-déterministes
  • Clôture booléenne des AFN (union, intersection, complémentaire)
  • Minimisation d'automates finis
  • Test du vide et équivalence/inclusion de langages réguliers
  • Recherche de motif (automate de Simon)

Compétences visées

  • Se servir aisément des bases de la logique pour valider ou réfuter un raisonnement.
  • Rédiger de manière synthétique et rigoureuse des preuves.
  • Utiliser les concepts fondamentaux de l'informatique (langages formels, logique, et graphes) pour la programmation et la modélisation.

Langue utilisée

Langue principale utilisée par cet enseignement : Français.

Bibliographie

  • Jacques Sakarovitch J. (2013) Elements of Automata Theory, Cambridge University Press.
  • Hopcroft, John E. ; Motwani, Rajeev ; Ullman, Jeffrey D. (2013). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Pearson.

Pré-requis recommandés

  • Architecture des ordinateurs (modèles à états déterministes finis : machines de Mealy)
  • Structures discrètes (préfixe, suffixe, facteur, opérations sur les mots, base de la combinatoire de mot)

Volume des enseignements

  • Cours magistraux : 9 heures
  • Travaux dirigés : 15 heures
  • Travaux pratiques : 6 heures

Les formations qui utilisent cet enseignement