[AAA7] Automates avancés et applications 2023–2024

1ère année de Master informatique, UFR informatique, Université de Paris

Modalités de contrôle des connaissances

contrôle continu, pour 50% de la note finale: CC₁, CC₂ et CC₃ : trois contrôles d'une heure chacun, les 12/10, 16/11 et 14/12
examen, pour 50% de la note finale: EX : examen final, en janvier

Séances et intervenant·e·s

cours : mardis 14:15–16:15 en salle Sophie Germain 1020
travaux dirigés : jeudis 11:00–13:00 en salle Sophie Germain 1020

Sylvain Schmitz du 19/09 au 12/10
Daniela Petrisan du 17/10 au 16/11
Roberto Mantaci du 21/11 au 14/12

Matériel pédagogique

page Moodle du cours
TD 1 : Langages rationnels
TD 2 : Langages rationnels, encore
TD 3 : Grammaires algébriques
TD 4 : Automates à pile
CC 1 : Automates à pile déterministes à rendre sur Moodle pour le 26 octobre 2023

Programme

1. Révisions

automates finis
expressions rationnelles
lemme de l'étoile
grammaires algébriques
automates à pile

2. Automates, monoïdes et logique

minimisation des automates déterministes
logique monadique du second ordre sur les mots
logique du premier ordre sur les mots
langages apériodiques

3. Ouvertures

apprentissage des automates déterministes
automates de Büchi
automates cellulaires

Autres ressources pédagogiques

En ligne

notes de préparation (incomplètes) pour l'agrégation de mathématiques de Benjamin Monmege et Sylvain Schmitz
notes de cours de François Yvon et Akim Demaille
notes de cours de Michel Rigo
exercices de TD 2022–2023 d'Arnaud Sangnier

Ouvrages

Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, 2008. catalogue bibliothèques 1^e édition, 2^e édition
Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003. catalogue bibliothèques