v2.11.0 (5380)

PA - C7 - INF561 : Randomization in Computer Science: Games, Networks, Epidemic and Evolution

Domaine > Informatique.

Descriptif

Randomized methods are one of the key tools in computer science, clearly not limited to their best-known use in randomized algorithms. Our aims for this course are twofold:

(i) We shall give an introduction to the diverse applications of 
randomized methods in computer science such as

- Randomized algorithms,
- liar games and guessing games (Mastermind) and their applications to noisy communication and privacy problems,
- random graphs and social networks,
- epidemic and gossip-based algorithms,
- evolutionary algorithms.

(ii) Parallel to this, we shall develop a small, but powerful set of mathematical tools that suffice to understand most uses of randomness in computer science:

- the first moment method,
- the coupon collector theorem,
- simple Chernoff bounds,
- a number of tricks to deal with dependencies.

Requirements: The beauty of this field is that relatively simple uses of randomness yield surprisingly powerful results. In such, no deep probability theory prerequisites are needed. However, naturally, this topic does require the use of elementary discrete probabilities. So if you are afraid of statements like "if you roll a standard 6-sided die, then the expect result is 3.5" or "the expected number of die rolls until you see a "one" is 6", then you should not take this course. A basic knowledge of algorithms and their analysis, e.g., as taught in INF421, is also helpful. Finally, this is not a mathematics course (by far not), but we use mathematical arguments to understand things. The course comes with PC, not with TD. It is thus similar in style to INF421.

Evaluation mechanism: A written exam of two hours length.

Languange: Everything is in English. For the exam, answers in French are equally accepted. 

Format des notes

Numérique sur 20

Littérale/grade réduit

Pour les étudiants du diplôme Diplôme d'ingénieur de l'Ecole polytechnique

Le rattrapage est autorisé (Note de rattrapage conservée)
    L'UE est acquise si note finale transposée >= C
    • Crédits ECTS acquis : 5 ECTS

    La note obtenue rentre dans le calcul de votre GPA.

    Pour les étudiants du diplôme Echanges PEI

    Le rattrapage est autorisé (Note de rattrapage conservée)
      L'UE est acquise si note finale transposée >= C
      • Crédits ECTS acquis : 5 ECTS

      La note obtenue rentre dans le calcul de votre GPA.

      Pour les étudiants du diplôme M1 MPRI - Foudations of Computer Science

      Le rattrapage est autorisé (Note de rattrapage conservée)
        L'UE est acquise si note finale transposée >= C
        • Crédits ECTS acquis : 5 ECTS

        Pour les étudiants du diplôme M1 Informatique - Voie Jacques Herbrand - X

        Le rattrapage est autorisé (Note de rattrapage conservée)
          L'UE est acquise si note finale transposée >= C
          • Crédits ECTS acquis : 5 ECTS

          La note obtenue rentre dans le calcul de votre GPA.

          Pour les étudiants du diplôme M1 - Applied Mathematics and statistics

          Veuillez patienter