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.

Formule pédagogique : Cours Magistral

(01/2024)

Appartenance départementale

Informatique et mathématique

Programme dans lequel se trouve ce cours

3775 Diplôme d'études supérieures spécialisées en informatique appliquée
© UQAC 2024. Tous droits réservés.