Plan de cours 

Enseignants

Horaire

  • jeudi: 10h30 à 12h20 au D4-2022
  • vendredi: 10h30 à 12h20 au D4-2022

Examen

  • Récupérez l'énoncé de l'examen sur Turnin  sous «Examen final» à partir du mercredi 15 avril à 9h
  • Rédigez vos solutions dans un document électronique ou numérisé
  • Remettez vos solutions au format PDF sur Turnin  avant le vendredi 17 avril à 21h
  • L'examen a été conçu comme si vous n'aviez que 3h et une feuille de note
  • Les règles usuelles de plagiat s'appliquent; en particulier, discuter de l'examen constitue du plagiat

Calendrier

Matériel

Contenu

1. Calculabilité (semaines 1‒2)

2. Décidabilité et logique (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
  • Logique du premier ordre: ≈ Sipser chap. 6.2
  • Indécidabilité (d'une extension) de l'arithmétique de Peano 

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

4. Calcul parallèlle et ses limitations (semaine 8)

  • AC, NC et P-complétude: ≈ Sipser chap. 10.5 (ignorez la classe NL) et Arora–Barak chap. 6.7

5. Au-delà de la NP-complétude (semaines 9‒10)

6. Informatique quantique (semaines 11‒12)

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