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
Pour toute information, écrivez-nous:
Bureau du registraire
Page réalisée par le Service des technologies de l'information
Extrait du système intégré de gestion des activités relatives à l'enseignement
© Université du Québec à Chicoutimi, 12/2024
| 3775 | Diplôme d'études supérieures spécialisées en informatique appliquée |