Aller au contenu

IFT767 - Théorie de la complexité

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

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.