Lycée Berthollet MP/MP* 2021-22

DS3 d’informatique pour tous, mercredi 2 mars 2022 (2h00)

Les documents, téléphones portables, ordinateurs et calculatrices sont interdits.
On s’intéresse ici aux algorithmes de tri. Du point de vue du tri d’un tableau, seul l’ordre de ses éléments nous intéresse
et nous nous restreindrons pour les expériences à des tableaux de taille n ∈ N? dont les éléments sont exactement les entiers
0, 1, . . . , n − 1 dans un ordre quelconque. On identifiera un tel tableau p à l’unique permutation σ p ∈ Sn telle que, pour tout
i ∈ [[0, n − 1]], p[i] = σ p (i) et on appellera donc permutation un tel tableau.
Du point de vue de l’implémentation, ces tableaux seront considérés comme statiques, c’est-à-dire de taille fixe, mais repré-
sentés en Python par des listes, sur lesquelles on s’interdira toute opération spécifique aux listes comme l’ajout ou la suppression
d’éléments (voire la méthode sort...).
Dans tout le devoir, le terme de comparaison signifie une comparaison entre deux valeurs du tableau initial, qui peuvent
cependant être stockées provisoirement dans des structures de données auxiliaires. On admettra que ce nombre de comparaisons
fournit un ordre de grandeur de la complexité temporelle de l’algorithme de tri considéré.
On demande à plusieurs endroits de compléter du code. Dans ce cas la notation ??? signifie qu’il faut insérer à cet endroit
une ou plusieurs lignes.
Tous les programmes doivent écrits en langage Python.

I. Quelques caractéristiques des permutations

Dans le but de pouvoir déterminer statistiquement si certains algorithmes de tri sont plus performants sur certaines catégories
de permutations, on élabore dans cette partie des fonctions obtenant des renseignements quantitatifs sur les permutations.
1. Écrire une fonction nbPtsFixes(p) prenant comme argument une permutation p et retournant le nombre d’indices
i ∈ [[0, n − 1]] tels que σ p (i) = i.
2. Pour une permutation σ, on appelle inversion tout couple (i, j) tel que 0 ≤ i < j ≤ n − 1 et σ(i) > σ( j). Écrire une fonction
nbInversions(p) prenant en argument une permutation p et retournant le nombre d’inversions de σ p .
3. Écrire une fonction orbite(x,p) prenant en argument un entier x ∈ [[0, n − 1]] et une permutation p et retournant la
liste formée, dans l’ordre, de x, σ p (x), σ p ◦ σ p (x), ..., c’est-à-dire de x et ses images successives par σ p , tant qu’elles sont
différentes de x. Par exemple, l’appel
orbite(7,[7,4,0,6,9,5,1,3,8,2])
renvoie la liste
[7,3,6,1,4,9,2,0]

4. Écrire une fonction cycles(p) prenant comme argument une permutation p et retournant sa décomposition en cycles à
supports deux-à-deux disjoints (sans ordre précis sur les cycles), sous forme d’une liste de listes. Par exemple, l’appel
cycles([7,4,6,0,9,5,1,3,8,2])
peut renvoyer la liste
[[0,7,3],[1,4,9,2,6]]

II. Algorithmes classiques

5. Compléter la fonction suivante pour qu’elle effectue un tri par insertion en place du tableau t et que, de plus, elle retourne
le nombre de comparaisons effectuées. On écrira sur la copie uniquement le code manquant.

def triInsertionCtr(t):
ctr = 0
for i in range(1,len(t)):
cle = t[i]
???
return ctr
 6. Prouver la terminaison du tri par insertion.
7. Lors de l’appel de triInsertionCtr sur un tableau de longueur n, montrer un encadrement du nombre de comparaisons
entre deux bornes dépendantes de n dont on montrera qu’elles sont atteintes pour des permutations particulières qu’on
précisera.
8. Réécrire en les complétant les codes des fonctions partition et triRec ci-dessous, pour que la fonction triRapideCtr
effectue un tri rapide en place tout en retournant le nombre de comparaisons effectuées.

def triRapideCtr(t):

def swap(i,j):
if i!=j:
t[i],t[j] = t[j],t[i]

def partition(b,e):
piv = t[b]
???
for i in range(b+1,e):
ctr[0] += 1
???
???
return sep

def triRec(b,e):
???

ctr = [0]
triRec(0,len(t))
return ctr[0]

9. Expliquer pourquoi on stocke cette fois-ci le compteur de comparaisons dans un tableau, contrairement à ce qu’on avait
fait pour le tri par insertion.
10. Décrire l’effet produit par l’appel partition(b,e) sur le tableau t.
11. Démontrer par récurrence forte sur e − b que l’appel triRec(b,e) trie la partie t[b:e] du tableau t.
12. Réécrire en les complétant les codes des fonctions fusion et triRec ci-dessous, pour que la fonction triFusionCtr
effectue un tri fusion en place tout en retournant le nombre de comparaisons effectuées.

def triFusionCtr(t):
tmp = [Link]()

def fusion(b,sep,e):
tmp[b:sep] = t[b:sep]
iG,iD = b,sep
for i in range(b,e):
???

