Français
Randomness and complexity - lecture 1
Multi angle
Authors : Perifel, Sylvain (Author of the conference)
CIRM (Publisher )
68Q05 - Models of computation (Turing machines, etc.)
68Q15 - Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 - Computational difficulty of problems
68Q30 - Algorithmic information theory (Kolmogorov complexity, etc.)
CIRM (Publisher )
Loading the player...
|
Abstract :
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.
Keywords : algorithmic complexity; information theory; Kolmogorov complexity
MSC Codes : Keywords : algorithmic complexity; information theory; Kolmogorov complexity
68Q05 - Models of computation (Turing machines, etc.)
68Q15 - Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 - Computational difficulty of problems
68Q30 - Algorithmic information theory (Kolmogorov complexity, etc.)
|
Information on the Video
Film maker : Hennenfent, GuillaumeLanguage : English Available date : 19/02/2024 Conference Date : 29/01/2024 Subseries : Research School arXiv category : Computational Complexity ; Computer Science Mathematical Area(s) : Computer Science Format : MP4 (.mp4) - HD Video Time : 01:36:20 Targeted Audience : Researchers ; Graduate Students ; Doctoral Students, Post-Doctoral Students Download : https://videos.cirm-math.fr/2024-01-29_Perifel_Part1.mp4 
|
Information on the Event
Event Title : Research School in Discrete Mathematics and Computer Science / École de recherche en mathématiques discrètes et informatique - WEEK 1Event Organizers : Cassaigne, Julien ; Chalopin, Jérémie ; Chepoi, Victor ; Guillon, Pierre ; Moutot, Etienne ; Theyssier, Guillaume Dates : 29/01/2024 - 02/02/2024 Event Year : 2024 Event URL : https://conferences.cirm-math.fr/3148.html
Citation Data
DOI : 10.24350/CIRM.V.20136103Cite this video as: Perifel, Sylvain (2024). Randomness and complexity - lecture 1. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.20136103 URI : http://dx.doi.org/10.24350/CIRM.V.20136103 |
See Also
- [Multi angle] Lost in ecological transition ? The trajectory of a (computer) scientist in the Anthropocene / Author of the conference Lefèvre, Julien.
- [Multi angle] Tutorial on cellular automata - lecture 2 / Author of the conference Ollinger, Nicolas.
- [Multi angle] An introduction to Walnut - lecture 2 / Author of the conference Rampersad, Narad.
- [Multi angle] Randomness and complexity - lecture 2 / Author of the conference Perifel, Sylvain.
- [Multi angle] Tutorial on cellular automata - lecture 1 / Author of the conference Ollinger, Nicolas.
- [Multi angle] Diagram groups and their geometry - lecture 1 / Author of the conference Skipper, Rachel.
- [Multi angle] An introduction to Walnut - lecture 1 / Author of the conference Rampersad, Narad.
- [Multi angle] Complexity and the hat / Author of the conference Goodman-Strauss , Chaim.
- [Multi angle] Diagram groups and their geometry - lecture 2 / Author of the conference Genevois, Anthony.
- [Multi angle] The crossing paths of Mandelbrot and Schützenberger: an episode of crossovers between maths and computing (1953-1963) / Author of the conference Bullynck, Maarten.
Bibliography
Imagette Video
