Utilité des permutations
Utilité des permutations
Bonjour.
En regardant un autre sujet, je suis tombé sur un document où l'on parle de permutations et de décompositions en produits de cycles.
Je me souviens avoir adoré ça (c'était très simple, c'est pour ça), mais sans réellement savoir à quoi cela pouvait bien servir.
Est-ce qu'il y a des exemples qui me montreraient que les permutations servent à quelques chose ?
PS : le seul exemple que j'ai est l'histoire du créateur du taquin ... ce qui n'est déjà pas mal ... mais j'en voudrais plus :D
En regardant un autre sujet, je suis tombé sur un document où l'on parle de permutations et de décompositions en produits de cycles.
Je me souviens avoir adoré ça (c'était très simple, c'est pour ça), mais sans réellement savoir à quoi cela pouvait bien servir.
Est-ce qu'il y a des exemples qui me montreraient que les permutations servent à quelques chose ?
PS : le seul exemple que j'ai est l'histoire du créateur du taquin ... ce qui n'est déjà pas mal ... mais j'en voudrais plus :D
Re: Utilité des permutations
Bonjour,masiuxus a écrit : Est-ce qu'il y a des exemples qui me montreraient que les permutations servent à quelques chose ?
Les déterminants par exemple.
Re: Utilité des permutations
Oui, effectivement ... Autant pour moi : je formule ma question différemment : y a-t-il des exemples qui n'apparaissent pas dans le programme du premier cycle universitaire ?
-
- Modérateur honoraire
- Messages : 1839
- Inscription : mercredi 01 juin 2005, 18:39
- Localisation : Un peu plus à l'Ouest
Re: Utilité des permutations
A peu près toute la théorie des groupes finis, et par la même tout ce qui est basé dessus, comme la théorie de Galois, par exemple (mais ça n'est vraiment qu'un exemple, les groupes de permutation c'est quand même un très très gros morceau).
Pas de questions en MP
La calculatrice, c'est comme Linux, c'est de la merde !
La calculatrice, c'est comme Linux, c'est de la merde !
Re: Utilité des permutations
A vue de nez je dirais dans à peu pres toute les situation ou tu etudies ou simplifie un "systeme fini ou discret" à travers ses symétries. La théorie de Galois est effectivement une application majeure, mais aussi la theorie des invariants, des représentations, des fonctions symétriques, des groupes finis en général. Je pense qu'il y aussi des applications en physique, meme si dans la vraie vie c'est plutot des groupes de Lie qu'on voit apparaitre (qu encodent aussi une notion de symétrie). Il y a aussi la combinatoire algébrique, et les généralisations des groupes symétriques, comme les groupes de Coxeter par exemple. Un autre truc qui généralise plus ou moins la notion de permutation est la théorie des tresses (on peut voir une tresse comme une permutation qui "enregistre" les transpositions effectuées) qui jouent un role fondamental dans de nombreux domaines physiques, dans l'etude de certaines equa diff, en topologie de basse dimension, en logique fondamentale, avec des liens etroits avec la theorie des categories, ...
et j'en oublie surement beaucoup :)
et j'en oublie surement beaucoup :)
-
- Modérateur honoraire
- Messages : 1839
- Inscription : mercredi 01 juin 2005, 18:39
- Localisation : Un peu plus à l'Ouest
Re: Utilité des permutations
Tu peux préciser ton idée ? (je ne connais rien aux groupes de Lie)jobherzt a écrit :Je pense qu'il y aussi des applications en physique, meme si dans la vraie vie c'est plutot des groupes de Lie qu'on voit apparaitre (qu encodent aussi une notion de symétrie).
Idem, ça a l'air âchement intéressant :)Un autre truc qui généralise plus ou moins la notion de permutation est la théorie des tresses (on peut voir une tresse comme une permutation qui "enregistre" les transpositions effectuées) qui jouent un role fondamental dans de nombreux domaines physiques, dans l'etude de certaines equa diff, en topologie de basse dimension, en logique fondamentale, avec des liens etroits avec la theorie des categories, ...
Pas de questions en MP
La calculatrice, c'est comme Linux, c'est de la merde !
La calculatrice, c'est comme Linux, c'est de la merde !
Re: Utilité des permutations
Alors : pour ce qui est des groupes de Lie et de la physique, j'avoue que c'est un truc "qui se sait" qu'ils en rencontrent à tous les coins de rue, mais j'avoue que je ne suis pas hyper calé sur le sujet. Pour faire simple, les groupes de Lie qu'ils rencontrent sont surtout des sous groupes de $GL_n$.. Si je ne dis pas de betises, lidée est la suivante : On considere un certain systeme physique a etudier, ce qui revient a resoudre certaines equation (differentielles, a priori). Le systeme physique est inscrit dans notre espace a 3 dimension, peut donc avoir certaine symetrie, ce qui revient a dire qu'il existe un sous groupe $G$ de $GL_3$ qui le laisse stable. Par ailleurs, les solutions de l'equation associé forment un espace vectoriel disons de dimension $k$. L'action (naturelle, geometrique) de G sur le systeme va induire une action (a priori beaucoup moins evidente) de G sur cet espace de dimension $k$. Autrement dit, cet espace est une representation de G. Donc, connaitre toutes les representations de G (ce qu'on sait assez bien faire, de facon abstraite) permet de recuperer enormement d'nformation sur la structure de l'espace des solutions de notre equation, disons qu'au lieu d'un espace arbitraire, on a une certaine representation d'un groupe ce qui restreint pas mal les possibilités...
Tout ceci a prendre avec des pincettes, evidemment....
Pour les tresses, la il y a un paquet de choses à raconter, c'est vaste. Une bonne reference, plutot axé sur l'aspect combinatoire : http://www.math.unicaen.fr/~dehornoy/Surveys/Dgz.pdf
En gros, une tresse est a peu pres ce qu'on imagine, a savoir des bouts de fils qui se balladent et se croisent. On autorise les brins a bouger tant qu'ils ne se passent pas au travers. Comme souvent en maths, ca revient a dire qu'il existe plusieurs maniere de "dessiner" la meme tresse abstraite. Les tresses forment un groupe, ou la loi consiste simplement a empiler les tresses..
D'un point de vue combinatoire, les tresses ont été pas mal etudié. On sait reconnaitre efficacement que 2 dessins representent la meme tresse. On sait definir un ordre total sur les tresses. C'est la dessus que Dehornoy (document plus haut) a travaillé. C'est par ce biais qu'il y a des liens avec la logique fondamentale (decidabilité, theorie des grands cardinaux, etc..)
D'un point de vue topologique, les groupes de tresses sont les groupes fondamentaux de certains "espaces de configurations". En gros, tu imagines $n$ particules qui bougent dans un plan. L'espace de configuration associé est l'ensemble des configurations ou elles peuvent se trouver, sachant que 2 particules ne peuvent evidemment pas avoir les memes coordonnées. Une tresse represente donc un "chemin continu" d'une configuration vers une autre (imagine que les particules bougent en devidant chacune une pelote de ficelle derriere elle et que le plan monte au fur et a mesure, tu obtiendras une tresse).
De ce point de vue elles sont reliés a l'etude des equation KZ relié a l'etude du mouvement de particules. La c'est aussi relié avec les groupes quantiques.
Enfin, du point de vue categorique, les tresses sont reliés a ce qu'on appelle les "categories monoidales tressées" qui sont l'analogue categorique des monoides commutatifs (en gros le role de la multiplication est joué par un genre de produit tensoriel). Comme on travaille dans des categories, cad que les elements sont eux meme ddes structures, on ne demande pas que $A \otimes B=B \otimes A$ mais que $A \otimes B$ soit isomorphe à $B \otimes A$. Donc il y a une notion de permutation (tu peux changer l'ordre des termes) sauf qu'en fait les transpositions satisfont une relation ($\tau^2=Id$) que ces isomorphismes ne satisfont pas en general. C'est pour ca qu'en fait on ne permute pas les termes, on les tresse :) (c'est dit un peu rapidement, j'ai conscience que ca doit pas etre tres clair).
Typiquement, il existe des algebres de Hopf (dite quasi tiriangulaire) dont la categorie des modules est tressée. Ce tressage est induit par un element (la R-matrice) qui au passage a des applications en mecanique statistique (equation de Yang Baxter)....
C'est assez vaste, donc c'est dur de resumer, desolé !!! si tu as des questions, n'hesite pas.
Tout ceci a prendre avec des pincettes, evidemment....
Pour les tresses, la il y a un paquet de choses à raconter, c'est vaste. Une bonne reference, plutot axé sur l'aspect combinatoire : http://www.math.unicaen.fr/~dehornoy/Surveys/Dgz.pdf
En gros, une tresse est a peu pres ce qu'on imagine, a savoir des bouts de fils qui se balladent et se croisent. On autorise les brins a bouger tant qu'ils ne se passent pas au travers. Comme souvent en maths, ca revient a dire qu'il existe plusieurs maniere de "dessiner" la meme tresse abstraite. Les tresses forment un groupe, ou la loi consiste simplement a empiler les tresses..
D'un point de vue combinatoire, les tresses ont été pas mal etudié. On sait reconnaitre efficacement que 2 dessins representent la meme tresse. On sait definir un ordre total sur les tresses. C'est la dessus que Dehornoy (document plus haut) a travaillé. C'est par ce biais qu'il y a des liens avec la logique fondamentale (decidabilité, theorie des grands cardinaux, etc..)
D'un point de vue topologique, les groupes de tresses sont les groupes fondamentaux de certains "espaces de configurations". En gros, tu imagines $n$ particules qui bougent dans un plan. L'espace de configuration associé est l'ensemble des configurations ou elles peuvent se trouver, sachant que 2 particules ne peuvent evidemment pas avoir les memes coordonnées. Une tresse represente donc un "chemin continu" d'une configuration vers une autre (imagine que les particules bougent en devidant chacune une pelote de ficelle derriere elle et que le plan monte au fur et a mesure, tu obtiendras une tresse).
De ce point de vue elles sont reliés a l'etude des equation KZ relié a l'etude du mouvement de particules. La c'est aussi relié avec les groupes quantiques.
Enfin, du point de vue categorique, les tresses sont reliés a ce qu'on appelle les "categories monoidales tressées" qui sont l'analogue categorique des monoides commutatifs (en gros le role de la multiplication est joué par un genre de produit tensoriel). Comme on travaille dans des categories, cad que les elements sont eux meme ddes structures, on ne demande pas que $A \otimes B=B \otimes A$ mais que $A \otimes B$ soit isomorphe à $B \otimes A$. Donc il y a une notion de permutation (tu peux changer l'ordre des termes) sauf qu'en fait les transpositions satisfont une relation ($\tau^2=Id$) que ces isomorphismes ne satisfont pas en general. C'est pour ca qu'en fait on ne permute pas les termes, on les tresse :) (c'est dit un peu rapidement, j'ai conscience que ca doit pas etre tres clair).
Typiquement, il existe des algebres de Hopf (dite quasi tiriangulaire) dont la categorie des modules est tressée. Ce tressage est induit par un element (la R-matrice) qui au passage a des applications en mecanique statistique (equation de Yang Baxter)....
C'est assez vaste, donc c'est dur de resumer, desolé !!! si tu as des questions, n'hesite pas.
Re: Utilité des permutations
Ah, et j'oubliais : si tu "refermes" une tresse, cad que tu attache les bouts du haut et les bouts du bas 2 a 2, tu obtiens un noeud (plus exactment un entrelac, cad une reunion disjointe de noeuds). Donc les tresses permettent de construire des invariants de noeuds, qui ont eux meme plein d'application en topologie et en physique.
-
- Modérateur honoraire
- Messages : 1839
- Inscription : mercredi 01 juin 2005, 18:39
- Localisation : Un peu plus à l'Ouest
Re: Utilité des permutations
Merci pour ces réponses. J'ai imprimé le texte sur les tresses :D
Si t'avais un papier qui décrit un peu plus on histoire de sous-groupe de $GL_n$ qui agit sur l'espace des solutions d'une ED, je suis aussi preneur, ça a l'air très joli !
Si t'avais un papier qui décrit un peu plus on histoire de sous-groupe de $GL_n$ qui agit sur l'espace des solutions d'une ED, je suis aussi preneur, ça a l'air très joli !
Pas de questions en MP
La calculatrice, c'est comme Linux, c'est de la merde !
La calculatrice, c'est comme Linux, c'est de la merde !
Re: Utilité des permutations
Je t'avoue que mes connaissances en physique sont limitées. Mais si tu n'as j'amais rencontré de groupes de Lie, je me rends compte que mon message peut donner l'impression de parler seulement d'une connexion un peu inattendue entre 2 domaines bien distincts. Ca n'est pas du tout ca, en réalité, les groupes et algèbres de Lie sont presque par définition des objets qui viennent de la géométrie différentielle. Or, la majeure partie de la physique "theorique" utilise a très haute dose de la géo diff. Il me semble meme qu'a chaque force fondamentale est associée un certain groupe de Lie, a tel point que par abus de langage on confond les 2....
Du coup je ne suis pas sur que ca aie un sens d'avoir "une" reference sur le sujet, physique et groupes sont vraiment imbriqués à tous les niveaux... Meme si ca m'interresserait toujours d'avoir des textes un peu facile à lire pour un matheux sur le sujet :)
Une piste quand meme : http://fr.wikipedia.org/wiki/Sym%C3%A9trie_de_jauge pour illustrer ce que je disais juste avant. SInon faut lire des cours de physique, ou chercher des trucs sur les origines des groupes de Lie, il me semble qu'ils ont vraiment été introduit comme des groupes de symétrie d'equation différentielles.
Du coup je ne suis pas sur que ca aie un sens d'avoir "une" reference sur le sujet, physique et groupes sont vraiment imbriqués à tous les niveaux... Meme si ca m'interresserait toujours d'avoir des textes un peu facile à lire pour un matheux sur le sujet :)
Une piste quand meme : http://fr.wikipedia.org/wiki/Sym%C3%A9trie_de_jauge pour illustrer ce que je disais juste avant. SInon faut lire des cours de physique, ou chercher des trucs sur les origines des groupes de Lie, il me semble qu'ils ont vraiment été introduit comme des groupes de symétrie d'equation différentielles.
-
- Utilisateur chevronné
- Messages : 1172
- Inscription : lundi 21 mai 2007, 13:57
- Statut actuel : Autre
- Localisation : Dordogne
Re: Utilité des permutations
On retrouve quantité de transformations en chimie organique, dont des symétries, permutations.
Un casse tête avec les permutations : les lacets de chaussures. Comment les placer judicieusement, notamment en les faisant garder la symétrie pour la partie émergeante lacée et qu'ils n'aient pas tendance à favoriser un côté en se décalant d'un laçage à l'autre.
Un casse tête avec les permutations : les lacets de chaussures. Comment les placer judicieusement, notamment en les faisant garder la symétrie pour la partie émergeante lacée et qu'ils n'aient pas tendance à favoriser un côté en se décalant d'un laçage à l'autre.
J'ai le virus des sciences, ça se soigne ?
Re: Utilité des permutations
Bon, me voilà satisfait. Je vois que ça sert oui, mais dans des problèmes qui ne s'intéressent pas trop :D
-
- Modérateur honoraire
- Messages : 1839
- Inscription : mercredi 01 juin 2005, 18:39
- Localisation : Un peu plus à l'Ouest
Re: Utilité des permutations
Ca ça m'étonnerait. Qu'est ce qui t'intéresses ?
Pas de questions en MP
La calculatrice, c'est comme Linux, c'est de la merde !
La calculatrice, c'est comme Linux, c'est de la merde !
Re: Utilité des permutations
En fait, parmi les quelques exemples qui ont été mentionnés ici (tresses, ...), je n'en trouve pas un qui m'intéresse. Je pensais que l'on pouvais trouver des exemples plus ... concret (je ne vois pas l'intérêt de la théorie des tresses par exemple). Je parlais dans mon message premier du taquin ... ça, c'est intéressant. Y a-t-il d'autres "jeux" qui font intervenir des permutations ?
-
- Modérateur honoraire
- Messages : 7097
- Inscription : lundi 28 août 2006, 13:18
- Localisation : Allemagne
- Contact :
Re: Utilité des permutations
Les chaises musicales :D, enfin si on ne change pas le nombre de chaises.masiuxus a écrit :Y a-t-il d'autres "jeux" qui font intervenir des permutations ?
-
- Modérateur honoraire
- Messages : 1839
- Inscription : mercredi 01 juin 2005, 18:39
- Localisation : Un peu plus à l'Ouest
Re: Utilité des permutations
Pourtant, si tu réfléchis deux minutes, tu dois trouver une foule de jeu dans lesquels on permute des choses. Un jeu de carte par exemple. Pour être plus précis, les permutations sont un objet de base de la combinatoire, elle-même omniprésente dans l'étude de jeux.
Mais bon, il va de soi que si tout ce qui t'intéresses et de résoudre un taquin ou un Rubik's Cube, même si tu peux faire plein de choses intéressantes dessus avec les permutations, ça n'est nullement obligatoire.
Dans le cas contraire, les permutations devraient avoir été au moins survolées par toute personne disposant d'un niveau Bac+2 en maths.
A propos du taquin, quelqu'un (Jobhertz ? Dark ? Valvino ?) y'a un an avait posté un TER qui parlait du taquin, de partitions d'un entier, et de diverses choses de combinatoire assez compliquées...
Mais bon, il va de soi que si tout ce qui t'intéresses et de résoudre un taquin ou un Rubik's Cube, même si tu peux faire plein de choses intéressantes dessus avec les permutations, ça n'est nullement obligatoire.
Dans le cas contraire, les permutations devraient avoir été au moins survolées par toute personne disposant d'un niveau Bac+2 en maths.
A propos du taquin, quelqu'un (Jobhertz ? Dark ? Valvino ?) y'a un an avait posté un TER qui parlait du taquin, de partitions d'un entier, et de diverses choses de combinatoire assez compliquées...
Pas de questions en MP
La calculatrice, c'est comme Linux, c'est de la merde !
La calculatrice, c'est comme Linux, c'est de la merde !
Re: Utilité des permutations
C'est pas moi
-
- Modérateur honoraire
- Messages : 1839
- Inscription : mercredi 01 juin 2005, 18:39
- Localisation : Un peu plus à l'Ouest
Re: Utilité des permutations
Je me rappelle sue je l'avais parcouru, puis j'avais lâché prise parce que ça n'avait rien d'évident...
Pas de questions en MP
La calculatrice, c'est comme Linux, c'est de la merde !
La calculatrice, c'est comme Linux, c'est de la merde !
Re: Utilité des permutations
Je n'ai pas dit le contraire vu que j'ai parlé du taquin dans ma question initiale :D Mais comme les calculs sur les permutations sont simples, nous sommes passés très vite dessus (sans doute pour passer directement aux déterminants), sans nécessairement voir des choses plus élaborées.Tryphon a écrit :Dans le cas contraire, les permutations devraient avoir été au moins survolées par toute personne disposant d'un niveau Bac+2 en maths.
Manquant sérieusement d'imagination, je ne vois pas réellement d'exemples concrets utiles de calculs sur les jeux de cartes faisant intervenir les permutations et leur signature. Enfin bon, à travers les quelques exemples que vous avez inscrit dans ce topic, je vois un peu. Merci.
-
- Utilisateur chevronné
- Messages : 1172
- Inscription : lundi 21 mai 2007, 13:57
- Statut actuel : Autre
- Localisation : Dordogne
Re: Utilité des permutations
Un outil utile pour les groups:
http://www.gap-system.org/~gap/
qui peut être appliqué aux permutations.
J'ai une idée d'application : les tris qui utilisent beaucoup les permutations. tris par bulle, etc.
Voir:
http://www.nrbook.com/a/bookcpdf.php
chapitre 8 Sorting.
avec les pdf à télécharger freeware.
Un livre:
http://www.amazon.com/exec/obidos/ASIN/ ... ksclub-20/
C'est très ardu, y compris pour moi.
http://www.gap-system.org/~gap/
qui peut être appliqué aux permutations.
J'ai une idée d'application : les tris qui utilisent beaucoup les permutations. tris par bulle, etc.
Voir:
http://www.nrbook.com/a/bookcpdf.php
chapitre 8 Sorting.
avec les pdf à télécharger freeware.
Un livre:
http://www.amazon.com/exec/obidos/ASIN/ ... ksclub-20/
C'est très ardu, y compris pour moi.
J'ai le virus des sciences, ça se soigne ?