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 Février 2003

Mesure alternative de la complexité d'une fonction booléenne

par Jean-Francis Michon (LIFAR)

La mesure traditionnelle de complexité des fonctions booléennes à n variables (depuis SHANNON) est celle des circuits booléens. Elle est, en général, très difficile à calculer. On montre comment d'autres mesures, plus calculables, pourraient etre définies et quelles difficultés on doit surmonter pour en faire de "vraies" mesures. Elles proviennent de la théorie des Diagrammes de Décision Binaire de R. Bryant et s'interprètent aussi en terme de minimisation d'automates. Je présente l'état actuel de mes connaissances sur ces mesures.

Mon exposé ne demande aucune connaissance préalable en dehors des graphes, automates , machine de Turing. Toutes les notions de complexité utilisées seront rappelées. Rien que des choses élémentaires en somme !

Références

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