Cours 2020-2021

Calculabilité et complexité [INFOM113]

  • 5 crédits
  • 30h
  • 2e quadrimestre
Langue d'enseignement: Français

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

Les modalités d'enseignement et d'évaluation des unités d'enseignement ont été rédigées en fonction de la situation à la rentrée académique 2020-2021. Cependant, ces modalités pourraient faire l'objet de modifications en fonction de l'évolution de la crise sanitaire liée à la covid-19. Les étudiants seront informés de toute modification de la situation générale (passage à l'enseignement à distance partiel ou complet) par les autorités de l'UNamur tandis que les modifications propres à chaque unité d'enseignement leur seront communiquées par les enseignants, via webcampus

Cours ex-cathédra.

Mode d'évaluation

Les modalités d'enseignement et d'évaluation des unités d'enseignement ont été rédigées en fonction de la situation à la rentrée académique 2020-2021. Cependant, ces modalités pourraient faire l'objet de modifications en fonction de l'évolution de la crise sanitaire liée à la covid-19. Les étudiants seront informés de toute modification de la situation générale (passage à l'enseignement à distance partiel ou complet) par les autorités de l'UNamur tandis que les modifications propres à chaque unité d'enseignement leur seront communiquées par les enseignants, via webcampus

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'enseignement

Français

Lieu de l'activité

NAMUR

Faculté organisatrice

Faculté d'informatique
rue Grandgagnage 21
5000 NAMUR
T. 081725252
F. 081724967
secretariat.info@unamur.be

Cycle

Etudes de 2ème cycle