Informatique

Cours autour des bases de l'algèbre linéaire et de l'optimisation numérique.

Ce cours a pour objectifs d’étudier des modèles probabilistes largement utilisés en informatique ainsi que des algorithmes probabilistes classiques. 

  • Rappels de probabilités discrètes : lois binomiales et normales, loi de puissance (application au graphe du Web)
  • Chaînes de Markov discrètes : modélisation de marches aléatoires et PageRank, comportements transient et stationnaire, périodicité et ergodicité, étude des composantes fortements connexes, étude algébrique
  • Processus de décision markoviens : modélisation, analyse à horizon borné, analyse infinie avec décote, algorithmes d’itérations de valeur ou de stratégie, approche par programmation linéaire 
  • Algorithmes randomisés : méthodes d’arrondi (application à MAX-SAT), méthodes d’échantillonnage (algorithme de type Monte Carlo, application à la recherche de deux points les plus proches), méthodes de randomisation (algorithmes de type Las Vegas, application au routage randomisé dans un hypercube)

M. Puterman : Markov Decision Processes : Discrete Stochastic Dynamic Programming. John Wiley & Sons inc., 1994

R. Motwani et P. Raghavan : Randomized Algorithms. Cambrige University Press, 1995.

D. Foata et A. Fuchs : Processus stochastiques. Processus de Poisson, chaînes de Markov et martingales. Dunod, 2002.

W. Appel : Probabilités pour les non-probabilistes. H&K, 2013.

UE Environnement et R&D en informatique

Ce cours est en construction.