Section outline

  • Travail encadré : 60 heures

    Travail personnel conseillé : 60 heures

    ECTS : 6

    Mots Clés :

    • Automates : 
      • définition : syntaxe et sémantique
      • déterminisme et non-déterminisme, déterminisation.
      • opérations de composition des automates
      • expression d'algorithmes (actions, contrôle, configurations, traces), correction.
    • Langages réguliers : reconnaissance par un automate d'états fini, propriétés algébriques, problèmes de décision, constante d'itération.
    • Expressions régulières : définition (syntaxe et sémantique), théorème de Kleene, conversions entre automates et expressions régulières, lemme d'Arden.
    • Grammaires régulières.
    • Langages non-réguliers : lemme de l'itération.


    Pré-requis pour cette UE : INF 201 (programmation fonctionnelle)

     

    Programme résumé : Langages réguliers et automates d'états finis

    • Reconnaissance d'un langage régulier par un automate d'états fini.
    • Propriétés algébriques des langages réguliers (expression régulières, traduction vers et depuis des automates).
    • Notion de non déterminisme (automates non-déterministes et avec epsilon-transitions), déterminisation d'un automate.
    • Problèmes de décision : langage vide, langage infini.

    Si le temps le permet : Définition inductive et preuve par induction

    • Théorème de Kleene et points fixes
    • Schéma de preuve par induction

    Compétences visées :

    • La maîtrise de la programmation s'appuie sur l'étude des langages et moyens d'expression utilisés en informatique et sur la compréhension des modèles de calcul sous-jacents.
    • Les automates sont des structures finies qui permettent de décrire des phénomènes infinis, par exemple l'ensemble des comportements d´un programme ou l'ensemble des phrases d'un langage.
    • La théorie des automates fait partie des fondements de l'informatique. Dans ce cours nous l'abordons avec les objectifs suivants :
    1. Apprendre à analyser des propriétés (correction, terminaison, coût) des algorithmes (en relation avec l'UE INF231).
    2. Apprendre à analyser formellement les propriétés d'un langage.


    Evaluation (version préliminaire) :

    • CC1 : examen à mi-parcours (au milieu du semestre), coefficient 0,4
    • CC2 : examens courts tout au long du semestre, coefficient 0,4
    • EF : examen final lors de la semestre de partiels prévue à cet effet, coefficient 1,2 

    La note finale est donc :

    (0,4*CC1 + 0,4*CC2 + 1,2*EF)  /  2.