IFT711 - Théorie du calcul

Sommaire

Cycle: 2e cycle
Crédits: 3 crédits

Faculté ou centre: Faculté des sciences
Trimestres *: Hiver 2025
Répartition de la charge de travail: 3-0-6

Cible(s) de formation

S’initier aux principaux modèles théoriques de l’informatique, à leur puissance descriptive et à leurs limitations. Apprendre à évaluer la complexité intrinsèque d’un problème.

Contenu

Automates finis déterministes et non déterministes. Langages réguliers et expressions régulières. Machines de Turing. Décidabilité et calculabilité. Calcul avec bornes de temps et d’espace; P et NP; problèmes NP-complets; introduction à la théorie de la complexité.

* Sujet à changement