Preuve des algorithmes

Nous avons déjà remarqué l'analogie entre un algorithme et un théorème si l'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. De la même manière qu'il est nécessaire de fournir une preuve pour valider un théorème, il faut fournir une preuve de correction de l'algorithme afin de s'assurer qu'il effectue le travail pour lequel il a été conçu. Une preuve de correction se décompose en deux parties :

1. D'après notre définition formelle d'un algorithme, il doit s'arrêter. Pour s'en assurer, on fait une 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. D'autre part, il faut s'assurer que l'algorithme renvoie le résultat attendu en fonction des données qu'il doit traiter, on cherche à établir alors une preuve de validité (ou preuve de correction partielle).

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 mais nous procéderons de manière re­la­ti­ve­ment souple cette année en nous contentant souvent de fournir les arguments clés de ces preuves.

La terminaison d'un algorithme ne peut poser un problème que dans la mesure où il con­tient une ou plusieurs boucles, dans le cas contraire elle est consubstantielle à la nature séquentielle et la finitude des instructions d'un algorithme. Pour prouver qu'un algorithme s'arrête, il faut démontrer pour cha­cune d'entre elles que la condition d'arrêt (la négation de la condition d'entrée dans la boucle) sera satisfaite 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 (très souvent strictement croissante ou décroissante) de quantités qui dépendent des variables impliquées dans les instructions qui constituent le corps de la boucle et dont les valeurs successives à chaque nouveau passage vont fixer les termes de cette suite. On parle de variant de boucle.

Pour prouver la validité d'un algorithme, il faut chercher un invariant de boucle, c'est-à-dire un prédicat de certaines variables de l'algorithme qui en font une proposition vraie à chaque entrée dans la boucle. Ce prédicat doit être choisi en rapport avec le résultat attendu, de manière à ce qu'une fois la condition d'arrêt sa­tis­fai­te, les valeurs des variables impliquées dans le prédicat en font un proposition vraie prouvant que le résultat attendu est correct. 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.

La méthode de preuve adaptée dans ce cas est la récurrence, l'initialisation consiste à vérifier que la proposition obtenue pour les valeurs des variables avant le premier passage dans la boucle est vraie, et l'hérédité consiste à supposer que la proposition est vraie avant l'entrée dans la boucle et qu'elle le reste à la fin des instructions de la boucle.

À 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 est le prédicat \(i > n\) (négation de la condition d'entrée \(i\leq n\)) sera donc satisfaite pour la valeur \(n+1\) de cette suite.

Passons à présent à la validité de l'algorithme en montrant que le prédicat \(P({\color{yellow}i})\) défini par \begin{equation}\label{eq:invar} S=\sum_{k=1}^{{\color{yellow}i}-1}L[k] \end{equation} est un invariant de la boucle tant que de cet algorithme. Initialisation : la proposition \(P(1)\) est vraie avant d'entrer dans la boucle puisque pour \(i=1\), 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.

Hérédité : Soit \(i\in\ab{1}{n}\). On suppose que \(P(i)\) est vrai à l'entrée de la boucle (hypothèe de récurrence). 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 de nouveau la proposition \((\ref{eq:invar})\) qui est satisfaite, ce qui achève la preuve d'hérédité et nous donne : \[\forall i\in\ab{1}{n+1}\quad P(i).\] Nous savons que \(i=n+1\) à la sortie de la boucle d'après la preuve d'arrêt, on conclut donc 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 la somme de tous les termes de \(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 :

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

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 linéarithmique (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 linéarithmique (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 li­néa­ri­thmi­que 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.

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.

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 :

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} \overline{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 une partition facilitant le calcul de \((\ref{moyenbis})\)

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

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'in­té­gra­li­té des instances de taille \(n\) et diviser ce nombre par \(2^{n}\) qui représente le nombre d'instances pos­si­bles (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 par­ti­tion­ne­ment 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 ) : \[\#\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 cours de combinatoire de première année 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. Re­pre­nons 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 \(\ab{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})\).

Incrémentation

Le principe général 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 passe au chiffre suivant, sinon on lui rajoute 1 et on a fini. Dans le programme sur la machine ram, on range la valeur \(b-1\) dans le registre #1 (\(b\) est la bas de numération 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).

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\) dans la cellule qui suit. Les instructions #12 à #25 balaient les chiffres en mémoire en incrémentant le premier possible à l'instruction #19 et en arrêtant l'exécution du programme, les chiffres précédents ayant été initialisés à 0 par l'instruction #16. Les instructions #28 à #32 écrivent le résultat sur la bande de sortie.

READ     ; LECTURE DE LA BASE b
DEC 0    ; CALCUL DE b - 1 ET 
STORE 1  ; R[1] ← b - 1
LOAD #3  ; INITIALISATION DU REGISTRE
STORE 2  ; D'INDEXATION MEMOIRE i = R[2] ← 3
READ     ; LECTURE D'UN CHIFFRE
STORE @2 ; RANGEMENT DANS R[i]
INC 2    ; i ← i + 1
JUMZ 5   ; SI CHIFFRE = 0 OU 
JUMG 5   ; SI CHIFFRE > 0 PASSER AU SUIVANT
LOAD #3  ; INITIALISATION DU REGISTRE
STORE 2  ; D'INDEXATION MEMOIRE i = R[2] ← 3
LOAD @2  ; CHARGEMENT CHIFFRE COURANT R[i]
JUML 21  ; SI R[i] = -1 => DEBORDEMENT RETENUE
SUB 1    ; SINON ON CALCULE D:=(R(i] -(b-1))
JUML 19  ; SI (D < 0) ON PEUT INCREMENTER R[i] 
STORE @2 ; SINON ON A D=0 ET R[i] ← 0
INC 2    ; i ← i + 1, ON PASSE 
JUMP 12  ; AU CHIFFRE SUIVANT
INC @2   ; R[i] ← R[i] + 1, INCREMENT DU CHIFFRE
JUMP 26  ; ET FIN: ON PEUT AFFICHER LE RESULTAT
LOAD #1  ; DEBORDEMENT: ON ECRASE LA BALISE -1
STORE @2 ; PAR LA RETENUE 1
INC 2    ; ET ON RAJOUTE UNE NOUVELLE 
LOAD #-1 ; BALISE -1  A LA POSITION SUIVANTE
STORE @2 ; EN MEMOIRE
LOAD #3  ; INITIALISATION DU REGISTRE
STORE 2  ; D'INDEXATION MEMOIRE i = R[2] ← 3
LOAD @2  ; ON CHARGE LE CHIFFRE R[i]
JUML 33  ; SI R[i] = -1 C'EST LA BALISE => FIN
WRITE    ; SINON ON ECRIT LE CHIFFRE R[i]
INC 2    ; i ← i + 1, ET ON PASSE AU
JUMP 28  ; 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}

Travaux pratiques