IFT503 - Théorie du calcul

programmes offrant cette activité pédagogique (cours)

Baccalauréat en informatique

Sommaire

Cycle
1er 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. 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