Algorithmes classiques

La suite de Fibonacci est clairement croissante (vous pouvez le prouver par récurrence), ce qui permet d'écrire :

Les deux égalités sont clairement vraies (par récurrence) pour tout $n>1$. En les soustrayant et en utilisant le fait que $\phi_+ - \phi_- = \sqrt{5}$ permet de conclure que :

Il faut démontrer que ce programme est bien un algorithme car il y a plusieurs récursions !

Ceci se fait facilement par une récurrence sur $n$ car chaque appel se rapproche strictement de la condition d'arrêt.

1. initialisation : fibonacci_rec(n) admet un nombre fini de récursion pour $n\leq 2$.
2. hypothèse de récurrence : fibonacci_rec(m) admet un nombre fini de récursion pour $m < n$.
3. Pour $n$, fibonacci_rec(n - 1) et fibonacci_rec(n-2) se terminent en un nombre fini de récursion donc la ligne 4 de l'algorithme aura aussi un nombre fini de récursion.

Une fois la finitude démontrée la correction est évidente, comme souvent avec les algorithmes récursifs, puisque l'algorithme ne fait que transcrire l'équation de récursion.

En notant $C(n)$ la complexité de fibonacci_rec(n), on a clairement l'équation suivante :

On prouve ensuite par récurrence que si $C(m) = \Omega(F(m))$ pour tout $m < n$ alors :

En utilisant deux accumulateurs, l'un pour $F(n - 1)$, l'autre pour $F(n - 2)$ on obtient :

fonction fibonacci_rec_terminale(n: entier, acc_n_1: entier, acc_n_2: entier) → entier:
     si n == 2:
          rendre acc_n_1
     sinon si n ≤ 1:
          rendre acc_n_2
     
     rendre fibonacci_rec_terminale(n-1, acc_n_1 + acc_n_2, acc_n_1)


algorithme fibonacci_rec(n: entier) → entier:
    rendre fibonacci_rec_terminale(n, 1, 1)

L'algorithme se termine puisque le paramètre d'arrêt de la récursion, n, décroît strictement à chaque appel.

Par une récurrence triviale sur n, les paramètres acc_n_1 et acc_n_2 de l'appel de fibonacci_rec_terminale(n - i, acc_n_1, acc_n_2) valent :

• acc_n_1 vaut $F(i + 2)$
• acc_n_2 vaut $F(i + 1)$

Lors du dernier appel on a fibonacci_rec_terminale(2, acc_n_1, acc_n_2) et donc acc_n_1 vaut $F(n-2 + 2) = F(n)$

La complexité $C(n)$ de l'algorithme satisfait l'équation de récurrence :

On a déjà vu cette récurrence, elle vaut : $C(n) = \mathcal{O}(n)$.

On adapte l'algorithme en récursion terminale :

algorithme fibonacci(n: entier) → entier:
    (acc_n_1 := entier) ← 1
    (acc_n_2 := entier) ← 1

    tant que n > 1:
        temp ← acc_n_1 
        acc_n_1 ← acc_n_1 + acc_n_2
        acc_n_2 ← acc_n_1
        n ← n - 1
    
    rendre acc_n_1

Sa correction est claire puisque c'est la transcription de l'algorithme récursif terminal et sa complexité est évidemment $\mathcal{O}(n)$.

Remarquer que l'on ne peut pas :

1. avancer uniquement dans une direction : il faut osciller
2. osciller en incrémentant d'un pas constant : on est de complexité au carré de $X$ (c'est facile à montrer)

L'idée est d'osciller autour de l'origine en puissances de 2 :

1. avancer de $2^0 = 1$ : position finale $+1$
2. reculer de $2^0 + 2^0$ : position finale $-1$
3. avancer de $2^0 + 2^1$ : position finale $+2$
4. reculer de $2^1 + 2^1$ : position finale $-2$
5. avancer de $2^1 + 2^2$ : position finale $+4$
6. reculer de $2^2 + 2^2$ : position finale $-4$
7. avancer de $2^2 + 2^3$ : position finale $+8$
8. reculer de $2^3 + 2^3$ : position finale $-8$
9. ...

Au pire, le robot arrivera sur la marque $X$ au bout de $2 \cdot \log_2(X)$ itérations.

