BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen - ECPv5.7.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
X-ORIGINAL-URL:https://www.greyc.fr
X-WR-CALDESC:évènements pour GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20250330T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20251026T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20250923T104500
DTEND;TZID=Europe/Paris:20250923T114500
DTSTAMP:20260419T043015
CREATED:20250901T143747Z
LAST-MODIFIED:20250924T083634Z
UID:11937-1758624300-1758627900@www.greyc.fr
SUMMARY:Séminaire Algorithmique : Julien Clément (GREYC\, Caen) « Compter les diagrammes de décision binaires »
DESCRIPTION:Les diagrammes de décision binaires sont une famille de structures de données permettant de représenter efficacement une fonction booléenne. Ils ont été notamment popularisés par Randal Bryant en 1986 et ont suscité de nombreuses applications. \nNous aborderons dans cet exposé quelques questions de comptage sur ces structures en nous concentrant sur la variante la plus connue\, dite réduite et ordonnée (Reduced ordered decision diagram ou ROBDD). Le principal résultat est de fournir un algorithme polynomial pour calculer le nombre de ROBDD à k variables de taille n (la taille étant le nombre de nœuds de décision de la structure). Après moult efforts\, nous avons pu appliquer la méthode pour k=16 variables (il faut savoir rester modeste). La gageure est de faire cela sans examiner naïvement une par une les 2^{2^{16}}= 2^{65536} fonctions booléennes pour vérifier leur taille en tant que diagramme de décision binaire. (Pour mémoire le nombre d’atomes dans l’univers est estimé être de l’ordre de 2^266.) \nComme application de ces résultats\, nous proposons la première méthode polynomiale de génération aléatoire uniforme (pour la taille) des ROBDD.
URL:https://www.greyc.fr/event/seminaire-algorithmique-julien-clement-greyc-caen-2/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
END:VCALENDAR