Les décompositions des fonctions en PITS

Simard, Patrick (2006). « Les décompositions des fonctions en PITS » Mémoire. Montréal (Québec, Canada), Université du Québec à Montréal, Maîtrise en mathématiques.

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (2MB)

Résumé

En 1971, Gilbert Labelle a introduit la fonction chapeau qui est une traduction entre deux représentations de fonctions booléennes. Cette fonction intimement liée au calcul propositionnel possède de remarquables propriétés et permet de trouver le polynôme associé à une table de vérité et réciproquement. La fonction chapeau est involutive et nous en fournissons une démonstration car l'article original de Gilbert Labelle n'en présentait pas. Pour une base de numération fixée p où p est premier, un nombre entier est identifié par une suite de chiffres appelés «pits» par analogie aux bien connus bits. Toute fonction définie sur N est exprimable par une fonction définie sur les pits. Une telle fonction est décomposable en une suite de sous-fonctions qui expriment individuellement chaque chiffre de sortie de la fonction originelle à partir des chiffres en entrée. Différentes décompositions de fonctions en pits sont présentées. Les calculs liés à ces décompositions sont difficiles et des algorithmes astucieux sont développés en Maple pour obtenir quelques résultats qui suggèrent des formules générales que nous prouvons par la suite. Un bit est un cas particulier des pits et il y a une bijection entre les opérateurs d'addition/produit et les portes logiques. Il est alors possible pour un concepteur en électronique de réaliser une implémentation parallèle de fonctions logiques/arithmétiques à partir des décompositions. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Représentations de fonctions, Calcul propositionnel, Décompositions de fonctions, Programmation Maple, Calcul parallèle.

Type:	Mémoire accepté
Informations complémentaires:	Le mémoire a été numérisé tel que transmis par l'auteur.
Directeur de thèse:	Laforest, Louise
Mots-clés ou Sujets:	Décompositions (Mathématiques), Fonction (Mathématiques), Calcul des propositions
Unité d'appartenance:	Faculté des sciences > Département de mathématiques
Déposé par:	RB Service des bibliothèques
Date de dépôt:	12 août 2010 18:16
Dernière modification:	05 déc. 2018 11:26
Adresse URL :	http://archipel.uqam.ca/id/eprint/3232

Modifier les métadonnées (propriétaire du document)

Statistiques