Introduction à l'algorithmique

On suppose qu'on dispose d'un CPU ne permettant d'effectuer que deux opérations :

L'incrémentation d'un registre (en Python, r += 1) consistant à ajouter une unité au contenu de ce registre,
la décrémentation d'un registre (en Python, r -= 1),
mais aussi tester si un registre contient le nombre 0.

On cherche à prouver que cela suffit pour programmer les 4 opérations sur ce système.

I/ Addition

1) Algorithme

Pour additionner 5 à 1, on peut imaginer que a==1 est un registre contenant 1 graine, et b==5 est un registre contenant 5 graines : 🀽. Additionner 5 à 1, c'est réunir (par exemple dans le registre a) les 5 graines et la graine : 🁛. Mais cela peut se faire graine par graine :

🀽
🁃
🁉
🁏
🁕
🁛

Or transférer une graine depuis le registre b vers le registre a peut se décomposer en deux étapes élémentaires :

enlever une graine de b (décrémentation de b),
puis la rajouter à a (incrémentation de a)

2) Programmation de l'algorithme

a) en Javascript

let addition = function(a,b) {
    let x, y
    for (x=a,y=b ; y>0 ; y-=1, x+=1 ) {}
    return x
}

donne ceci :

	a = `1`
	b = `5`
a + b =	`6`

b) en Haskell

Axiomes de Peano (1889)

addition :: Int -> Int -> Int
addition x 0 = x
addition x y = addition (x+1) (y-1)

c) en Bash

addition(){
    local x=$1
    local y=$2
    while [ $y -gt 0 ]; do
        let "y=$y-1"
        let "x=$x+1"
    done
    echo $x
}

d) en Python

def addition(a,b):
    #@ requires a>=0
    #@ requires b>=0
    #@ ensures result==a+b
    x = a
    y = b
    while y>0:
        #@ variant y
        #@ invariant y>=0
        #@ invariant x+y==a+b
        y -= 1
        x += 1
    return x

Ce script peut être prouvé en ligne à l'aide de why3.

3) Étude de l'algorithme

Pour certifier un algorithme, on doit prouver deux choses :

que la fonction définie par l'algorithme est calculable, c'est-à-dire que l'exécution du programme prend un temps fini,
et que ce que calcule la fonction est bien ce que l'on veut (ci-dessus, une addition).

En algorithmique, on étudie aussi la manière dont le temps de calcul dépend de la taille des données d'entrée.

a) Terminaison

Pour prouver que le calcul se termine, on utilise un variant : il s'agit d'une expression dépendant des variables, et dont la valeur (entière) est

positive
décroissant à chaque passage dans la boucle.

Alors le variant ne peut prendre qu'un nombre fini de valeurs possibles, et le temps de calcul sera lui aussi fini.

Pour l'algorithme d'addition ci-dessus, la variable y est un variant de choix parce que la seule fois que sa valeur change dans la boucle, c'est la ligne y -= 1 qui est une décrémentation. Pour prouver la terminaison, why3 a dû d'abord prouver que y≥0, non seulement à un instant donné, mais tout le temps. Cette propriété est un invariant.

b) Correction

Pour prouver que l'algorithme d'addition est correct, on procède ainsi :

on cherche un invariant : il s'agit d'une proposition logique (un booléen) P vérifiant la propriété suivante : si P est vraie à l'entrée de la boucle, alors elle est également vraie à la sortie de la boucle.
On prouve que P est effectivement un invariant.
On prouve que P est vraie au début (avant la première entrée dans la boucle).
On en déduit que P est vraie à la fin (après le dernier passage dans la boucle ; on a déjà prouvé qu'il y a un dernier passage : c'est la terminaison vue ci-dessus).

L'invariant doit être choisi de manière à justifier la correction de l'algorithme. Ici, x+y==a+b convient :

Si, avant un passage dans la boucle, on a déjà x+y==a+b, alors après le passage dans la boucle,
- y a été décrémenté (est devenu y-1),
- et x a été incrémenté (est devenu x+1).
donc à ce moment, x+y est devenu x+1+y-1==x+y. La valeur de x+y n'ayant pas changé, cette expression est toujours égale à a+b : x+y==a+b est effectivement un invariant.
Avant l'entrée dans la boucle, x==a et y==b donc x+y==a+b.
Donc l'invariant x+y==a+b est toujours vrai à la fin du calcul. Mais à ce moment là, y==0 puisqu'on est sorti de la boucle. Donc x+0==a+b ou x==a+b : la variable x, à la fin du calcul, contient effectivement la somme a+b cqfd.

