Bienvenue au LaCIM

Le Laboratoire de combinatoire et d'informatique mathématique (LaCIM) est un centre international de recherche, basé à Montréal, et regroupant des chercheurs en mathématiques et en informatique mathématique.

Les domaines privilégiés par les chercheurs du LaCIM sont:

  • la combinatoire;
  • la combinatoire algébrique;
  • la bioinformatique;
  • les aspects mathématiques de l'informatique.

Upcoming seminars

2015-02-27T14:00:00-05:00

Echantillonnage des distributions non uniformes.

Séminaire conjoint avec EmoSTA: Claude Gravel, Université de Montréal

résumé: Nous discutons du problème de la génération d'une variable aléatoire à partir d'une suite de bits aléatoires non biaisés, indépendants et distribués identiquement. Nous commençons brièvement par rappeler le résultat de Knuth et Yao en 1976 qui donnent un algorithme optimal pour l'échantillonnage exact des lois discrètes. Il s'agit d'un algorithme probabiliste basé sur l'étude d'un certain type d'arbre aléatoire appelé arbre DDG (Discrete Data Generator). Un algorithme est optimal si la complexité espérée du nombre de bits aléatoires est minimale. Ensuite, nous abordons la génération d'une variable aléatoire continue et nous discutons du choix naturel de la métrique de Wasserstein afin de mesurer la précision. Nous montrons une minoration universelle pour la complexité espérée du nombre de bits non biaisés requis, minoration qui dépend de la précision.

Cet exposé est donné dans le cadre d'un séminaire conjoint avec ÉMoStA.

2015-03-06T13:30:00-05:00

pas de séminaire