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
3775 | Diplôme d'études supérieures spécialisées en informatique appliquée |