Fonctions booléennes complexes
Les complexités
Fonctions booléennes
Diapositive PPT
Formes normales canoniques
Arbre de vérité
La Table de vérité (ordre lexicographique)
Arbre de vérité = automate
Réduction
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
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
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