DENIF – Documents d’Enseignement Numériques en Informatique Fondamentale

Transcrit par les étudiants. Avec seulement des corrections superficielles par l'enseignant. Il manque des choses sur les algorithmes probabilistes (min-cut par contraction d'arête, programmation linéaire avec arrondi randomisé), les graphes aléatoires (loi 0-1), les chaînes de Markov (convergence vers la distribution stationnaire, algorithme pour 2-SAT). Ces points sauf la loi 0-1 sont dans les notes de cours de 2000-2001.

Sources : celles des années précédentes, ainsi que Game Theory, Guillermo Owen, second edition, Academic Press, 1982.

Note : il manque parfois des définitions ou des morceaux de démonstration.

Sources : * Introduction aux probabilités, P. Brémaud, Springer-Verlag 1984 ; * Markov Chains, Gibbs Fields, Monte-Carlo Simulation and queues, P. Brémaud, Springer 1999 ; * exercices de probabilités, Marie Cottrell, Valentine Genon-Catalot, Christian Duhamel, Thierry Meyre, Cassini 1999 ; * exercices ordinaires de probabilités, Gérard Frugier, ellipses ; * An introduction to probability theory and its applications, vol. 1, William Feller, Jon Wiley & Sons.