Algo Démonstration

Identification

Infoforall

4 - Terminaison, correction, coût


Nous allons voir comment l'algorithmique permet de prouver :

  • qu'un algorithme s'arrête toujours, ou pourrait boucler parfois
  • qu'un algorithme fournit toujours la bonne valeur, ou pourrait se tromper parfois
  • qu'un algorithme répond vite ou trop lentement

Evaluation Bonus pour les plus rapides : deux questions

Documents de cours : open document ou pdf

1 - Complément : les suites

1.1 Suite

Définition : suite

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

  • Le terme u0 est le 10
  • Le terme u1 est le 7
  • Le terme u2 est le 4
Théorème général

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.

1.2 Suite arithmétique

Formules pour les suites arithmétiques

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

  • de valeur initiale u0 = 5 (on part de 5)
  • de raison r = 10 (on rajoute 10 à chaque fois qu'on passe au successeur)

A partir de ces deux informations, on peut obtenir les valeurs successives des éléments de la suite.

  • u0 = 5
  • u1 = 15      car u1 = u0 + 10
  • u2 = 25      car u2 = u1 + 10
  • u3 = 35      car u3 = u2 + 10
  • u4 = 45      car u4 = u3 + 10

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
  • u4 = 45      car u4 = 5 + 4*10
  • u1000 = 10005      car u1000 = 5 + 1000*10
Suite croissante ou décroissante

Puisqu'on ajoute la raison pour obtenir le terme suivant :

  • Toute suite arithmétique dont la raison est positive (mais différente de 0) est nécessairement croissante
  • Avec une raison de 2 : 10, 12, 14, 16, 18...

  • Toute suite arithmétique dont la raison est négative est nécessairement décroissante
  • 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 !

Théorème

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)

J'ai des flottants ! Comment je fais ?

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

  • Quelle est la raison de cette suite ?
  • On considère que le premier terme u0 vaut 100. Donner les valeurs du terme u1,
  • u2,
  • u3 et
  • u4.
  • L'un des autres futurs termes de la suite peut-il être nul ou négatif ?

...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

  • Quelle est la raison de cette suite ?
  • On considère que le premier terme u0 vaut 100. Donner les valeurs du terme u1,
  • u2,
  • u3 et
  • u4.
  • L'un des autres futurs termes de la suite peut-il être nul ou négatif ?

...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.

1.3 Suite géométrique

