UE Automates et langages - INF302 -

Programme résumé :

• Thème 0 : Définition inductive et preuve par induction
  • Théorème de Kleene et points fixes
  • Schéma de preuve par induction

• Thème 1 : Automates
  • Expression d'algorithmes par des automates : actions, contrôle ; configurations, traces d'exécution
  • Correction partielle d'un automate : invariants, schéma de preuve
  • Correction totale, schéma de preuve

• Thème 2 : 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
  • Notion de non déterminisme, déterminisation d'un automate
  • Problèmes de décision : langage vide, langage infini

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 :

• Apprendre à analyser des propriétés (correction, terminaison, coût) des algorithmes (en relation avec l'UE INF301)
• Apprendre à analyser formellement les propriétés d'un langage