Liens transverses ENS de Lyon

INFO4217 : Complexité Algorithmique

Computational complexity

Niveau M1+M2

Discipline(s) Informatique

ECTS 3.00

Période 2e semestre

Localisation Site Monod

Année 2021-2022

 Public externe (ouverts aux auditeurs de cours)
 

Objectif du cours

What computing resources do we need to solve a computational problem? The computational complexity theory studies this question from a structural point of view. Building up on the Turing machine model, we will discover and study deterministic and nondeterministic complexity classes, space and time complexity and hierarchy, completeness, randomized algorithms classes, boolean circuits and counting classes.

 

La note du cours sera (CC+NE)/2, où NE est la note d’un examen final écrit, et CC la note de contrôle continu.

La seconde session sera un oral.

Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak (mostly chapters 1 to 7)

more about computational complexity

Modifié le :
02/07/2021 16:59:34