c) Complexité

On suppose que les opérations d'incrémentation et de décrémentation ont le même coût noté c. Alors le coût de chaque passage dans la boucle est 2×c (une incrémentation et une décrémentation). Le coût total de l'algorithme est donc 2c fois le nombre de passages dans la boucle. Comme y est décrémenté à chaque passage dans la boucle, le nombre de passages dans la boucle est la valeur initiale de y, soit b : le coût total est 2×c×b. Le temps de calcul est donc proportionnel à la taille du second terme, et l'algorithme est dit de complexité linéaire.

Remarque : on déduit de ceci la terminaison de l'algorithme puisque b est fini.

II/ Soustraction

1) Algorithme

Pour soustraire 4 à 6, on imagine que le registre a==6 contient 6 graines et que le registre b==4 contient 4 graines. Alors on peut enlever, tant que possible (c'est-à-dire tant qu'il reste au moins une graine à enlever du registre b), une graine simultanément de chacun des deux registres :

🁟
🁗
🁏
🁇
🀿

La soustraction est terminée avec pour résultat 2 : 6-4==2

L'algorithme consiste donc à décrémenter simultanément les deux registres a et b jusqu'à ce que le plus petit d'entre eux (on suppose que c'est b) vaille 0. À ce moment c'est a qui contient la différence.

2) Programmation de l'algorithme

a) en Javascript

Si jamais a est inférieur à b, on choisit d'envoyer 0 comme résultat de la soustraction :

let soustraction = function(a,b) {
    if ( a<b ) { return 0 }
    let x, y
    for (x=a,y=b ; y>0 ; y-=1, x-=1 ) {}
    return x
}

donne ceci :

	a = `6`
	b = `4`
a - b =	`2`

b) en Haskell

soustraction :: Int -> Int -> Int
soustraction x 0 = x
soustraction x y = soustraction (x-1) (y-1)

c) en Bash

soustraction(){
    local x=$1
    local y=$2
    while [ $y -gt 0 ]; do
        let "y=$y-1"
        let "x=$x-1"
    done
    echo $x
}

d) en Python

def soustraction(a,b):
    #@ requires a>=0
    #@ requires b>=0
    #@ requires a>=b
    #@ ensures result==a-b
    x = a
    y = b
    while y>0:
        #@ variant y
        #@ invariant y>=0
        #@ invariant x-y==a-b
        x -= 1
        y -= 1
    return x

Ce script aussi peut être prouvé en ligne par why3.

3) Étude de l'algorithme

a) Terminaison

Comme pour l'addition, la variable y est un variant, et pour la même raison : on ne fait que la décrémenter à chaque passage dans la boucle. Ce qui prouve que l'algorithme se termine.

b) Correction

La quantité x-y est invariante : c'est la différence entre les opérandes et celle-ci reste la même quand on décale (ici, décrémente) les opérandes. La proposition x-y==a-b est donc un invariant. Mais au début on a x==a et y==b donc x-y==a-b. Donc à la fin x-y est toujours égal à a-b. Or à la fin y==0 puisqu'on a quitté la boucle, donc à la fin x-y==x et l'égalité donnée par l'invariant devient la postcondition x==a-b. La différence est donc stockée dans la variable x.

c) Complexité

Le coût d'une décrémentation étant supposé égal à celui d'une incrémentation, l'algorithme de soustraction est lui aussi linéaire.

III/ Multiplication

1) Algorithme

Maintenant qu'on sait comment effectuer une addition et une soustraction, on considère le mini langage de programmation, comme enrichi de ces deux opérations.

Par exemple si on veut multiplier 4 par 3, on peut donner une unité à l'un des opérandes (par exemple 4) et considérer que le nombre 4 représente, ici, 🍐🍐🍐🍐. Son produit par 3 est constitué de 3 rangées de 🍐🍐🍐🍐, soit

🍐🍐🍐🍐
🍐🍐🍐🍐
🍐🍐🍐🍐

ce qui donne 🍐🍐🍐🍐+🍐🍐🍐🍐+🍐🍐🍐🍐 = 🍐🍐🍐🍐🍐🍐🍐🍐🍐🍐🍐🍐 : ici 4×3==4+4+4.

