Fonctions booléennes complexes

séminaire du 12/04/2001


Cliquez ici pour démarrer


Table des matières

Fonctions booléennes complexes

Les complexités

Fonctions booléennes

Diapositive PPT

Diapositive PPT

Diapositive PPT

Formes normales canoniques

Diapositive PPT

Diapositive PPT

Diapositive PPT

Arbre de vérité

La Table de vérité (ordre lexicographique)

Diapositive PPT

Diapositive PPT

Arbre de vérité = automate

Diapositive PPT

Réduction

Diapositive PPT

BDD : réduction supplémentaire du BDDQR

BDD et rang des noeuds

BDDQR et complexité algorithmique

Tous les QRBDD minimaux pour n=3

Graphes des fonctions dures pour n=3

Tous les QRBDD minimaux pour n=4

Diapositive PPT

Fonctions booléennes dures

Complexité algorithmique des fonctions booléennes dures

Fonctions dures (suite)

QRBDD des fonction dures

Dénombrement des possibilités n=3

Dénombrement : cas de n=4

Dénombrement : cas général

Problème combinatoire

Solution

Pourquoi 31728 ?

Forme explicite

Classement des fonctions booléennes par leur complexité

Résultats

Questions ouvertes

Applications

Le groupe symétrique

Groupe symétrique et complexité

De Sn ý S2n

Echange de variables sur l'arbre de vérité

Exemple d'effet d'un échange

Fonctions symétriques

Bibliographie

Bibliographie suite

Auteur: Jean-Francis MICHON

Messagerie: jean-francis.michon@univ-rouen.fr

Page d'accueil: http://iml.univ-mrs.fr:80/ati/

Télécharger la source de la présentation


Mise à Jour : 10 avril 2001, EL