L'unité d'enseignement « Calculabilité et décidabilité » est une UE de niveau (300) spécialisation relevant de la licence d'informatique. Elle possède un volume de 6 ECTS et s'étend sur 12 semaines. Elle est placée sous la responsabilité de Safey El Din, mohab.

Description

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.

Les applications des différentes notions abordées sont nombreuses (expressions régulières sous bash, emacs, awk, perl, ou sed par exemple, cartes à puces, systèmes embarqués, etc.). La mise en pratique en TME permettra d'acquérir la maîtrise de ces notions. La connaissance de ces concepts est un pré-requis à de nombreuses formations (Parcours STL du Master d'Informatique de l'UPMC, Master UPMC Mathématiques-Informatique, Master Parisien de Recherche en Informatique, Option d'informatique à l'agrégation de mathématiques, etc.). Les unités d'enseignements LI325 (Conception d'algorithmes et applications) ou LI329 (Arithmétique, algorithmes et applications) offrent un très bon complément algorithmique à cet enseignement.

Préalables et buts pédagogiques

Bibliographie

• The design and analysis of computer algorithms. Aho, Hopcroft, Ullman, Addison-Wesley, 1974

• Calculabilité et décidabilité. Autebert, Masson, 1992

• Computational complexity. Papadimitriou, Addison-Wesley, 1994

• Fondements mathématiques de l'informatique, J. Stern, McGraw-Hill, 1990.

Contenu indicatif par semaine

1. Notions de base (alphabets, automates).

2. Langages réguliers (automates à états finis, grammaires, lemme de pompage).

3. Langages hors-contexte : automates à pile déterministe et non déterministe, grammaires hors-contexte.

4. Langages hors-contexte (suite) : équivalence APN et grammaires hors-contexte.

5. Langages récursivement énumérables: Machines de Turing déterministes. Modification de la machine. Machines de Turing non-déterministes.

6. Langages récursivement énumérables (suite) : Grammaires sans restriction, langage sensible hors-contexte.

7. Calculabilité : de l'hypothèse de Church à la machine universelle.

8. Calculabilité : Exemples de problèmes indécidables. Théorèmes de Rice. Problème de correspondance de Post.

9. Complexité : Notions de base et propriétés.

10. Complexité : Hiérarchie des langages et rapports entre classes de complexité.

11. NP-complétude : Classes et réductions polynomiales. Premier problème NP-complet.

12. NP-complétude (suite) : Exemples de réduction, la classe co-NP, complétude pour autres classes.