Comme a×b==a+a+a+...+a avec b termes, on peut donc programmer la multiplication avec l'algorithme suivant :

On initialise un registre x à 0 ;
on boucle jusqu'à ce que b==0 :
- on décrémente b
- on ajoute a à x
à la fin x contient le produit (on va le prouver plus bas).

2) Programmation de l'algorithme

a) en Javascript

let multiplication = function(a,b) {
    let x, y
    for (x=0,y=b ; y>0 ; y-=1, x+=a ) {}
    return x
}

donne ceci :

	a = `4`
	b = `3`
a × b =	`12`

b) en Haskell

Axiomes de Peano (1889)

multiplication :: Int -> Int -> Int
multiplication x 0 = 0
multiplication x y = multiplication x (y-1) + x

c) en Bash

multiplication(){
    local x=0
    local y=$2
    while [ $y -gt 0 ]; do
        let "y=$y-1"
        let "x=$x+$1"
    done
    echo $x
}

d) en Python

def multiplication(a,b):
    #@ requires a>=0
    #@ requires b>=0
    #@ ensures result==a*b
    c = 0
    x = a
    y = b
    while y>0:
        #@ variant y
        #@ invariant y>=0
        #@ invariant c+x*y == a*b
        c += x
        y -= 1
    return c

La vérification en ligne

3) Étude de l'algorithme

a) Terminaison

Comme précédemment, la variable y est décrémentée à chaque passage dans la boucle, donc elle est un variant de boucle. Ce qui prouve qu'il faut un temps fini pour effectuer une multiplication.

b) Correction

Comme invariant on propose c+x*y==a*b. Ici on a noté c la variable qui contient la somme partielle (celle à laquelle on ajoute a ou x à chaque passage dans la boucle). C'est bien un invariant, parce que si, avant un passage dans la boucle, on a déjà c+x*y==a*b, alors après le passage dans la boucle

c est devenu c+x puisqu'on lui a ajouté x,
y est devenu y-1 puisqu'il a été décrémenté.

Alors c+x*y est devenu c+x+x*(y-1) == c+x+x*y-x*1 == c+x+x*y-x == c+x*y et n'a donc finalement pas changé. C'est bien un invariant. Mais au début on a c==0, x==a et y==b d'où (au début) c+x*y==0+a*b==a*b. Donc l'invariant est vrai dès le début, donc aussi à la fin. Et à la fin, x==a (n'a pas changé au cours du calcul), y==0 (puisqu'on est sorti de la boucle), donc c+x*y==c+x*0==c et donc (à la fin) c==a*b : c'est la variable c qui contient a×b à la fin.

c) Complexité

Le nombre de passages dans la boucle est la valeur initiale de y, soit b (second opérande ; c'est la raison pour laquelle, en calcul mental, on conseille de choisir 17×2 plutôt que 2×17). Or à chaque passage dans la boucle,

on ajoute x à c : coût proportionnel à a
on décrémente y : coût constant donc négligeable devant celui de l'addition.

Donc le coût de la multiplication est proportionnel à a×b. Si a et b sont tous les deux du même ordre de grandeur n, on a un coût de l'ordre de n². On dit que cet algorithme est de complexité quadratique.

L'utilisation du binaire permet de calculer un produit bien plus rapidement : avec l'architecture de Von Neumann, le coût d'une multiplication est proportionnel au nombre de chiffres des opérandes. Or si on regarde le nombre de bits nécessaires pour écrire des entiers :

nombre	0	1	2	3	4	5	6	7	8	9	10	11
nombre de bits	1	1	2	2	3	3	3	3	4	4	4	4

on constate qu'à part 0 qui est rarement pris comme opérande, il y a moins de chiffres binaires que le nombre lui-même. La multiplication binaire est donc bien plus efficace que celle présentée ici.

IV/ Division euclidienne

1) Algorithme

On veut partager 17 🍐 entre 5 demi-pensionnaires. Alors

on en donne déjà une à chacun, et il reste 17-5 soit 12 🍐 à distribuer ;
comme 12 est plus grand que 5, on peut en donner une deuxième à chacun, et il reste alors 12-5=7 🍐 à distribuer ;
comme 7 est plus grand que 5, on peut donner une troisième 🍐 à chaque demi-pensionnaire, qui aura donc 🍐🍐🍐 chacun.
Il reste alors 🍐🍐 que l'on ne peut répartir équitablement entre plus de 2 personnes.

