Plan de cours 

Diaporama d'introduction 

Enseignants

Horaire

  • mercredi: 10h30 à 12h20 au D4−2022
  • vendredi: 10h30 à 12h20 au D4−2022

Calendrier

Matériel

Contenu

1. Calculabilité (semaines 1‒2)

2. Décidabilité (semaines 3‒5)

  • Indécidabilité du problème d'arrêt: ≈ Sipser chap. 4
  • Preuves par réductions et autres problèmes indécidables: ≈ Sipser chap. 5
  • Réductions de Turing: ≈ Sipser chap. 6.1
  • Théorème de la récursion: ≈ Sipser chap. 6.3

3. P vs. NP (semaines 5‒7)

4. Logique (semaines 7‒8)

5. Calcul parallèlle et ses limitations (semaine 8‒9)

  • Notes de cours 
  • Autres références sur AC, NC et la P-complétude: Sipser chap. 10.5 et Arora–Barak chap. 6.7

6. Complexité en espace (semaines 9‒11)

7. Temps exponentiel et bornes inférieures (semaines 9‒11)

8. Informatique quantique (semaines 11‒12)

  • Références: Chuang–Nielsen chap. 1.2–1.4, 2.1–2.3, 4.1–4.4 et Arora-Barak chap. 10

Étude

Références

  • Michael Sipser: Introduction to the Theory of Computation. Second edition, Thomson Course Technology, 2006.
  • Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
  • Isaac Chuang et Michael Nielsen: Quantum Computation and Quantum Information. Cambridge University Press.

Références complémentaires

Devoirs