IFT503 - Théorie du calcul

Sommaire

Cycle: 1er 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. 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 (MAT120 et IFT436))

* Sujet à changement