Résumé de section
-
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 :
- Apprendre à analyser des propriétés (correction, terminaison, coût) des algorithmes (en relation avec l'UE INF231).
- 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.