On obtient alors la situation suivante :

🍐🍐🍐🍐🍐 (première distribution)
🍐🍐🍐🍐🍐 (seconde distribution)
🍐🍐🍐🍐🍐 (troisième distribution)
🍐🍐 (reste)

Pour diviser a par b, on soustrait b à a tant que c'est possible, et on compte le nombre de soustractions : le nombre de fois qu'on peut soustraire b à a est le quotient, et la valeur finale de a est le reste de la division. On utilise donc deux registres

q initilialisé à 0 et incrémenté à chaque passage dans la boucle,
r initialisé à a et auquel on soustrait b à chaque passage dans la boucle.

La condition de sortie de la boucle est que le reste r est devenu plus petit que le diviseur b.

2) Programmation de l'algorithme

Cette fois-ci les fonctions ne renvoient plus un entier mais une liste de deux entiers (quotient et reste).

a) en Javascript

let division = function(a,b) {
    let q, r
    for (q=0,r=a ; r>=b ; r-=b,q+=1 ) {}
    return [q,r]
}

donne ceci :

	a = `17`
	b = `5`
quotient	`3`
reste	`2`

b) en Haskell

translation :: (Int,Int) -> (Int,Int)
translation (x,y) = (x+1,y) 

division :: Int -> Int -> (Int,Int)
division a b
    | a <= b = (0,a)
    | otherwise = translation (division (a-b) b)

c) en Bash

division(){
    local reste=$1
    local quotient=0
    while [ $reste -gt $2 ]; do
        let "reste-=$2"
        let "quotient+=1"
    done
    echo $quotient" "$reste
}

d) en Python

def division(a,b):
    #@ requires a>=0
    #@ requires b>0
    #@ ensures result[1]>b
    #@ ensures result[1]>=0
    #@ ensures b*result[0]+result[1]==a
    L = [0,a]
    while L[1]>=b:
        #@ variant L[1]
        #@ invariant L[1]>=0
        #@ invariant b*L[0]+L[1]==a
        L[1] -= b
        L[0] += 1
    return L

Pour vérifier en ligne avec why3

3) Étude de l'algorithme

a) Terminaison

Comme variant, on prend la variable r qui est initialisée au dividende a mais finira (à prouver ci-dessous) par contenir le reste de la division. En effet, cette variable décroît à chaque passage dans la boucle puisqu'on lui soustrait b. Ceci n'est toutefois vrai que sous la précondition b≠0 parce que sinon r ne varierait pas. D'ailleurs dans ce cas l'algorithme ne s'arrêterait jamais et on bouclerait sans fin. Ce bug très connu s'appelle erreur de division par zéro.

Il ne suffit pas que r décroisse au cours du temps, il faut aussi qu'il ne soit pas négatif. On a donc ici également besoin de la postcondition (portant sur la valeur finale de r) selon laquelle à la fin, 0≤r<b.

b) Correction

Il y a deux postconditions à montrer : 0≤r<b et a==b*q+r.

0≤r<b
- La propriété r≥0 est un invariant. En effet si, avant un passage dans la boucle, r≥0, alors
  - ou bien r≥b (soit r-b≥0) et après soustraction de b on a toujours r≥0
  - ou bien 0≤r<b et dans ce cas on ne parcourt pas la boucle.
- Or au début on a r==a qui est supposé positif (précondition)
- Donc à la fin on a bien 0≤r<b
a==b*q+r :
- C'est un invariant : en supposant qu'avant passage dans la boucle on a a==b*q+r, alors après le passage dans la boucle
  - q a été incrémenté et est devenu q+1
  - r a été diminué de b et est devenu r-b
  donc bq+r est devenu b(q+1)+r-b == bq+b+r-b == bq+r
- Or au début r==a et q==0 donc bq+r==b×0+a==a : l'égalité est vraie dès le début.
- Donc à la fin on a bien la postcondition a == b*q+r qui caractérise la division euclidienne.

c) Complexité

La variable q contient à la fin le nombre de soustractions effectuées. Chacune ayant un coût proportionnel à b, le coût de la division est de l'ordre de q×b soit de l'ordre du dividende a.