English
Randomness and complexity - lecture 1
Multi angle
Auteurs : Perifel, Sylvain (Auteur de la conférence)
CIRM (Editeur )
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 (Editeur )
Loading the player...
|
Résumé :
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.
Mots-Clés : algorithmic complexity; information theory; Kolmogorov complexity
Codes MSC : Mots-Clés : 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.)
|
Informations sur la Vidéo
Réalisateur : Hennenfent, GuillaumeLangue : Anglais Date de Publication : 19/02/2024 Date de Captation : 29/01/2024 Sous Collection : Research School Catégorie arXiv : Computational Complexity ; Computer Science Domaine(s) : Informatique Format : MP4 (.mp4) - HD Durée : 01:36:20 Audience : Chercheurs ; Etudiants Science Cycle 2 ; Doctoral Students, Post-Doctoral Students Download : https://videos.cirm-math.fr/2024-01-29_Perifel_Part1.mp4 
|
Informations sur la Rencontre
Nom de la Rencontre : Research School in Discrete Mathematics and Computer Science / École de recherche en mathématiques discrètes et informatique - WEEK 1Organisateurs de la Rencontre : Cassaigne, Julien ; Chalopin, Jérémie ; Chepoi, Victor ; Guillon, Pierre ; Moutot, Etienne ; Theyssier, Guillaume Dates : 29/01/2024 - 02/02/2024 Année de la rencontre : 2024 URL de la Rencontre : https://conferences.cirm-math.fr/3148.html
Données de citation
DOI : 10.24350/CIRM.V.20136103Citer cette vidéo: 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 |
Voir Aussi
- [Multi angle] Lost in ecological transition ? The trajectory of a (computer) scientist in the Anthropocene / Auteur de la conférence Lefèvre, Julien.
- [Multi angle] Tutorial on cellular automata - lecture 2 / Auteur de la conférence Ollinger, Nicolas.
- [Multi angle] An introduction to Walnut - lecture 2 / Auteur de la conférence Rampersad, Narad.
- [Multi angle] Randomness and complexity - lecture 2 / Auteur de la conférence Perifel, Sylvain.
- [Multi angle] Tutorial on cellular automata - lecture 1 / Auteur de la conférence Ollinger, Nicolas.
- [Multi angle] Diagram groups and their geometry - lecture 1 / Auteur de la conférence Skipper, Rachel.
- [Multi angle] An introduction to Walnut - lecture 1 / Auteur de la conférence Rampersad, Narad.
- [Multi angle] Complexity and the hat / Auteur de la conférence Goodman-Strauss , Chaim.
- [Multi angle] Diagram groups and their geometry - lecture 2 / Auteur de la conférence Genevois, Anthony.
- [Multi angle] The crossing paths of Mandelbrot and Schützenberger: an episode of crossovers between maths and computing (1953-1963) / Auteur de la conférence Bullynck, Maarten.
Bibliographie
Imagette Video