def triRec(b,e):
???

ctr = [0]
triRec(0,len(t))
return ctr[0]

2
 III. Base de données

On stocke les caractéristiques des permutations employées et les résultats des tests de tri dans une base de donnée formée
de quatre tables. La table PERMUTATIONS a comme attributs Formule (chaîne de caractère représentant la permutation
p), le nombre n d’éléments, le nombre NbFixes de points fixes, le nombre NbInv d’inversions, et decCycles (chaîne de
caractère représentant la décomposition en cycles disjoints) :
PERMUTATIONS
Formule n NbFixes NbInv decCycles
[3, 4, 1, 2, 0] 5 0 8 [[0, 3, 2, 1, 4]]
[6, 8, 2, 0, 7, 9, 3, 1, 5, 4] 10 1 25 [[0, 6, 3], [1, 8, 5, 9, 4, 7]]
[5, 3, 4, 1, 2, 0] 6 0 13 [[0, 5], [1, 3], [2, 4]]
... ... ... ... ...
On a ensuite un table par algorithme de tri (TRIINSERTION, TRIRAPIDE, TRIFUSION) pour stocker les performances des
tris, dont les attributs sont Formule, le nombre NbComp de comparaisons effectuées et le temps d’exécution Temps. Par
exemple, pour le tri rapide :
TRIRAPIDE
Formule NbComp Temps
[6, 8, 2, 0, 7, 9, 3, 1, 5, 4] 21 4.200000000764703e-05
[1, 5, 6, 4, 3, 2, 0] 16 1.8000000011397788e-05
[3, 4, 1, 2, 0] 7 2.3999999996249244e-05
... ... ...

13. Écrire une requête SQL permettant d’obtenir les formules et décompositions en cycles de toutes les permutations de taille
100 renseignées dans la base.
14. Écrire une requête SQL permettant d’obtenir le nombre moyen de points fixes de toutes les permutations de taille n de la
table PERMUTATIONS, pour tous les n possibles.
15. Écrire une requête SQL permettant d’obtenir le temps moyen d’exécution du tri fusion parmi toutes les permutations de
taille 42 sans point fixe ayant au moins 51 inversions.
16. On dispose d’une fonction InterrogeBase(req) qui prend en argument une requête SQL sous la forme d’une chaîne de
caractères req et retourne la table résultat de la requête sous la forme d’une liste de listes (les listes intérieures représentant
les lignes de la table, suivant la convention usuelle).
Écrire une fonction moyenne(car) prenant en argument une chaîne valant ’i’, ’r’ ou ’f’, qui travaille suivant la valeur
de cette chaîne respectivement sur le tri par insertion, rapide ou fusion et qui retourne trois listes : la liste des tailles
(de permutations) effectivement représentées dans la table, rangée par ordre strictement croissant, la liste donnant, pour
chaque taille de la première liste, le nombre moyen de comparaisons effectuées dans le tri et enfin la liste, donnant, pour
chaque taille de la première liste, le temps d’exécution moyen du tri.
17. Écrire une fonction graphiqueTemps(listeN) qui affiche sur un même graphique, pour chaque tri, les temps moyens
d’exécution du tri en fonction de la taille de la permutation, les tailles étant prises dans la liste d’entiers listeN passée
en argument.
On supposera pour cela l’importation suivante déjà effectuée :
import [Link] as plt

IV. Listes de permutations

Pour abonder la base de données, on peut, pour les petites tailles, utiliser toutes les permutations disponibles, et pour les
tailles plus grandes, prendre un échantillon aléatoire.
18. Écrire une fonction récursive listePermut(n) retournant la liste de toutes les permutations de taille n.

3
19. Écrire une fonction permutAleatoire(n) qui tire au hasard une permutation de taille n avec equiprobabilité.
On supposera pour cela que l’importation
import [Link] as rd
a été préalablement effectuée et on rappelle que l’appel [Link](k) retourne un entier aléatoire m tel que 0 ≤ m ≤
k − 1, avec équiprobabilité sur cet intervalle.
20. Écrire une fonction listePermutAleatoires(n,taille=100) qui tire au hasard un echantillon de taille taille de
permutations de taille n et le retourne sous forme d’une liste de permutations.

V. Analyse des résultats

À l’aide des fonctions précédentes et d’autres analogues, on peut remplir la base de donnée et en tirer les graphiques
suivants concernant le nombre moyen de comparaisons et le temps d’exécution moyen.

Sur chaque graphique, on a trois courbes représentatives. Les étoiles correspondent à un tri, les points ronds à un autre et
les losanges au dernier, avec la même convention pour les deux graphiques.
21. Déterminer à quel tri correspondent les courbes représentées par des points ronds en argumentant à l’aide des résultats du
cours.
22. Déterminer ensuite les courbes des deux autres tris en étudiant plus finement les algorithmes.
23. Pourriez-vous expliquer pourquoi les courbes de droite sont plus capricieuses que celles de gauche ?
24. Les nombres de comparaisons sont-ils conformes aux résultats théoriques prouvés en cours ?