Il aura effectué un déplacement d'au plus : $2 \cdot (X + X/2 + X/4 + \dots + 1)$ unités. Or $2 \cdot (X + X/2 + X/4 + \dots + 1) = 2\cdot X \cdot \sum_{i=0}^{i=\log_2(X)} 1/2^i = 2\cdot X \cdot(1- 1/2^{\log_2(X)}) = \mathcal{O}(X)$.

L'astuce de se déplacer par puissance de 2 permet de majorer la distance par $X$ car la série des $\sum 1/2^i$ qui est, on l'a vu, convergente. Il est crucial de connaître cette technique qui vous tirera de nombreux mauvais pas en algorithmie.

def successeur(N):
    i = 0

    while (i < len(N)) and (N[i] == 1):
        N[i] = 0
        i += 1

    if i < len(N):
        N[i] = 1

Le successeur d'un élément est l'élément plus 1. La somme du dernier bit de N avec 1 fait alors soit :

• 1 si le dernier bit vaut 0
• 10 si le dernier bit vaut 1

Si la somme vaut 10, cela revient à réitérer le processus sur le prochain bit.

Donc on commence par regarder le bit N[i] en commençant par le dernier. S'il vaut :

• 1 on le place à 0 et on incrémente i
• 0 on le place à 1 et on stoppe.

La complexité de l'algorithme va dépendre du nombre d'éléments dans la liste en entré. Notons $n = N.\mbox{\small longueur}$.

On remarque (facilement) que cette complexité vaut $C(n) = K \cdot \mathcal{O}(1)$ où $K$ est le nombre de fois où l'on rentre dans la boucle tant que. D'où :

• complexité (max) : parcourt toute la liste (pour une liste uniquement constituée): $\mathcal{O}(n)$
• complexité min : parcourt 1 seul élément de la liste (pour une liste se terminant par un 0): $\mathcal{O}(1)$

On suppose que chaque nombre décrit par $N$ peut apparaître de façon équiprobable. En posant $n = N.\mbox{\small longueur}$, séparons les $2^n$ nombres possibles en classes selon le nombre d'itérations dans la boucle :

• dernier élément vaut 0 : 0 itération. Vrai pour $2^n/2$ nombres. Probabilité de 1/2.
• derniers éléments valent [0, 1] : 1 itération. Vrai pour $(2^N/2)/2 = 2^N/4$ nombres. Probabilité de 1/4.
• derniers éléments valent [0, 1, 1] : 2 itérations. Vrai pour $(2^N/4)/2 = 2^N/8$ nombres. Probabilité de 1/8.
• ...
• derniers éléments valent [0] + i *[1] : i itérations. Vrai pour $(2^N/4)/2 = 2^N/2^{i+1}$ nombres. Probabilité de 1/2^{i+1}.
• le premier élément vaut 0 et tous les autres valent 1 : $N-1$ itérations Vrai pour 1 nombre. Probabilité de 1/2^{N}.

Le nombre moyen d'itérations dans la boucle vaut alors :

On a vu que $\sum_{i=0}^{+\infty} i \cdot \frac{1}{2^{i}} = 2$, donc $\sum_{i=0}^{N-1} i \cdot \frac{1}{2^{i+1}} \leq \frac{1}{2}\sum_{i=0}^{N-1} i \cdot \frac{1}{2^{i}} \leq \frac{1}{2}\sum_{i=0}^{+\infty} i \cdot \frac{1}{2^{i}} \leq 1$. Ceci montre que $W_\text{moy}(N) \leq \mathcal{O}(1)$.

def successeur(N):
    K = 0
    i = 0

    while i < len(N) and (N[i] == 1):
        K += 1

        N[i] = 0
        i += 1

    if i < len(N):
        N[i] = 1

    return K


def tous(n):

    N = [0] * n
    total = 0
    for i in range(2**n):
        K = successeur(N)
        total += K
        print(N, K)

    return total / 2 ** n


x = tous(5)
print(x)

def tous_rec(N, i):
    if i == -1:
        print(N)
    else:
        for x in range(2):
            N[i] = x
            tous_rec(N, i -  1)

def tous(n):
    N = n * [0]
    tous_rec(N, n-1)

tous(5)

Chaque récursion modifie le tableau à une position inférieure, cet élément valant d'abord 0, puis 1 lorsque l'on reviendra à cette fonction après la récursion.

La complexité en mémoire est de $n$, car chaque aucune récursion ne crée de nouveau tableau ! C'est le même tableau qui est modifié à chaque récursion.

Clairement, l'algorithme suivant fonctionne :

fonction tous_rec(N: [caractère], i: entier) → vide:

    si i == -1:
        affiche à l'écran N
    sinon:
        pour chaque x de ["⚀", "⚁", "⚂", "⚃", "⚄", "⚅"]:
        N[i] ← x
        tous_rec(N, i-1)

algorithme tous(n) → vide:
    N ← nouveau tableau de caractères de taille n

    tous_rec(N, n-1)

Ou en python :

def tous_rec(N, i):
    if i == -1:
        print(N)
    else:
        for x in ["⚀", "⚁", "⚂", "⚃", "⚄", "⚅"]:
            N[i] = x
            tous_rec(N, i -  1)

def tous(n):
    N = n * [0]
    tous_rec(N, n-1)

tous(5)

On peut utiliser l'algorithme suivant, qui modifie le tableau passé en paramètre :

algorithme tri_paquet(E: [entier], f:(entier) → entier) → ∅:
    (m := entier) ← max(f(x) | x de E)
    (T = [entier]) ← [entier]{longueur: m + 1}
    T[:] ← ∅  # ou m + 1 si on a pas accès à ∅ pour un tableau d'entiers

    pour chaque (x:= entier) de E:
        T[f(x)] ← x
    
    (i := entier) ← 0
    pour chaque (x:= entier) de T:
        si x ≠ ∅:
            E[i] ← x
            i ← i + 1

Cet algorithme marche car $f$ est une injection, tout éléments de $E$ sera dans T à un indice différent des autres.

La complexité est en $\mathcal{O}(m)$ en temps et en mémoire.

Si l'on veut trier $n$ entiers deux à deux différents, on utilise la fonction identité et la complexité est en $\mathcal{O}(\max(E))$.

