Nous allons aujourd'hui comment l'algorithmique permet de prouver :
Evaluation Bonus pour les plus rapides : deux questions
Documents de cours : open document ou pdf
Une suite est une famille d'éléments indexés par les entiers naturels. Chaque élément de la suite se nomme un terme.
Il y a un premier élément, puis un deuxième, un troisième...
Exemple : 10, 7, 4, 1, -2, -5
Toute suite d’entiers positifs strictement décroissante ne peut prendre qu’un nombre fini de valeurs.
Ainsi, on voit bien que la suite précédente s'arrête à 1 : 10, 7, 4, 1.
Une suite arithmétique est une suite dans laquelle (hormis pour le tout premier terme) chaque terme un+1 se calcule en additionnant le terme précédent un et une valeur appelée la raison r.
Par exemple, la suite de nombres 5, 15, 25, 35... caractérise une suite arithmétique
A partir de ces deux informations, on peut obtenir les valeurs successives des éléments de la suite.
On peut donc calculer le terme un+1 si on connaît le terme un et la raison r :
Formule 1 (successeur)
|
un+1 = un + r
|
Calculer le terme 1000 ainsi serait un peu long, il faudrait calculer u1, u2, u3... jusqu'à u1000.
Heureusement, il existe une autre façon de faire : on peut calculer le terme un en connaissant le terme initial u0 et la raison r de la suite arithmétique.
Formule 2 (cas général)
|
un = u0 + n*r
|
Puisqu'on ajoute la raison pour obtenir le terme suivant :
Avec une raison de 2 : 10, 12, 14, 16, 18...
Avec une raison de -3 et des ENTIERS : 10, 7, 4, 1, -2, -5...
Avec une raison de -2.5 et des FLOTTANTS : 10.0, 7.5, 5.0, 2.5, 0.0, -2.5...
Avec une raison de -0.0000000000000001 et des FLOTTANTS : 10.0, 10.0, 10.0, 10.0, 10.0... Ca ne fonctionne donc pas systématiquement lorsqu'il y a des flottants !
Toute suite arithmétique uN
d'entiers positifs
strictement décroissante
ne peut prendre qu’un nombre fini de valeurs.
En effet, en partant d'une valeur entière positive qui devient de plus en plus petite, on finit toujours par s'arrêter car on finit par atteindre une valeur négative.
Avec les flottants et leurs représentations approximatives, on peut avoir des problèmes : la suite mathématique théorique peut-être décroissante mais le calcul réel peut mener à une suite constante (voir exemple 3)
Si l'une des conditions n'est pas vraie (ce n'est pas une suite, ce ne sont pas des entiers...), cela ne veut pas dire que l'algorithme ne va pas s'arrêter systématiquement.
Il faudra juste trouver d'autres moyens de montrer que ça s'arrête TOUJOURS ou au contraire que cela boucle PARFOIS.
01° On vous donne la suite arithmétique définie ci-dessous :
un+1 = un + 12
...CORRECTION...
un+1 = un + 12
u0 = 100
La raison est +12.
u1 = 112
u2 = 124
u3 = 136
u4 = 148
On voit bien qu'aucun terme ne pourra jamais être nul.
02° On vous donne la suite arithmétique définie ci-dessous :
un = 20 + n*(-5) = 20 - n*5
...CORRECTION...
un = 20 + n*(-5) = 20 - n*5
u0 = 20
La raison est -5.
u1 = 15
u2 = 10
u3 = 5
u4 = 0
Oui, les autres termes seront négatifs.
03° Donner la valeur du terme u150 d'une suite arithmétique de terme initial 500 et de raison -2.
Cette suite est-elle croissante ou décroissante ?
...CORRECTION...
un = 500 + n*(-2) = 500 - n*2
u150 = 500 - 150*2 = 200
La raison arithmétique étant négative, la suite est strictement décroissante.
Une suite géométrique est une suite dans laquelle (hormis pour le tout premier terme) chaque terme vn+1 se calcule en multipliant le terme précédent vn par une valeur appelée la raison q.
Par exemple, la suite de nombres 5, 10, 20, 40... caractérise une suite géométrique
A partir de ces deux informations, on peut obtenir les valeurs successives des éléments de la suite.
On peut donc calculer le terme vn+1 si on connaît le terme vn et la raison q :
Formule 1 (successeur)
|
vn+1 = vn * q
|
Calculer le terme 1000 ainsi serait un peu long, il faudrait calculer v1, v2, v3... jusqu'à v1000.
Heureusement, il existe une autre façon de faire : on peut calculer le terme vn en connaissant le terme initial v0 et la raison q de la suite géométrique.
Formule 2 (cas général)
|
vn = v0 * qn
|
Attention aux flottants : puisqu'on multiplie la raison pour obtenir le terme suivant, on devrait pouvoir dire en théorie que
Avec une raison de 10 : 5, 50, 500, 5000, 50000...
Avec une raison de 0.5 (une division euclidienne par 2) et des ENTIERS : 10, 5, 2, 1, 0. Fini, ça fonctionne.
Avec une raison de 0.5 et des FLOTTANTS : 10, 5, 2, 1, 0.5, 0.25, 0.125, 0.0625.... On n'attendra jamais 0. Ca ne fonctionne pas !
Mais, il y a même plus grave : une suite géométrique croissante en théorie peut rester constante s'il s'agit de flottants : si la raison est de 1.0000000000000001 et le premier terme est 10, vous pouvez tester avec Python : on garde 10.0 ! Idem avec 0.9999999999999999.
>>> 10.0 * 1.0000000000000001
10.0
>>> 10.0 * 0.99999999999999999
10.0
Une géométrique vN
d’entiers positifs
strictement décroissante
ne peut prendre qu’un nombre fini de valeurs.
En effet, en partant d'une valeur entière positive qui devient de plus en plus petite, on finit toujours par s'arrêter car on finit par atteindre une valeur négative.
Prouver qu'un algorithme s'arrête pour toutes ENTREES correctement fournies revient à prouver que toutes les boucles présentes dans l'algorithme ne s'exécuteront qu'un nombre fini de fois.
La preuve de terminaison d'un algorithme permet d'affirmer qu'il s'arrête de façon certaine sur toutes les entrées valides qu'on lui fournit (c'est à dire les entrées respectant les préconditions).
Preuve de terminaison : si les deux propositions suivantes sont vraies alors la boucle s'arrête :
(A et B) implique alors que l'algorithme se termine.
Attention à la négation
(A et B) implique que l'algorithme s'arrête TOUJOURS.
NON (A et B) ou encore (NON A) ou (NON B) d'après De Morgan n'implique rien de particulier.
Il est possible que l'algorithme ne boucle jamais, boucle parfois ou boucle toujours.
Si les conditions A et B sont vraies, le VARIANT va nécessairement décroître et devenir à un moment négatif ou nul.
Si on veut que la boucle soit parcourue au moins une fois, le variant doit bien être initialement positif.
Prenons ce court programme :
1
2
3 | x = 3
while x < 100:
x = x + 10
|
Etape 1 : AVANT le premier tour
Ligne 1 : on voit que x vaut 3 initialement.
Comme nous avons fait 0 tour de boucle TANT QUE, nous noterons ceci :
| x0 = 3 | (1) |
Etape 2 : PENDANT un tour
Ligne 3 : on voit qu'on augmente x de 10 à chaque tour de boucle. En notant n le nombre de tours de boucle effectué, on peut donc écrire que
| xN = 3 + 10*n | (2) |
Etape 3 : recherche du VARIANT
On cherche si on peut ramener la condition de boucle de la ligne 2 à une forme de ce type :
L2 | while VARIANT > 0:
|
On commence la démonstration en récupérant la condition de boucle et en remplaçant x par xN.
L2 | while xN < 100:
|
On remplace xN en utilisant (2) :
L2 | while (3 + 10*n) < 100:
|
Pour revenir un symbole supérieur plutôt qu'inférieur, on écrit b > a plutôt que a < b :
L2 | while 100 > (3 + 10*n):
|
Pour obtenir 0 à droite, on distribue puis on passe tous les termes à gauche :
L2 | while 100 > ( + 3 + 10*n ):
|
L2 | while ( 100 - 3 - 10*n ) > 0:
|
L2 | while (97 - 10*n) > 0:
|
Nous obtenons alors le VARIANT de boucle exprimé de cette façon :
L2 | while VARIANT > 0: avec VARIANT = uN = 97 - 10*n
|
Etape 4 : conclusion
On voit que le variant est une suite d'entiers décroissante puisqu'on perd 10 à chaque tour de boucle.
Nous obtenons donc bien
Les deux propriétés A et B précédentes prouvent la terminaison de cette boucle.
04° Prouver la terminaison (ou non) du programme ci-dessous. Il faudra trouver un variant qui soit une suite d'entiers positifs strictement décroissante et montrer que la condition du TANT QUE revient à écrire TANT QUE VARIANT > 0
1
2
3
4
5
6
7
8
9 | def exercice(seuil):
"""Fonction-exercice qui ne sert à rien
:: param seuil(int) :: un entier positif
:: return (int) :: un résultat
"""
x = 0
while 5*x < seuil:
x = x + 1
return x
|
...CORRECTION...
Etape 1 : AVANT le premier tour
Ligne 6 : on voit que x vaut 0 initialement. Comme nous avons fait 0 tour de boucle TANT QUE, nous noterons ceci :
x0 = 0 |
(1) |
Etape 2 : PENDANT un tour
Ligne 8 : on voit qu'on augmente x de 1 à chaque tour de boucle.
xN = 0 + 1*n
On obtient donc juste :
xN = n |
(2) |
Etape 3 : recherche du VARIANT
On cherche si on peut ramener la condition de boucle de la ligne 7 à une forme de ce type :
L7 | while VARIANT > 0:
|
On commence la démonstration en récupérant la condition de boucle et en remplaçant x par xN.
L7 | while 5*xN < seuil:
|
On remplace xN en utilisant (2) :
L7 | while 5*n < seuil:
|
Pour obtenir un symbole supérieur plutôt qu'inférieur, on écrit b > a plutôt que a < b :
L7 | while 5*n < seuil:
|
L7 | while seuil > 5*n:
|
Pour obtenir un zéro à droite, on doit passer les termes de droite à gauche :
L7 | while seuil > + 5*n:
|
L7 | while (seuil - 5*n) > 0:
|
Nous obtenons alors le VARIANT exprimé de cette façon :
L7 | while VARIANT > 0: avec VARIANT = uN = seuil - 5*n
|
Etape 4 : conclusion
Le variant est une suite d'entiers décroissante puisqu'on perd 5 à chaque tour de boucle.
Nous obtenons donc bien
while uN > 0 uN = seuil - 5*n une suite d'entiers strictement décroissante.Les deux affirmations précédentes prouvent la terminaison de cette boucle.
05° Prouver la terminaison (ou non) du programme ci-dessous. Il faudra trouver un variant qui soit une suite strictement décroissante d'entiers positifs et montrer que la condition du TANT QUE revient à écrire : TANT QUE VARIANT > 0
1
2
3
4
5
6
7
8
9 | def exercice(seuil):
"""Fonction-exercice qui ne sert à rien
:: param seuil(int) :: un entier positif
:: return (int) :: un résultat
"""
x = 0
while 5*x < seuil:
x = x - 1
return x
|
...CORRECTION...
Etape 1 : AVANT le premier tour
Ligne 6 : on voit que x vaut 0 initialement. Comme nous avons fait 0 tour de boucle TANT QUE, nous noterons ceci :
x0 = 0 |
(1) |
Etape 2 : PENDANT un tour
Ligne 8 : on voit qu'on diminue x de 1 à chaque tour de boucle.
xN = 0 - 1*n
On obtient donc juste :
xN = -n |
(2) |
Etape 3 : recherche du VARIANT
On cherche si on peut ramener la condition de boucle de la ligne 7 à une forme de ce type :
L7 | while VARIANT > 0:
|
On commence la démonstration en récupérant la condition de boucle et en remplaçant x par xN.
L7 | while 5*xN < seuil:
|
On remplace xN en utilisant (2) :
L7 | while 5*(-n) < seuil:
|
L7 | while -5*n < seuil:
|
Pour obtenir un symbole "supérieur à", on écrit b > a plutôt que a < b :
L7 | while -5*n < seuil:
|
L7 | while seuil > - 5*n:
|
Pour obtenir 0 à droite, on doit passer les termes de droite à gauche :
L7 | while seuil > - 5*n:
|
L7 | while (seuil + 5*n) > 0:
|
Nous obtenons alors le VARIANT de boucle exprimé de cette façon :
L7 | while VARIANT > 0: avec VARIANT = uN = seuil + 5*n
|
Etape 4 : conclusion
On voit que le variant est une suite d'entiers croissante puisqu'on gagne 5 à chaque tour de boucle.
Nous obtenons donc
while uN > 0 uN = seuil + 5*n une suite d'entiers strictement croissante.Nous venons donc de prouver que cet algorithme ne s'arrête pas nécessairement. D'ailleurs, comme la suite est croissante et qu'il n'y a pas d'autre condition d'arrêt, nous sommes certains, sur ce cas particulier, qu'on obtient une boucle infinie.
Alors, notre algorithme de recherche linéaire, consistant à lire les éléments un à un jusqu'à trouver le bon se termine-t-il ?
Nous aurons parfois des algorithmes pour lesquels le TQ s'exprime de façon plus complexe que TANT QUE VARIANT > 0.
Imaginons une boucle qui s'écrit TANT QUE C1 and C2.
La boucle va continuer tant que C1 and C2.
La boucle va se terminer dès que not (C1 and C2).
Or not (C1 and C2) = (not C1) or (not C2).
En français, cela veut dire que la boucle va s'arrêter si C1 devient fausse ou si C2 devient fausse.
Notre boucle a donc deux possibilités pour s'arrêter mais elle est compliquée à gérer.
Que peut-on faire si on veut montrer qu'elle s'arrête ?
Simplifier : il suffit d'en choisir une et de montrer qu'elle va nécessairement devenir fausse à un moment.
Or, si on montre que la boucle s'arrête en ne considérant déjà que l'une des deux conditions d'arrêt, c'est qu'elle va encore plus s'arrêter si on considère les deux possibilités !
Si on applique cela à notre parcours :
while i < longueur and t[i] != x:
On pourrait décider de ne travailler qu'avec la première condition et voir si cela suffit pour montrer la terminaison.
while i < longueur and t[i] != x:
06° Prouver la terminaison du programme de recherche linéaire en faisant comme si le TANT QUE n'avait qu'une seule condition.
1
2
3
4
5
6
7
8
9
10
11
12 | def rechercher(t, x):
"""Renvoie l'indice de la première occurrence de x dans t, -1 si non présent"""
i = 0
longueur = len(t)
while i < longueur and t[i] != x:
i = i + 1
if i < longueur:
reponse = i
else:
reponse = -1
return reponse
|
...CORRECTION...
Etape 1 : AVANT le premier tour de boucle
Ligne 4 : on voit que i vaut 0 initialement. Comme nous avons fait 0 tour de boucle TANT QUE, nous noterons ceci :
i0 = 0 |
(1) |
Etape 2 : PENDANT chaque tour
Ligne 7 : on voit qu'on augmente i de 1 à chaque tour de boucle.
iN = 0 + 1*n
On obtient donc juste :
iN = n |
(2) |
Etape 3 : recherche du VARIANT
On cherche si on peut ramener la condition de boucle de la ligne 7 à une forme de ce type :
L6? | while VARIANT > 0:
|
On commence la démonstration en récupérant la condition de boucle et en remplaçant i par iN.
L6 | while iN < longueur:
|
On remplace iN en utilisant (2) :
L6 | while n < longueur:
|
Pour obtenir un symbole "supérieur à", on écrit b > a plutôt que a < b :
L6 | while n < longueur:
|
L6 | while longueur > n:
|
Pour obtenir un zéro à droite, on doit passer les termes de droite à gauche :
L6 | while longueur > + n:
|
L6 | while (longueur - n) > 0:
|
Nous obtenons alors le VARIANT de boucle exprimé de cette façon :
L6 | while VARIANT > 0: avec VARIANT = uN = longueur - 1 * n
|
Etape 4 : conclusion
On voit que le variant est une suite d'entiers décroissante puisqu'on perd 1 à chaque fois.
Nous obtenons donc bien
while uN > 0 uN = longueur - n une suite d'entiers strictement décroissante.Nous venons donc de prouver la terminaison de cette boucle.
Puisqu'il s'agit de la seule boucle de cette fonction, on peut en déduire que la fonction se termine également.
En Français, une correction veut dire modifier quelque chose en vue de l'améliorer.
Ce n'est pas le sens de la PREUVE PAR CORRECTION en informatique. Le mot CORRECTION fait ici référence à CORRECT : on va prouver que l'algorithme dont on a fait la preuve donnera toujours la bonne réponse, la réponse correcte.
A toujours avoir en tête : on ne peut pas prouver la correction d'un algorithme en réalisant simplement un très grand nombre de tests. Nous ne parviendrions qu'à prouver que l'algortihme fonctionne dans sur les cas testés. On peut en déduire une probabilité de bonnes réponses éventuellement, mais jamais une certitude à 100 %.
Seul cas où on peut utiliser des tests pour prouver la correction d'un algorithme : lorsque les différentes valeurs d'entrée sont en nombre fini : on peut alors éventuellement tester une par une toutes les possibilités et si on ne tombe jamais sur un cas faux, c'est que l'algorithme fonctionne correctement.
Cela pourra être le cas avec le morpion : 9 cases et chaque case ne peut porter que 3 valeurs : vide, joueur 1 ou joueur 2. On a donc 39 possibilités différentes à tester. 19683. C'est trop pour un humain mais facile pour un ordinateur.
Une démonstration où on teste un par un tous les cas possibles se nomme une démonstration par cas.
C'est ce type de démonstration que nous avons utilisé lorsque nous avons montré que la table de vérité de NOT(a NAND b) correspond à la table de vérité de a AND b : il n'y a que 4 cas différents à tester : 00, 01, 10 et 11.
Avec notre recherche, on ne peut pas faire cela. On ne pourra jamais tester toutes les valeurs à tester et encore moins générer tous les tableaux possibles.
Pour prouver la correction de l'algorithme, il va falloir la démontrer.
La preuve de correction d'un algorithme permet d'affirmer
Pour faire la preuve de correction d'un algorithme, il faut trouver un INVARIANT : une propriété P vérifiable qui reste vraie lors des différentes étapes de l'algorithme.
Un INVARIANT DE BOUCLE est une propriété VRAIE à chaque début de tour, juste avant l'exécution de la première instruction de la boucle.
Cet invariant permettra de prouver que le résultat final après exécution est bien le résultat attendu.
Malheureusement, il n'y a pas de méthodologie automatique miraculeuse pour trouver cet invariant. Il faut réfléchir et tenter des choses, comme avec toute démonstration.
Une fois qu'on dispose d'un INVARIANT P, la démonstration se fait en trois temps.
On doit prouver que l'INVARIANT est VRAI lorsqu'on commence le premier tour de boucle mais sans l'avoir réalisé en entier. On a donc fait 0 tour en entier.
Le plus souvent, cette partie est triviale. Mais pas toujours...
SI P est vrai après k tours de boucles, ALORS P sera encore vrai en ayant fait un tour de boucles supplémentaire.
On fait l'hypothèse qu'on a fait k tours de boucles et qu'on est au début du tour k+1. L'INVARIANT Pk est donc considéré juste.
On doit montrer qu'en réalisant ce tour complétement jusqu'au début du prochain, l'invariant P reste vrai à la fin de cette boucle. On aura donc fait k+1 tours de boucle complet, Pk+1 serait encore vérifiée.
On se place dans le cadre d'un tour qui est suivi d'un autre tour. On ne se place pas dans le cadre de la toute dernière boucle ici. On boucle, point.
On doit y prouver qu'à la fin du dernier tour, on obtient la situation voulue. Ni trop tôt, ni trop tard. C'est pour cela qu'on nomme cette partie la phase de terminaison, à ne pas confondre avec la preuve de terminaison.
P0 ➡ P1 ➡ P2 ➡ P3... ➡ Pfinal
Prouver la correction d'un algorithme, c'est prouver qu'il répond correctement dans sa totalité.
Dans un premier temps, on commence souvent par montrer la correction de sa boucle.
Ensuite, on utilise ce résultat pour faire une deuxième démonstration qui prouve le résultat de l'algorithme en lui-même.
Initialisation
07° On considère l'invariant Pk suivant :
Pk : lors du tour k, l'élément cherché x n'est pas dans le sous-tableau t[0 .. k].
Au début du tour k, i = k.
Démontrer l'initialisation.
...CORRECTION...
Commençons par voir comment commencer effectivement ce premier tour de boucle :
Situation initiale lorsqu'on parvient à commencer un premier tour
On voit ligne 4, qu'on place i à 0.
4
5
6 | i = 0
longueur = len(t)
while 0 < longueur and t[0] != x:
|
Si on remplace i par cette valeur, on voit que pour commencer ce premier tour de boucle, il faut que la case 0 EXISTE et qu'elle ne contienne pas l'élément x.
Propriété P0
P0 : lors du tour 0, l'élément cherché x n'est pas dans le sous-tableau t[0, 0] = t[0].
Au début du tour 0, i = 0.
◻
Conservation
08° On considère l'invariant Pk suivant :
Pk : lors du tour k, l'élément cherché x n'est pas dans le sous-tableau t[0 .. k].
Au début du tour k, i = k.
Démontrer la conservation.
...CORRECTION...
Hypothèse de départ : Pk est vraie
Pk : lors du tour k, l'élément cherché x n'est pas dans le sous-tableau t[0 .. k].
Au début du tour k, i = k.
D'après l'hypothèse, on se trouve en début de ligne 7 avec
i = k et
t[i] != x (puisque x n'est pas dans t[0 .. k] et que i = k)
Déroulement du tour de boucle (k) jusqu'au début du prochain tour(k+1)
Une seule instruction dans la boucle : on incrémente i, qui valait k, et passe donc à k+1 à la fin de ce tour.
En fin de tour k, la propriété Pk est encore vraie (en effet, x n'était pas dans [0 .. k] et il ne s'y trouve toujours pas puisque nous n'avons touché ni à x, ni à t, ni à k).
On repart alors en ligne 6 avec cette fois i = k+1, et pour passer en ligne 7, on a donc nécessairement :
Avec (1)+(2), on en déduit t[k+1] != x.
Or, l'hypothèse de départ que x n'était pas dans t[0 .. k].
On peut donc dire que x n'est pas dans t[0 .. k+1]
Si on résume, on atteint le début de la ligne 7 avec :
Il s'agit précisement de la propriété Pk+1.
◻
Terminaison
09° On considère l'invariant Pk suivant :
Pk : lors du tour k, l'élément cherché x n'est pas dans le sous-tableau t[0 .. k].
Au début du tour k, i = k.
Démontrer la correction de l'algorithme en utilisant notamment la terminaison de la boucle.
1
2
3
4
5
6
7
8
9
10
11
12 | def rechercher(t, x):
"""Renvoie l'indice de la première occurrence de x dans t, -1 si non présent"""
i = 0
longueur = len(t)
while i < longueur and t[i] != x:
i = i + 1
if i < longueur:
reponse = i
else:
reponse = -1
return reponse
|
...CORRECTION...
Terminaison
Nous allons étudier l'algorithme en démontrant par cas qu'il répond toujours la bonne réponse.
Si le tableau est non vide, nous avons déjà montré l'initialisation et la conservation.
Cas A : le tableau est vide
Lignes 4-5 : On a i = 0 et longueur = 0
Ligne 6 : on ne rentre pas dans la boucle puisque le tableau est vide : 0 n'est pas inférieur à 0.
On atteint la ligne 8 et puisque 0 n'est pas inférieur à 0, on atteint la ligne 10 puis 11 : on répond bien -1 pour signaler qu'on ne trouve pas x.
Correct sur ce cas.
CAS B : on atteint la fin du tableau de taille n.
On considère n valeurs dont les indices vont de 0 à (n-1).
Lignes 4-5 : On a i = 0 et longueur = n
Démontrons la terminaison de la boucle dans ce cas :
On rentre dans la boucle et le dernier tour est le tour (n-1).
Donc Pn-1 est vérifiée.
Donc x n'est pas dans t[0 .. n-1] (tout le tableau donc).
A la fin de la dernière boucle, i passera de n-1 à n.
On atteint la ligne 8 et puisque n n'est pas inférieur à n, on atteint la ligne 10 puis 11 : on répond bien -1 pour signaler qu'on ne trouve pas x.
Correct sur ce cas.
On considère n valeurs dont les indices vont de 0 à (n-1).
Lignes 4-5 : On a i = 0 et longueur = n
Démontrons la terminaison de la boucle dans ce cas :
On rentre dans la boucle et le dernier tour est le tour (i-1).
Donc Pi-1 est vérifiée.
Donc x n'est pas dans t[0 .. i-1].
A la fin de la dernière boucle, i passera de i-1 à i avec t[i] = x.
On atteint la ligne 8 et puisque i est inférieur à n, on place cet indice dans la réponse.
Correct sur ce cas.
Nous avons traité les 3 cas possibles.
L'algorithme est correct sur ces 3 cas.
◻
La démonstration par récurrence d'une proriété sert lorsqu'on veut démontrer qu'une propriété, dépendant de n, est vraie pour toutes les valeurs de n.
il y a donc des similitudes avec la preuve de correction d'un algoritmhe mais également une énorme différence :
C'est pour cela que les phases ne portent pas exactement les mêmes noms sur ces deux preuves.
Nommée phase d'initialisation dans les deux cas.
Nommée phase de conservation pour une preuve de correction : si c'est vrai au début de la boucle k, on doit y montrer qu'en réalisant ce tour de boucle jusqu'au bout, cela sera vrai également au début du tour SI on continue la boucle. Il est possible qu'on ne reboucle pas en fin de tour.
Nommée phase d'hérédité pour une preuve par récurrence : si c'est vrai pour cette étape, on devra montrer que cela restera vrai pour l'étape suivante. On "reboucle" toujours. Pas d'arrêt.
Nommée phase de terminaison sur une preuve de correction : on y montre qu'à la fin, on est bien dans configuration voulue.
Nommée phase de conclusion sur une preuve de récurrence. Rien y à faire de particulier à part conclure que la propriété est vrai quelque soit k, jusqu'à l'infini.
P0 ➡ P1 ➡ P2 ➡ P3... sans jamais s'arrêter.
Voyons maintenant comment comparer des algorithmes entre eux.
Nous allons étudier ce qu'on appelle la complexité de l'algorithme. On parle également de coût de l'algorithme.
Le coût d'un algorithme exprime la façon dont l'algorithme réagit globalement à l'augmentation du nombre n de données à traiter.
On évalue souvent le coût dans le pire des cas car il borne le comportement de l'algorithme : s'il se comporte bien dans le pire des cas, c'est qu'à priori nous allons pouvoir l'utiliser.
PROBLEME FACILE
Exemple
C'est donc pas mal !
Exemple
Ce coût se situe donc entre CONSTANT et LINEAIRE.
Si on double les données, on double les actions.
Si le nombre de données est multiplié par 3, le nombre d'instructions élémentaires est multiplié par 3 aussi.
Exemple
C'est donc pas mal !
C'est un peu plus long que du coût constant.
Si on double les données, on multiplie les actions par 4, on quadruple.
Si le nombre de données est multiplié par 3, le nombre d'instructions élémentaires est multiplié par 9....
Exemple
Plus k est grand, plus l'algorithme va être lent.
On notera que le coût linéaire et le coût quadratique sont des cas particuliers de coûts polynomiaux. Ce sont d'ailleurs ceux qui répondent le plus rapidement.
PROBLEME DIFFICILE
Plus k est grand, plus l'algorithme va être lent.
Exemple
>>> 2**100
1267650600228229401496703205376
>>> 2**1000
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
On notera bien que n est en position d'exposant.
Exemple
On pourrait croire que cela évolue moins vite que l'exponentiel mais dès que n devient grand, cela explose encore plus vite que le coût exponentiel.
>>> import math
>>> math.factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
>>> math.factorial(1000)
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Notez bien que les problèmes difficiles sont donc décidables en théorie mais que l'ordinateur ne répondra certainement pas assez rapidement pour qu'ils soient décidables en pratique.
Nous allons tenter de voir expérimentalement, comment évolue notre algorithme de recherche.
Pour répondre expérimentalement à la question, nous allons modifier un peu notre algorithme de recherche : nous allons insérer un print() de façon à afficher le nombre de tours de boucle effectuées.
10° Réaliser les actions suivantes :
1
2
3
4
5
6
7
8
9
10
11
12
13 | def rechercher(t:list, x:'élément') -> int:
"""Renvoie l'indice de la première occurrence de x dans t, -1 si non présent"""
i = 0
longueur = len(t)
while i < longueur and t[i] != x:
i = i + 1
print(i+1)
if i < longueur:
reponse = i
else:
reponse = -1
return reponse
|
>>> valeurs = [x for x in range(100)]
>>> rep = rechercher(valeurs, -10)
>>> valeurs = [x for x in range(1000)]
>>> rep = rechercher(valeurs, -10)
>>> valeurs = [x for x in range(10000)]
>>> rep = rechercher(valeurs, -10)
...CORRECTION...
100 données, 100 boucles.
1000 données, 1000 boucles.
10000 données, 10000 boucles.
On voit donc clairement que le coût est linéaire.
11° Dans le pire des cas, l'élément cherché n'est pas présent dans le tableau. En déduire le nombre de fois où on réalise la boucle et donc la comparaison si on considère que le tableau contient n données.
...CORRECTION...
Le tableau contient n cases.
Il va falloir les explorer une par une jusqu'à la dernière.
Puisqu'on explore une case par tour de boucle, on en déduit qu'on aura besoin de n tours de boucle.
On voit donc clairement que le coût est linéaire par rapport à n.
Ces notations ne sont pas explicitement du programme. Néanmoins, la recherche de coût revient en réalité à étudier ces notions. Je présente donc ici deux notations intéressantes, mais il en existe d'autres.
Commençons par voir la notation 𝓞 (qu'on prononce GRAND O) qui permet de définir une borne supérieure au comportement d'un algorithme.
Nous allons donc classer les coûts dans l'ordre suivant (du meilleur au pire) :
Parfois, on ne peut pas trouver facilement le comportement exact d'un algorithme. Son comportement peut être très variable en fonction des entrées fournies par exemple.
Cette notation va permettre de préciser que notre algorithme se comporte au pire de cette façon.
On obtient une indication un peu similaire à "inférieur ou égal" vis à vis des complexités.
Exemple n°1 :
𝓞(n2) veut dire que notre algorithme se comporte peut-être en n2, ou en n, ou en log2(n) ou même en 1.
Le coût est inférieur ou égal à un coût quadratique.
Exemple n°2 :
𝓞(n4) veut dire que notre algorithme se comporte peut-être en n4, ou en n3, ou moins encore.
Le coût est inférieur ou égal à un coût polynomial en n4.
Exemple n°3 :
𝓞(n) veut dire que notre algorithme se comporte peut-être en n, ou en n1/2 ou n, ou en log2(n) ou en moins encore.
Le coût est inférieur ou égal à un coût linéaire.
Exemple n°4 :
𝓞(2n) veut dire que notre algorithme se comporte peut-être en n4, ou en n3 ou moins encore.
Le coût est inférieur ou égal à un coût exponentiel (puissance de 2 ici).
Parfois, on connait mieux l'algorithme que cela. On peut prévoir comment il réagit vraiment et pas juste donner une borne supérieure à son comportement.
On utilise alors la notation 𝞗 (on prononce Theta).
Pour comparer les complexités des algorithmes entre eux, on utilise la notation suivante par exemple :
f(n) = 𝞗(n2) indique que la fonction f(n) se comporte d'une façon similaire à n2 pour les grandes valeurs de n.
On obtient une indication un peu similaire à "se comporte toujours comme" vis à vis des complexités.
Exemple n°1
Si f(n) = 4 n2 + 100 n + 6, on doit écrire f(n) = 𝞗(n2) uniquement.
Exemple n°1
Si f(n) = 12 n3 - 500 n + 10000, on doit écrire f(n) = 𝞗(n3) uniquement.
Le principe est donc de ne garder que l'allure la plus rapide et de négliger tous les facteurs constants.
12° Trouver la complexité des algorithmes dont on vous donne l'expression mathématique du nombre d'opérations à effectuer en fonction du nombre n de données d'entrée.
f(n) = 10 n4 + 3 n2 + 4000 n
f(n) = 300 n3 + 9000 n2 + 10 n
f(n) = 9000 n2 + 10 n
... CORRECTION ...
f(n) = 10 n4 + 3 n2 + 4000 n
On voit que f(n) évolue comme une fonction n4 pour les grandes valeurs de n.
On peut écrire f(n) = 𝞗(n4).
On pourrait également écrire
f(n) = 300 n3 + 9000 n2 + 10 n
On voit que f(n) évolue comme une fonction n3.
On peut écrire f(n) = 𝞗(n3).
f(n) = 9000 n2 + 10 n
On voit que f(n) évolue comme une fonction n2.
On peut écrire f(n) = 𝞗(n2).
13° Imaginons que les trois algorithmes répondent à au même problème. Lequel est le plus performant d'un point de vue algorithmique ?
Cet algorithme à coût linéaire : f(n) = 4000 n + 60
Cet algorithme à coût cubique : f(n) = 300 n3 + 9000 n2 + 10 n
Cet algorithme à coût quadratique : f(n) = 9000 n2 + 10 n
... CORRECTION ...
Puisqu'on néglige tous les coefficients, l'algorithme le plus performant sur les données en grand nombre est l'algorithme linéaire.
Il s'agit de la fonction logarithme (ici en base 2).
C'est une fonction extrêmement utile : on peut la voir en première approximation comme la fonction qui renvoie la puissance de 2 permettant d'écrire le nombre.
Quelques exemples avec Python
>>> import math
>>> math.log2(1)
0.0
Pourquoi ? Simplement car 1 = 20. On renvoie 0.
>>> math.log2(2)
1.0
Pourquoi ? Simplement car 2 = 21. On renvoie 1.
>>> math.log2(4)
2.0
Pourquoi ? Simplement car 4 = 22. On renvoie 2.
>>> math.log2(8)
3.0
Pourquoi ? Simplement car 8 = 23. On renvoie 3.
Le mieux, c'est que cela fonctionne également avec les valeurs qui ne sont pas une puissance entière de 2 !
>>> math.log2(6)
2.584962500721156
Pourquoi ? Simplement car 6 = 22.584962500721156. On renvoie 2.584962500721156. Si vous avez bien compris l'activité sur les floats, vous devriez comprendre qu'il s'agit certainement d'une valeur approximative.
Il existe un logarithme pour toutes les bases possibles et imaginables.
Le logarithme base 10 donne ainsi log10(1000) = 3 puisque 1000 = 103
Ou encore le logarithme népérien ln qui est en lien avec la fonction exponentielle : ln(20) = 2.995732273553991 car on peut écrire
Oui.
Lorsqu'on parle simplement de log, on parle du log dans une base donnée. Si c'est rien n'est précisé, c'est certainement la base 10.
Habituellement, si on note juste log, on parle du log10.
Si on note lg(x), on parle de log2(x) dans un contexte informatique. Cela évite de noter log10(x). On note juste lg(x)
Attention donc au contexte dans lequel apparaît un logarithme.
Activité publiée le 17 03 2024
Dernière modification : 17 03 2024
Auteur : ows. h.