IFT503/IFT711 – Théorie du calcul (hiver 2026)

Calendrier

Matériel

Contenu

1. Calculabilité (semaines 1‒2)

• Chap. 1 des notes de M. Blondin 

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

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

3. P vs. NP (semaines 5-6)

• Export de mes notes (pdf) [P vs NP]
  Export de mes notes (pdf) [NP-complétude]
  Export de mes notes (pdf) [Réductions]
  Théorème de Cook-Levin [diapos]
  
• Exercices supplémentaires
  SOLUTIONS
• NP et NP-complétude : Sipser chap. 7

4. Logique (semaine 7)

• Chap. 4 des notes de M. Blondin 

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

• Chap. 5 des notes de M. Blondin 

5. Informatique quantique (semaines 9‒10)

• Notes disponibles sur le groupe Teams
• Postulats de l'informatique quantique: ≈ Nielsen and Chuang chap. 2.2
• Circuits et portes quantiques: ≈ Nielsen and Chuang chap. 4

6. Complexité en espace (semaines 11-13)

• Complexité en espace 1 (export de mes notes)
  
• Complexité en espace 2 (export de mes notes)
  
• Géographie généralisée est PSPACE-complet (export de mes notes)
  

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.
• Michael Nielsen et Isaac Chuang : Quantum Computation and Quantum Information. Cambridge University Press.

Références complémentaires

• Javier Esparza et Michael Blondin: Algorithmic Theory — An Algorithmic Approach. MIT Press, 2023. 
• Sylvain Perifel: complexité algorithmique. Ellipses, 2014. 
• Lecture avancée: Christoph Haase: A survival guide to Presburger arithmetic. SIGLOG News 5(3), 2018. 
• Raymond Greenlaw, Walter L. Ruzzo, H. James Hoover: Limits to Parallel Computation. Oxford University Press, 1995. 

Examens de pratique

• Examen de pratique pour l'intra 
• Examen de pratique pour le final 

Devoirs

• Devoir 1 
• Devoir 2 
• Devoir 3 
• Devoir 4 
• Devoir 5 
• Devoir 6