Formules pour les suites géométriques

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

  • de valeur initiale v0 = 5 (on part de 5)
  • de raison q = 2 (on multiplie par 2 à chaque fois qu'on passe au successeur)

A partir de ces deux informations, on peut obtenir les valeurs successives des éléments de la suite.

  • v0 = 5
  • v1 = 10      car v1 = v0 * 2
  • v2 = 20      car v2 = v1 * 2
  • v3 = 40      car v3 = v2 * 2
  • v4 = 80      car v4 = v3 * 2

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
  • v4 = 80      car v4 = 5 * 24 = 5 * 16 = 80
  • v1000 = beaucoup trop      car v1000 = 5 * 2**1000
Suite croissante ou décroissante

Attention aux flottants : puisqu'on multiplie la raison pour obtenir le terme suivant, on devrait pouvoir dire en théorie que

  • Toute suite géométrique à valeurs positives dont la raison (positive) est strictement supérieure à 1 est strictement croissante
  • Avec une raison de 10 : 5, 50, 500, 5000, 50000...

  • Toute suite géométrique à valeurs positives dont la raison (positive) est strictement inférieure à 1 est strictement décroissante
  • 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
Théorème

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.

2 - Preuve de terminaison ou preuve d'arrêt

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.

2.1 Preuve de terminaison et VARIANT

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 :

  • Proposition A : les boucles s'expriment sous la forme TANT QUE VARIANT > 0
  • Proposition B : le VARIANT est une suite d'ENTIERS strictement décroissante.

(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.

2.2 Preuve de terminaison : exemple

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

  1. une condition de poursuite de type while VARIANT > 0
  2. avec un variant VARIANT = uN = 97 - 10*n qui est donc une suite d'entiers strictement décroissante.

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

  1. une condition du type  while uN > 0 
  2. avec  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

  1. une condition du type  while uN > 0 
  2. mais avec  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 ?

2.3 Preuve de terminaison : le cas des TANT QUE plus compliqués

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

  1. une condition du type  while uN > 0 
  2. avec  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.

Nous venons de voir à l'aide de la notion de variant de boucle comment prouver qu'une boucle se termine.

Par contre, la terminaison ne permet pas de prouver que l'algorithme est correct, c'est à dire renvoie le bon résultat. Nous prouvons juste qu'il donnera une réponse pour l'instant.

3 - Preuve de correction

Attention au vocabulaire français et informatique

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.

3.1 TESTER n'est pas PROUVER

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.

3.2 Preuve de correction et INVARIANT

Définitions

La preuve de correction d'un algorithme permet d'affirmer

  • qu'il fournit toujours une réponse correcte
  • sur toutes les entrées valides qu'on lui fournit.

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.

Démonstration en 3 phases : Initialisation-Conservation-Terminaison

Une fois qu'on dispose d'un INVARIANT P, la démonstration se fait en trois temps.

  1. Phase d'initialisation : P0 est VRAI
  2. 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...

  3. Phase de conservation : Pk Pk+1
  4. SI P est vrai après k tours de boucles, ALORS P sera encore vrai en ayant fait un tour de boucles supplémentaire.

    1. Hypothèse de départ :
    2. 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.

    3. Déroulement du tour de boucle (k+1) jusqu'au début du prochain
    4. 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.

    5. On peut donc écrire Pk Pk+1
  5. Phase de terminaison
  6. 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

    Preuve de correction de boucle et preuve de correction de l'algorithme

    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 :

  • i = k+1 est un indice valide
  • la case i = k+1 ne contient pas x : t[k+1] != x

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 :

  • i = k+1
  • x n'est pas dans t[0 .. k+1]

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 :

  • i = n-1
  • x n'est pas dans t[0 .. n-1]

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.

3.3 En math : preuve par récurrence, à l'infini

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 :

  • Lors d'une preuve par récurrence, on veut montrer que c'est TOUJOURS VRAI, jusqu'à l'infini. Cela ne s'arrête jamais.
  • Lors d'une preuve de correction, on veut montrer que cela va finir par fournir la bonne réponse au bon moment.

C'est pour cela que les phases ne portent pas exactement les mêmes noms sur ces deux preuves.

  1. Phase 1 : P0
  2. Nommée phase d'initialisation dans les deux cas.

  3. Phase 2 : Pk Pk+1
  4. 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.

  5. Phase 3
  6. 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.

4 - Complexité et coût

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.

4.1 (Rappel) - Introduction à la notion de coût d'un algorithme

Définition

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.

Coût constant (noté 1 ou CST)
Si n*2 alors op inchangé

Si on modifie le nombre n de données, le nombre d'opérations élémentaires op reste le même.

Exemple

  • Avec n = 6 données, on a besoin de op = 5 opérations élémentaires.
  • Si n*2 (n = 12), alors op = 5.
  • Si n*4 (n = 24), alors op = 5.
  • Si n*8 (n = 48), alors op = 5.

C'est donc pas mal !

Les coûts logarithmiques (notés logk(n)
si n*k alors op+1

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 :

  • log10 : n*10 alors op+1. Celui-ci est souvent utilisé en physique-chimie.
  • log3 : n*3 alors op+1
  • loge ou juste ln : n*e alors op+1. e est la constante de Néper qui vaut approximativement 2,71. Ce logarithme particulier se nomme d'ailleurs le logarithme népérien.
  • log2 ou juste lg  : n*2 alors op+1. C'est celui qu'on rencontre le plus souvent en informatique.
dont le coût logarithmique base 2 (noté log2(n) ou lg(n) )
si n*2 alors op+1

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,

  • si n est multiplié par 2, alors on augmente juste op de 1;
  • si n est multiplié par 4, alors on augmente juste op de 2;
  • si n est multiplié par 8, alors on augmente juste op de 3;
  • ...

Exemple

  • Avec n=6 données, on a besoin de op=5 opérations élémentaires.
  • Si n*2 (12 données), on aura op+1 soit 5+1=6 opérations.
  • Si n*4 (24 données), on aura op+2 soit 5+2=7 opérations.
  • Si n*8 (48 données), on aura op+3 soit 5+3=8 opérations.

Ce coût se situe donc entre CONSTANT et LINEAIRE.

Les coûts polynomiaux (notés nk)
Si n*2 alors op*constante (on notera que la constance vaut 2k)

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 :

  • n1 : n*2 alors op*2 : le coût linéaire.
  • n2 : n*2 alors op*22 : le coût quadratique.
  • n3 : n*2 alors op*23 : le coût cubique.
dont le coût linéaire (noté n)
Si n*2 alors op*2

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,

  • si n est multiplié par 2, alors on multiple op par 2;
  • si n est multiplié par 3, alors on multiple op par 3;
  • si n est multiplié par 4, alors on multiple op par 4
  • ...

Exemple

  • Avec n=6 données, on a besoin de op=5 opérations élémentaires.
  • Si n*2 (12 données), on aura op*2 soit 5*2=10 opérations.
  • Si n*4 (24 données), on aura op*4 soit 5*4=20 opérations.
  • Si n*8 (48 données), on aura op*8 soit 5*8=40 opérations.

C'est un peu plus long que du coût constant.

dont le coût quadratique (noté n2)
Si n*2 alors op*(22)

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,

  • si n est multiplié par 2, alors on multiple op par 22;
  • si n est multiplié par 3, alors on multiple op par 32;
  • si n est multiplié par 4, alors on multiple op par 42
  • ...

Exemple

  • Avec n=6 données, on a besoin de op=5 opérations élémentaires.
  • Si n*2 (12 données), on aura op*22 soit 5*4=20 opérations.
  • Si n*4 (24 données), on aura op*42 soit 5*16=80 opérations.
  • Si n*8 (48 données), on aura op*82 soit 5*64=320 opérations.

Cela devient réellement de plus en plus grand lorsque les données deviennent importantes.

et tous les autres coûts polynomiaux (notés nk)
Si n*2 alors op*(2k)

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,

  • si n est multiplié par 2, alors on multiple op par 2k;
  • si n est multiplié par 3, alors on multiple op par 3k;
  • si n est multiplié par 4, alors on multiple op par 4k
  • ...

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.

Coût exponentiel (noté kn)
Si n*2 alors op*(kn), ou encore si n+1 alors op*k

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 :

  • 2n : n+1 alors op*2. L'exponentielle base 2 est rencontrée assez souvent en informatique.
  • en : n+1 alors op*e. e est la constante de Néper qui vaut approximativement 2,71. Cette fonction exponentielle particulière se nomme juste "fonction exponentielle".
  • 3n : n+1 alors le op*3. L'exponentielle base 3.
  • 10n : n+1 alors le op*10. L'exponentielle base 10.
dont l'exponentielle base 2 (noté 2n)
Si n*2 alors op*(2n), ou encore si n+1 alors op*2

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

  • Avec n=1 données, on a besoin de op=5 opérations élémentaires.
  • Si on passe de 1 à 2 données (n+1 avec n=1), on aura op*2 soit 5*2=10 opérations.
  • Si on passe de 2 à 3 données (n+1 avec n=2), on aura op*2 soit 10*2=20 opérations.
  • Si on passe de 3 à 4 données (n+1 avec n=3), on aura op*2 soit 20*2=40 opérations.
  • Si on passe de 4 à 5 données (n+1 avec n=4), on aura op*2 soit 40*2=80 opérations.

Exemple 2 où on double les données :

  • Avec n=6 données, on a besoin de op=5 opérations élémentaires.
  • Si on passe de 6 à 12 données (n*2 avec n=6), on aura op*2n soit 5*26=5*64=320 opérations.
  • Si on passe de 12 à 24 données (n*2 avec n=12), on aura op*2n soit 320*212=320*4096=1310720 opérations.

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.

Coût factoriel (noté n!)
Si n*2 alors plus que op*((n+1)n) opérations car op dépend de n!= n*(n-1)*(n-2)*...*3*2*1.

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

  • Avec n = 1 donnée, n! = 1 = 1.
  • Avec 2, n! = 1*2 = 2.
  • Avec 3, n! = 1*2*3 = 6.
  • Avec 4, n! = 1*2*3*4 = 24.
  • Avec 5, n! = 1*2*3*4*5 = 120.
  • Avec 6, n! = 1*2*3*4*5*6 = 720.
  • Avec 7, n! = 1*2*3*4*5*6*7 = 5040.
  • Avec 8, n! = 1*2*3*4*5*6*7*8 = 40320.

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. Lancer cette version de la fonction rechercher() et le programme principal associé.
  2. 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
  3. Réaliser alors les instructions suivantes dans la console (on crée un tableau d'entiers positifs, on cherche une valeur négative qui ne peut pas s'y trouver et on observe le nombre de tours de boucle réalisés avant réponse) :
  4. >>> 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)
  5. Question : combien de tours de boucle pour 100, 1000 et 10000 données à traiter ?
  6. Question : lorsqu'on fournit à cet algorithme un tableau de n éléments, le coût de cet algorithme de recherche est-il lié
    1. à 1 (on parle de coût constant) ?
    2. à log2(n) (on parle de coût logarithmique) ?
    3. à n (on parle de coût linéaire) ?
    4. à n2 (on parle de coût quadratique) ?
    5. à n3 (on parle de coût cubique) ?
    6. à 2n (on parle de coût exponentiel) ?

...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.

4.2 - coût : combiner différentes parties de l'algorithme

A - Principe

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.

B - Exemple

Considérons un algorithme composé :

  • D'une première partie composée de 4 actions à coût constant : 4*1.
  • D'un deuxième partie composée d'un boucle dont le coût est 2*n3.
  • D'une dernière partie dont le coût est quadratique en 10*n2.

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.

Nous avons donc pu montrer formellement que :

  1. L'algorithme de recherche se termine à chaque fois à l'aide d'une preuve de terminaison.
  2. L'algorithme fournit toujours la bonne réponse à l'aide d'une preuve de correction.

  3. L'algorithme est linéaire (et la recherche est donc un problème facile) en étudiant le nombre d'instructions basiques à effectuer.

Un peu de vocabulaire pour la route :

Lorsqu'on dispose d'une preuve de correction mais pas de la preuve de terminaison, on parle de correction partielle : on a juste montré que lorsque l'algorithme répond, il répond bien. Mais il est possible qu'il tourne en boucle et ne réponde jamais...

Si on démontre d'une preuve de correction et d'une preuve de terminaison, on parle de correction totale.

5 - Notations 𝓞 et 𝞗 (culture générale)

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.

5.1 - Définition simplifiée de la notation 𝓞 : borne supérieure du coût de l'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).

5.2 - Définition simplifiée de la notation 𝞗 : comportement exact de l'algorithme

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) = 𝞞(n4) ou
  • f(n) = 𝞞(n5) ou pire
  • f(n) = 𝞞(2n) puisque cette notation indique "une complexité inférieure ou égale".

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.

6 - FAQ

J'ai vu O(log2 n). C'est quoi ce truc ?

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

  • 20 = e2.995732273553991 ou encore
  • 20 = exp(2.995732273553991)

Log et Lg, c'est différent ?

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.

Dans la prochaine activité, nous verrons d'autres algorithmes sur les tableaux. Ensuite, il sera temps de voir un premier algorithme permettant de faire de l'intelligence artificielle, à savoir de l'analyse de données à un niveau inaccessible à un observateur humain.

Activité publiée le 17 03 2024
Dernière modification : 17 03 2024
Auteur : ows. h.