Master informatique
Théorie des Programmes (TP)
Code apogéeDINF7TPRStructurexxDernière mise à jour le19 Septembre 2018
Responsable pédagogiqueMONIN François (Maître de conférences, 27ème section)
Parcours
  • Master 1 2017-2022
TypeObligatoire
Semestre7Volume horaire48Crédits ECTS0
Nombre d'heures Cours magistraux (CM)18 Travaux dirigés (TD)18 Travaux pratiques (TP)12 
Pré-requis  Connaissances dans le domaine des fondements des langages et de la programmation et des systèmes formels.
Co-requis 
Objectif Terminal 
Objectif Pédagogique

 Acquisition de fondements théoriques nécessaires à la compréhension de la programmation.

Conception et vérification de différents schémas de programmes.

Définition d’une sémantique de langage et définition de support formel pour la représentation de programmes.

Compréhension et analyse de complexité de programmes.  

Contenu détaillé de l'enseignement
  •  Lambda-calcul : l’alpha-équivalence et la béta-réduction, formes normales, propriété de confluence, currification, combinateurs de points fixes, représentation de fonctions récursives, logique combinatoire, lambda-calcul typé, correspondance de Curry-Howard.
  • Calculabilité : dénombrabilité, fonctions primitives récursives, prédicats primitifs récursifs, minimisations bornée et non bornée, fonction d’Ackermann, fonctions récursives,  machines de Turing, Thèse de Church, décidabilité.
  • Complexité : croissance de fonctions, notation et analyse asymptotique, mesures et classes de complexité, études de programmes.
Méthodes d'enseignement Cours s’appuyant sur TD et TP
Evaluation session 1

Examen écrit de 2 heures (3/4)+ Projet (1/4)

Evaluation session 2 Examen écrit de 2 heures.
Références Bibliographiques 1. Lambda-calcul, types et modèles, Jean-Louis Krivine, Editions Masson.

2. The Lambda-calculus. H.P. Barendregt. Volume 103, Elsevier Science Publishing Company.

3. Logique, réduction, résolution. R. Lalement. Editions Masson.

4. Logique mathématique (Tome 2). René Cori et Daniel Lascar. Editions Dunod.

5. Introduction à la calculabilité. Pierre Wolper. InterEditions.

6. Introduction à l’algorithmique. T.H Cormen, C.E Leiserson, R.L Rivest, C. Stein. Edition Dunod.