IFT767 - Théorie de la complexité

programmes offrant cette activité pédagogique (cours)

Doctorat en informatique

Maîtrise en informatique

Sommaire

Cycle
2e 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

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.