Fondements de la programmation

Master 1 en Informatique, année académique 2017-2018

Ce cours d'informatique théorique est la continuation naturelle de cours de license info tels que Calculabilité (L3) et Logique (L1). Je suis responsable des séances de TD, tandis que les CM sont assurés par Paulin de Naurois.

Le cours porte sur les modèles de calcul : machines de Turing, autres machines idéalisées de type RAM (séquentielles ou concurrentes), fonctions récursives, lambda-calcul pur et son interprétation par la machine de Krivine (en appel-par-nom ou appel-par-valeur), extensions Turing-completes du lambda-calcul simplement typé.

Voici la version finale des notes de cours.

Pour davantage de références, je vous renvoie à cette page de Pierre Boudes, qui a monté ce cours avec Virgile Mogbil dans les années passées. (Remarquer que la première partie du cours est pour la plupart tirée du chapitre 7 de Computability and Complexity par Neil Jones.)

Vous trouverez ci-dessous les fiches de TD du cours, avec quelques solutions, et aussi les corrigés du partiel et de l'examen final. N'hesitez pas à me contacter pour tout autre renseignement !

Fiches de TD

• Fiche 1: machines de Turing
  [ voici la solution de l'exercice 8 ]
  
• Fiche 2: machines à compteurs et SRAM
  [ voici la solution des exercices 3 et 5 ]
• Fiche 3: RAM concurrentes
  [ voici la solution de l'exercice 3 ]
  
• Fiche 4: fonctions (primitives) récursives
  [ voici la solution des exercices 1, 3, 4 ]

• Fiche 5: lambda-calcul pur
  
  
• Fiche 6: lambda-calcul pur (suite)
  [ voici la solution des exercices 3, 4, 5, 6, 7, 8 et 10 ]
• Fiche 7: machines de Krivine
• Fiche 8: lambda-calcul simplement typé
• Fiche 9: extensions du lambda-calcul simplement typé