Diviser pour régner

Dans quel cas ?

  • On parvient à découper un problème en sous-problèmes indépendants les uns des autres. On poursuit cette démarche jusqu’à aboutir à une situation simple : cas de base.
  • La solution du cas de base est généralement simple à obtenir et permet la construction de la solution du problème.

Remarque

C’est l’indépendance des sous-problèmes qui permet la construction de la solution globale directe par recombinaison des solutions intermédiaires.

Exemples

  • Exponentiation rapide
  • Recherche dichotomique dans un tableau trié, dans une liste triée
  • Tri rapide d’un tableau
  • Tri fusion récursif d’un tableau
  • etc.

Schéma de résolution

Diviser
On décompose le problème initial en un ou plusieurs sous-problèmes de plus petites tailles.
Régner
Chaque sous-problème est résolu
Combiner
Les solutions des sous-problèmes sont combinées pour construire la solution du problème initial.

Remarques

  • Cette procédure se prête naturellement à un traitement récursif des problèmes mais une approche itérative reste possible.
  • Cette procédure assure que l’algorithme est correct. Il reste à valider sa terminaison (que le cas de base est toujours atteint ).

Exercice : exponentiation rapide

L’algorithme suivant permet de calculer $a^n$ : $$ a^n = \begin{cases} 1 &\text{if } n=0 \\ a \times a^{n-1} &\text{if } n>0 \end{cases} $$

  1. Programmer la fonction puissance1 dont la spécification est :
1
2
3
4

def puissance1(a: int, n: int) -> int:
    """
    Calcul de a^n.
    """

Penser à écrire quelques tests.

Réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def puissance1(a: int, n: int) -> int:
    """
    Calcul de a^n.
    Implémentation de l'algorithme 1.
    """
    if n == 0:
        return 1
    else:
        return a * puissance1(a, n - 1)


if __name__ == "__main__":
    assert puissance1(3, 2) == 9
    assert puissance1(5, 0) == 1
    assert puissance1(2, 8) == 256

    print("Done!")
  1. Quelle est la complexité de cet algorithme ?
Réponse

Le calcul nécessite $n$ appels récursifs et $n+1$ multiplications. La complexité est donc en $O(n)$.

L’algorithme suivant permet aussi de calculer $a^n$ : $$ a^n = \begin{cases} 1 &\text{if } n=0 \\ ( a^k )^2 &\text{if } n = 2k \text{ (n est pair)} \\ a \times ( a^k )^2 &\text{if } n = 2k + 1 \text{ (n est impair)} \end{cases} $$

  1. Programmer la fonction puissance2 dont la spécification est :
1
2
3
4
5

def puissance2(a: int, n: int) -> int:
    """
    Calcul de a^n.
    Implémentation de l'algorithme 2.
    """

Penser à écrire quelques tests.

Réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def puissance2(a: int, n: int) -> int:
    """
    Calcul de a^n.
    """
    if n == 0:
        return 1

    calc = puissance2(a, n // 2)
    
    if n % 2 == 0:
        return calc**2
    else:
        return a * (calc)**2


if __name__ == "__main__":
    assert puissance2(3, 2) == 9
    assert puissance2(5, 0) == 1
    assert puissance2(2, 8) == 256

    print("Done!")
  1. Justifier que le seconde algorithme met en œuvre le raisonnement « Diviser pour règner ».
Réponse
  • La première ligne de l’algorithme correspond au cas de base pour lequel $n=0$ et $a^n=1$.
  • Pour $n>0$, à partir de la valeur $n$, le calcul se poursuit avec la valeur $\left\lfloor \dfrac{n}{2} \right\rfloor$. On décompose le calcul de $a^n$ en celui de $a^{\left\lfloor \dfrac{n}{2} \right\rfloor}$, puis celui de $a^{\left\lfloor \dfrac{n}{2} \right\rfloor / 2}$, etc. jusqu’à atteindre le cas de base. Chaque calcul intermédiaire se fait sur une instance plus petite.
  • Chaque calcul intermédiaire est aussi indépendant du calcul précédent.

Remarque

  • $\left\lfloor \dfrac{n}{2} \right\rfloor$ est la notation mathématique pour l’opération en Python n // 2, c’est à dire le plus grand entier inférieur au résultat de la division de $n$ par 2.

  • $\left\lceil \dfrac{n}{2} \right\rceil$ est la notation mathématique pour l’opération en Python n // 2 + 1, c’est à dire pour le plus petit entier supérieur au résultat de la division de $n$ par 2.

  1. Pourquoi appelle-t-on l’algorithme 2, l’exponentiation rapide ?
Réponse

Soit $k$ le nombre de fois qu’il faut diviser (division euclidienne) $n$ par 2 pour parvenir à la valeur 1. $k$ est tel que $$ 1 = \dfrac{n}{2^k} \iff 2^k = n \iff k = \log_2 n $$.
Il reste un appel récursif supplémentaire à effectuer pour arriver au cas de base.
La complexité de l’algorithme est donc en $O(\log_2 n)$ ; elle est bien meilleure que celle de l’algorithme 1.

Conclusion

  • La méthode « Diviser pour régner » est le paradigme naturel de la récursivité.
  • La complexité d’un algorithme qui s’appuit sur le paradigme « Diviser pour régner » est parfois optimale (exponentiation rapide, recherche dichotomique, tri fusion, etc.) mais pas toujours (recherche du minimum et du maximum dans une liste, somme des éléments d’une liste, recherche dans une liste non triée, etc.).
  • L’efficacité d’un algorithme qui s’appuit sur le paradigme « Diviser pour régner » dépend de l’implémentation de la récursivité par le langage choisi.

Exercice : recherche dichotomique

  1. Écrire le code de la fonction recherche1 dont la spécification est la suivante :
1
2
3
4
5
6
7
8
9

def recherche1(liste: list[int], val: int) -> int:
    """
    Retourne l'indice de la valeur dans la liste si cette 
    dernière est présente, -1 sinon.

    HYPOTHÈSE : val est unique si présente.

    Algorithme itératif.
    """
Réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def recherche1(liste: list[int], val: int) -> int:
    """
    Retourne l'indice de la valeur dans la liste si cette 
    dernière est présente, -1 sinon.

    HYPOTHÈSE : val est unique si présente.

    Algorithme itératif.
    """
    g = 0               # indice le plus petit
    d = len(liste) - 1  # indice le plus grand

    trouve = False
    while (g < d) and not trouve:
        m = (g + d) // 2  # indice milieu
        if liste[m] == val:
            trouve = True
        elif liste[m] > val:
            d = m - 1
        else:
            g = m + 1
    return m if trouve else -1

  1. Tester la fonction recherche1.

  2. Écrire le code de la fonction recherche2 dont la spécification est la suivante :

1
2
3
4
5
6
7
8
9

def recherche2(liste: list[int], val: int, g: int, d: int) -> bool:
    """
    Retourne l'indice de la valeur dans la liste si cette 
    dernière est présente, -1 sinon.

    HYPOTHÈSE : val est unique si présente.

    Algorithme récursif.
    """
Réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def recherche2(liste: list[int], val: int, g: int, d: int) -> bool:
    """
    Retourne l'indice de la valeur dans la liste si cette 
    dernière est présente, -1 sinon.

    HYPOTHÈSE : val est unique si présente.

    Algorithme récursif.
    """
    if g > d:
        return -1
    else:
        m = (g + d) // 2  # indice milieu
        if liste[m] == val:
            return m
        elif liste[m] > val:
            return recursive(liste, val, g, m - 1)
        else:
            return recursive(liste, val, m + 1, d)
  1. Tester la fonction recherche2.
Diviser pour régner 

Suggestions de lecture :