00:00:00 / 00:00:00

Appears in 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.

Information about the video

Citation data

  • DOI 10.24350/CIRM.V.20136703
  • Cite this video Perifel, Sylvain (01/02/2024). Randomness and complexity - lecture 2. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.20136703
  • URL https://dx.doi.org/10.24350/CIRM.V.20136703

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow


  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
  • Get notification updates
    for your favorite subjects
Give feedback