Ensimag Rubrique Formation 2022

Automates finis - 3MM1AF

  • Volumes horaires

    • CM 13.5
    • Projet -
    • TD 13.5
    • Stage -
    • TP -
    • DS -

    Crédits ECTS

    Crédits ECTS 3.0

Objectif(s)

Ce cours vise à donner aux élèves les bases de la théorie des automates finis.
Il fait partie des cours explicitant les fondements de l'informatique et vise à donner aux élèves aussi bien des connaissances théoriques que des compétences pratique leur permettant d'utiliser les automates à bon escient dans leur vie professionnelle.

Responsable(s)

Sylvain BOULME

Contenu(s)

Automates finis

  • Comment modéliser un langage régulier par un automate et une expression régulière
  • Equivalence de ces deux modèles
  • Algorithmes liés à ces modèles : déterminisation et minimisation
  • Limites de ces modèle : le lemme de l'étoile
  • Application des automates à la résolution de problèmes
    • Ce cours est donné en Période(s) Académique(s) 1 **

Prérequis

Néant.

Contrôle des connaissances

Evaluation : Examen Ecrit (2h)

Rattrapage : Examen Ecrit (2h)

Session 1:

  • ET1 = examen écrit 2h, tous documents autorisés
  • N1 = ET1

Session 2 :

  • ET2 = examen écrit 2h, tous documents autorisés
  • N2 = ET2

Calendrier

Le cours est programmé dans ces filières :

  • Cursus ingénieur - Alternance - Alternance 1ere annee
cf. l'emploi du temps 2025/2026

Informations complémentaires

Code de l'enseignement : 3MM1AF
Langue(s) d'enseignement : FR

Le cours est rattaché aux structures d'enseignement suivantes :

  • Equipe Bases théoriques de l'informatique

Vous pouvez retrouver ce cours dans la liste de tous les cours.

Bibliographie

  • Introduction to automata theory, languages, and computation de Hopcroft, Motwani & Ullman (2007)