Corrigé du partiel du 2 décembre 2002

Exercice 2, premiere partie

1)

8 9 7 9 3 2 3 4
8 9 7 9 2 3 3 4
8 7 9 2 9 3 3 4
7 8 2 9 3 9 3 4
7 2 8 3 9 3 9 4
2 7 3 8 3 9 4 9
2 3 3 7 4 8 9 9
2 3 3 4 7 8 9 9

2)

Pour tout i indice du tableau A, on note i' la nouvelle position de l'entier qui était en i et A' le nouveau tableau. Alors pour tout i<j tels que i'<j', INV(A,i,j) = INV(A',i',j').
Soit D l'ensemble des couples (i,j) tels que i<j et i'>j' et D' l'ensemble des couples (i',j') tels que i>j et i'<j'.
On a donc sigma(A)-sigma(A') = somme_{i,j in D} INV(A,i,j) - somme_{i,j in D'} INV(A',i',j')
Or si (i,j) est dans D', alors j et i sont consécutifs et échangés à cette étape, donc INV(A',i',j')=0. De même, si (i,j) sont dans D, alors i et j sont consécutifs et échangés à cette étape, donc INV(A,i,j)=1.
Donc sigma(A)-sigma(A') vaut le nombre de couples actifs échangés à cette étape. Si ce nombre est 0, alors aucun couple n'est échangé. Si il est 0 deux fois de suite, alors A est trié. On en déduit que soit A est trié, soit sigma(A) diminue strictement en deux étapes. Comme sigma(A) est positif, le tableau sera trié au bout d'un certain nombre d'étapes.

3)

Soit (k,k+1) le couple actif. Dans tous les cas, INV(A',k,k+1)=INV(B',k,k+1)=0.

Si A[k]>A[k+1], alors B[k]>B[k+1] et
INV(A',i,k) = INV(A,i,k+1) <= INV(B,i,k+1) = INV(B',i,k)
INV(A',i,k+1) = INV(A,i,k) <= INV(B,i,k) = INV(B',i,k+1)
INV(A',k,j) = INV(A,k+1,j) <= INV(B,k+1,j) = INV(B',k,j)
INV(A',k+1,j) = INV(A,k,j) <= INV(B,k,j) = INV(B',k+1,j)

Si A[k] <= A[k+1] et B[k]>B[k+1] alors
INV(A',i,k) = INV(A,i,k) <= INV(B,i,k) <= INV(B,i,k+1) = INV(B,i,k)
INV(A',i,k+1) = INV(A,i,k+1) <= INV(A,i,k) < INV(B,i,k) = INV(B',i,k+1)
INV(A',k,j) = INV(A,k,j) <= INV(A,k+1,j) <= INV(B,k+1,j) = INV(B',k,j)
INV(A',k+1,j) = INV(A,k+1,j) <= INV(B,k+1,j) <= INV(B,k,j) = INV(B',k+1,j)

Et dans les autres cas, INV ne change pas, donc l'ordre sur A et B est conservé.

4)

Pour tout i<j, INV(M,i,j)=1, donc tout tableau A est plus petit que M. Cet ordre est préservé après chaque étape du tri. Au bout de N_M étapes, le tableau M est devenu M' et pour tout i<j INV(M',i,j)=0. Il en est donc de même pour A', donc A' est trié.

5)

L'entier m-1 est d'abord échangé avec son voisin de gauche, puis il reste en place, puis il doit encore être déplacé de m-2 positions, soit en tout au moins m étapes.

6)

a)

Les déplacements sont de la forme G^k ou G^k S D^l ou D^k ou D^k S G^l (k et l possiblement nuls). Comme le nombre maximal d'étapes efficaces est m (cf 5)), on n'a pas d'autre déplacement possible.

b)

Puisque INV(A,l,l+1)=0 et que la première étape est efficace, a se déplace d'abord à gauche et b à droite (sauf si l=1 ou l=m-1). Pour que a se retrouve à nouveau à une position à droite de b, il faut au moins que les deux éléments changent de sens de déplacement. Le déplacement de a sera donc G^{l-1} S D^{k-l} et celui de b sera D^{m-l} S G^{k+l-m-1}. Donc la position de a sera k-l+1 et celle de b sera 2m-k-l+1. donc si k<=m-1, la position de a est au plus m-l et celle de b au moins m-l+2, soit un écarrt d'au moins deux cases entre a et b.

c)

