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:20230326T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20231029T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20230411T100000
DTEND;TZID=Europe/Paris:20230411T110000
DTSTAMP:20260423T123816
CREATED:20221216T135437Z
LAST-MODIFIED:20230407T114716Z
UID:11033-1681207200-1681210800@www.greyc.fr
SUMMARY:Séminaire Algorithmique : Julien Clément (GREYC\, Caen) « Combinatorics of reduced ordered binary decision diagrams. Application to random uniform sampling »
DESCRIPTION:Any Boolean function corresponds to a complete full binary decision tree. This tree can in turn be represented in a maximally compact form as a directed acyclic graph where common subtrees are factored and shared\, keeping only one copy of each unique  subtree. This yields the celebrated and widely used structure called reduced ordered binary decision diagram (ROBDD). In the random uniform model over the set of Boolean functions with a fixed number of variables the size of a typical ROBDD is of near maximal (exponential) size. This makes random sampling of small ROBDDs (the ones usable in practice) a difficult task even for a few variables. In this talk we want to compute the distribution of ROBDDs (for a fixed number of variables) with respect to the size. As a by-product we get a random uniform and exhaustive sampler for ROBDDs for a given number of variables and size with polynomial time complexity. \nJoint work with Antoine Genitrini (LIP6\, Paris).
URL:https://www.greyc.fr/event/seminaire-algorithmique-julien-clement-greyc-caen/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,Séminaire Algo
END:VEVENT
END:VCALENDAR