Aller au contenu

IFT503 - Théorie du calcul

Présentation

Sommaire

Cycle
1er cycle
Crédits
3 crédits
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. Grammaire hors contexte et automates à pile de mémoire. 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é.

Préalable(s)

(IFT313 ou (MAT115 ou MAT120) et IFT436)