Partager cette page :
Discipline(s) : Infomatique et télécommunications

Fondements de l'informatique 1 : langages formels et calculabilité

Semestre Semestre 1
Type Obligatoire
Nature UE
Crédits ECTS 6
Volume horaire total 40
Volume horaire CM 20
Volume horaire TD 20

Pré-requis

Mathématiques élémentaires (démonstrations, etc.).
Un prérequis en théorie des automates finis est apprécié mais n’est pas obligatoire (la théorie des automates est revisitée en début de cours).

Objectifs

Acquérir une bonne intuition sur les capacités d'expression des différents modèles. Savoir mettre en œuvre les modèles et les algorithmes associés (déterminisation, minimisation, etc.). Le cours et les TD associés sont aussi l'occasion d'acquérir ou de renforcer de bons réflexes de rigueur dans les raisonnements.

Contenu

Description du cours

L'objectif du cours est d'étudier conjointement deux des piliers fondamentaux de l'informatique : les notions de langage formel, et de machine, appréhendée en tant que modèle de calcul. Le but ultime est de répondre à la question : qu'est-ce qui est calculable par une machine ? On s'intéresse donc aux différentes classes de langages (rationnels, algébriques, récursifs, etc.), et aux dispositifs permettant de les reconnaître (automates finis, automates à pile, machines de Turing, etc.) ou de les générer (expressions rationnelles, grammaires). Le cours s'attache à montrer le pouvoir d'expression de ces différentes classes, et à mettre en lumière quelque liens avec les domaines d'applications de ces fondements (algèbre, logique, compilation, etc.).

Programme

A – Langages rationnels 
1. Expressions rationnelles
2. Automates finis
3. Théorème de Kleene
4. Automates déterministes complets.
5. Type abstrait « langage rationnel » : application à l’arithmétique de Presburger.
6. Automate minimal
B – Langages algébriques
1. Grammaires algébriques
2. Problème du mot
3. Automates à pile
C – Calculabilité
4. Machines de Turing
5. Théories des fonctions récursives
6. Décidabilité et indécidabilité

Références

Compléments de cours sur le site du cours :
http://people.irisa.fr/Francois.Schwarzentruber/mit1_lf_2016/

Bibliographie

J.-M. Autebert, Théorie des langages et des automates, Masson, 1994.
 
Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, 2008.
 
John E. Hopcroft, Rajeev Motwani, et Jeffrey D. Ullman, Introduction to
Automata Theory, Languages, and Computation, Prentice Hall, 2007.
 
J. Sakarovitch, Eléments de théorie des Automates, Vuibert, 2003.
 
Pierre Wolper, Introduction à la calculabilité, Dunod, 2006.
 
Michael Sipser. Introduction to the Theory of Computation. Boston : Thomson Course Technology, 2006.

Contrôles des connaissances

Contrôles continus (CC) : un devoir maison et un rapport sur un sujet non abordé en cours au choix parmi une liste de sujets possibles et un devoir sur table final
En session de rattrapage, un examen oral (O).
Note finale en session 1 : CC
Note finale en session 2 : O

Mise à jour le 12 juillet 2017