Programme de l’UE

A) Partie Informatique: Possibilités inattendues offertes par le hasard en algorithmique (N. Schabanel)

Depuis une trentaine d’années, les informaticiens ont révélé que l’on pouvait faire des usages assez étonnants du hasard, d’autant plus étonnants que ces résultats sont violemment contre-intuitifs. Nous verrons dans ce cours comment utiliser du hasard pour compter exactement avec une mémoire toute petite (randomized counters), comment corriger un programme buggé sans modifier son code (autocorrection de code), comment tester si quelqu’un sait quelque
chose, sans rien apprendre ni savoir de son secret (zero-knowledge), étudier les étranges propriétés des graphes expandeurs et leurs étonnantes applications.

Le plus surprenant est que ces méthodes sont très simples, tant  prouver et qu’  mettre en oeuvre, et sont le plus souvent bien plus efficaces que leurs alternatives déterministes: à la fois plus rapides et plus économiques en ressources. Ces techniques ont donc toutes les chances d’être favorisées par la sélection naturelle et pourraient donc bien se retrouver dans la nature, donc autant s’y préparer ! Le hasard est ainsi loin d’être seulement un bruit dont on chercherait à se débarrasser mais est au contraire appeler à jouer des rôles moteur insoupçonnés. Nous verrons également comment la notion de hasard peut être reliée à la notion de problèmes difficiles.

B) Partie physique :  Bruit et/ou information  (P. Borgnat et P. Flandrin)

Classiquement le bruit est vu comme une nuisance dont il faut s’affranchir dans des méthodes d’analyse de données, que ce soit en traitement du signal et des images, en statistiques ou dans des opérations d’acquisition de données. Cependant, au-delà de dire parfois que l’information peut être portée par du bruit, certaines méthodes proposent d’utiliser le bruit comme aide à l’analyse et à la décision. Plusieurs de ces approches ont une origine dans le monde des sciences physiques. On propose de couvrir trois familles d’approches en ce sens :

  1. Accès à des données avec de l’aléatoire dans les mesures : Echantillonnage ou quantification aléatoires ou irréguliers ; idée d’échantillonnage compressif (compressed sensing) ; estimation par projections aléatoires (scketch, filtres de Bloom,…)
  2. Méthodes de brassage aléatoire des données : bootstrap ; données substituts (surrogates),…
  3. Analyse assistée par le bruit : résonance stochastique ; moyennes robustes par l’ajout de bruit ; liens avec les algorithmes ou les simulations assistés par le bruit (gradients stochastiques, méthodes de Monte-Carlo, recuit simulé).

C) Partie biologie: le hasard au coeur de la cellule (O. Gandrillon) (à confirmer)

Mots clés.

 

Prérequis.

 

Modalités de l’examen.

 

Intervenants

  • Nicolas Schabanel, DR CNRS (responsable)
  • Pierre Borgnat, CR CNRS
  • Patrick Flandrin, DR CNRS
  • Olivier Gandrillon, Univ. Lyon 1