• Votre sélection est vide.

    Enregistrez les diplômes, parcours ou enseignements de votre choix.

Automates finis et applications

  • Composante

    ENSEIRB-MATMECA

Code interne

EI5IF114

Description

Les automates finis permettent de modéliser des programmes informatiques à mémoire finie. Ils permettent de résoudre des problèmes à un niveau d'abstraction élevé, sans s'encombrer des spécificités d'un langage donné, et en se concentrant sur les invariants à maintenir pour parvenir à une solution. L'étude de ce modèle s'inscrit dans le cadre général de la théorie des langages abordée ensuite dans les modules IF203 (compilation) et IF228 (calculabilité et complexité). L'enseignement aborde des notions théoriques (automates finis, langages réguliers, expressions régulières, équivalence de ces trois formalismes, non-déterminisme, automate minimal, lemme de l'étoile) ainsi que leur utilisation pour la résolution de problèmes concrets.

Lire plus

Heures d'enseignement

  • CMCours Magistral9,31h
  • TDTravaux Dirigés14h

Pré-requis obligatoires

Syllabus


Automates finis, langages
Expressions régulières, théorème de Kleene
Langages non-régulier, lemme de l'étoile
Grammaires
Déterminisme, algorithme de déterminisation
Automate minimal, algorithme de minimisation
Introduction à l'analyse lexicale

Lire plus

Bibliographie

Polycopié

Lire plus

Modalités de contrôle des connaissances

Évaluation initiale / Session principale - Épreuves

Type d'évaluationNature de l'épreuveDurée (en minutes)Nombre d'épreuvesCoefficient de l'épreuveNote éliminatoire de l'épreuveRemarques
Contrôle Continu IntégralContrôle Continu1