Acquis d'apprentissage

Ce cours vise à donner une introduction aux théories de calculabilité et de complexité dans l'informatique.

Objectifs

Ce cours vise à donner une introduction aux théories de calculabilité et de complexité dans l'informatique.

Contenu

Dans une première partie on parle des notions de base comme le concept d'algorithme, les ensembles dénombrables, les fonctions calculables, les ensembles (semi-)décidables et les problèmes insolubles. Dans une deuxième partie, on étudie quelques modèles de calcul comme les langages de programmation, le lambda-caclcul, les fonctions récursives, et les machines de Turing, et on introduit quelques résultats-clés de la calculabilité: le problème d'arrêt, le théorème de Rice, la relation entre interprétation et compilation et les projections de Futamura. Dans une troisième partie, on introduit la théorie de la complexité et on parle des classes de complexité P, NP, et coNP, et on parle des problèmes NP-complets et leur pertinence.

Table des matières

  • Introduction
  • Les ensembles infinis et l'existence des fonctions non-calculables
  • Résultats fondamentaux
    • Langages de programmation
    • Interprétation et compilation
    • Le programme universel
    • Le problème d'arrêt
    • Le théorème de Rice
    • Le théorème de la paramétrisation
    • L'équivalence des langages de programmation
    • Le théorème du point-fixe
  • Les automates finis et les automates à pile
  • Les machines de Turing
  • Les fonctions récursives
  • Le Lambda-calcul
  • Introduction à la complexité
    • La classe P et les transformations polynomiales
    • La classe NP
    • Les problèmes NP-complets
    • La classe NPC
    • Au delà de P, NP, et NPC

Méthodes d'enseignement

Cours ex-cathédra.

Méthode d'évaluation

Examen écrit. L'examen comporte des questions de compréhension et de reproduction.

Sources, références et supports éventuels

  • W. Vanhoof, Calculabilité et complexité, course notes.
  • D. Harel, Algorithmics - The spirit of computing, Addison-Wesley,2004.
  • J.E. Hopcroft, R. Motwani, and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation, Pearson, 3th ed., 2007
  • N.D. Jones, Computability and Complexity, The MIT Press, 1997.
  • B.M. Moret, The Theory of Computation, Addison-Wesley, 1998.
  • C.H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
  • A. Setzer, Computability theory, 2003.
  • T.A. Sudkamp, Languages and Machines, Pearson International, 2006.

Langue d'instruction

Français