Inversion d'une permutation

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Fortysecond
Messages: 3
Enregistré le: 19 Avr 2015, 18:29

Inversion d'une permutation

par Fortysecond » 19 Avr 2015, 18:41

Bonjour,

J'arrive au bout d'un projet de programmation et un énoncé me pose problème au niveau mathématique.
Le but est de calculer l'inverse d'une permutation donnée à l'aide de différentes fonctions définies auparavant et qui effectuent ceci :

L'une, pour une permutation Sigma, donne une série de transpositions (cycles de longueur 2) qui, si on en fait la composée, donnent Sigma. Un exemple de transpositions serait, pour sigma sous-forme de cycle = (1,3,6,2)(4,5,7)(8) : (1,3)(3,6)(6,2)(4,5)(5,7)(8).

La seconde, au sein d'une permutation Identité, échange les positions de deux nombres.
Par exemple, pour (1,2,3,4,5), elle peut donner, selon les paramètres définis, (1,4,3,2,5) (places de 2 et 4 échangées) ou encore (3,2,1,4,5) (places de 1 et 3 échangées).

La dernière effectue simplement la composition de deux permutations sigma et tau.

Comment, en utilisant ces trois fonctions, construire une méthode permettant d'inverser une permutation?
J'ai refait le tour de mes connaissances sans résultat et me suis décidé à demander un peu d'aide, ou au moins une piste.

Merci d'avance.



Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21481
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 19 Avr 2015, 20:41

C'est extrêmement simple... dans les deux cas.

Si tu écrit ta permutation comme composée de transpositions, il suffit d'écrire les transpositions "à l'envers" pour avoir l'inverse de la permutation de départ vu que :
- Une transposition est sa propre inverse.
- L'inverse d'un produit, c'est le produit des inverse mais écrits dans l'autre sens : (ab)^{-1}=b^{-1}a^{-1}
Donc par exemple, l'inverse de (1,3)(3,6)(6,2)(4,5)(5,7)(8) est : (8)(5,7)(4,5)(6,2)(3,6)(1,3)

Si ta permutation est écrite sous forme de composée de cycles (si possible à support disjoint de façon à ce qu'ils commutent entre eux) alors il suffit d'inverser les cycles ce qui revient bètement à les écrire "à l'envers" : l'inverse de (1,2,3,4,5) est (5,4,3,2,1) (que tu peut obtenir uniquement en "échangeant les places", mais c'est pas le plus malin...)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Fortysecond
Messages: 3
Enregistré le: 19 Avr 2015, 18:29

par Fortysecond » 19 Avr 2015, 20:50

C'est ce que je pensais faire, mais on me demande d'utiliser les TROIS fonctions données (y compris donc celle qui échange les positions des éléments d'une permutation identité). Or, ce qu'on fait avec les transpositions (les écrire "à l'envers", puis en faire la composée) ne fait pas appel à cette fonction... si? Ou est-il possible d'utiliser cette fonction pour inverser l'ordre des transpositions?

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21481
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 19 Avr 2015, 21:04

Tu peut tout à fait utiliser cette fonction si tu y tient absolument (c'est un peu con con, mais bon...)
Si tu as écrit ta permutation comme produit de transpositions puis que tu applique ces transposition à l'identité en commençant par la dernière, alors tu tombe (par définition) sur la transposition de départ.
Et si tu fait la même chose en les appliquant en commençant par la première, ben tu obtient l'inverse de la permutation de départ.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Fortysecond
Messages: 3
Enregistré le: 19 Avr 2015, 18:29

par Fortysecond » 19 Avr 2015, 21:10

Je ne suis pas certain de suivre.
Cela signifierais que je devrais d'abord mettre la permutation sous forme de produit de transpositions et faire la composition avec l'identité après avoir utiliser la fonction "changement de places au sein de l'identité" pour... pour quoi, exactement?

Pour le côté con con de la chose, je ne fais que ce qu'on me demande. Il est impératif de se servir de chaque fonction de manière non triviale. Les consignes sont formelles...

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 70 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite