Randomness and complexity - lecture 2
Apparaît dans la collection : Research School in Discrete Mathematics and Computer Science / École de recherche en mathématiques discrètes et informatique - WEEK 1
The first lecture will cover basic notions of algorithmic complexity (model of computation, P, NP, NP-completeness. . . ). In the second lecture we shall discuss randomness through randomized algorithms and Kolmogorov complexity. In the exercise session, besides training on these notions, you'll also be briefly introduced to Shannon entropy.
