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

Calendrier

Matériel

Contenu

1. Calculabilité (semaines 1‒3)

• Automates et langages formels: ≈ Sipser chap. 1.1
• Machines de Turing: ≈ Sipser chap. 3
• Machine de Turing pour l'addition sur trois rubans 

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)

• Export de mes notes
  -- Classes P et NP (8 février)
  -- Problèmes NP-complets (10 février)
  -- Réductions (15 février)
• Exercices supplémentaires
  -- Solutions
  
• NP et NP-complétude : Sipser chap. 7

4. Logique (semaine 8)

• Logique du premier ordre: ≈ Sipser chap. 6.2
• Indécidabilité (d'une extension) de l'arithmétique de Peano 

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

• 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. 

Devoirs

• Devoir 1 
• Devoir 2 
• Devoir 3 
• Devoir 4