[{"command":"insert","method":null,"selector":".course-modal-ajax-placeholder-950876","data":"\u003Cdiv class=\u0022container content-rte\u0022\u003E\n  \u003Cdiv class=\u0022row\u0022\u003E\n    \u003Cdiv class=\u0022box col-md-6 bg-primary text-white\u0022\u003E\n      \u003Ch2 class=\u0022h1 text-left\u0022\u003E  [M1 DiPaQ] Algorithmes probabilistes\n\u003C\/h2\u003E\n                  \u003Cdiv class=\u0022field-spacing\u0022\u003E\n        \u003Cdiv class=\u0022field__label h3 dash\u0022\u003EECTS :\n          3\n        \u003C\/div\u003E\n      \u003C\/div\u003E\n                  \u003Cdiv class=\u0022field-spacing\u0022\u003E\n        \u003Cdiv class=\u0022field__label h3 dash\u0022\u003ESemestre calendaire :\n          Semestre 2\n        \u003C\/div\u003E\n      \u003C\/div\u003E\n            \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003ED\u00e9tail du volume horaire\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                          \u003Cspan class=\u0022field__label h4 mt-5 \u0022\u003ECours magistraux :\u003C\/span\u003E\n                                      \u003Cspan\u003E10.5\u003C\/span\u003E\n                      \u003C\/div\u003E\n                                              \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                          \u003Cspan class=\u0022field__label h4 mt-5 \u0022\u003ETravaux dirig\u00e9s :\u003C\/span\u003E\n                                      \u003Cspan\u003E10.5\u003C\/span\u003E\n                      \u003C\/div\u003E\n                                                            \u003C\/div\u003E\n        \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003ELangue d\u0026#039;enseignement\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003EAnglais\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n        \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003EEnseignement \u00e0 distance\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003Enon\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n      \u003C\/div\u003E\n    \u003Cdiv class=\u0022box col-md-6\u0022\u003E\n            \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003EPr\u00e9requis\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003E\u003Cp\u003E\u003Cstrong\u003EPrerequisites:\u003C\/strong\u003E\u003C\/p\u003E\n\u003Cul\u003E\n\u003Cli\u003EBackground in algorithms and data structures.\u003C\/li\u003E\n\u003Cli\u003EBasic knowledge of discrete mathematics and probability theory is recommended but not mandatory.\u003C\/li\u003E\n\u003Cli\u003EFamiliarity with asymptotic analysis (Big-O notation) and complexity concepts.\u003C\/li\u003E\n\u003Cli\u003EProgramming experience in a general language (e.g., Python, C++, or Java) is recommended.\u003C\/li\u003E\n\u003C\/ul\u003E\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n        \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003EProgramme \/ plan \/ contenus\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003E\u003Cp\u003E\u003Cstrong\u003ECourse program, plan, content:\u003C\/strong\u003E\u003C\/p\u003E\n\u003Cp\u003E\u003Cstrong\u003ETotal duration:\u003C\/strong\u003E\u0026nbsp;21 hours (6 sessions \u00d7 3.5 hours)\u003C\/p\u003E\n\u003Cul\u003E\n\u003Cli\u003E\u003Cstrong\u003ESession 1 (Lecture + Lab):\u003C\/strong\u003E\u0026nbsp;Introduction to randomization (Motivation and examples: why randomization?) Review of basic probability concepts (expectation, variance, independence).\u0026nbsp; Case study: Randomized QuickSort and its expected complexity.\u003C\/li\u003E\n\u003Cli\u003E\u003Cstrong\u003ESession 2 (Lecture + Lab):\u003C\/strong\u003E\u0026nbsp;Probabilistic analysis tools: linearity of expectation and indicator variables, the coupon collector problem and conditional probability laws.\u003C\/li\u003E\n\u003Cli\u003E\u003Cstrong\u003ESession 3 (Lecture + Lab):\u003C\/strong\u003E\u0026nbsp;Probabilistic Bounds and Applications (Markov, Chebyshev, and Chernoff bounds). The balls-into-bins paradox and implications for load balancing. Verification problems and Bayesian classification examples.\u003C\/li\u003E\n\u003Cli\u003E\u003Cstrong\u003ESession 4 (Lecture + Lab):\u003C\/strong\u003E\u0026nbsp;Introduction to Online Algorithms (The ski-rental problem, Online paging and caching algorithms, Basics of load balancing in online settings).\u003C\/li\u003E\n\u003Cli\u003E\u003Cstrong\u003ESession 5 (Lecture + Lab):\u003C\/strong\u003E\u0026nbsp;Hashing and Streaming Algorithms (Randomized hashing and collision analysis, universal hashing and expected performance, introduction to streaming algorithms and approximate counting).\u003C\/li\u003E\n\u003Cli\u003E\u003Cstrong\u003ESession 6 (Lab):\u003C\/strong\u003E\u0026nbsp;Project presentations and discussions of student projects.\u003C\/li\u003E\n\u003Cli\u003E\u003Cstrong\u003ESession 7 (Final exam):\u003C\/strong\u003E\u0026nbsp;1h30 written exam.\u003C\/li\u003E\n\u003C\/ul\u003E\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n        \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003EObjectifs d\u0026#039;apprentissage\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003E\u003Cp\u003E\u003Cstrong\u003ELearning objectives:\u003C\/strong\u003E\u003C\/p\u003E\n\u003Cp\u003EAt the end of this course, students will be able to:\u003C\/p\u003E\n\u003Cul\u003E\n\u003Cli\u003EUnderstand the principles and motivations behind randomized algorithm design.\u003C\/li\u003E\n\u003Cli\u003EApply probabilistic tools such as the Chernoff and Markov inequalities for performance analysis.\u003C\/li\u003E\n\u003Cli\u003EAnalyze the expected performance and probabilistic guarantees of randomized algorithms.\u003C\/li\u003E\n\u003Cli\u003EDesign and implement efficient algorithms using randomization as a core technique.\u003C\/li\u003E\n\u003C\/ul\u003E\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n        \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003EOrganisation g\u00e9n\u00e9rale et modalit\u00e9s p\u00e9dagogiques\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003E\u003Cp\u003E\u003Cstrong\u003EGeneral course organization and teaching modalities:\u003C\/strong\u003E\u003C\/p\u003E\n\u003Cul\u003E\n\u003Cli\u003EThe course combines \u003Cstrong\u003Electures\u003C\/strong\u003E introducing theoretical concepts with \u003Cstrong\u003Eexercise labs\u003C\/strong\u003E that allow students to apply these concepts.\u003C\/li\u003E\n\u003Cli\u003EEach 3.5-hour session blends approximately 1h lecture and 2h30 exercises.\u003C\/li\u003E\n\u003Cli\u003EEvaluation is based \u003Cstrong\u003Eon one project and one written exam\u003C\/strong\u003E.\u003C\/li\u003E\n\u003C\/ul\u003E\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n                \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003EComp\u00e9tences\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003E\u003Cp\u003E\u003Cstrong\u003ECompetencies gained in the course:\u003C\/strong\u003E\u003C\/p\u003E\n\u003Cp\u003EUpon successful completion, students will have acquired the following competencies:\u003C\/p\u003E\n\u003Cul\u003E\n\u003Cli\u003E\u003Cstrong\u003ETechnical competence:\u003C\/strong\u003E\u0026nbsp;Designing random algorithms with probabilistic guarantees.\u003C\/li\u003E\n\u003Cli\u003E\u003Cstrong\u003EAnalytical competence:\u003C\/strong\u003E\u0026nbsp;Analyzing the complexity and performance of random algorithms.\u003C\/li\u003E\n\u003Cli\u003E\u003Cstrong\u003EPractical competence:\u003C\/strong\u003E\u0026nbsp;Implementation and empirical evaluation of random algorithms.\u003C\/li\u003E\n\u003Cli\u003E\u003Cstrong\u003EProblem-solving competence:\u003C\/strong\u003E\u0026nbsp;Comparing deterministic and random algorithms.\u003C\/li\u003E\n\u003Cli\u003E\u003Cstrong\u003ETransferable skills:\u003C\/strong\u003E\u0026nbsp;Modeling real-world problems and writing rigorous mathematical proofs.\u003C\/li\u003E\n\u003C\/ul\u003E\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n        \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003EBibliographie\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003E\u003Cp\u003E\u003Cstrong\u003EBibliography:\u003C\/strong\u003E\u003C\/p\u003E\n\u003Cul\u003E\n\u003Cli\u003EKleinberg, J., \u0026amp; Tardos, E. (2006). Algorithm design. Pearson Education India.\u003C\/li\u003E\n\u003Cli\u003EMotwani, R., \u0026amp; Raghavan, P. (1996). Randomized algorithms. ACM Computing Surveys (CSUR), 28(1), 33-37.\u003C\/li\u003E\n\u003Cli\u003EMitzenmacher, M., \u0026amp; Upfal, E. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press, 2017.\u003C\/li\u003E\n\u003Cli\u003EVazirani, V. V. Approximation Algorithms. Springer, 2001.\u003C\/li\u003E\n\u003C\/ul\u003E\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n        \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003ENature de l\u0026#039;\u00e9valuation\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003EEvaluation Continue non Int\u00e9grale\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n      \u003C\/div\u003E\n  \u003C\/div\u003E\n\u003C\/div\u003E\n","settings":null}]