Horaire
- jeudi: 10h30 à 12h20 au
D4-2022
- vendredi: 10h30 à 12h20 au D4-2022
- 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
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