Horaire
- mercredi: 08h30 à 10h20 au D4−2022
- vendredi: 10h30 à 12h20 au D4−2022
Contenu
1. Calculabilité (semaines
1‒3)
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 6‒7)
4. Logique (semaine 8)
5. Calcul parallèle et ses
limitations (semaine 9)
- AC, NC et P-complétude: ≈ Sipser chap. 10.5 et
Arora–Barak chap. 6.7
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