IFT767 - Théorie de la complexité
Présentation
Sommaire
- Cycle
- 2e cycle
- Crédits
- 3 crédits
- Faculté ou centre
- Faculté des sciences
- Répartition de la charge de travail
- 3-0-6
Cible(s) de formation
Identifier les principaux aspects de la théorie de la complexité et évaluer la complexité intrinsèque d'un problème.
Contenu
Modèles de calculs séquentiels et parallèles. Mesures de la complexité : temps, espace, nombre de processeurs. Hiérarchie des classes de complexité : NC, P, NP, Pespace. Notions afférentes : décidabilité, non-déterminisme, oracles, complétude. Calcul de bornes inférieures.