La première étape est évidement efficace. On considère le tableau M après k étapes supposées efficaces. Si il existe l tel que A[l]<A[l+1] alors soit (l,l+1) a été échangé à la précédente étape, et donc ce couple ne sera pas actif à l'étape k+1, soit ils ont été distants d'au moins une case à l'étape précédente, et d'après b), il a fallu au moins m-1 étapes depuis leur comparaison, ce qui est impossible si k<m. Donc par récurrence sur k, les m premières étapes sont effiaces.

d)

D'après la preuve de 2), chaque étape efficace diminue sigma du nombre de couples actifs. Donc si m est impair, chaque étape diminue sigma de (m-1)/2 et donc au bout de m étapes efficaces, sigma a diminué de m(m-1)/2. Si m est pair, les étapes impaires diminuent sigma de m/2 et les étapes paires de m/2-1, soit un total de m-1 toutes les 2 étapes et donc m(m-1)/2 au bout de m étapes. Or au départ, sigma(M)=m(m-1)/2, donc au bout des m premières étapes, qu'on a prouvé efficaces, sigma vaut 0 et donc le tableau est trié.
D'où N_M = m.

Exercice 2, deuxieme partie

1)

Apres l'étape 1, chaque sous-carré contient un certain nombre de lignes (remplies d'éléments plus petits que n) consécutives, suivie d'une ligne éventuelle partiellement remplie, puis uniquement des éléments plus grands que n. Cette ligne partielle est remplie de gauche à droite en haut et de droite à gauche en bas.

Apres l'étape 2, chaque demi-colonne est composé de a_i (i vaut 0 ou 1) lignes pleines et d'une ligne partiellement remplie. En effet, on retrouve les lignes des sous-carrés et les deux lignes partielles qui, étant remplies dans un sens différent donnent soit une ligne trouée au milieu, soit une ligne pleine plus une ligne remplie au milieu uniquement.
Si a_0 = a_1 alors apres les trois étapes suivantes, l'ensemble des éléments plus petits que n forme des lignes consécutives suivies d'une ligne partiellement remplie de gauche à droite.

Sinon, soit a_0 = a_1 + b_0. Après l'étape 3, on a donc a_1 lignes consécutives remplies, puis une ligne de taille > m/2, puis des lignes commençant alternativement à droite et à gauche de taille m/2, puis une ligne de taille < m/2. Soit c le côté par lequel la première ligne non pleine commence (c vaut gauche ou droit) et c' l'autre côté.

Après l'étape 4, si b_0 est pair, les deux colones (demi-tableaux) contiennent chacune a_1+b_0/2 lignes pleines puis une ligne incomplète (partant de c). A l'étape 5, on a donc au total a_1+b_0/2 lignes pleines suivies d'une ligne incomplète commençant à gauche.
Si b_0 est impair, la colone c contient a_0+(b_0+1)/2 lignes pleines et la colone c' contient a_0+(b_0-1)/2 lignes complètes suivies soit d'une ligne complète et d'une ligne incomplète remplie au milieu uniquement, soit une ligne incomplète avec un trou au milieu. Dans le premier cas, après l'étape 5, on a a_1+(b_0+1)/2 lignes complètes suivies d'une ligne incomplète (de longueur < m/2) commençant à gauche. Dans le second cas, après l'étape 5, on a a_1+(b_0-1)/2 lignes complètes suivies d'une ligne incomplète (de longueur > m/2) commençant à gauche.
CQFD.

2)

Soient a et b deux nombres consécutifs en parcourant le tableau de gauche à droite après l'algorithme. On sait d'après 1) que Xb contient aussi a, donc a < b, donc le tableau est trié.

3)

a)

L'algorithme consiste en trier chacun des 4 sous-tableaux de taille m/2 x m/2, ce qui peut se faire en parallèle en T_{m/2} étapes. Puis chacun des points suivants de l'algorithme peut se faire en m étapes d'après la partie précédente.
D'où T_m = T_{m/2} + 4m

b)

Soit u_n = T_{2^n}. Alors u_n = u_{n-1} + 2^{n+2}. De plus u_0 = T_1 qui ne nécéssite aucune opération donc u_0=1. Soit évidemment T_m = 8m - 8.

4)

Les algorithmes de tri traditionnels sont en n.log(n). On a vu que dans le cas de n processeurs, on pouvait faire le tri en n opération, et si n est une puissance de 2, en O(sqrt(n)).