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

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