Nous allons voir 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 : au début du tour k, i = k et l'élément x cherché n'est pas dans le sous-tableau t[0 .. k].
Démontrer la phase d'initialisation de notre algorithme de recherche en utilisant l'INVARIANT fourni.
Rappel de la fonction de recherche :
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...
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
7 | i = 0
longueur = len(t)
while 0 < longueur and t[0] != x:
# début de Ligne 7 sans la faire pour le moment
|
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 : au début du tour 0, i = 0 et l'élément x cherché n'est pas dans le sous-tableau t[0 .. 0] = t[0].
D'après nos lignes 4 et 6, c'est vrai sur le premier tour de boucle.
◻
Conservation
08° On considère l'invariant Pk suivant :
Pk : au début du tour k, i = k et l'élément x cherché n'est pas dans le sous-tableau t[0 .. k].
Démontrer la phase de la conservation.
Rappel de la fonction de recherche :
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...
Hypothèse de départ : Pk est vraie
Pk : au début du tour k, i = k et l'élément x cherché n'est pas dans le sous-tableau t[0 .. k].
Fin du tour de boucle k
D'après l'hypothèse Pk, on est en début de ligne 7 avec i = k et t[i] différent du x cherché puisque x n'est pas dans t[0 .. k].
6
7 | while i < longueur and t[i] != x:
i = i + 1
|
L7 : i passe de k à k+1.
x n'est toujours pas dans t[0 .. k].
Début du tour de boucle k+1
On repart en ligne 6 avec i = k+1. Au vu des deux conditions dans le while, si on commence bien un nouveau tour, c'est que :
Puisque x n'est pas dans t[0 .. k] ni dans t[k+1], on en déduit que x n'est pas dans t[0 .. k+1].
On atteint donc 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 : au début du tour k, i = k et l'élément x cherché n'est pas dans le sous-tableau t[0 .. k].
Démontrer la phase de terminaison de la boucle et en déduire la correction de la fonction.
Rappel de la fonction de recherche :
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.
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 une case d'indice k contenant x.
Nous avons montré l'initialisation et la conservation lors des questions 7 et 8. Démontrons la terminaison de la boucle dans ce cas.
Le dernier tour est le tour (k-1) puisque t[k-1] != x.
Donc Pk-1 est vérifiée.
Donc x n'est pas dans t[0 .. k-1].
A la fin de la dernière boucle, i passe de k-1 à k avec t[k] = x.
Fin du TANT QUE car la condition de poursuite n°2 n'est plus valide.
On atteint la ligne 8 avec i = k et puisque i est inférieur à n, on place cet indice dans la réponse.
Correct sur ce cas.
CAS C : on atteint la fin du tableau de taille n.
On considère n valeurs dont les indices vont de 0 à (n-1).
Nous avons montré l'initialisation et la conservation lors des questions 7 et 8. Démontrons la terminaison de la boucle dans ce cas :
On commence la dernière boucle avec i = k = n-1.
Puisque Pn-1 est vérifiée, on a ceci en début de boucle :
A la fin de cette boucle, i passe de n-1 à n.
Fin du TANT QUE car la condition de poursuite n°1 n'est plus valide.
On atteint la ligne 8 : n n'est pas inférieur à n. On passe donc en ligne 10 puis 11 : on répond bien -1 pour signaler qu'on ne trouve pas x.
Correct sur ce cas.
Nous avons traité les 3 cas possibles.
L'algorithme est correct.
◻
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.
PROBLEMES FACILES
Facile veut dire qu'on peut utiliser un programme qui fournira la réponse en un temps raisonnable.
Si on modifie le nombre n de données, le nombre d'opérations élémentaires op reste le même.
Exemple
C'est donc pas mal !
Si on multiple par k le nombre n de données, alors on augmente juste op de 1.
Plus k est grand, plus l'algorithme va être rapide. Quelques exemples où le coût devient de moins en moins bon :
Si on multiple par 2 le nombre n de données, alors on augmente juste op de 1.
De façon plus détaillée,
Exemple
Ce coût se situe donc entre CONSTANT et LINEAIRE.
Si on multiple par 2 le nombre n de données, on multiple par la constante 2k le nombre op d'opérations élémentaires.
Plus k est grand, plus l'algorithme va être lent. Quelques exemples où le coût devient de moins en moins bon :
Si on double le nombre n de données, on double le nombre op d'opérations élémentaires.
De façon plus mathématique,
Exemple
C'est un peu plus long que du coût constant.
Si on double le nombre n de données, on quadruple le nombre op d'opérations élémentaires.
De façon plus mathématique,
Exemple
Cela devient réellement de plus en plus grand lorsque les données deviennent importantes.
Si on double le nombre n de données, on multiplie par la constante 2k le nombre op d'opérations élémentaires.
De façon plus mathématique,
PROBLEMES DIFFICILES
Difficile veut dire qu'on peut utiliser un programme mais qu'il fournira la réponse en un temps déraisonnable lorsque le nombre de données n deviendra grand.
Si on double le nombre n de données, on multiplie par kn le nombre op d'opérations élémentaires. Notez bien que le facteur multiplicatif n'est donc plus une constante par rapport à n.
Cela veut également dire que si on augmente juste de 1 le nombre n de données, on multiplie par k le nombre op d'opérations élémentaires.
Plus k est grand, plus l'algorithme va être lent.. Quelque exemples où le coût devient de moins en moins bon :
Si on double le nombre n de données, on multiplie par 2n le nombre op d'opérations élémentaires. Notez bien que le facteur multiplicatif n'est donc plus une constante par rapport à n.
Cela veut également dire que si on augmente juste de 1 le nombre n de données, on multiplie par 2 le nombre op d'opérations élémentaires.
Exemple 1 où on augmente les données de 1 à la fois
Exemple 2 où on double les données :
On voit bien qu'avec une évolution exponentielle (même base 2, la moins "grave"), on perd rapidement la possibilité de réaliser tous les calculs nécessaires :
>>> 2**100
1267650600228229401496703205376
>>> 2**1000
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
On notera bien que n est en position d'exposant.
Par définition, la factorielle de n vaut n*(n-1)*(n-2)*...*3*2*1.
Lorsqu'on double le nombre de données, on passe donc de n! à (2n)!.
Cela veut dire qu'on prend le nombre d'opérations nécessaires pour n! et qu'on les multiplie par (n+1)*(n+2)*(n+3)*...*(n+n).
On a donc n multiciplication à faire par des facteurs qui sont tous plus grand que n.
On doit donc multiplier le nombre d'opérations par un facteur plus grand que nn. C'est donc encore pire que le coût exponentiel.
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
PROBLEMES INDECIDABLES
Notez bien que les problèmes faciles et difficiles sont décidables (le programme finira toujours par fournir une réponse si on lui laisse le temps).
Il existe des problèmes encore plus complexes :: les problèmes indécidables. Sur ces problèmes, l'ordinateur répond parfois mais par sur une infinité de calculs sur d'autres entrées. Et dans ce cas, il ne pourra jamais vous répondre.
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.
Rechercher un coût revient à se demander l'allure de la fonction qui simule le nombre d'opérations fondamentales à réaliser pour répondre au problème lorsque les données n augmentent.
On parle de coût asymptotique car on se demande ce qui se passe lorsque n devient asymptotiquement grande.
Lorsqu'on est confronté à un algorithme qui possède plusieurs phases ayant chacune son propre coût, comment faire ?
Facile.
On prend le coût le moins favorable.
Considérons un algorithme composé :
Si on ajoute les trois, cela donne 4*1 + 2*n3 + 10*n2.
On ne garde que le coût le plus défavorable : 2*n3.
On supprime le facteur constant : n3.
Le coût de cet algorithme est donc un coût cubique.
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.
Cette notation se note GRAND O.
Parfois, on ne peut pas trouver le comportement exact d'un algorithme. Son comportement peut être très variable en fonction des entrées fournies par exemple.
Cette notation indique que dans le pire des cas, l'algorithme aura ce coût.
On obtient donc une indication 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 : on peut prévoir comment il réagit vraiment.
On utilise alors la notation 𝞗 (on prononce Theta).
Cette notation se note 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.