22
Etude d’une bibliothèque: Permutations sur les listes

Etude dune bibliothèque: Permutations sur les listes

Embed Size (px)

Citation preview

Page 1: Etude dune bibliothèque: Permutations sur les listes

Etude d’une bibliothèque:

Permutations sur les listes

Page 2: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

1 2 3 4

• Les permutations standard:

- permutations sur un ensemble d ’entiers naturels.

- permutations sur un ensemble de la forme [0,n[ où n est un entier naturel.

- généralisation aux ensembles de la forme [0, n[ où n peut être infini.

• Les permutations appliquées aux listes

Page 3: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

2 1 3 4

ÞPermutation: sigma: [ nat -> nat]

ÞDéfinie sur nat ou un ensemble de nat (setof[nat])

Þ 2 fonctions définissent le domaine d’application de la permutation

o support?(ns: setof[nat])(sigma:[nat -> nat]) :bool

o below?(n:nat): [nat->bool]

Page 4: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

2 1 3 4

Support?Support?

Prédicat définito sur un ensemble d’entiers naturels nso sur une fonction de permutation sigma: [nat-> nat]

si k n’appartient pas ns alors la permutation de l’élément à l’indice k n’a aucun effet => sigma(k) =k si k n’appartient pas ns, car k ne fait pas partie de l’ensemble des éléments à permuter.

support?(ns: setof[nat])(sigma:[nat -> nat]) :boolsupport?(ns: setof[nat])(sigma:[nat -> nat]) :bool

Page 5: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

2 1 3 4

Below?Below?

Prédicat définito sur un entier no qui retourne un sous-ensemble de nat

Ce prédicat retourne l’ensemble des entiers inférieurs à n, elle permet d’effectuer une restriction de l’ensemble des nat, en le bornant par n.

below? (n:nat): [nat->bool] below? (n:nat): [nat->bool]

Page 6: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

2 1 3 4

Permutation?Permutation?

Þ Deux définitions de la permutation, c’est à dire surcharge de la fonction

permutation?(ns:setof[nat])(sigma: [nat->nat]) :bool

permutation?(n:nat)(sigma: [nat->nat]) :bool

Page 7: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

2 1 3 4

Permutation?Permutation?permutation?(ns:setof[nat])(sigma: [nat->nat]) :bool

Þ sigma est une permutation sur ns si:

sigma est bijective et si support?(ns)(sigma) est vrai

Þ sigma bijective signifie:

o Pour tout x appartenant à nat, il existe y appartenant à nat / sigma(x) = y

o Pour tout y appartenant à nat, il existe un unique x nat / sigma(x) = y

Page 8: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

2 1 3 4

Permutation?Permutation?permutation?(ns:setof[nat])(sigma: [nat->nat]) :bool

Þ support?(ns)(sigma) est vrai signifie que pour tout élément k n’appartenant pas à ns, sigma(k)=k Ce qui veut dire que sigma est une permutation sur l’ensemble ns.

Page 9: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

2 1 3 4

Permutation?Permutation?permutation?(n:nat)(sigma: [nat->nat]) :bool permutation?(n:nat)(sigma: [nat->nat]) :bool

Þ la permutation n’est plus définie sur un ensemble d’entiers infini mais sur un ensemble finis d’entiers borné par n.

Þ sigma est une permutation si permutation?(below?(n))(sigma) est vrai On fait ici appel à la définition de la permutation sur un ensemble d’entiers définie précédemment.

Page 10: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

2 1 4 3

Les différents lemmes :Les différents lemmes :

On retrouve pour les deux types de permutations (finies et sur un ensemble de naturels) les lemmes suivants :

• L ’ identité est une permutation.• L ’inverse d ’une permutation est une permutation.• La composition d ’une permutation est une permutation.

Page 11: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

2 1 4 3

• La permutation préserve le support.

• Toute permutation sur un ensemble est une bijection sur cet ensemble.

Les différents lemmes :Les différents lemmes :

Page 12: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

2 1 4 3

Généralisation à des permutations finies ou Généralisation à des permutations finies ou infinies :infinies :

• Prédicat initial?(ns :setof[nat]) : indique si ns est de la forme [0, r[.

• Jugement below_n_initial_segment : indique que (below?) et (initial?) ont le même type.

Page 13: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

2 1 4 3

•Lemme initial_segment_cases : explique la signification de initial?, c ’est à dire qu’un ensemble est de type (initial?) s ’il est infini où de la forme [0, r[.

•Prédicat initial_permutation? : c ’est la même chose que finite_permutation? Généralisé à des ensembles infinis.

Page 14: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

4 1 2 3

• Contexte fini

• Théorie paramétrée par le type des éléments des listes

• On se rapporte au cas de permutations sur des intervalles entiers en assimilant un élément de la liste à son rang dans la liste

Page 15: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

4 1 2 3

Prédicat principal : Prédicat principal : permute?permute?

• permute? : L1 : list[T] x L2 : list[T] x s : [nat -> nat] : bool

• Renvoie VRAI si s(L1) = L2 – Longueur(L1) = Longueur(L2) = L– s est une permutation de support [1,L]– Pour tout i < L, L1[i] = L2[s(i)]

Page 16: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

4 1 2 3

Une extension de Une extension de permute?permute?

• On surcharge permute? : ce nouveau prédicat prend deux listes et renvoie vrai si l’une est une permutation de l’autre

• permute? : L1 : list[T] x L2 : list[T] : bool

• Utilisation du prédicat permute? original : permute?(L1,L2) il existe s : (nat -> nat) tq permute?(L1,L2,s)

Page 17: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

4 1 2 3

LemmesLemmes

• permute? présente plusieurs propriétés intéressantes :– Réflexive– Symétrique– Transitive

Page 18: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

4 1 2 3

DémonstrationsDémonstrations : réflexive: réflexive

• Démontrer qu’une liste est une permutation d’elle-même par l’identité

• Démonstration triviale

Page 19: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

4 1 2 3

Démonstrations : symétriqueDémonstrations : symétrique

• permute?(L1,L2,s) => permute?(L2,L1,s-1)

• 3 buts :– Longueur(L2) = Longueur(L1) : trivial– s-1 est une permutation : on utilise le lemme

inverse_permutation– Pour tout i : L1[i] = L2[s(i)]

On applique le lemme permutation_preserve_support et un peu de calcul

Page 20: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

4 1 2 3

Démonstrations : transitiveDémonstrations : transitive

• permute?(L1,L2,s12) & permute?(L2,L3,s23)

=> permute?(L1,L3,s12 o s23)

• Longueurs : trivial

• s12 o s23 est une permutation d’après le lemme compose_finite_permutation

• Calcul avec utilisation du lemme permutation_preserve_support

Page 21: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

4 1 2 3

Une propriété : permute?_equivalenceUne propriété : permute?_equivalence

• Ce jugement affirme l’équivalence entre :– permute?(L1,L2)– equivalence?(L1,L2)

• Equivalence?

Page 22: Etude dune bibliothèque: Permutations sur les listes

Introduction Permutation Propriétés Listes Conclusion

4 2 1 3

Þ Cette bibliothèque permet une définition simple de la permutation appliquée à n ’importe quel ensemble d ’entiers

Þ On peut l’utiliser par exemple pour la définition d ’un algorithme de tri par permutation.