L2 MIASHS, Algorithme et Programmation 2, année 2021

Les paradigmes algorithmiques

Pour trouver différents algorithmes, on peut s’appuyer sur des grands paradigmes pour être guider. Ces paradigmes peuvent être d’une grande diversité, selon les modèles calculatoires sous-jacent.

Nous allons étudier deux de ces paradigmes parmi les plus commun.

Diviser pour régner

Le cas du max

On va reprendre le problème de la fonction max vu dans les deux derniers cours pour illustrer une approche diviser pour régner. La complexité obtenue ne sera pas meilleur, mais ça permettra d’illustrer la méthodologie

Rappel:

On va diviser la liste en deux, chercher le max dans chaque partie et assembler le résultat. Cela donne une définition récursive:

def max_divise_regner(L):
    n = len(L)
    if n == 1:
        return L[0]
    m1 = max_divise_regner(L[:n//2])
    m2 = max_divise_regner(L[n//2:])
    return max(m1, m2)

On peut vérifier sur un exemple que ça marche bien:

print(max_divise_regner([0, 42, 3, 4, 5]))
42

Analyse de complexité (algorithmique)

Si on note \(C_n\) la complexité de l’algorithme max_divise_regner pour \(n\) la taille de la liste, alors on a la relation de récurrence:

\[ \begin{cases} C_{2n} &= 2C_n + 3\\ C_{2n+1} &= C_n + C_{n+1} + 3 \end{cases} \]

En posant \(F_n = C_{n+1} - C_n\) alors on a que \[ \begin{cases} F_{2k} &= C_k + C_{k+1} + 3 - (2C_k + 3) &= C_{k+1} - C_k = F_k&\text{(cas $n=2k$ est paire)}\\ F_{2k+1} &= 2C_{k+1} + 3 - (C_{k+1} + C_{k} + 3) &= C_{k+1} - C_k = F_k&\text{(cas $n=2k+1$ est impare )} \end{cases} \]

On a donc dans tous les cas \(F_n\) est constante égale \(F_1=C_2 - C_1\) avec \(C_1=2\) et \(C_2= 2C_1 + 3=7\), et donc F_n=5$. On a donc que \(C_{n+1} = C_n+5 = 5n+2\), ce qui donne une complexité en \(O(n)\) (comme prévu).

Analyse de complexité (adapté à Python)

Nous avons considéré ici que l’opération \(L[:n//2]\) n’était pas couteuse, hors cette opération réalise une copie complète de la liste jusqu’à \(n//2\). On peut le vérifier facilement expérimentalement:

liste_copy

lien vers le code qui a générer l’image

Avec les copies, l’analyse de complexité et beaucoup moins bonne, on obtient en effet:

\[ \begin{cases} C_{2n} &= 2C_n + 2n + 3\\ C_{2n+1} &= C_n + C_{n+1} + 2n + 4 \end{cases} \]

En posant \(F_n = C_{n+1} - C_n\) alors on a que \[ \begin{cases} F_{2k} &= C_k + C_{k+1} + 2n + 4 - (2C_k + 2n + 3) &= C_{k+1} - C_k + 1 &= F_k + 1&\text{ (cas $n=2k$ est paire) }\\ F_{2k+1} &= 2C_{k+1} + 2n + 5 - (C_{k+1} + C_{k} + 2n + 4) &= C_{k+1} - C_k + 1 &= F_k + 1&\text{ (cas $n=2k+1$ est impaire) } \end{cases} \]

Ça nous donne que \(F_n = \log_2(n)\) et donc \(C_{n+1} = C_n + \log{n}\) et que \(C_n = \sum_{i=0}^n \log(i) = \log(n!)\) On peut utiliser la formule de Stirling ce qui nous donne que \(C_n = \log(\sqrt(2\pi n)(\frac{n}{e})^n) = C.\log(n) + n\log(\frac{n}{e}) = O(n\log n)\).

Implémentation en Python sans copie de liste

Il est en faite possible de fournir une implémentation qui évite les copies de liste inutile. On va donc refaire une implémentation, en représentant les sous liste par des des paires d’entiers.

def max_divise_regner2_aux(L, a, b):
    """ Retourn le max de L entre a et b """
    if a == b + 1:
        return L[a]
    point_median = a + (b - a)/2
    m1 = max_divise_regner2_aux(L, a, point_median)
    m2 = max_divise_regner2_aux(L, point_median, b)
    return max(m1, m2)

def max_divise_regner2(L):
    return max_divise_regner2_aux(L, 0, len(L))

Il est souvent pratique d’introduire des fonctions auxiliaires quand on fait des fonctions par récurrence. Il ne faut vraiment pas hésiter à le faire.

On peut mesurer les différentes implémentations:

maxs

liens vers le code qui a générer l’image

Les tris !

Le problème du tri d’une liste (d’entier) est l’un des problèmes algorithmiques les plus anciens de l’informatique. Ces problèmes sont utilisés partout. Dans les grosses bases de données, dans beaucoup d’algorithmes utilisés au quotidiens, dans des problèmes de routage.

Le tri par insertion

Un algorithme très simple pour le tri:

def tri_insertion(L):
    if len(L) <= 1:
        return L
    m = max(L)
    L.remove(m)
    K = tri_insertion(L)
    K.append(m)
    return K

On vérifie que ça marche sur un exemple:

L = [0, 42, 3, 27]
print(tri_insertion(L))
[0, 3, 27, 42]

Il est possible d’en faire une version iterative:

def tri_insertion_iterative(L):
    K = []
    while L:
        m = min(L)
        L.remove(m)
        K.append(m)
    return K

On vérifie que ça marche sur un exemple:

print(tri_insertion_iterative(L))
[0, 3, 27, 42]

Analyse de complexité

La version récursive et itérative ont la même complexité qui dépend de la complexité de l’opération remove sur les listes. Cette dernière peut nécessiter de recopier la liste entièrement (ce qui est en \(O(n)\)\(n\) est la taille de la liste). On obtient donc: \(C_{n+1} = 2n + 1 + C_n\) avec \(C_1 = 1\) et donc

\[C_n = 1 + \sum_{i=2}^n(2i+1) = 1 + 2\sum_{i=2}^n i + (n-2) = n-3 + \sum_{i=1}^n i = n-3 + n(n-1) = O(n^2)\]

Il est possible d’améliorer cette implémentation en évitant le remove mais cela nécessite un code plus long sans faire diminuer la complexité finale. Ça sera certes plus rapide, mais aussi plus compliqué à coder pour un gain pas forcément intéressant.

Les deux implémentations qu’on propose ne sont pas en place: elle stock le résultat dans un tableau intermédiaire. Il est possible de faire bien mieux en modifiant la liste directement.

def argmax(L, maxsize=None):
    """
    Retourne l'indice où on trouve la
    première occurrence de la valeur maxisum
    de la liste jusqu'à maxsize.
    """
    n = maxsize if maxsize else len(L)
    arg = 0
    maxv = 0
    for i in range(n):
        if L[i] > maxv:
            arg = i
            maxv = L[i]
    return arg

Par exemple:

L = [0, 4, 5, 42, 3, 4]
print(argmax(L))
print(argmax(L, maxsize=3))
3
2

Avec cette fonction, on peut améliorer le tri par insertion:

def tri_insertion_iterative2(L):
    n = len(L)
    for i in range(n):
        j = argmax(L, maxsize=n-i)
        L[j], L[n-i-1] = L[n-i-1], L[j]

On vérifie que ça marche sur un exemple. Remarquez qu’on n’affiche pas le résultat de la fonction, mais la même liste initial, qui a été modifié (en place).

tri_insertion_iterative2(L)
print(L)
[0, 3, 4, 4, 5, 42]

Analyse expérimental

On peut regarder les performances des différents tris en pratique:

tri_insertion

lien vers le code qui a généré l’image

On voit que la version tri_insertion_terative2 n’est pas performante. C’est le coût de faire le max à la main et de ne pas utiliser la version optimisé par Python. Il faut toujours privilégier les fonctions optimisé à les refaire à la main.

Le tri fusion

Nous allons proposer un meilleur algorithme de tri, basé sur diviser pour régner. L’idée principal et de couper le tableau en deux. De trier la partie gauche, trier la partie droite et de fusionner le résultat.

def tri_fusion(L):
    n = len(L)
    if n <= 1:
        return L
    K1 = tri_fusion(L[:n//2])
    K2 = tri_fusion(L[n//2:])
    # On fusionne
    resultat = []
    while bool(K1) and bool(K2):
        # Tant que les deux listes sont non vides
        if K1[0] > K2[0]:
            resultat.append(K2.pop(0))
        else:
            resultat.append(K1.pop(0))
    if K2:
        resultat.extend(K2)
    if K1:
        resultat.extend(K1)
    return resultat

Comme d’habitude, on vérifie sur un exemple que ça marche:

L = [0, 42, 3, 7, 9, 21, 1, 9, 0]
print(tri_fusion(L))
[0, 0, 1, 3, 7, 9, 9, 21, 42]

Exercice: Essayez de proposer une version en place.

Analyse de complexité

En posant \(C_n\) la complexité, on a:

\[ \begin{cases} C_{2n} &= 2C_{n} + 2 + 2n\\ C_{2n+1} &= C_n + C_{n+1} + 2 + 2n \end{cases} \] avec \(C_1 = 2\).

En posant \(F_n = C_{n+1} - C_n\), on a

\[ \begin{cases} F_{2n} &= C_{2n+1} - C_{2n} &= C_n + C_n{n+1} + 2 + 2n - (2C_n + 2 + 2n) &= C_{n+1} - C_n&=F_n\\ F_{2n+1} &= C_{2(n+1} - C_{2n+1} &= 2C_{n+1} + 4 + 2n - (C_n + C_{n+1} + 2 + 2n) &= C_{n+1} - C_n + 2 &= F_n + 2 \end{cases} \]

De plus, un simple calcul montre que \(F_1 = C_2 - C_1 = 6\).

On prouve que \(F_n = 2k + 4\)\(k\) est le nombre de \(1\) dans la décomposition binaire de \(n\) que l’on note \(|n|_2\).

Comme \(F_1 = 2\times 1 + 4 =6\), le cas de base (\(n=1\)) est immédiat.

On suppose que le résultat est vrai pour tout entier jusqu’à \(n\) et on le montre pour \(n+1\).

Finalement, on a que \[C_n = \sum_{i=0}^n F_i = 4n + 2\sum_{i=0}^n |i|_2\]

Or, on remarque que \(|i|_2 \leq \log_2 n\) et donc que \(C_n = O(n\log(n))\).

Calculer la valeur exacte de cette somme est ardue, il est néanmoins possible de l’encadrer simplement. On utilise pour ça le fait que \(2^k \leq n \leq 2^{k+1}\) et donc \[\sum_{i=0}^{2^k} |i|_2\leq \sum_{i=0}^{n} |i|_2 \leq \sum_{i=0}^{2^{k+1}} |i|_2\]

Hors, comme les \(0\) et les \(1\) sont équitablement répartie dans les décomposition en binaires des nombre jusqu’à \(2^k\) et \(2^{k+1}\), et en considérant que le nombre de symbôle nécessaire pour écrire tous les nombre est exactement \(k2^k\) et \((k+1)2^{k+1}\), on a que \(\sum_{i=0}^{2^k} |i|_2 = k2^{k-1}\) et \(\sum_{i=0}^{2^k} |i|_2 = k2^{k-1}\).

On obtient alors \(3n + n\log_2(n) \leq C_n \leq 4n + n \log_2 n\). La borne supérieur est ainsi pas trop loin de la valeur réelle pour \(C_n\), le terme dominant asymptotiquement étant de toute façon, \(n\log_2(n)\).

Analyse Expérimentale

On peut regarder les performances des différents tris vu jusqu’à présent qu’on compare au tri implémenté par défaut dans Python:

tri_total

lien vers le code qui a généré l’image

On remarque que les allures des courbes des tris Fusion et de Python sont similaires. Le tri par insertion est plus efficaces que le tri fusion pour de petites valeurs de liste, mais le dépasse rapidement quand la taille de la liste grossi.

Complexité des algorithmes vs Complexité des problèmes algorithmiques

Cette partie du cours est facultative, sa compréhension n’est pas indispensable pour le reste du cours.

Nous avons jusqu’à présent comment analyser la complexité d’un algorithme donné.

Quand on parle de la complexité d’un problème algorithmique on parle de la complexité de résoudre ce problème par le meilleur algorithme possible.

Ainsi, quand on parle de la complexité du problème du tri, on se demande quel est le meilleur algorithme pour résoudre le problème du tri.

Dans certain cas, il est possible de montrer qu’il n’est pas possible d’avoir une certaine complexité. On parle alors de borne inférieures de complexité.

Trouver des bornes inférieures de complexité est un thème important de la recherche en informatique théorique. Certaines bornes inférieures sont simple, nous allons en voir et d’autre toujours ouvert malgré des décennies de travaux sur le sujet.