Introduction à la théorie de la complexité (I231)

Objectifs du cours

Ce cours de première année de master a pour objectif de familiariser les étudiants d'informatique avec trois théories extrêmement riches et dont les développements récents ont été spectaculaires : la théorie de la calculabilité et de la décidabilité, la théorie de la complexité et la théorie de l'ap­pro­xi­ma­tion.

La théorie de la programmation, qui englobe ces trois théories, cherche à répondre formellement à trois questions fondamentales posées de manière in­for­mel­le :

  1. Que peut-on calculer ?
  2. Que peut-on calculer efficacement ?
  3. Que peut-on approximer efficacement ?
La première question est la question clef de la théorie de la calculabilité et la décidabilité (un problème est décidable si on peut répondre par oui ou non à la question formulée), la deuxième est celle de la théorie de la complexité et la dernière celle de la théorie de l'approximation.

La dématérialisation croissante et la virtualisation progressive de notre univers quotidien ont ali­men­té des questions fondamentales qui semblaient réservées aux logiciens et/ou aux philosophes au début du siècle dernier. La cryptographie, l'analyse numérique, l'intelligence artificielle, pour ne citer que ces domaines, ont stimulé les recherches sur la notion de calcul qui n'ont jamais été aussi vivaces qu'aujourd'hui en informatique.

La première partie du cours est consacrée à la théorie de la calculabilité et de la décidabilité. Avant même d'aborder les notions de performances et d'efficacité, il est utile de connaître la portée des ordinateurs et savoir ce que l'on peut espérer en obtenir. Cette question nous amènera à décortiquer le concept de calcul et nous verrons que tout ne peut pas être calculé, indépendamment du temps et de l'espace disponible.

Le cours de complexité algorithmique en 2024.

La deuxième partie est dévolue à l'étude de la théorie de la complexité. C'est cette théorie qui s'inscrit naturellement dans la suite des enseignements d'algorithmique de licence. Les notions de complexité en temps et en espace ont été abordées dès la première année, formalisées en deuxième année avec l'introduction de la machine ram et sont devenues centrales en 3ème année. On sait à présent comparer l'efficacité des algorithmes grâce à leurs fonctions de complexité. Cette fois, il ne s'agit pas d'étudier de nouveaux algorithmes et leur complexité, si ce n'est pour illustrer le propos, mais d'établir une classification et une hiérarchie dans les problèmes de décision. Nous verrons que nous ne savons pas résoudre efficacement de nombreux problèmes fondamentaux.

La dernière partie est une introduction à la théorie de l'approximation. Il s'agit d'une piste naturelle pour franchir cette apparente barrière établie par la théorie de la complexité. L'idée est simple, si on ne peut pas trouver de procédé efficace pour calculer la solution d'un problème, peut-on faire mieux en relâchant nos exigences sur le résultat attendu ?

Contrôle des connaissances

Le contrôle des connaissances est constitué :

  1. D'une épreuve écrite de 3 heures ;
  2. D'un mini projet évalué.

Annales des contrôles terminaux

  1. Session 1 - Session 2 (2018-2019)
  2. Session 1 - Session 2 (2020-2021)
  3. Session 1 - Session 2 (2021-2022)
  4. Session 1 - Session 2 (2022-2023)

Documents de travail

Vous trouverez le polycopié du cours ici dans sa version pdf. La version en ligne n'est pas encore achevée (la plupart des liens ci-dessous sont encore inactivés).

  1. ✍ Introduction
  2. ✍ Contradictions et théorie des ensembles
  3. ✍ Ensembles finis et infinis
  4. ✍ Modèles de calcul, algorithmes
  5. ✍ La machine ram
  6. ✍ La machine de Turing
  7. ✍ Calculabilité et décidabilité
  8. ✍ Le voyageur de commerce
  9. ✍ Fonctions de complexité
  10. ✍ Les classes P et NP
  11. ✍ Réduction polynomiale, classe NP-complet
  12. ✍ Théorème de Cook et exemples
  13. ✍ Approximation
Quelques fiches sont disponibles dans l'attente de rédaction des chapitres correspondants.
  1. Fiche machine ram et le simulateur
  2. Fiche machine de Turing et le simulateur
  3. Fiche premiers problèmes NP-complets

Travaux pratiques

Les travaux pratiques consistent d'une part à étudier les deux problèmes suivant puis à implanter une solution (et non implémenter) en langage C puis d'écrire un simulateur pour la machine de Turing.

  1. Le problème du cavalier (une solution en langage C)
  2. Le problème du sudoku
  3. L'algorithme dpll (voir dans le polycop).
  4. Instructions pour l'écriture du simulateur
Outre la connexion avec les notions étudiées en cours, ces tp sont avant tout un prétexte pour que les étudiants programment. Il y a six séances de 3 heures (soit deux séances par sujet à traiter) et une dernière séance consacrée à l'examen pratique.

Bibliographie

Les deux premiers ouvrages demandent assez peu de connaissances mathématiques mais une bonne maturité pour comprendre les tenants et les aboutissants de cette théorie. La deuxième référence est également très abordable mais les démonstrations omniprésentes demandent une pratique certaine dans le domaine des mathématiques discrètes. Le dernier ouvrage est le plus difficile, les outils mathématiques sous-jacents dépassent rarement le niveau de la licence, mais ils sont très variés. La nature du sujet et les démonstrations parfois extrêmement élaborées, en font un ouvrage qui s'adresse principalement aux étudiants de master avec une bonne culture mathématique.
  1. Sur la calculabilité :
  2. Sur la théorie de la complexité et l'approximation :