IFT711 - Théorie du calcul
Présentation
Sommaire
- Cycle
- 2e 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. 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é.