Topic outline
Informations Générales
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.
Transparents du Cours
Cette section contient les transparents de cours.
Illustrations
Tutorial Sessions (INF 332)
This section contains the chapters of the booklet for tutorial sessions.
Examens Précédents
Cette section contient les examens précédents.
Quelques liens en rapport avec ce cours