Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 11 Janvier 2005

Classification des fonctions booléennes pour la corrélation d'ordre 1

par Jean-Marie Le Bars (GREYC, Université de Caen)

Dans cet exposé nous verrons commment classifier les fonctions booléennes à n variables, pour n fixé, en fonction de leur "distance" aux fonctions sans corrélation d'ordre 1. Ces dernières forment les classes (à n variables) les plus grandes, et les cardinalités respectives des autres classes diminuent plus elles s'en éloignent. Nous disposons d'un opérateur binaire qui construit une classe à n variables en composant deux classes à n-1 variables. Un opérateur "inverse" (basé sur une méthode récursive) permet d'énumérer l'ensemble des fonctions booléennes d'une classe à n variables, pour n peu élevé. Nous verrons que cette méthode permet d'obtenir la première borne inférieure non triviale du nombre de fonctions sans corrélation d'ordre 1. D'autre part, elle fournit un algorithme pour générer aléatoirement une fonction booléenne parmi une fraction importante des fonctions sans-corrélation d'ordre 1.

(Travail en collaboration avec Thomas Leduc, CERMA)

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr