Algorithmique ii - Preuve et complexité

Preuve des algorithmes

La correspondance de Cur­ry­-­Ho­ward valide for­mel­le­ment cette simple ana­lo­gie.

Par analogie avec les mathématiques, si on as­si­mil­e res­pec­ti­ve­ment l'entrée et la sortie d'un al­go­ri­thme à l'hy­po­thè­se et la conclusion d'un théorème, il est nécessaire d'en fournir une preuve afin de s'assurer formellement que l'algorithme effectue le travail pour lequel il a été conçu. Une preuve d'un algorithme se décompose en deux parties :

  1. D'après notre définition formelle, un algorithme, ne peut être qualifié comme tel que s'il s'arrête. Comme le respect de la syntaxe ne suffit pas à le garantir, il faut s'en s'assurer, c'est le rôle de la preuve d'arrêt (ou preuve de terminaison) ;
    Le mot correction doit être entendu ici au sens de justesse et non de rec­ti­fi­ca­tion.
  2. Il faut également s'assurer qu'il renvoie effectivement le résultat attendu en fonction des données qu'il a à traiter, on parle alors de preuve de validité (ou preuve de correction).

Nous verrons en troisième année une méthodologie plus formelle pour réaliser la preuve d'un al­go­ri­thme grâce à la logique de HoareHoare est le concepteur de l'al­go­ri­thme du tri ra­pi­de et nous procéderons de manière re­la­ti­ve­ment souple cette année en nous contentant de fournir les arguments clés de ces preuves.

La question de la terminaison d'un algorithme ne se pose que dans la mesure où l'algorithme con­tient une ou plusieurs boucles. Pour prouver qu'un algorithme s'arrête, il faut démontrer pour cha­cune d'entre elles que la condition d'entrée sera invalidée dans un temps fini, autrement dit après un nombre fini de passages dans cette boucle. Pour cela, il faut mettre en évidence une suite con­ver­gen­te (généralement monotone croissante ou décroissante) de quantités qui sont fonctions des variables impliquées dans les instructions qui constituent le corps de la boucle et dont les valeurs successives à chaque nouveau passage constituent précisément les termes de cette suite. La condition de sortie de la boucle est liée à une valeur que la suite doit atteindre. C'est ce qui explique que pour une simple boucle \(i\) allant de \(1\) à \(n\), on préfère écrire une condition sous la forme \(i < n\) plus robuste que \(i\not = n\) dans une boucle tant que, en effet une incrémentation (par erreur) de 2 au lieu de 1 de la variable \(i\) engendrera une boucle infinie dans le premier cas alors que le programme s'arrêtera malgré tout dans le second.

Pour prouver la validité d'un algorithme, il faut cette fois mettre en évidence un invariant de boucle, c'est-à-dire une proposition toujours vraie à chaque fois que l'on entre dans la boucle. Cette proposition doit être choisie en rapport avec le résultat attendu, de manière à ce qu'une fois sa­tis­fai­te elle assure que le résultat est bien celui attendu à la sortie de la boucle. Le travail à fournir ici consiste à s'assurer que les différentes instructions de la boucle ne changent pas la valeur de vérité de la proposition, justifiant ainsi son qualificatif d'invariant.

À titre d'exemple, montrons que l'algorithme ci-dessous renvoie bien la somme des valeurs contenues dans la liste d'entrée \(L\). La liste est supposée ne contenir que des valeurs sommables et \(0\) joue le rôle de l'élément neutre pour l'ensemble sous-jacent qui n'est pas spécifié dans l'algorithme.

Somme(L)
données
   L: liste de valeurs
variables
   i: entier
   S: valeur
debut
   S ← 0
   i ← 1
   TQ (i ≤ #L) FAIRE
      S ← S + L[i]
      i ← i + 1
   FTQ
   RETOURNER S
FIN

Notons \(n:=\#L\) la taille de la liste \(L\). La preuve d'arrêt est simple, on considère la suite constituée par les valeurs successives de la variable \(i\). Avant d'entrer dans la boucle, la variable \(i\) est initialisée à 1 et n'est modifiée qu'à l'instruction #12 qui l'incrémente, il s'agit donc de la suite strictement croissante des entiers na­tu­rels non-nuls. La con­di­tion d'arrêt de la boucle \(i > n\) (qui est la négation de la condition d'entrée dans la boucle \(i\leq \#L\)) sera donc satisfaite pour la valeur \(i=n+1\).

Passons à présent à la validité de l'algorithme en montrant que la proposition \begin{equation}\label{eq:invar} S=\sum_{k=1}^{i-1}L[k] \end{equation} est un invariant de la boucle tant que de cet algorithme. La proposition est vraie avant d'entrer dans la boucle puisque \(i=1\) et que la somme vide est égale à 0 par convention et que l'on a pris soin d'ini­tia­li­ser la variable \(S\) à 0 avant d'entrer dans la boucle. Après l'exécution de l'instruction #11, on a \begin{align} S&=\sum_{k=1}^{i-1}L[k]+L[i]\\ &=\sum_{k=1}^{i}L[k] \end{align} et après l'incrémentation de la variable \(i\) (instruction #12) c'est à nouveau la proposition \((\ref{eq:invar})\) qui est satisfaite. Nous savons que \(i=n+1\) à la sortie de la boucle d'après la preuve d'arrêt. On conclut donc d'après \((\ref{eq:invar})\) que \begin{align} S&=\sum_{k=1}^{n+1-1}L[k]\\ &=\sum_{k=1}^{n}L[k] \end{align} Ce qui achève de prouver que l'algorithme renvoie bien la somme de tous les termes de la liste \(L\).

Complexité

Généralités

Le mot al­go­ri­thme fait à présent référence à un programme écrit dans un modèle abstrait, ici le mo­dè­le de la machine RAM. Notons qu'il ne s'agit pas de la définition du mot al­go­ri­thme, il existe bien d'autres modèles et donc autant de définitions. Cependant il a été démontré que les différents modèles proposés ont les mêmes capacités calculatoires, ainsi un problème que l'on peut résoudre avec un modèle \(A\) peut être résolu avec un modèle \(B\) et réciproquement. Les questions relatives au choix d'un modèle de calcul seront abordées dans le cadre du cours de complexité al­go­ri­thmique du master.

On peut à présent définir précisément la notion de complexité d'un al­go­ri­thme. On cherche à quan­ti­fier deux ressources indispensables au fonctionnement d'un al­go­ri­thme, le temps et l'espace. L'un des atouts du modèle RAM est que son jeu d'instruction est très proche de celui que l'on trouve dans de véritables pro­ces­seurs. Ainsi, la con­nais­san­ce du nombre d'opérations décodées par la machine ram pour traiter une donnée permet d'évaluer le temps de calcul qui sera réellement nécessaire dès lors que l'on est en mesure de traduire chaque instruction abstraite en ins­truc­tions d'un processeur dont on connaît les temps d'exécution. De la même manière, l'estimation du nombre de registres mémoire utilisés durant l'exécution d'un al­go­ri­thme sur la machine ram nous donne une indication précieuse sur la quantité de mémoire dont il faudra disposer dans une véritable machine. Dans ce cours, nous nous intéresserons donc à ce que l'on appelle la com­ple­xi­té en temps et la com­ple­xi­té en espace.

On note \(e:=e_0,e_1,\ldots,e_{n-1}\) la séquence des entiers en entrée d'un programme et \(s:=s_0,s_1,\ldots,s_{m-1}\) la séquence en sortie. La séquence \(e\) est qualifiée d'ins­tan­ce du programme et on note \(|e|\) ou \(\#e\) sa taille, qui n'est ni plus ni moins que la longueur de la séquence \(e\) (on utilise des notations similaires pour les sorties mais on ne parle pas d'instance).

Nous avons vu au chapitre précédent que \(\eta(e)\) désignait le nombre d'instructions décodées par la machine ram pour traiter l'instance \(e\) mais on souhaite cette fois définir le nombre d'instructions décodées uniquement en fonction de la taille \(n\) de l'instance et pas de l'instance elle même. Mais l'uti­li­sa­tion du singulier défini le n'est pas possible à ce stade. En effet, pour un programme donné, le traitement de deux instances \(e\) et \(e'\) de même taille \(n\) ne nécessite pas nécessairement le même nombre d'opé­ra­tions. Sans même décrire précisément comment nous trions un jeu de carte, il semble que le nombre de manipulations à réaliser pour trier un jeu de 52 cartes est différent selon que ces cartes sont déjà triées (Une simple comparaison des cartes deux-à-deux suf­fit à s'assurer qu'il n'y a rien à faire) ou alors bien mélangées. Le nombre d'opérations dépend donc de l'instance à traiter et pas uniquement de sa taille. En se limitant aux instances les moins coû­teu­ses et aux plus coû­teu­ses, l'unicité du minimum et du maximum permet de définir deux fonctions :

On appelle complexité dans le pire des cas (resp. dans le meilleur des cas d'un al­go­ri­thme \(A\), les fonctions définies respectivement par \begin{align} \label{pire}\hat T_A(n)&:=\max_{e,\ |e|=n}\eta(e),\\ \label{meilleur}\check T_A(n)&:=\min_{e,\ |e|=n}\eta(e),\\ \end{align}
Quand on parle du meilleur des cas ou du pire des cas, on utilise le singulier car on fait référence à l'unicité du min et du max, en revanche il peut exister plusieurs instances \(e\) telles que \(\eta(e)\) atteint ce min ou ce max (si la meilleure note à l'examen d'al­go­ri­thmi­que est 17, rien n'interdit que plusieurs étudiants aient atteint cette note).

Le nombre d'instructions \(\eta(e)\) décodées par la machine ram pour traiter l'ins­tan­ce \(e\) n'est pas la taille du programme. Une même instruction du programme placée dans une boucle peut en effet être exécutée plusieurs fois. Pour que ce nombre \(\eta(e)\) soit bien défini, cela suppose que l'instruction ARRET a été exécutée, nous faisons donc l'hypothèse que le pro­gram­me s'arrête pour pouvoir définir sa fonction de complexité. La convergence de l'al­go­ri­thme est donc un prérequis fondamental même si cette précision est redondante puisque par définition un al­go­ri­thme doit s'arrêter.

Dans certains cas ces deux fonctions sont confondues. Considérons par exemple l'al­go­ri­thme qui cal­cu­le la som­me de \(n\) entiers à l'aide d'une simple boucle mettant à jour le cumul des valeurs. Si l'on suppose que la taille de chaque entier se limite à un registre machine, le nombre d'opérations ne dépend que de l'entier \(n\) et non pas des \(n\) valeurs sur la bande d'entrée. Dans ce cas on note sim­ple­ment \(T(n)\) la fonction de complexité. Certains auteurs parlent de la complexité \(T(n)\) d'un al­go­ri­thme quand bien même il y a lieu de distinguer différentes situations pour une même taille \(n\) de données à traiter. C'est alors au pire des cas qu'il est fait référence.

Cas de la complexité moyenne

Connaître le meilleur des cas et le pire des cas n'est pas suffisant pour mesurer les performances d'un al­go­ri­thme. Les situations défavorables peuvent être extraordinairement rares, ou au contraire très fréquentes, et dans ce cas l'information fournie par la complexité dans le pire des cas ne permet pas de comprendre comment l'algorithme va se comporter en général. Ce comportement général est décrit par la fonction de complexité moyenne qui complète l'information fournie par les deux autres fonctions de complexité. Connaître la plus mauvaise note et la meilleure note d'une classe à un examen ne dit pas tout, ni même la moyenne des notes d'ailleurs. Le calcul de l'écart type, de la valeur médiane ou d'une distribution en déciles permettent, entre autres, de préciser la situation.

Le fameux tri rapide, ou quicksort, qui sera étudié en détail en troisième année, a une fonction de complexité dans le meilleur des cas qui est quasi-linéaire (soit \(O(n\log n)\)) et une fonction de comp­le­xi­té dans le pire des cas qui est quadratique (soit \(O(n^2)\)).Nous reviendrons sur les no­ta­tions a­sym­pto­ti­ques étu­diées en ma­thé­ma­ti­ques en pre­miè­re an­née com­me \(O\) dans un cha­pi­tre dé­dié. Dans le meilleur des cas, il fait moins bien que le simplissime tri à bulles qui est linéaire (soit \(O(n)\)), et dans le pire des cas il fait moins bien que le tri par tas qui est quasi-linéaire (et linéaire dans le meilleur des cas) ! Cette seule in­for­ma­tion suffirait à le disqualifier si sa fonction de complexité dans le cas moyen n'était pas quasi-linéaire avec une constante cachée plus petite que celle des autres al­go­ri­thmes de tri.

La complexité moyenne est par conséquent un élément fondamental d'évaluation et conditionne l'uti­li­sa­tion effective d'un al­go­ri­thme, elle est malheureusement souvent délicate à obtenir, même pour des al­go­ri­thmes simples en apparence. C'est une question cruciale qui fait l'objet de travaux de re­cher­ches, il n'est donc pas rare de trouver des études empiriques (ce que les anglos-saxons qualifient de benchmarks) pour estimer le temps d'exé­cu­tion de certains al­go­ri­thmes quand on n'est pas en me­su­re d'obtenir des résultats formels.

Dans le cas d'une ma­chi­ne ram binaire, l'univers \(\Omega\) est l'en­sem­ble \(\{0,1\}^n\) et un évè­ne­ment élé­men­tai­re est un mot de lon­gueur \(n\). Un évè­ne­ment pour­rait-être l'en­sem­ble des mots qui com­men­cent par \(1\).

L'étude de la complexité moyenne s'appuie sur les probabilités. On interprète le fonctionnement d'un algorithme comme une expérience aléatoire dont l'univers \(\Omega\) des évènements élémentaires est l'en­semble des instances de taille \(n\) de l'al­go­ri­thme, l'expérience consistant à tirer au hasard une ins­tance \(e\) qui sera ensuite traitée par l'algorithme pour un coût \(\eta(e)\). On rappelle qu'une partie quel­con­que de \(\Omega\) est qualifiée d'évè­ne­ment.

La loi de probabilité sur \(\Omega\) décrit le comportement des évènements, c'est une fonction \[P:\mathscr{P}(\Omega)\rightarrow[0,1]\] qui mesure la probabilité qu'un évènement ait lieu, une probabilité égale à \(0\) signifiant que l'évè­ne­ment n'arrive jamais et une probabilité égale à \(1\) signifiant que l'évènement est certain. Cette fonc­tion vérifie les trois propriétés suivantes : \begin{align} &\forall A\in\mathscr{P}(\Omega),\quad P(A)\geq 0\\ & P(\Omega)=1\\ &\forall A,B\in\mathscr{P}(\Omega),\quad A\cap B=\varnothing\Rightarrow P(A\cup B)=P(A)+P(B) \label{sum} \end{align} Quand l'espace \(\Omega\) est au plus dénombrable, on dit que la probabilité est discrète. C'est le cas dans notre contexte puisque les instances de taille \(n\) sont en nombre fini, \(\Omega:=\{e\ |\ \#e=n\}\). Par con­sé­quent l'assertion \((\ref{sum})\) impose : \begin{equation}\label{eq:toutsum} \sum_{\omega\in\Omega}P(\omega)=1. \end{equation}

On peut à présent définir la complexité moyenne.

On appelle complexité moyenne d'un al­go­ri­thme \(A\), la fonction définie par \begin{equation}\label{moyen} \overline{T}_A(n):=\sum_{e, |e|=n}P(e)\eta(e) \end{equation}
Dans le langage des probabilités, la fonction \(\eta:\Omega\rightarrow{\mathbf R}^+\) qui mesure le nombre d'instructions nécessaire à traiter une instance (un évènement élémentaire dans cette vision probabiliste) de l'al­go­ri­thme est une variable aléatoire discrète et la fonction de complexité moyenne est l'espérance de cette variable aléatoire.

La loi de probabilité discrète \(P\) sera supposée uniforme dans tous les algorithmes que nous traiterons pour ne pas compliquer inutilement l'étude. L'hypothèse est largement justifiée par la nature des algorithmes qui seront traités. La loi uniforme est la plus simple, elle suppose que tous les évè­ne­ments élémentaires (les instances de l'algorithme) sont équiprobables, autrement dit :

\begin{equation} \forall\omega\in\Omega,\quad P(\{\omega\}) = \frac{1}{|\Omega|}. \end{equation}

Dans ce cas et en pratique, on regroupe les instances/évènements qui ont le même coût. Autrement dit, on partitionne l'ensemble \(\Omega\) des instances de taille \(n\) en un certain nombre de classes \(\Omega_i\), \(i\in I\), telles que toutes les instances d'une même classe \(\Omega_i\) ont le même coût \(c_i\), i.e. \begin{equation} \forall\omega\in\Omega_i,\quad \eta(\omega) = c_i. \end{equation} Ainsi, l'expression (\ref{moyen}) devient : \begin{equation}\label{moyenbis} \bar T(n)=\frac{1}{|\Omega|}\sum_{i\in I}c_i|\Omega_i|. \end{equation}

Toute la difficulté du calcul de la complexité en moyenne consiste donc à trouver un critère sur l'en­trée \(e\) qui permet d'obtenir la partition la plus simple possible.

Démontrez l'égalité \((\ref{eq:toutsum})\). Indication : montrez que l'ensemble des singletons de \(\Omega\) forme une partition de \(\Omega\).

Exemples

Moyenne arithmétique

Reprenons le premier exemple fourni dans le chapitre de présentation de la machine RAM et qui calcule la moyenne arithmétique des valeurs en entrée. Par convention la valeur nulle sert de marqueur pour la fin des données à lire sur la bande d'entrée. Le registre \(R_1\) contient le nombre de valeurs lues, le registre \(R_2\) la somme des valeurs lues.

LOAD #0     ; ACC ← 0
STORE 1     ; R[1] ← ACC
STORE 2     ; R[2] ← ACC
READ        ; ACC ← ENTREE[i++]
JUMZ 8      ; SI ACC = 0 SAUTER A L'INSTRUCTION #8
ADD 2       ; ACC ← ACC + R[2]
STORE 2     ; R[2] ← R[2]
INC 1       ; R[1] ← R[1] + 1
JUMP 3      ; SAUTER A L'INSTRUCTION #3
LOAD 2      ; ACC ← R[2]
DIV 1       ; ACC ← ACC / R[1]
WRITE       ; SORTIE[j++] ← ACC
STOP        ; ARRET

En toute rigueur, on devrait désigner par \(n\) le nombre total de valeurs saisies, y compris la valeur négative indiquant la fin de la lecture des données. On note plutôt \(n+1\) la taille de l'entrée pour que la fonction de complexité exprime le nombre d'opérations en fonction des données utilisées pour le calcul de la moyenne. Cette dérogation n'a évidemment aucune incidence asymptotiquement.

Les trois premières instructions sont toujours exécutées une première fois. Les instructions #5 à #8 sont exécutées autant de fois que la valeur lue n'est pas nulle, soit \(n\) fois mais l'instruction #3 de lecture et le test #4 sont exécutés une fois de plus pour lire la valeur nulle et dérouter le programme. Les \(4\) dernières instructions sont exécutées une seule fois. La complexité de cet al­go­ri­thme ne dépend pas de la nature de l'instance traitée, seulement de sa taille \(n\). Au final nous avons \begin{align*} T(n)&=3 + 4n + 2(n+1) + 4\\ &=6n + 9 \end{align*} La complexité est donc asymptotiquement proportionnelle au nombre de valeurs à traiter.

Poids binaire

Le programme suivant lit les valeurs binaires sur la bande d'entrée (la lecture s'arrête quand une valeur négative est rencontrée) et calcule le poids binaire de la séquence, c'est-à-dire le nombre de bits non-nuls. Par exemple, si la séquence \(1,0,0,0,1,1,0,1,-1\) est saisie sur la bande d'entrée, la bande de sortie contiendra la valeur \(4\). Le registre \(R_1\) est initialisé à 0 par les instructions #0 et #1 et est incrémenté d'une unité à chaque fois qu'une valeur non-nulle est lue (hormis la valeur négative servant de balise de fin de lecture) :

LOAD #0     ; ACC ← 0
STORE 1     ; R[1] ← ACC
READ        ; ACC ← ENTREE[i++]
JUML 7      ; SI ACC < 0 SAUTER A L'INSTRUCTION #7
JUMZ 2      ; SI ACC = 0 SAUTER A L'INSTRUCTION #2
INC 1       ; R[1] ← R[1] + 1
JUMP 2      ; SAUTER A L'INSTRUCTION #2
LOAD 1      ; ACC ← R[1]
WRITE       ; SORTIE[j++] ← ACC
STOP        ; ARRET
On note \(n+1\) le nombre de valeurs de la bande d'entrée, les \(n\) premières représentant une séquence binaire. Les instructions #0 et #1 d'initialisation du registre \(R_1\) sont exécutées une seule fois tout comme les instructions #7, #8 et #9 pour l'écriture du résultat et l'arrêt. On note \(p\) le poids binaire de l'entrée \(e\) traitée par l'algorithme. La lecture des valeurs (instruction #2) ainsi que le test #3 de la valeur lue sont exécutés \(n+1\) fois. Le test #4 qui vérifie si le bit est nul est exécuté \(n\) fois. Si \(p\) désigne le poids binaire de la séquence des \(n\) bits, l'instruction #5 d'incrémentation ainsi que le saut #6 ne sont exécutés que \(p\) fois. La table ci-dessous résume pour chaque instruction le nombre de fois où celle-ci est décodée par la machine.

IndexInstruction#Décodages
0LOAD #0 \(1\)
1STORE 1 \(1\)
2READ \(n+1\)
3JUML 7 \(n+1\)
4JUMZ 2 \(n\)
5INC 1 \(p\)
6JUMP 2 \(p\)
7LOAD 1 \(1\)
8WRITE \(1\)
9STOP \(1\)

Il suffit d'additionner toutes ces valeurs pour obtenir le nombre d'opérations décodées pour traiter une entrée \(e\) de poids binaire \(p\) : \begin{align} \eta(e)&=2 + 2(n+1) + n + 2p + 3\\ &=\color{yellow}{3n + 2p + 7}\label{eq:tbn} \end{align} Dans le meilleur des cas le poids binaire est nul, i.e. \(p=0\), on a donc \[\check T(n)=3n+7.\] Dans le pire des cas, les \(n\) bits sont égaux à 1, i.e. \(p=n\), et on a \[\hat T(n)=5n+7.\]

Pour le cas moyen, il faut calculer le nombre total d'instructions décodées par la machine pour l'intégralité des instances de taille \(n\) et diviser ce nombre par \(2^{n}\) qui représente le nombre d'instances possibles (par commodité, on écarte la \((n+1)\)-ème valeur négative qui marque la fin de la lecture).

Comme suggéré dans la section 2, on cherche à partitionner l'ensemble \(\Omega\) des \(2^{n}\) instances possibles en classes \(\Omega_i\) de même coût pour pouvoir calculer la complexité moyenne à l'aide de l'expression \((\ref{moyenbis})\). D'après l'expression (\ref{eq:tbn}), c'est le poids binaire \(p\) qui conditionne le nombre d'instructions décodées pour des instances de taille \(n\). Conséquemment, le partionnement est constitué des classes con­te­nant tous les mots de longueur \(n\) et de poids binaire \(p\), soit : \[\Omega_p:=\left\{u\in\{0,1\}^{n}\ |\ \#\{i\ |\ u_i=1\}=p\right\}.\] Le cardinal de \(\Omega_p\) est égal au nombre de parties à \(p\) éléments dans un ensemble à \(n\) éléments, en effet il faut fixer \(p\) valeurs à 1 sur les \(n\) possibles, soit (voir mémento ma­thé­ma­ti­que) : \[\#\Omega_p=\binom{n}{p}.\] On a donc pour complexité moyenne la fonction \begin{align*} \bar T(n)\label{eq:reprise} &=\frac{1}{2^{n}}\sum_{p=0}^{n}({\color{yellow}{3n+2p+7}})\binom{n}{p}\\ &=\frac{1}{2^{n}}\Big[(3n+7)\color{lightblue}\sum_{p=0}^{n}\binom{n}{p}+2\color{lightgreen}\sum_{p=0}^{n}p\binom{n}{p}\Big] \end{align*} Ces deux sommes avec coefficients binomiaux sont fournies dans le mémento ma­thé­ma­ti­que section 3  et valent respectivement \(\color{lightblue}2^{n}\) et \(\color{lightgreen}n2^{n-1}\). Finalement \begin{equation} \label{eq:cmo} \bar T(n)=4n+7. \end{equation}

Un peu de réflexion pouvait nous éviter de dérouler mécaniquement le calcul de la moyenne. Reprenons l'analyse différemment. On note \(p_0,p_1,\ldots,p_{2^n-1}\) les poids des \(2^n\) mots binaires de longueur \(n\). En sommant l'expression \((\ref{eq:tbn})\) sur toutes les séquences et en divisant par \(2^n\), on obtient : \begin{align*} \bar T(n) &=\frac{1}{2^{n}}\sum_{i=0}^{2^n-1}(3n+2p_i+7)\\ &=(3n+7)+\frac{1}{2^{n-1}}{\color{orange}\sum_{i=0}^{2^n-1}p_i}. \end{align*} Il reste à calculer la somme des poids de tous les mots binaires de longueur \(n\). Rangeons ces mots dans une matrice \(B_n\) et dans l'ordre naturel (on décompose les entiers de l'intervalle \([0,2^n-1]\) en base \(2\)). Exemple pour \(n=3\) : \begin{equation*} B_3:=\begin{pmatrix} 0&0&0\\ 0&0&\color{orange}1\\ 0&\color{orange}1&0\\ 0&\color{orange}1&\color{orange}1\\ \color{orange}1&0&0\\ \color{orange}1&0&\color{orange}1\\ \color{orange}1&\color{orange}1&0\\ \color{orange}1&\color{orange}1&\color{orange}1 \end{pmatrix} \end{equation*}

Chacune des \(n\) colonnes de la matrice \(B_n\) contient autant de 0 que de 1 soit exactement \(2^{n-1}\) occurences de chaque. Autrement dit il y a au total exactement \(\color{orange}n2^{n-1}\) valeurs égales à 1 et on retrouve bien la valeur de la complexité moyenne de l'expression \((\ref{eq:cmo})\).

Dans ce cas particulier, la complexité moyenne est égale à la moyenne de la complexité dans le meilleur des cas et de la complexité dans le pire des cas. Ce n'est pas le cas en général !

Incrémentation

Le programme ci-dessous incrémente un entier naturel \(a\) représenté dans une base arbitraire \(b\), c'est-à-dire calcule la fonction successeur \(s:{\mathbf N}\rightarrow{\mathbf N}\) définie par \begin{equation} s(a):=a+1 \end{equation} La première cellule de la bande d'entrée doit contenir la valeur \(b\) de la base choisie, les suivantes les \(n\) chiffres \(a_i\) de \(a\) dans cette base en supposant que \begin{equation}\label{eq:dec} a=a_0+a_1b+a_2b^2+\cdots+a_{n-1}b^{n-1}. \end{equation} autrement dit les chiffres sont rangés du moins significatif au plus significatif contrairement à l'usage général. Pour indiquer la fin de la lecture, la dernière case contient la valeur -1. Par exemple, si \(a={\color{#FFF}329}\) en base 10, la bande d'entrée doit contenir la séquence \[{\color{#FF0}10},\ {\color{#FFF}9,\ 2,\ 3},\ {\color{#46F}-1},\] et à la fin de l'exécution, la bande de sortie contiendra \[{\color{#FFF}0,\ 3,\ 3}.\]

Le principe de l'al­go­ri­thme est le suivant : on commence par le chiffre des unités ; s'il est égal à \(b-1\) il y a retenue on le remplace donc par \(0\) et on recommence avec le chiffre suivant, sinon on lui rajoute 1 et on a fini. Dans le programme sur la machine ram, on range la valeur \(b\) de la base dans le registre #1 (plus précisément la valeur \(b-1\) pour les calculs) et le registre #2 sert de registre d'indexation pour l'adressage indirect des registres qui vont contenir les chiffres de \(a\) (à partir du registre #3). Les instructions #0 à #4 réalisent ces initialisations.

La boucle réalisée par les instructions #5 à #9 range les chiffres \(a_i\) dans les registes \(R[3+i]\) ainsi que le drapeau \(-1\) sans cellule qui suit. Les instructions #10 à #13 rajoute un autre drapeau \(-1\) à la suite du premier, en effet si on a un dépassement due aux retenues successives (par exemple \(a=999\rightarrow 1000\) en base 10), le premier drapeau servira à ranger cette retenue (instructions #18 et #19).

Les instructions #14 à #29 balaient les chiffres en mémoire en incrémentant le premier possible à l'instruction #27 et en arrêtant l'exécution du programme, les chiffres précédants ayant été initialisés à 0 par l'instruction #23. Les instructions #30 à #36 écrivent le résultat sur la bande de sortie.

READ       ; ACC ← ENTREE[I++] // LECTURE DE LA BASE b
DEC 0      ; ACC ← ACC - 1 // CALCUL DE b - 1
STORE 1    ; R[1] ← ACC // RANGEMENT DE b - 1 
LOAD #3    ; ACC ← 3 // INDEX DEBUT RANGEMENT DES CHIFFRES
STORE 2    ; R[2] ← ACC // RANGEMENT DE INDEX INDIRECT
READ       ; ACC ← ENTREE[I++]
JUML 10    ; SI ACC < 0 SAUTER A L'INSTRUCTION #10 // FIN DE LECTURE
STORE @2   ; SINON R[R[2]] ← ACC // ON RANGE LE CHIFFRE
INC 2      ; R[2] ← R[2] + 1 // ON PASSE AU 
JUMP 5     ; SAUTER A L'INSTRUCTION #5 // CHIFFRE SUIVANT
STORE @2   ; R[R[2]] ← ACC // ON GARDE -1 COMME DRAPEAU DE FIN
INC 2      ; R[2] ← R[2] + 1 
LOAD #-1   ; ACC ← -1 // ON VA RAJOUTER -1 EN FIN DE MEMOIRE POUR
STORE @2   ; R[R[2]] ← ACC // NOUVEAU DRAPEAU EN CAS DE DEPASSEMENT
LOAD #3    ; ACC ← 3 // INDEX DEBUT RANGEMENT DES CHIFFRES 
STORE 2    ; R[2] ← ACC // RANGEMENT DE INDEX INDIRECT
LOAD @2    ; ACC ← R[R[2]] // CHARGEMENT D'UN CHIFFRE
JUMG 21    ; SI ACC > 0 SAUTER A L'INSTRUCTION #21 // RESTE CHIFFRES
LOAD #1    ; SINON ACC ← 1 // ON EST AU BOUT => DEPASSEMENT 
STORE @2   ; R[2] ← ACC // ON REMPLACE LE DRAPEAU PAR 1
JUMP 30    ; SAUTER A L'INSTRUCTION #29 // ECRITURE DU NOMBRE
SUB 1      ; ACC ← ACC - R[1] // CHIFFRE - (b - 1)
JUML 27    ; SI ACC < 0 SAUTER A L'INSTRUCTION #26 // CHIFFRE < b - 1
LOAD #0    ; SINON ACC ← 0 // CHIFFRE = b - 1 => MISE A 0
STORE @2   ; R[R[2]] ← 0 // DU CHIFFRE COURANT
INC 2      ; R[2] ← R[2] + 1 
JUMP 16    ; SAUTER A L'INSTRUCTION #16 // CHIFFRE SUIVANT
INC @2     ; R[R[2]] ← R[R[2]] + 1 // INCREMENT DU CHIFFRE ET FIN
LOAD 1     ; ACC ← R[3] // CHARGEMENT DE b-1
SUB @2     ; ACC ← ACC - R[R[2]]
LOAD #3    ; ACC ← 3 // INDEX DEBUT RANGEMENT DES CHIFFRES
STORE 2    ; R[2] ← ACC // RANGEMENT DE INDEX INDIRECT
LOAD @2    ; ACC ← R[R[2]]
JUML 37    ; SI ACC < 0 ALORS SAUTER A L'INSTRUCTION #37 // FIN
WRITE      ; // SINON ECRIRE LE CHIFFRE
INC 2      ; R[2] ← R[2] + 1
JUMP 32    ; SAUTER A L'INSTRUCTION #32 // CHIFFRE SUIVANT
STOP       ; FIN

Nous allons évaluer la complexité comme une fonction du nombre de chiffres modifiés, y compris en cas de dépassement de capacité. La modification (ou ajout) d'un chiffre aura un coût unitaire de \(1\). Dans le meilleur des cas, i.e. quand le chiffre des unités est strictement inférieur à \(b-1\), on a \(\check T(n)=1\). Dans le pire des cas, il y a dépassement de capacité, il faut modifier \(n\) chiffres et en rajouter 1 et la complexité est donc \(\hat T(n)=n+1\).

Pour l'étude du cas moyen, on partitionne l'ensemble \(E\) des \(b^n\) instances de taille \(n\) possibles en \(n+1\) parties \(E_k\). Pour \(1\leq k\leq n\), \(E_k\) contient les instances dont \(k\) chiffres sont modifiés, il s'agit de la situation où \begin{equation}\label{eq:digit} a_0=a_1=\cdots=a_{k-2}=b-1\quad \text{et}\quad a_{k-1}\lt b-1. \end{equation}

Et pour \(k=n+1\), \(E_{n+1}=\{a^n-1\}\), instance dont les \(n\) chiffres sont modifiés et qui demande l'écriture d'un chiffre supplémentaire. Le cardinal des parties \(E_k\), \(1\leq k\leq n\), est facile à calculer. D'après (\ref{eq:digit}), les \(k-1\) premiers chiffres sont fixés à \(b-1\), on a \(b-1\) possibilités pour le chiffre \(a_{k-1}\) et les \(n-k\) chiffres restants sont quelconques, soit \begin{equation} \#E_k = \begin{cases} (b-1)b^{n-k},&\text{si}\ 1\leq k \leq n.\\ 1,&\text{si}\ k=n+1. \end{cases} \end{equation}

On vérifie aisément que \(\displaystyle\sum_{k=1}^{n+1}\#E_k=\#E\). On obtient: \begin{align} \bar T(n) &= \frac{1}{b^n}\sum_{k=1}^{n+1} k\#E_k\\ &= \frac{1}{b^n}\big((n+1) + (b-1)b^n\sum_{k=1}^{n}kb^{-k}\big)\\ &=\label{eq:fin}\frac{n+1}{b^{n}}+(b-1)\underbrace{\color{yellow}\sum_{k=1}^{n}kb^{-k}}_{\color{yellow}S(b^{-1})}. \end{align} Il reste à calculer la somme \(\color{yellow}S(b^{-1})\) :

\(S(b^{-1})= \displaystyle\frac{b^{n+1}-b(n+1)+n}{b^{n}(b-1)^2}\)
Considérons le polynôme \(P(X):=X^n+X^{n-1}+\cdots+X^2+X+1\). On a \begin{equation}\label{eq:PX} P(X)=\frac{X^{n+1}-1}{X-1} \end{equation} On dérive la première expression de \(P(X)\) et on multiplie par \(X\): \begin{equation*} XP'(X) =nX^n+(n-1)X^{n-1}+\cdots+X^2+X. \end{equation*} On pose alors \begin{equation}\label{eq:Sn} S(X):=XP'(X) \end{equation} On dérive la deuxième expression de \(P(X)\): \begin{equation}\label{eq:PpX} P'(X)=\frac{(n+1)X^n(X-1)-(X^{n+1}-1)}{(X-1)^2} \end{equation} Il reste à remplacer (\ref{eq:PpX}) dans l'expression (\ref{eq:Sn}) et à remplacer \(X\) par \(b^{-1}\) pour conclure.
On remplace cette expression dans (\ref{eq:fin}) et on peut conclure:
Le nombre moyen de chiffres modifiés par l'al­go­ri­thme d'incrémentation d'un entier de \(n\) chiffres exprimé en base \(b\) est \begin{equation}\label{eq:TN} \bar T(n) = \frac{b}{b-1}-\frac{1}{b^{n}(b-1)}. \end{equation}
et donc asymptotiquement égale à \(b/(b-1)\). Ainsi l'incrémentation d'un registre binaire coûte en moyenne deux changements de bits.
Écrivez une fonction Incrément(@A, b) qui reçoit en entrée une liste \(A\) de \(n\) entiers qui sont les \(n\) chiffres de son écriture en base \(b\) (cf. (\(\ref{eq:dec})\)) et qui incrémente \(A\), autrement dit qui réalise l'opération \(A \mapsto A+1\) en tenant compte du dépassement de capacité possible. La fonction Incrément doit renvoyer le nombre de chiffres de \(A\) qui auront été modifiés pour réaliser l'incrément.

L'objectif est de vérifier de manière expérimentale le résultat (\ref{eq:TN}) à savoir que la complexité moyenne de l'al­go­ri­thme est asymptotiquement égale à \(b/(b-1)\).

Écrivez une fonction test(n, b) qui calcule le nombre total de modifications pour toutes les listes de taille \(n\) en base \(b\). Estimez par le calcul les limites à fixer sur les valeurs de \(n\) et \(b\) pour que cette fonction termine son exécution dans un temps raisonnable. Faites quelques expériences avec différentes valeurs de \(b\) et \(n\) et comparez les résultats avec le calcul théorique obtenu en (\ref{eq:TN}).