Nous allons voir que l'algorithmique permet d'utiliser des théorèmes sur les algorithmes et prouver :
Documents de cours : open document ou pdf
Exercices supplémentaires 🏠 : sur le site
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 qu'aucune des boucles présentes dans l'algorithme ne peut prvoquer de bouclage infini.
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).
[Théorème de la] Preuve de terminaison (en français) :
Si les deux propositions A et B suivantes sont vraies alors la boucle s'arrête :
Justification : si le variant est effectivement une suite entière décroissante, il va nécessairement décroître et devenir négatif ou nul. Cela va alors provoquer l'arrêt de la boucle puisqu'on boucle tant qu'il est positif uniquement.
[Théorème de la] Preuve de terminaison (en langage mathématique) :
Cette écriture peut se traduire de ces deux façons similaires :
Si A est vrai et B est vrai, alors l'algorithme s'arrête TOUJOURS au bout d'un certain temps.
A vrai et B vrai implique que l'algorithme s'arrête TOUJOURS au bout d'un certain temps.
Attention à la négation
Si A ou B sont faux, on n'apprend rien sur l'arrêt certain de l'algorithme : il est possible que l'algorithme s'arrête toujours, boucle parfois ou boucle toujours.
Il s'agit bien d'une implication, pas d'une équivalence.
(A et B) ⇒ Arrêt
non (A et B) ⇒ Aucune information certaine Les formules de De Morgan permettent d'ailleurs de l'écrire de cette façon également : (non A) ou (non B) ⇒ Aucune information certaine Cela veut bien dire : "Si A est faux ou si B est faux alors on ne peut tirer aucune conclusion sur l'arrêt certain ou pas de cette boucle".
Prenons ce court programme :
1
2
3 | x = 3
while x < 100:
x = x + 10
|
Nous allons tenter de prouver sa terminaison en utilisant le théorème de la preuve de terminaison :
(A et B) ⇒ Arrêt
1 - AVANT le premier tour
(Ligne 1) x vaut 3
2 - PENDANT un tour
(Ligne 3) x augmente de 10 à chaque tour. En notant n le nombre de tours effectués, on peut écrire :
x = 3 + 10*n (Formule 1 où n est le nombre de tours)
3 - Recherche du VARIANT
On tente de mettre la condition de boucle de la ligne 2 sous cette forme :
L2 | while VARIANT > 0
|
On commence en récupérant la condition de boucle et en remplaçant x par la formule (1).
L2 | while x < 100
|
L2 | while 3 + 10*n < 100
|
Pour revenir au symbole "supérieur à", on transforme a < b en b > a :
L2 | while 100 > 3 + 10*n
|
Pour obtenir 0 à droite, on passe tout à 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
|
C'est une suite d'entiers puisque 97, 10 et n sont des entiers.
Cette suite arithmétique est strictement décroissante puisque la raison r vaut -10.
4 - Conclusion
Utilisons la preuve de terminaison : (A et B) ⇒ Arrêt :
Les deux propriétés A et B 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...
Utilisons le théorème de la preuve de terminaison :
A et B ⇒ Arrêt
1 - AVANT le premier tour
(Ligne 6) x vaut 0
2 - PENDANT un tour
(Ligne 8) On augmente x de 1 à chaque tour de boucle.
Si on note n le nombre de tours de boucle, on peut écrire :
x = 0 + 1*n = n
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 remplaçant x par n.
L7 | while 5*x < seuil
|
L7 | while 5*n < seuil
|
L7 | while 5*n < seuil
|
L7 | while seuil > 5*n
|
Pour obtenir 0 à droite, on passe tout à 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
|
Le variant est une suite d'entiers puisque seuil, 5 et n sont des entiers.
La raison vaut r=-5, le variant est donc strictement décroissant.
4 - Conclusion
Utilisons le théorème de la preuve de terminaison : A et B ⇒ Arrêt :
Les deux propriétés A et B 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...
Utilisons le théorème de la preuve de terminaison :
A et B ⇒ Arrêt :
1 - AVANT le premier tour
(Ligne 6) x vaut 0.
2 - PENDANT un tour
(Ligne 8) On diminue x de 1 à chaque tour de boucle. Si n est le nombre de tours de boucle :
x = 0 - 1*n = -n
3 - Recherche du VARIANT
On cherche à ramener la condition de boucle de la ligne 7 à une forme de ce type :
L7 | while VARIANT > 0
|
On part du problème :
L7 | while 5*x < seuil
|
L7 | while 5*(-n) < seuil
|
L7 | while -5*n < seuil
|
L7 | while -5*n < seuil
|
L7 | while seuil > - 5*n
|
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
|
Cette suite est une suite d'entiers strictement croissante puisque la raison r=+5
4 - Conclusion
On ne prouve donc rien. Cet algorithme ne s'arrête pas "nécessairement".
Ici, comme la suite est croissante et qu'il n'y a pas d'autre condition d'arrêt, nous sommes certains 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 ?
Imaginons une boucle while C1 and C2.
Pour continuer la boucle, il faut donc que les DEUX conditions soient vraies.
Cela veut dire qu'on va arrêter de boucler si UNE des conditions est fausse .
CONCLUSION : Notre boucle a donc deux possibilités pour s'arrêter : C1 devient fausse, ou C2 devient fausse.
Pour obtenir une preuve d'arrêt simple, nous allons tenter de ne prendre en compte que l'une des deux conditions.
Analogie : si on prouve qu'une unique porte de sortie d'urgence permet d'évacuer 30 élèves en moins d'une minute, rajouter une deuxième porte de sortie ne changera à la conclusion : on peut toujours faire sortir les élèves en moins d'une minute.
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...
Utilisons le théorème de la preuve de terminaison :
A et B ⇒ Arrêt :
1 - AVANT le premier tour de boucle
(Ligne 4) i vaut 0.
2 - PENDANT chaque tour
(Ligne 7) i augmente de 1 à chaque tour de boucle. Si n désigne le nombre de tours, on peut donc écrire :
i = 0 + 1*n = n
3 - Recherche du VARIANT
On cherche à écrire la boucle comme ceci :
L6? | while VARIANT > 0
|
On commence la démonstration en récupérant la condition de boucle.
L6 | while i < longueur
|
L6 | while n < longueur
|
L6 | while n < longueur
|
L6 | while longueur > n
|
L6 | while longueur > + n
|
L6 | while longueur - n > 0
|
L6 | while VARIANT > 0 avec VARIANT = uN = longueur - 1 * n
|
On a une suite d'entiers (longueur, 1 et n sont des entiers).
Cette suite arithmétique est strictement décroissante puisque sa raison est -1.
4 - Conclusion
On applique le théorème de la preuve de terminaison :
A et B ⇒ Arrêt :
On prouve donc l'arrêt de cette boucle en ne prenant qu'une des deux conditons d'arrêt.
Lui donner une deuxième façon de s'arrêter ne modifie pas la conclusion : la boucle s'arrête toujours.
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.
On ne peut pas prouver la correction d'un algorithme en réalisant des tests.
Réaliser un milliard de tests qui fonctionnent ne permet pas d'affirmer que le test suivant sera nécessairement valide. On peut en déduire une probabilité de bonnes réponses éventuellement, mais jamais une certitude à 100 %. Or, prouver, c'est être certain à 100% que c'est vrai.
Vous allez voir ou avez déjà vu :
Lorsque les différentes valeurs d'entrée sont en nombre fini, on peut tester une par une toutes les possibilités. Si on ne tombe jamais sur un cas faux, c'est que l'algorithme fonctionne correctement.
C'est le cas avec le morpion : 9 cases, 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.
C'est ce type de démonstration que nous avons utilisé lorsque nous avons montré que
not(a or b) = not(a) or not(b)
Il n'y a que 4 cas différents à tester : 00, 01, 10 et 11. Il suffit donc de comparer la sortie des deux tables de vérité.
On ne peut pas faire de démonstration par cas : il en a une infinité.
Aucune valeur maximale de la longueur du tableau et aucune contrainte sur le contenu des cases.
Il va falloir prouver cela autrement.
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
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 avant le premier tour de boucle. On a donc fait 0 tour en entier.
Le plus souvent, cette partie est triviale.
On fait l'hypothèse que la propriété Pk est vraie après un certain nombre de tours de boucle.
On doit montrer qu'en réalisant un tour supplémentaire, l'invariant P reste vrai à la fin de cette boucle. Pk+1 sera donc vérifiée.
On doit prouver qu'après le dernier tour, l'algorithme termine exactement sur la situation voulue. Ni trop, ni trop peu.
C'est pour cela qu'on nomme cet étape "la phase de terminaison", à ne pas confondre avec la preuve de terminaison / preuve d'arrêt.
On utilisant (1) + (2), on montre ceci :
P0 ➡ P1 ➡ P2 ➡ P3... >
On utilisant (3), on montre en plus que l'algorithme s'arrête au bon moment.
P0 ➡ P1 ➡ P2 ➡ P3... ➡ Pfinal
Prouver la correction d'un algorithme, c'est prouver qu'il répond correctement.
Parfois la boucle n'est qu'un des éléments de l'algorithme.
On prouve alors la correction de la boucle puis on utilise le résultat de cette preuve pour conclure sur l'algorithme en lui-même.
07° On considère l'INVARIANT Pk suivant :
Pk : après k tours effectués, on peut affirmer que
Notez l'INVARIANT sur votre copie.
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...
On considère que nous n'avons pas effectué de tour de boucle pour le moment.
On a donc k = 0. On doit prouver que :
P0 :
◻
08° On considère l'invariant Pk suivant :
Pk : après k tours effectués, on peut affirmer que
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
On ne sait donc si Pk est vraie ou pas mais on fait l'hypothèse que c'est vrai.
Pk : après k tours effectués, on peut affirmer que
On effectue un tour de boucle supplémentaire
On suppose que Pk est vraie. On en déduit que
Puisqu'on considère qu'on réalise un tour supplémentaire, les conditions du while sont nécessairement vraies (voir ligne 6) : l'indice k existe dans ce tableau et x n'est pas dans la case d'indice k.
6 | while i < longueur and t[i] != x:
|
Dans ces conditions, on effectue la ligne 7, et on incrémente i : i=k+1.
On revient alors en ligne 6.
Après ce nouveau tour de boucle, on peut donc affirmer que
C'est exactement la propriété Pk+1.
◻
09° On considère l'invariant Pk suivant :
Pk : après k tours effectués, on peut affirmer que
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 : i n'est pas strictement inférieur à 0.
On atteint la ligne 8. Puisque i n'est toujours pas inférieur à 0, on atteint la ligne 10 puis 11 : on répond bien -1 pour signaler qu'on ne trouve pas x dans ce tableau vide.
Correct sur ce cas.
CAS B : on atteint une case d'indice k contenant x : t[k] = x.
Nous avons fait k tours et la propriété Pk est vraie.
On ne fait pas de tour supplémentaire puisque t[k] contient bien x.
On sort de la boucle à cause de la deuxième condition.
On atteint la ligne 8 avec i=k et puisque i est inférieur à la longueur, on place cet indice k dans la réponse.
Correct sur ce cas puisqu'on a bien t[k]=x.
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 fait n tours et la propriété Pn est vraie : x ne se trouve pas dans [0..n-1] et i=n. On peut donc dire que x n'est pas présent dans le tableau car il n'y a plus de cases derrière.
On ne fait pas de tour supplémentaire puisque i=n n'est pas strictement inférieur à n . On sort de la boucle à cause de la première condition.
On atteint la ligne 8 puis 10 avec i=n et on place -1 dans la réponse.
Correct sur ce cas puisque x n'est pas présent dans le tableau.
Nous avons traité les 3 cas possibles.
L'algorithme est correct.
◻
La démonstration par récurrence d'une proprié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 une énorme différence avec la preuve de correction :
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.
Nommée phase d'hérédité pour une preuve par récurrence.
Nommée phase de terminaison sur une preuve de correction.
P0 ➡ P1 ➡ P2 ➡ P3...➡ PFIN et on stoppe.
Nommée phase de conclusion sur une preuve de récurrence.
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 effectués.
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.
On veut l'allure de la fonction qui simule le nombre d'opérations fondamentales à réaliser lorsque les données n augmentent.
On parle de coût asymptotique car on se demande ce qui se passe lorsque n devient asymptotiquement grand.
Lorsqu'on est confronté à un algorithme qui possède plusieurs étapes ayant chacune son propre coût, comment faire ?
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.
Cette notation indique le coût de l'algorithme dans le pire des cas.
On obtient une indication similaire à "inférieur ou égal" vis à vis des complexités : l'algorithme pourrait se mieux se comporter sur certaines entrées.
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.
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 indicationsimilaire à "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'évolution la plus importante 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).
On pourrait également écrire
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) = 90 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.
Vous la connaissez sous la forme d'énoncé de la forme "B est vrai SI ET SEULEMENT SI A est vrai".
Cela veut dire que :
En notation mathématique : A ⇔ B
Notez bien que cette notation est symétrique : A ⇔ B représente la même situation que B ⇔ A.
Vous la connaissez sous la forme d'énoncé de la forme "SI A est vrai ALORS B vrai".
Cela veut dire que :
En notation mathématique : A ⇒ B
Notez bien que cette notation n'est pas symétrique : A ⇒ B et B ⇒ A ne signifie pas la même chose.
"SI A est vrai ALORS B vrai" veut également dire que "SI B est faux ALORS A est faux".
Pourquoi ?
En notation mathématique : A ⇒ B permet donc d'écrire not(B) ⇒ not(A)
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 on note lg(x), on parle de log2(x) dans un contexte informatique. Cela évite de noter log10(x).
Activité publiée le 17 03 2024
Dernière modification : 17 03 2024
Auteur : ows. h.