IFT711 - Théorie du calcul

programmes offrant cette activité pédagogique (cours)

Doctorat en informatique

Maîtrise en informatique

Sommaire

Cycle
2e cycle
Crédits
3 crédits
Durée
1 trimestre
Faculté/Centre
Faculté des sciences
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é.