Calculabilité et décidabilité (ICC), MAIN4, 2021-2022
Nouvelles fraîches
- Début des cours le lundi 13
septembre 2021
- Les cours ont lieu toutes les semaines
Les TD ont lieu les 01/10, 08/10, 22/10, 12/11, 26/11
Description de l'UE
De nombreuses réalisations informatiques allant du parser aux systèmes embarqués, sont basées sur
des modèles de calcul plus ou moins complexes.
Dans cette unité d'enseignement, nous abordons les différents modèles de calculateurs classiques via
la théorie des automates (finis, à pile, etc.), puis les machines de Turing. Nous caractérisons les
problèmes pouvant ou non être résolus par chacun de ces modèles. En outre, ils seront illustrés par
une application classique en informatique. Sur la base de ces constructions, nous introduisons la
notion de complexité et en étudions les grandes classes.
Programme indicatif par semaine
- Notions de base (alphabets, automates)
- Langages réguliers (automates à états finis, grammaires, lemme de pompage)
- Langages hors-contexte : automates à pile déterministe et non déterministe, grammaires hors-contexte
- Langages hors-contexte (suite) : équivalence APN et grammaires hors-contexte
- Langages récursivement énumérables: Machines de Turing déterministes. Modification de la machine. Machines de Turing non-déterministes
- Langages récursivement énumérables (suite) : Grammaires sans restriction, langage sensible hors-contexte
- Calculabilité : de l'hypothèse de Church à la machine universelle
- Calculabilité : Exemples de problèmes indécidables. Théorèmes de Rice. Problème de correspondance de Post
- Complexité : Notions de base et propriétés
- Complexité : Hiérarchie des langages et rapports entre classes de
complexité, classes et réductions polynomiales. Premier problème NP-complet
Équipe pédagogique
Horaire
- Cours : le lundi de 13h45 à 15h45, salle (voir ADE)
- TD : le vendredi de 13h45 à 15h45, salle (voir ADE) les 01/10, 08/10, 22/10, 12/11, 26/11
Examens et notations
La note de module est composée de la moyenne des 3 interrogations.
Documents disponibles
- Semaine 1 :
- Cours1 : Rappels sur les automates finis
déterministes et non-déterministes, équivalence AFD/AFN, epsilon-transitions
- TD1
- Semaine 2 :
- Cours2 : Epsilon-transitions, expressions régulières, expressions régulières et automates finis
- TD1
- Semaine 3 :
- Cours3 : Expressions régulières et automates
finis, propriétés des langages réguliers, minimisation d'automate
- TD1
- Semaine 4 :
- Cours4 : Grammaires et langages hors-contexte,
définitions, constructions, inférence, dérivations, arbres de dérivation,
ambiguité + interrogation
- TD2
- Semaine 5 :
- Cours5 : Automates à piles, définition,
premières propriétés, reconnaissance par états acceptants, par pile vide, automates à pile et grammaires hors-contexte, automates à pile déterministe
- TD2
- Semaine 6 :
- Cours6 : Forme normale de Chomsky, lemme de pompage, propriétés de cloture des langages hors-contexte, problèmes de décision sur les langages hors-contexte
- TD2
- Semaine 7 :
- Cours7 : Machines de Turing, représentations
(descriptions instantannées, diagrammes)
- TD2
- Semaine 8 :
- Cours8 : Langage reconnu par une MT, arrêt d'une MT, MT multi-rubans, automates multi-piles, machines à compteurs, équivalences + interrogation
- TD3
- Semaine 9 :
- Cours9 : Indécidabilité, langage diagonale,
langage universel, machine de Turing universelle
- TD4
- Semaine 10 :
- Cours10 : PCP, complexité, classe P et NP + interrogation
- TD4
Logiciels
Pour simuler des automates, expressions regulières, automates à piles, grammaires et machines de Turing, vous pouvez
utiliser les outils suivants :
Interrogations
Interrogations des années précédentes
Bibliographie
- Introduction
to automata theory, languages and computation; Hopcroft, Motwani, Ullman; 3e
édition; Addison-Wesley; 2006
- Introduction
to the theory of computation; Michael Sipser; 3e édition; Cengage Learning; 2012
- Introduction à la calculabilité; Wolper; 3e édition; Dunod; 2006
- Formal language, a practical introduction; Adam Webber; Franklin, Beedle & Associates; 2008
- Langages formels, calculabilité et complexité; Carton; Vuibert; 2014
- An introduction to formal languages and automata; Linz; 6e édition; Jones & Bartlett Learning; 2016
- Automata and Computability, A Programmer's Perspective; Ganesh Gopalakrishnan; CRC Press; 2019
Stef Graillat
(Dernière modification : juillet 2021)