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

Calendrier

Matériel

Contenu

1. Calculabilité (semaines 1‒2)

• Séances vidéos en rediffusion: jeudi 14 jan.  | ven. 15 jan. 
• Automates et langages formels: ≈ Sipser chap. 1.1
• Machines de Turing: ≈ Sipser chap. 3
• Machine de Turing pour l'addition sur trois rubans 

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. 
• Raymond Greenlaw, Walter L. Ruzzo, H. James Hoover: Limits to Parallel Computation. Oxford University Press, 1995. 

Devoirs

• Devoir 1  (gabarit LaTeX )