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.  | jeudi 21 jan.  | ven. 22 jan. 
• 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‒4)

• 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 5-6)

• Séances vidéos semaine 5 (youtube, en direct et disponible en rediffusion):
  
  - Cours du jeudi 11 mars, à 10h30
  ---- Export de mes notes (pdf) [Définitions de base]
  
  - Cours du vendredi 12 mars, à 10h30
  ---- Export de mes notes (pdf) [Définition de NP-complet]
• Séances vidéos semaine 6 (youtube, en direct et disponible en rediffusion):
  
  - Cours du jeudi 18 mars, à 10h30
  ---- Export de mes notes (pdf) [Réductions, réductions...]
  
  - Cours du vendredi 19 mars, à 10h30
  ---- Export de mes notes (pdf) [3-COL est NP-Complet]
  ---- Export de mes notes (pdf) [Théorème de Cook-Levin]
• Exercice supplémentaires
  -- SOLUTIONS
• Sipser chap. 7

4. Calcul parallèlle et ses limitations (semaines 7‒8)

• Séances vidéos en rediffusion: jeudi 11 mars  | ven. 12 mars  | jeudi 18 mars 
• AC, NC et P-complétude: ≈ Sipser chap. 10.5 et Arora–Barak chap. 6.7
• L, NL et NL-complétude: ≈ Sipser chap. 8.4–8.5 et Arora–Barak chap. 4.3
• NL-complétude de 2-SAT 

5. Complexité de l'approximation (semaines 8‒9)

• Séances vidéos semaine 8 (youtube, en direct et disponible en rediffusion):
  - Cours du vendredi 19 mars, à 10h30
  ---- Export de mes notes (pdf) [Algos d'approximation]
  
  - Cours du jeudi 25 mars, à 10h30
  ---- Export de mes notes (pdf) [Inapproximabilité]
  ---- Export de mes notes (pdf) [Classe PCP]
  
  
  - Cours du vendredi 26 mars, à 10h30
  ---- Export de mes notes (pdf) [Classe PCP, infos devoir]
  
• Exercice supplémentaires
  ---- Solutions
• Références: Arora–Barak chap. 11, réduction pour MinTSP  (réf. de l'U. de Toronto)

6. Informatique quantique (semaines 10‒11)

• Références: Chuang–Nielsen chap. 1.2–1.4, 2.1–2.3, 4.1–4.4

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 )
• Devoir 2 
• Devoir 3  (Pistes de solutions)
• Devoir 4 
• Devoir 5