UE Automates et langages (INF 352)

• 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 INF351)
• Apprendre à analyser formellement les propriétés d'un langage.