uqac.ca

web

8INF809

Algorithmes et complexité

(3.0 cr.)

Introduire l'étudiant à la théorie de la complexité et aux limites infrangibles des ordinateurs.

Théorie de la NP-complétude. Algorithmes et problèmes algorithmiques. Machines de Turing déterministes, non déterministes et probalistes. Mesures de complexité : temps et espace mémoire. Principales classes de complexité. NP-complétude. Réductions polynomiales. Théorème de Cook. Sujets choisis : hiérarchie polynomiale, preuves interactives, théorème PCP, complexité parallèles, complexité de la communication, etc.

(06/2012)

Appartenance départementale

Informatique et mathématique

Programmes dans lesquels se trouve ce cours

3081 Doctorat en sciences et technologies de l'information
3775 Diplôme de deuxième cycle en informatique appliquée
À propos du site Web institutionnel - © UQAC 2017. Tous droits réservés.