Exercices : diviser pour régner

B. Le paradigme DPR consiste à (1) diviser le problème en sous-problèmes plus petits, (2) résoudre récursivement chacun de ces sous-problèmes, (3) combiner les résultats pour obtenir la solution du problème initial. A et D décrivent des étapes d’algorithmes séquentiels. C décrit le principe du tri par échange (tri à bulles), pas du DPR.

C. À chaque étape, l’intervalle de recherche est divisé par deux. On effectue au plus $\lfloor \log_2 n \rfloor + 1$ comparaisons. A est la complexité de la recherche séquentielle. D est la complexité du tri fusion. B est la complexité des tris naïfs.

D. Le tri fusion a une complexité en $O(n \log n)$ dans tous les cas (meilleur, pire, moyen), contrairement aux tris naïfs (sélection, insertion) qui sont en $O(n^2)$ dans le pire cas. C’est l’un des avantages majeurs de cet algorithme.

A. Le tri fusion crée des sous-tableaux à chaque étape de fusion : il n’est pas en place et nécessite $O(n)$ mémoire supplémentaire. B est faux ($O(n \log n)$ est meilleur que $O(n^2)$). C est faux (le tri fusion est stable). D est faux (il fonctionne sur tout type comparable).

a) milieu = (0 + 8) // 2 = 4. tab[4] = 25. On a $25 < 33$ donc la valeur cherchée est dans la moitié droite.

b) Nouvelles bornes : gauche = 5, droite = 8. milieu = (5 + 8) // 2 = 6. tab[6] = 42. On a $42 > 33$ donc la valeur cherchée est dans la moitié gauche.

c) Bornes : gauche = 5, droite = 5. milieu = (5 + 5) // 2 = 5. tab[5] = 33. On a $33 = 33$ : trouvé à l’indice 5. Trois étapes ont été nécessaires.

Tableau récapitulatif :

d) Recherche de 20 :

gauche (4) > droite (3) : l’algorithme s’arrête car l’intervalle de recherche est vide. La valeur 20 n’est pas dans le tableau.

e) $\lfloor \log_2 9 \rfloor + 1 = 3 + 1 = 4$ comparaisons au maximum. Cela correspond bien à la recherche de 20 qui a nécessité quatre étapes.

a) Le tableau a six éléments. milieu = 6 // 2 = 3. Moitié gauche : [38, 12, 45]. Moitié droite : [7, 21, 33].

b) Arbre de décomposition (à chaque étape, milieu = len(tableau) // 2) :

          [38, 12, 45, 7, 21, 33]
              /              \
       [38, 12, 45]       [7, 21, 33]
        /       \           /       \
     [38]   [12, 45]     [7]   [21, 33]
             /    \             /    \
          [12]   [45]        [21]   [33]

c) Fusions au niveau le plus bas :

• [12] et [45] : $12 < 45$, donc résultat [12, 45] (une comparaison) ;
• [21] et [33] : $21 < 33$, donc résultat [21, 33] (une comparaison) ;
• [38] et [7] restent seuls à leur niveau : ils sont fusionnés à l’étape suivante avec [12, 45] et [21, 33].

d) Fusions au niveau supérieur :

Fusion de [38] et [12, 45] :

• $38 > 12$ → on place 12 ;
• $38 < 45$ → on place 38 ;
• il reste 45 → résultat : [12, 38, 45] (deux comparaisons).

Fusion de [7] et [21, 33] :

• $7 < 21$ → on place 7 ;
• il reste [21, 33] → résultat : [7, 21, 33] (une comparaison).

Fusion finale de [12, 38, 45] et [7, 21, 33] :

• $12 > 7$ → on place 7 ;
• $12 < 21$ → on place 12 ;
• $38 > 21$ → on place 21 ;
• $38 > 33$ → on place 33 ;
• il reste [38, 45] → résultat : [7, 12, 21, 33, 38, 45] (quatre comparaisons).

e) Total : $1 + 1 + 2 + 1 + 4 = 9$ comparaisons. Le tri par sélection effectue $\frac{n(n-1)}{2} = \frac{6 \times 5}{2} = 15$ comparaisons. Le tri fusion est plus efficace, et l’écart se creuse quand $n$ augmente.

a) (1) : gauche[i] et (2) : droite[j]. On ajoute le plus petit élément des deux listes pour que le résultat soit trié.

b) (3) : j += 1. Quand on ajoute un élément de droite, il faut avancer l’indice j dans cette liste.

c) (4) : gauche[i:] et (5) : droite[j:]. Quand la boucle while se termine, l’une des deux listes a été entièrement parcourue, mais pas nécessairement l’autre. Il faut ajouter les éléments restants, qui sont déjà triés.

Code complet :

def fusion(gauche, droite):
    resultat = []
    i, j = 0, 0
    while i < len(gauche) and j < len(droite):
        if gauche[i] <= droite[j]:
            resultat.append(gauche[i])
            i += 1
        else:
            resultat.append(droite[j])
            j += 1
    resultat.extend(gauche[i:])
    resultat.extend(droite[j:])
    return resultat

d) fusion([3, 8, 15], [1, 9, 12]) :

j = 3 = len(droite) : la boucle s’arrête. On ajoute gauche[2:] = [15]. Résultat final : [1, 3, 8, 9, 12, 15].

