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)