cours:c-2-15
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | |||
|
cours:c-2-15 [2024/12/10 09:36] panafieu [Calendar for 2024 – 2025] |
cours:c-2-15 [2025/06/07 17:26] (current) panafieu [Detailed outline] |
||
|---|---|---|---|
| Line 49: | Line 49: | ||
| ==== Detailed outline | ==== Detailed outline | ||
| - | * **Rational models** (Marie Albenque) Exact enumeration by ordinary generating functions. Elementary models for words and languages, link between automata, rational functions, linear systems and transfer matrices. | + | * **Rational models** (???) Exact enumeration by ordinary generating functions. Elementary models for words and languages, link between automata, rational functions, linear systems and transfer matrices. |
| - | * **Labeled objects** (Marie Albenque) Exact enumeration by exponential generating functions, and asymptotic extraction using singularity analysis and the saddle-point method. Study of random permutations, | + | * **Labeled objects** (???) Exact enumeration by exponential generating functions, and asymptotic extraction using singularity analysis and the saddle-point method. Study of random permutations, |
| * **Graphs** (Marie Albenque) Exact and asymptotic enumeration of various graph families (degree constraints, | * **Graphs** (Marie Albenque) Exact and asymptotic enumeration of various graph families (degree constraints, | ||
| * **Analysis of sorting algorithms** (Vincent Jugé) The focus is on the analysis and improvement of algorithms, as well as the choice of the random models. We will in particular study sorting algorithms where various settings can be explored to describe what a typical input should be. | * **Analysis of sorting algorithms** (Vincent Jugé) The focus is on the analysis and improvement of algorithms, as well as the choice of the random models. We will in particular study sorting algorithms where various settings can be explored to describe what a typical input should be. | ||
| - | * **Probabilistic approach** (Lucas Gerin) | + | * **Probabilistic approach** (Marie Albenque) Introduction to randomization and probabilistic techniques. These tools play an important role in modern computer science, with applications ranging from combinatorial optimization and machine learning to communication networks and secure protocols. |
| + | - Probabilistic Toolbox (Events / Mean / Deviations, Conditioning) | ||
| + | - The Probabilistic method (First and second moment and algorithmic applications, | ||
| + | - Balls-in-bins and random allocations (Birthday paradox and Coupon collector process, Maximal load) | ||
| + | - Probabilistic algorithms for data streams (Approximate counting, Cardinality estimation with HyperLogLog) | ||
| * **Advanced analytic combinatorics** (Florent Koechlin) Mellin transform, depoissonization, | * **Advanced analytic combinatorics** (Florent Koechlin) Mellin transform, depoissonization, | ||
cours/c-2-15.txt · Last modified: 2025/06/07 17:26 by panafieu