Posts classified under: Amacc

La méthode de Boltzmann permet de “compiler” un générateur aléatoire uniforme efficace pour les structures discrètes définies par une spécification combinatoire. Après avoir introduit quelques définitions et la méthode, je présenterai notre implémentation de cette méthode : la librairie Python usain-boltz (travail commun avec Martin Pépin). Au fur et à mesure de cette présentation, j’introduirai … Continue reading Séminaire Algorithmique : Matthieu Dien (GREYC, Caen) « Méthode de Boltzmann : quand la génération aléatoire se passe Dien et sans Pépin »

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. Nous aborderons dans cet exposé quelques questions de comptage sur ces structures en nous concentrant sur la variante la plus … Continue reading Séminaire Algorithmique : Julien Clément (GREYC, Caen) « Compter les diagrammes de décision binaires »

In this work co-written by Louis Jachiet (Télécom Paris), we attempt to answer the following questions: Given that many computer systems are efficient thanks to preprocessing (index calculations in a database, knowledge compilation in AI), which complexity classes with preprocessing are relevant? In this framework, does constant time have any meaning? For this purpose, we … Continue reading Séminaire Algorithmique : Etienne Grandjean (GREYC), « How does preprocessing make it possible to obtain constant time? »