Un concept que j'ai inventé (enfin j'espère), j'appelle ça la fragmentation unitaire
Soit $M = \{0;1\}^n$
Soit $F $ l'ensemble des fonctions $f$ de $M \times \{0;1\} \rightarrow \{0;1\}$ où
il existe $k \leq n$ et $h: \{0;1\}^2 \rightarrow \{0;1\}$ tq $\forall (x,b) \in M \times\{0;1\}: $ $f(x,b) = h(x_k,b)$.
il existe $k \leq n$ et $h: \{0;1\}^2 \rightarrow \{0;1\}$ tq $\forall (x,b) \in M \times\{0;1\}: $ $f(x,b) = h(x_k,b)$.
Alors pour toutes fonctions $g$ de $M \rightarrow \{0;1\}$, il existe $f_1, f_2, \dots, f_m$ toutes dans $F$ telles que $g= f_1 \circ f_2 \circ\dots\circ f_m(Id,0)$,
avec la notation abusive $f_i \circ f_{i+1} (x,b) = f_i(x, f_{i+1}(x,b))$.
C'est plutôt sympa comme mode de représentation d'une fonction, ça peut être utile quelque part. On peut pousser la théorie plus loin en se restreignant à un sous-ensemble strict de $F$ et essayer alors de déterminer le m maximum sur ce sous-ensemble, ça mesure un peu la complexité maximale des fonctions de ce sous-ensemble.
Réponses
-
Bonjour,
c’est illisible pour moi…
Peux-tu rendre ton message plus propre en ce qui concerne les textes mathématiques ?
Cordialement
Dom
[GRAND MERCI !] -
BonsoirMis à part quelques coquilles à corriger, cela me fait étrangement penser à ce que l'on peut examiner dans le livre d'algèbre de Bourbaki, en bas de la page A I.81, et au début de la page A I.82. A quelques notations près, le procédé est bien connu depuis des décennies.Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
-
Bonsoir @Thierry Poma
je ne vais pas vous mentir je n'ai jamais lu les Bourbakiet je n'arrive pas à trouver le livre en ligne malheureusement.
Poussent-ils l'étude à examiner les complexités de sous-ensemble de fonctions de Mx{0;1} -> {0;1} ou la complexité est définie comme le maximum des cardinaux des tailles des décompositions minimales des fonctions dans le sous-ensemble ?
edit : j'avais trouve ça: http://sites.mathdoc.fr/archives-bourbaki/PDF/033_iecnr_040.pdf mais ça ne parle pas de ça au lieu dit peut être pcq [parce que ?] ce n'est pas la version définitive. -
EtNonLesShills : je ne dis pas que tu mens. Je vais essayer de revenir demain sur ce point.
Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême). -
Merci bien, à demain.
-
---> I believe in Chuu-supremacy : https://www.youtube.com/watch?v=BVVfMFS3mgc <---
-
EtNonLesShills : bonjour. Je rappelle que $M_n=\{0,\,1\}^n$ pour un entier naturel $n$ non nul. Tu écris (en ayant modifié légèrement ton texte) :Alors, pour toute fonction $g:M_n \rightarrow \{0;1\}$, il existe $f_1, f_2, \dots, f_m$, toutes dans $\mathcal{F}_n$, telles que $g= f_1 \circ f_2 \circ\dots\circ f_m(\mathrm{id},\,0)$Pour un entier naturel $n$ non nul, penses-tu que $u\circ{}v$ ait un sens pour des fonctions $u$ et $v$ appartenant à $\mathcal{F}_n$ que tu as défini ? Je rappelle que $\mathcal{F}_n$ est l'ensemble des applications définies sur $M_n\times\{0,\,1\}$ à valeurs dans $\{0,\,1\}$ vérifiant une propriété qui sera, elle aussi, à revoir intégralement. Veux-tu définir ce $\mathrm{id}$ que tu utilises ?Pourtant, je parviens à comprendre l'idée, vu que Bourbaki l'a déjà utilisée.Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
-
Cette "notation abusive" est expliquée supra : $f \circ g(x,b) = f(x, g(x,b))$.
-
@Math Coss : bonjour. Justement, il y a un moyen de s'affranchir de cette notation abusive inepte afin de donner un nouveau cadre de travail naturel. Je veux que l'auteur y réfléchisse.
Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême). -
Le théorème est malheureusement faux, une preuve de cela en dessous (c/c le pavé sur maths exange ici ça ne formate pas certaines parties).
edit: errata 4h30 -
EtNonLesShills a dit :Soit $F $ l'ensemble des fonctions $f$ de $M \times \{0;1\} \rightarrow \{0;1\}$ où il existe $k \leq n$ et $h: \{0;1\}^2 \rightarrow \{0;1\}$ tq $f(x,b) = h(x_k,b)$.
x_k est la k-ème coordonnée de x ?
Pourrais-tu utiliser des quantificateurs pour introduire x et b ? -
MagnéthoraxouiThierry Poma a dit :@Math Coss : bonjour. Justement, il y a un moyen de s'affranchir de cette notation abusive inepte afin de donner un nouveau cadre de travail naturel. Je veux que l'auteur y réfléchisse.
$f_1\circ\dots\circ f_m(x,0)$ il faut écrire $f_1(x,\dots(x, f_m(x,0)))$.
Je ne l'ai pas fait dans la contre preuve car c'est un peu trop lourd.Par contre à partir du moment où les fonctions de décomposition (notées $F$ dans le post initial) ne touchent pas au mot $x$, je doute du caractère naturel. -
J'ai oublié de le dire vu que pour moi ça coule de source, comme ça ne marche pas le but est alors évidemment de trouver un autre ensemble F de fonctions le plus petit possible rendant le théorème vrai.Par contre les fonctions de F doivent rester à valeur dans {0,1}, si vous autorisez à valeur dans {0,1}² le problème devient trivial vous écrivez sous forme normale disjonctive la fonction que vous voulez décomposer et l'une des deux variables de {0;1}² stocke le fait que l'ensemble des disjonctions précédentes est vrai pendant que l'autre stocke si la disjonction qui est en train d'être analysée a déjà rencontré un terme vrai. Et avec ce principe on construit facilement un très petit ensemble F capable de décomposer toutes les fonctions.Je ne sais pas si je me fais comprendre mais bref les fonctions de F doivent être à valeur dans {0;1} pour que le problème soit un minimum intéressant.
-
Je suis en train de finaliser la preuve pour le cas général, ça sera probablement prêt pour demain à moins que j'ai fait une erreur.3 points.1) Non il n'existe pas de petit F pouvant générer toute les fonctions, c'est donc un non-résultat (du point de vue pratique).2) Toute fonctions pouvant être générée peut être générée par moins de 2card(F)^3 compositions. C'est un vrai résultat du point de vu pratique, vu que cela dit que s'il existe un programme dans un certain ensemble (les fonctions générées par F) alors il existe un programme rapide faisant la même chose.3) La preuve porte en elle même la direction de la suite des travaux : une transformation du problème "envoie" le dit problème sur des matrices diagonales de Z/2Z, mais la résolution qui suit (et donc le résultat en 2) ) aurait très bien pu s'effectuer sur juste un ensemble de matrices simultanément diagonalisables de Z/2Z, la question se pose alors quels sont ces problèmes qui après transformations sont envoyés sur un ensemble de matrices simultanéments diagonalisables de Z/2Z ?[Comme tu sembles en difficulté avec les accents, préfère le verbe "engendrer" au verbe "générer".
AD]
un peu de retard quasi fini -
tuturu
c/c sur stack exange
n'hésiter pas a réfléchir au point 3 du dernier post, j'y ai un peu pense l'embêtant c'est que je ne sais pas si les résultat de diagonalisation connu sont vrais pour les matrices a coefficient dans Z/2Z. Par exemple la diagonalisation simultane si diagonalisable + commutativite, ca reste vrai ?
(Z/2Z)^n peut il etre munis d'un "produit scalaire" rendant vrai le théorème spectral ? bref
erreta: precise F C H la ou c'etait vrai et non mentionne
errata: $card(\overline{F})+2$ a la place de n+2 dans la preuve du dernier theoreme + je crois que je m'etais emmele dans mes c/c sur blocnote oups
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 165.6K Toutes les catégories
- 65 Collège/Lycée
- 22.2K Algèbre
- 37.7K Analyse
- 6.3K Arithmétique
- 61 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 26 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.8K Géométrie
- 86 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 29 Mathématiques et finance
- 344 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.4K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 805 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres