Archive 2019
Validationexamen
EnseignantPaul Rozière et Hervé Fournier
Horaires hebdomadaires 4 h CM , 2 h TD
Années Master Logique et Fondements de l'Informatique

Syllabus

  • Calculabilité : fonctions récursives et fonctions calculables par machine ; caractérisation logique des fonctions calculables ; théorème smn et théorèmes de point fixe ; notions de réduction et problèmes indécidables.
  • Introduction à la complexité : classes en temps et espace, théorèmes de hiérarchie, réductions, complétude, circuits booléens, introduction à la complexité algébrique.
  • Arithmétique formelle : axiomes de Peano et sous-systèmes faibles ; arithmétisation de la logique ; théorèmes d’indécidabilité ; les théorèmes d’incomplétude de Gödel.

Bibliographie

  • J.BARWISE (ed) : Handbook of Mathematical Logic (North-Holland, 1977-1999).
  • R.CORI & D.LASCAR : Logique mathématique : cours et exercices (Dunod, 2 tomes, 2003).
  • R.LASSAIGNE & M. de ROUGEMONT : Logique et Complexité (Hermès, 1996).
  • M. MACHTEY & P. YOUNG : An introduction to the General Theory of Algorithms (North Holland, 1978).
  • J.R. SCHOENFIELD : Mathematical Logic (Addison-Wesley, 1967. Assoc. for Symb. Logic, 2001).
  • R. SMULLYAN : Les Théorèmes d’Incomplétude de Gödel (Masson, 1993).
  • O. GOLDREICH : Computational Complexity : A Conceptual Perspective (Cambridge University Press, 2008).
  • N.D. JONES : Computability and Complexity : From a Programming Perspective (MIT Press, 1997).