Cet algorithme est utile si on doit trier des objets via une fonction $f: \mathcal{E} \to [0, m[$ où $m$ borné pas trop grand. C'est souvent le cas lorsque l'on utilise des données complexes, pensez à un tableau excel où nos données sont les lignes et l'index le numéro de la ligne (ou une colonne spécifique dont la valeur va de 1 au nombre de lignes).

Si l'on veut trier des entiers pouvant être égaux, on peut utiliser l'algorithme suivant qui compte dans $T[i]$ le nombre de fois où $i$ est présent dans $E$.

algorithme tri_paquet(E: [entier]) → ∅:
    m ← max(x | x de E)
    T ← un nouveau tableau d'entier de taille m + 1
    T[:] ← 0  # ou m + 1 si on a pas accès à ∅ pour un tableau d'entiers

    pour chaque x de E:
        T[x] ← T[x] + 1
    
    i ← 0
    pour x allant de 0 à m:
        tant que T[x] > 0:
            E[i] = x
            i ← i + 1
            T[x] ← T[x] - 1

Il n'y aucune relation entre $n$ et $\max(E)$. On peut par exemple tenter de trier le tableau $[1, 2^{10000000}]$, la complexité de notre algorithme sera de $2^{10000000}$ et non pas de 2.

Ce n'est donc pas un algorithme linéaire... Mais il est très efficace si les nombres ne sont pas trop grand devant $n$. Ce qui est souvent le cas en pratique.

L'algorithme suivant mime exactement le procédé décrit dans le sujet. Nos données étant des tableaux de bits, l'entrée de l'algorithme est un tableau de tableaux de bit. Cela s'écrit : [[bit]] :

algorithme tri_base(T: [entier],
                    N: entier     # T[i] < 2^N pour tout i
                   ) → ∅
    (T0 := [entier]) ← [entier]{longueur: T.longueur}
    (i0 := entier) ← 0

    (T1 := [entier]) ← [entier]{longueur: T.longueur}
    (i1 := entier) ← 0

    pour (i:= entier) de [0 .. N[:
        pour chaque x de T:
            si x // 2^i est pair:  # (x // 2^i) mod 2 == 0
                T0[i0] ← x
                i0 ← i0 + 1
            sinon:
                T1[i1] ← x
                i1 ← i1 + 1
        pour j allant 0 à i0-1:
            T[j] ← T0[j]
        pour j allant 0 à i1-1:
            T[i0 + j] ← T1[j]

On prouve cet algorithme par invariant de boucle.

Invariant de boucle : À la fin de la ième itération, $T$ est trié si on considère les éléments de $T$ modulo $2^i$

1. initialisation : à la fin de la première boucle il est clair que les élément $x$ de tels que $a(x)_0 = 0$ sont placés avant les éléments tels que $a(x)_0 = 1$.
2. récursion : si l'invariant de boucle est vrai à la fin de la i-1 ème itération, les éléments de $T0$ et de $T1$ seront triés si on considère uniquement les éléments modulo $2^i$. Comme $a(x)_i = 0$ pour tous les éléments $x$ de $T0$ et $a(x)_i = 1$ pour tous les éléments $x$ de $T1$ : les éléments de $T0$ sont inférieur aux éléments de T1 si on les considèrent modulo $2^i$.
3. à la fin des T.longueur itérations, l'invariant de boucle montre que les éléments de $T$ sont bien triés.

En notant $n$ la taille du tableau en entrée et $2^N$ une borne maximum des entiers à trier, on a clairement une complexité de $\mathcal{O}(nN)$.

Si la taille des entiers est fixée, ce qui est le cas au niveau du processeur où tous les entiers sont codés sur 64bits, ce tri est le plus efficace possible : il est linéaire.

algorithme sous_sequence(S1: chaîne, S2: chaîne) → booléen:
    (i1 := entier) ← 0
    (i2 := entier) ← 0
    tant que i1 < S1.longueur et i2 < S2.longueur:
        si S2[i2] == S1[i1]:
            i2 ← i2 + 1
        i1 ← i1 + 1

    rendre i2 == S2.longueur

Comme i1 augmente à chaque itération, la boucle va forcément s'arrêter ce qui finira l'algorithme.

Enfin l'algorithme fonctionne car i2 est incrémenté à la première occurrence possible.

Sa complexité est en $\mathcal{O}(\max(n_1, n_2))$. Cet algorithme est linéaire il est optimal.

L'algorithme suivant regrade toutes les possibilités pour $S_2$ d'être un sous-mot de $S_1$. Il s'arrête à la première possibilité. Dans le pire des cas, il va effectuer $\mathcal{O}(n_1 \cdot n_2)$ opérations.

algorithme sous_mot(S1: chaîne, S2: chaîne) → booléen:
    
    pour chaque i1 de [0 .. S1.longueur[:
        (i2 := entier) ← 0
        (stop := booléen) ← Faux
        tant que (stop == Faux) et (i2 < S2.longueur):
            si S2[i2] == S1[i1 + i2]:
                i2 ← i2 + 1
            sinon:
                stop ← Vrai
        
        si i2 == S2.longueur:
            rendre Vrai

    rendre Faux

Si tous les caractères de $S_2$ sont différents, il n'est pas nécessaire de tout recommencer. On peut utiliser l'optimisation suivante, qui donne la complexité voulue :

algorithme sous_mot(S1: chaîne, S2: chaîne) → booléen:
    (i1, i2 := entier) ← 0, 0
    stop := booléen

    tant que i1 < S1.longueur:
        i2 ← 0        
        stop ← Faux
        tant que (stop == Faux) et (i2 < S2.longueur):
            si S2[i2] == S1[i1 + i2]:
                i2 ← i2 + 1
            sinon:
                stop ← Vrai
        
        si i2 == S2.longueur:
            rendre Vrai
        i1 ← i1 + i2

    rendre Faux

La solution est optimale puisqu'elle est en $\mathcal{O}(n)$

algorithme permutation(S: [caractère], k: entier) → [caractère]:
    S2 ← un tableau de n caractères

    pour chaque i de [0 .. k [:
        S2[i] ← S[S.longueur-k + i]
    pour chaque i de [k .. S.longueur[:
        S2[i] ← S[i-k]
    
    rendre S2

L'algorithme ci-dessus rend un tableau, il est donc facile de faire le décalage.

Si on droit qu'à un nombre constant de variables ceci n'est plus possible. Il faut ruser en utilisant des retournements

algorithme retournement(S: [caractère]) → ∅:
    pour chaque i de [0 .. S.longueur // 2[:
    S[i], S[S.longueur - 1 - i] ← S[S.longueur - 1 - i], S[i]

Comme $(A^R)^R = A$ et $(AB)^R = B^RA^R$, on a :

L'algorithme de permutation est alors tout simple :

algorithme permutation(S: [caractère], k: entier) → ∅:
    retournement(S[:-k])
    retournement(S[k:])
    retournement(S)

Et sa complexité est bien $\mathcal{O}(n-k) + \mathcal{O}(k) + \mathcal{O}(n) = \mathcal{O}(n)$.

algorithme pgcd_mod(a: entier, b: entier) → entier:  # a, b ≥ 0
    si b == 0:
        rendre a
    si a < b:
        a, b ← b, a
    
    rendre pgcd_mod(b, a mod b)

Comme $a \bmod b < b$, si $b \leq \frac{a}{2}$ la propriété est démontrée et si $b > \frac{a}{2}$ on a $a // b = 1$ et donc $a \bmod b = a - b < \frac{a}{2}$

Le nombre de récursions ne peut excéder le nombre de fois où l'on peut diviser $a$ ou $b$ par 2 : il est inférieur à $\log_2(a)$.

Si le calcul du modulo s'effectue en $\mathcal{O}(1)$ opérations, la complexité totale de l'algorithme est en $\mathcal{O}(\ln(\max(a, b)))$, ce qui est très bon !

Par définition, on a $F(n+1) = F(n) + F(n-1)$ et comme $F(n) > F(n-1)$, cette équation est aussi la division euclidienne de $F(n)$ par $F(n-1)$ puisqu'elle est unique.

La propriété précédente nous montre que pgcd_mod(F(n+1), F(n)) va appeler pgcd_mod(F(n), F(n+1) % F(n)) = pgcd_mod(F(n), F(n-1)). Il va donc y avoir $n$ récursion jusqu'à arriver à l'appel de pgcd_mod(F(1), 0) qui va conclure la récursion.

Montrer que ces nombres sont minimaux se fait simplement par récurrence sur le nombre de récursions.

• initialisation. Pour qu'il y ait qu moins 1 récursion, il faut que $a \geq b \geq 1 = F(2) = F(1) > 0$.
• récursion. On suppose que pour faire au moins $k$ itérations il faut que $a \geq F(k+1)$ et $b \geq F(k)$. Soit $a \geq b$ deux entiers tels que pgcd_mod(a, b) effectue $k+1$ itérations. Ceci implique que pgcd_mod(b, a % b) effectue $k$ itérations, par hypothèse de récursion on a alors que $b \geq F(k+1)$ et $a {\small \%} b \geq F(k)$ et donc $a \geq F(k+1) + F(k) = F(k+2)$.

Cette propriété permet que l'on peut borner le nombre de récursions par $b$ ! Pour qu'il y ait au moins $n$ récursion, il faut que $a \geq b \geq F(n)$.

Comme $F(n) = \mathcal{O}(2^n)$ on en déduit que le nombre de récursions et donc la complexité de pgcd_mod(a, b) est en $\mathcal{O}(\ln(\min(a, b)))$. Ce qui est à comparer à l'algorithme avec des soustractions dont la complexité était $\mathcal{O}(\min(a, b))$.

Les propriétés utilisées conservent clairement le pgcd et, comme pour l'algorithme du pgcd initial, à chaque récursion le max de $a$ et $b$ sera strictement plus petit : on arrivera forcément à la condition d'arrêt ce qui en fait bien un algorithme.

Le calcul de sa complexité se fait comme pour l'exponentiation indienne et permet de prouver qu'elle est en $\mathcal{O}(\max(a, b))$. L'intérêt de cette version est qu'elle se fait tres simplement en machine où les entiers sont codés par des tableaux de bits et où la multiplication et la division d'un nombre par 2 revient à décaler sa représentation binaire d'un bit vers la droite ou la gauche respectivement.

Il n'y a pas à calculer le modulo, opération plus complexe.