a) Le cas de base est un tableau de zéro ou un élément (len(tab) <= 1) : il est déjà trié.

b)

def tri_fusion(tab):
    if len(tab) <= 1:
        return tab
    milieu = len(tab) // 2
    gauche = tri_fusion(tab[:milieu])
    droite = tri_fusion(tab[milieu:])
    return fusion(gauche, droite)

c) Vérification :

>>> tri_fusion([38, 27, 43, 3, 9, 82, 10])
[3, 9, 10, 27, 38, 43, 82]

d) Les trois étapes du paradigme DPR :

• Diviser : le tableau est coupé en deux moitiés à l’indice milieu ;
• Régner : chaque moitié est triée récursivement par tri_fusion ;
• Combiner : les deux moitiés triées sont fusionnées par la fonction fusion pour produire le tableau trié final.

a)

def recherche_dicho(x, tab, gauche, droite):
    if gauche > droite:
        return -1
    milieu = (gauche + droite) // 2
    if tab[milieu] == x:
        return milieu
    elif tab[milieu] < x:
        return recherche_dicho(x, tab, milieu + 1, droite)
    else:
        return recherche_dicho(x, tab, gauche, milieu - 1)

b)

def chercher(x, tab):
    return recherche_dicho(x, tab, 0, len(tab) - 1)

c) L’algorithme relève du paradigme DPR car :

• Diviser : l’intervalle [gauche, droite] est coupé en deux par le milieu ;
• Régner : on cherche récursivement dans une seule des deux moitiés ;
• Combiner : la combinaison est triviale (on renvoie directement le résultat).

La particularité est qu’on ne résout qu’un seul sous-problème (celui de la bonne moitié), au lieu de deux pour le tri fusion. C’est pour cela que la complexité est en $O(\log n)$ au lieu de $O(n \log n)$.

a) Le pixel (0, 0) (valeur 1) se retrouve en position (0, 3). Le pixel (3, 0) (valeur 13) se retrouve en position (0, 0). La règle générale pour une image $n \times n$ : le pixel en position (i, j) se retrouve en position (j, n - 1 - i).

b)

def rotation_directe(image):
    n = len(image)
    resultat = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            resultat[j][n - 1 - i] = image[i][j]
    return resultat

c) Quand on tourne l’image d’un quart de tour horaire, le bloc en haut à gauche (A) se retrouve en haut à droite, le bloc en haut à droite (B) en bas à droite, le bloc en bas à droite (D) en bas à gauche, et le bloc en bas à gauche (C) en haut à gauche. C’est une rotation circulaire des quatre blocs. De plus, chaque bloc subit lui-même une rotation d’un quart de tour, car les pixels à l’intérieur de chaque bloc sont eux aussi tournés.

d)

def extraire_bloc(image, ld, cd, taille):
    return [image[ld + i][cd:cd + taille]
            for i in range(taille)]

def assembler(hg, hd, bg, bd):
    n = len(hg)
    resultat = []
    for i in range(n):
        resultat.append(hg[i] + hd[i])
    for i in range(n):
        resultat.append(bg[i] + bd[i])
    return resultat

e)

def rotation_dpr(image):
    n = len(image)
    if n == 1:
        return [[image[0][0]]]
    m = n // 2
    A = extraire_bloc(image, 0, 0, m)
    B = extraire_bloc(image, 0, m, m)
    C = extraire_bloc(image, m, 0, m)
    D = extraire_bloc(image, m, m, m)
    A_rot = rotation_dpr(A)
    B_rot = rotation_dpr(B)
    C_rot = rotation_dpr(C)
    D_rot = rotation_dpr(D)
    return assembler(C_rot, A_rot, D_rot, B_rot)

Le cas de base est une image $1 \times 1$ : un seul pixel, qui reste inchangé par rotation.

f) Vérification :

image = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12],
    [13, 14, 15, 16]
]
assert rotation_directe(image) == rotation_dpr(image)

Les deux fonctions produisent le même résultat : [[13, 9, 5, 1], [14, 10, 6, 2], [15, 11, 7, 3], [16, 12, 8, 4]].

a)

b) Pour $n = 1,000,000$ : la recherche séquentielle fait au plus $1,000,000$ comparaisons. La recherche dichotomique fait au plus $\lfloor \log_2(1,000,000) \rfloor + 1 = 20$ comparaisons. Le facteur de gain est d’environ $50,000$ : la dichotomie est cinquante mille fois plus rapide dans le pire cas.

c) Argument en faveur : le tri fusion garantit $O(n \log n)$ dans tous les cas, y compris le pire, ce qui n’est pas le cas des tris naïfs. Contre-argument : le tri fusion nécessite $O(n)$ mémoire supplémentaire (il n’est pas en place). Pour de petits tableaux ou des tableaux presque triés, le tri par insertion est plus rapide en pratique (meilleur cas en $O(n)$).

d) Coût de la stratégie « tri + recherches dichotomiques » : $O(n \log n) + k \times O(\log n) = O(n \log n + k \log n)$. Coût des recherches séquentielles : $O(k \times n)$.

La stratégie devient avantageuse quand $n \log n + k \log n < k \times n$, c’est-à-dire quand $k > \frac{n \log n}{n - \log n} \approx \log n$ (pour $n$ grand). Pour $n = 1,000,000$, dès qu’on fait plus d’une vingtaine de recherches, il vaut mieux trier d’abord.