IFT503/IFT711 – Théorie du calcul

• Enseignant: Michael Blondin (en remplacement de Martin Beaudry)
• Plan de cours: 
• Horaire:
  – mercredi: 10h30 à 12h20 au D4-2022
  – jeudi: 15h30 à 16h20 au D4-2022
  
• Examen final: mercredi 24 avril de 13h30 à 15h30 au local D3-2036
• Disponibilité sans rendez-vous: mardi de 11h30 à 12h30 et jeudi de 14h30 à 15h30

Calendrier

Matériel

Matière

• Machines de Turing: chapitre 1 (notes de cours), voir aussi chapitres 3.1–3.2 (Sipser)
• Indécidabilité: chapitre 2 (notes de cours), voir aussi chapitres 4–5 (Sipser)
• Relativisation: chapitre 3 (notes de cours)
• Introduction à la complexité du calcul: chapitre 7.1 (Sipser)
• La classe P: chapitre 7.2 (Sipser)
• La classe NP: chapitre 7.3 (Sipser)
• NP-complétude: chapitres 7.4–7.5 (Sipser)
• Logique et arithmétique: chapitre 6.2 (Sipser)

Références

• Notes de cours de Martin Beaudry:   
• Michael Sipser: Introduction to the Theory of Computation. Second edition, Thomson Course Technology, 2006.

Devoirs

• Devoir 1  (notes disponibles sur Genote depuis le 1^er avr.)
• Devoir 2    (notes disponibles sur Genote depuis le 14 avr.)