Catalogue des formations

Diplômes intégrant cet élément pédagogique :

• Licence Mathématiques
• Licence Informatique

Descriptif

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

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 :

• 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

Informations complémentaires

Lieu(x) : Grenoble, Valence
Langue(s) : Français