Algo Preuve Sélection

Identification

Infoforall

11 - Preuve du tri par sélection


Une activité-leçon assez théorique et mathématique par certains côtés.

Quasiment toutes les questions sont munies de la correction.

Logiciel nécessaire pour l'activité : Python 3 : Thonny, IDLE ou le site repl.it ...

Prérequis : Algorithme : tri par sélection

Evaluation ✎ : questions -

Documents de cours : open document ou pdf

1 - Rappel visuel du tri et algorithme

Nous avons tout vu dans l'activité précédente. Si vous ne vous en souvenez plus trop, voici l'animation suivi de l'algorithme.

Tri par sélection du plus petit au plus grand

Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 60 89 15 56 82 1 86 97 24 86 75 6 14 69 98 31 37 89 91 56
Algorithme de tri par sélection

But : trier sur place un tableau initialement non trié.

(ici par odre croissant)

Description des entrées / sortie

  • ENTREES :
    • tableau : un tableau contenant au moins deux éléments.
    • (optionnelle selon les langages d'implémentation): longueur, le nombre d'éléments dans le tableau
  • SORTIE : aucune. Le tableau est trié sur place. On modifie directement tableau.

Exemple :

Prenons tableau = [13, 18, 89, 1024, 45, -12, 18]

Initialement le tableau contient donc cela :

Index 0 1 2 3 4 5 6
Elément 13 18 89 1024 45 -12 18

Après le tri, le tableau contiendra cela :

Index 0 1 2 3 4 5 6
Elément -12 13 18 18 45 89 1024

En Français

  • Pour chaque index debut du tableau
    • On cherche l'index index_min contenant le plus petit élément dans le sous-tableau [index debut ; index final].
    • On intervertit les contenus des index debut et index_min.

Algorithme

    debut est l'index (flèche en vert clair dans l'animation) de la case à remplir

    POUR debut variant de 0 à (longueur - 1)

      index_minminimum(tableau, debut)

      on cherche l'index de la plus petite valeur présente dans la partie non triée (index debut et plus)

      intervertir(tableau, debut, index_min)

      on intervertit les valeurs situées aux index debut et index_min

    Fin POUR

    Renvoyer VIDE (∅)

Algorithme de minimum(tableau, debut)

Algorithme

    debut est l'index (flèche en vert clair dans l'animation) de la case à remplir

    index_mindebut

    POUR index variant de (debut + 1) à (longueur - 1)

      SI tableau[index] < tableau[index_min]

        index_minindex

      Fin SI

    Fin POUR

    Renvoyer index_min

Algorithme de intervertir(tableau, debut, index_min)

Algorithme

    temptableau[debut]

    tableau[debut]tableau[index_min]

    tableau[index_min]temp

    Renvoyer Vide

2 - Preuve de terminaison

Pour rappel :

Variant de boucle

Pour prouver qu'une boucle non bornée (Tant que) s'arrête, il faut montrer

  • que la condition de poursuite de la boucle est de type while un > 0 et
  • que la suite un est une suite à valeurs
    • entières
    • strictement décroissante (on est certain que la valeur diminue à chaque boucle)
    • positives (on a bien une valeur supérieure à 0 au début) si on veut savoir si elle s'effectue au moins une fois

Cette suite un est ce qu'on nomme le variant de boucle.

L'arrêt est donc obligatoire au bout d'un certain nombre de bouclages si on peut écrire la condition sous une forme semblable à :

1
while un > 0 :

Prouver la terminaison d'un algorithme revient donc à dire qu'on est certain que l'algorithme va s'arrêter quelque soit l'entrée (pourvu que l'entrée respecte les préconditions bien entendu).

01° Je vous donne ci-dessous trois façons de faire la même chose. Analysez bien les trois façons de faire pour vous persuader que ces actions provoquent le même comportement de boucle.

Montrer alors la terminaison de la boucle en utilisant la version TANT QUE.

Version avec une boucle bornée POUR

    POUR i variant de 45 à 199 par incrémentation de 10

      Faire un truc (qui ne modifie pas la valeur de i !)

    Fin POUR

Version avec une boucle non bornée TANT QUE

    i45

    TANT QUE i < 200

      Faire un truc (qui ne modifie pas la valeur de i !)

      ii + 10

    Fin TANT QUE

Version Python avec la boucle bornée FOR

1 2
for i in range(45,200,10) : faire_un_truc()

...CORRECTION...

Je vais travailler avec la forme TANT QUE.

On voit que i a pour valeur initiale 45 et augmente de 10 à chaque tour de boucle.

On peut donc représenter les valeurs successives que va prendre la variable i par une suite entière arithmétique de valeur intiale 45 et de raison 10.

in = 45 + 10*n

On peut donc écrire de cette façon la condition de la boucle TANT QUE :

On part de la condition de départ :

    TANT QUE in < 200

On remplace la suite in par son expression :

    TANT QUE (45 + 10*n) < 200

On fait tout passer dans le membre de droite :

    TANT QUE 0 < (200 - 45 - 10*n)

On simplifie :

    TANT QUE 0 < (155 - 10*n)

On écrit la comparaison dans l'autre sens 

    TANT QUE (155 - 10*n) > 0

On pose

un = 155 - 10*n

En utilisant notre variant, la condition devient alors :

    TANT QUE un > 0

On en déduit que la boucle se termine puisque le variant un est bien

  • une suite d'entiers
  • initialement positive (155)
  • strictement décroissante (puisque sa raison est r = - 10)

Voici l'algorithme minimum.

    debut est l'index (flèche en vert clair dans l'animation) de la case à remplir

    index_mindebut

    POUR index variant de (debut + 1) à (longueur - 1)

      SI tableau[index] < tableau[index_min]

        index_minindex

      Fin SI

    Fin POUR

    Renvoyer index_min

02° Montrer la terminaison de cet algorithme.

...CORRECTION...

Nous avons un compteur partant de (debut + 1) et augmentant jusqu'à atteindre (longueur - 1).

Notons n le numéro du tour de boucle.

La boucle continue donc tant que :

debut + 1 + n < longueur

0 < longueur - debut - 1 - n

Il suffit d'écrire l'inégalité dans l'autre sens :

longueur - debut - 1 - n > 0

Si on pose u0 = longueur - debut - 1, on peut alors écrire le variant sous la forme un = uO - n

Il s'agit d'une suite d'entiers strictement décroissante.

On obtient finalement :

un > 0

un est une suite strictement décroissante d'entiers.

On en conclut que l'algorithme se termine.

Regardons maintenant notre algorithme de tri.

    debut est l'index (flèche en vert clair dans l'animation) de la case à remplir

    POUR debut variant de 0 à (longueur - 1)

      index_minminimum(tableau, debut)

      on cherche l'index de la plus petite valeur présente dans la partie non triée (index debut et plus)

      intervertir(tableau, debut, index_min)

      on intervertit les valeurs situées aux index debut et index_min

    Fin POUR

    Renvoyer VIDE (∅)

03° Montrer la terminaison de cet algorithme de tri.

...CORRECTION...

Nous avons un compteur partant de 0 et augmentant jusqu'à atteindre (longueur - 1).

Notons n le numéro du tour de boucle.

La boucle continue donc tant que :

0 + n < longueur

0 < longueur - n

longueur - n > 0

On en conclut encore une fois que cette boucle POUR se termine puisque le terme de gauche correspond bien à une suite strictement décroissante d'entiers.

L'algorithme se termine donc car :

  • La fonction minimum se termine
  • La fonction intervertir se termine (il s'agit juste de 3 affectations)
  • La boucle POUR principale qui contient les deux fonctions précédentes se termine également

Comme il s'agit de boucles FOR, il suffit de façon moins rigoureuse de simplement vérifier qu'on ne modifie pas la variable de boucle en cours de boucle ou que la longueur du tableau n'augmente pas par exemple.

Nous venons de prouver que les deux boucles de notre algorithme se terminent. L'algorithme se termine donc également.

Oui, mais... Est-il rapide ?

3 - Coût du tri par sélection

Dans l'activité précédente, nous avons vu qu'il n'existe pas ici de meilleur des cas ou de pire des cas : quelque soit l'allure des données à trier, l'algorithme prend le même temps.

Pour cela, nous allons prendre comme critère de coût le nombre de comparaisons à effectuer lorsque notre tableau possède n éléments. La variable longueur contient donc la valeur n.

Algortihme du tri par sélection

    debut est l'index (flèche en vert clair dans l'animation) de la case à remplir

    POUR debut variant de 0 à (longueur - 1)

      index_minminimum(tableau, debut)

      on cherche l'index de la plus petite valeur présente dans la partie non triée (index debut et plus)

      intervertir(tableau, debut, index_min)

      on intervertit les valeurs situées aux index debut et index_min

    Fin POUR

    Renvoyer VIDE (∅)

Et voici l'algorithme de la fonction minimum.

Algorithme de minimum(tableau, debut)

    debut est l'index (flèche en vert clair dans l'animation) de la case à remplir

    index_mindebut

    POUR index variant de (debut + 1) à (longueur - 1)

      SI tableau[index] < tableau[index_min]

        index_minindex

      Fin SI

    Fin POUR

    Renvoyer index_min

04° On considère un tableau de n éléments. On considère qu'on effectue le premier tour de boucle. La variable debut contient donc 0. Combien de comparaison va devoir faire la fonction minimum avant de renvoyer sa réponse ?

Attention, dans les versions "Algorithme" des boucles POUR, on donne bien la vraie valeur finale. Pas la borne extrême supérieure qu'on atteint pas. Ce n'est pas comme avec le range de Python.

...CORRECTION...

La variable debut contient 0. La variable index commence donc à 1.

La longueur vaut n. La variable index finit donc à n-1.

La lecture de l'algorithme de la fonction nous montre donc que la variable index va prendre les valeurs successives 1 ... jusqu'à n-1. Au total, on a donc n-1 comparaisons.

05° On considère le deuxième tour de boucle. La variable debut contient donc 1. Combien de comparaison va devoir faire la fonction minimum avant de renvoyer sa réponse sur ce tour de boucle ? Combien a-t-il fallu de comparaisons au total pour l'instant ?

...CORRECTION...

La variable debut contient 1. La variable index commence donc à 2.

La longueur vaudra toujours n. La variable index finit donc à n-1.

La lecture de l'algorithme de la fonction nous montre donc que la variable index va prendre les valeurs successives 2 ... jusqu'à n-1. Au total, on a donc n-2 comparaisons.

Au total, on a donc n-1 + n-2 comparaisons.

06° A votre avis, combien de comparaisons au total lors du prochain tour de boucle ?

...CORRECTION...

On va rajouter n-3 comparaisons.

Au total, on a donc n-1 + n-2 + n-3 comparaisons.

07° Combien l'algorithme va-t-il faire de comparaisons pour déterminer le contenu de l'avant-dernière cas, lorsque debut vaut longueur-2 ?

...CORRECTION...

La variable debut contient longueur-2, soit n-2. La variable index commence donc à n-1.

La longueur vaudra toujours n. La variable index finit donc à n-1.

On aura donc une simple comparaison effectuée.

08° Combien l'algorithme va-t-il faire de comparaisons pour déterminer le contenu du dernière cas, lorsque debut vaut longueur-1 ?

Combien de comparaisons aura-t-on effectué au total sur tout le tableau ?

...CORRECTION...

La variable debut contient longueur-1, soit n-1. La variable index commence donc à n.

La longueur vaudra toujours n. La variable index finit donc à n-1.

La boucle ne va donc pas fonctionner (croissant, mais le début est supérieur à la fin) et il n'y aura pas de comparaisons.

Au total, on a donc ce nombre de comparaisons :

Cn = 1 + 2 + 3 + 4 + 5 + ... + (n-5) + (n-4) + (n-3) + (n-2) + (n-1)

Cela devrait vous rappeler des souvenirs. Nous avons déjà rencontré cette série et nous avions démontré sa formule.

Formule de la série

Comme cette somme est longue à écrire, on utilise parfois la notation ci-dessous qui veut dire exactement la même chose :

Formule de la série

09° Démontrer cette formule (sans utiliser les formules vues éventuellement en spécialité mathématiques de première).

...CORRECTION...

Notre série Cn est la somme de (n-1) éléments :

Cn = 1 + 2 + 3 + 4 + ... + (n - 4) + (n - 3) + (n - 2) + (n - 1)

Nous voudrions associer les éléments deux par deux, mais il est possible qu'ils soient en nombre impair. Comment faire ? Multiplier chacun des membres par deux !

2 * Cn = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + ... + (n - 4) + (n - 4) + (n - 3) + (n - 3) + (n - 2) + (n - 2) + (n - 1) + (n - 1)

Du coup, le membre de droite comporte maintenant le double d'éléments, soit 2(n-1) éléments. Nous sommes certain qu'il y a un nombre pair d'éléments.

Associons alors les 2(n-1) éléments deux par deux, par complément du type 3 + (n - 3).

Cela nous permettra d'obtenir (n-1) couples.

2 * Cn = 1 + (n - 1) + 1 + (n - 1) + 2 + (n - 2) + 2 + (n - 2) + 3 + (n - 3) + 3 + (n - 3) + 4 + (n - 4) + 4 + (n - 4) + ...

2 * Cn = (1 + n - 1) + (1 + n - 1) + (2 + n - 2) + (2 + n - 2) + (3 + n - 3) + (3 + n - 3) + (4 + n - 4) + (4 + n - 4) + ...

Nous voyons donc que nous obtenons (n-1) couples qui valent tous n.

2 * Cn = (n) + (n) + (n) + (n) + (n) + (n) + (n) + (n) + ...

On peut donc écrire

2*Cn = (n-1)n

Au final, cela donne donc :

Formule de la série

10° Retrouver la formule en utilisant cette fois les formules habituelles sur quelques séries typiques.

Série arithmétique des nombres de 1 à n

Formule de la série
Formule de la série formule 1'

Série arithmétique des carrés de 12 à n2

Formule de la série des carrés
Formule de la série des carrés formule 2

Série arithmétique des cubes de 13 à n3

Formule de la série des cubes
Formule de la série des cubes formule 3

Série géométrique (un exemple avec x différent de 0)

Formule de la série géométrique de l'exemple
Formule de la série des cubes formule 4

...CORRECTION...

Il suffit de prendre la formule (1) qui correspond à une somme de 1 à n.

Formule de la série

On pose donc n = n' - 1.

On remplace donc

  • n par n'-1
  • n+1 par n'-1+1, soit n'

On obtient donc bien la formule suivante en renommant simplement notre variable n.

Formule de la série

11° QCM : que peut-on écrire de la complexité du tri par sélection ?

  • A : Elle est logarithmique (Θ(lg n) ), c'est à dire que la complexité évolue moins vite que le nombre n de données (par exemple : si on multiplie le nombres de données n par 100, le temps d'exécution n'est multiplié que par 8)
  • B : Elle est linéaire ( Θ(n) ), c'est à dire que la complexité évolue comme le nombre n de données (par exemple : si on multiplie le nombres de données n par 100, le temps d'exécution est multiplié par 100)
  • C : Elle est quadratique ( Θ(n2) ), c'est à dire que la complexité évolue comme le carré du nombre n de données (par exemple : si on multiplie le nombres de données n par 100, le temps d'exécution est multiplié par 10000, 100*100)
  • D : Elle est exponentielle ( Θ(xn) ), c'est à dire que la complexité évolue à terme beaucoup plus vite que n'importe quelle fonction polynomiale du nombre n de données (par exemple : si on multiplie le nombres de données n par 100, le temps d'exécution est multiplié par 2100, soit 1267650600228229401496703205376)

...CORRECTION...

On cherche à voir uniquement le comportement global de cet algorithme lorsqu'on augmente les données qu'il doit traiter.

On va donc simplifier notre formule : le but est de savoir à quelle type de fonction se rapproche le coût de notre algorithme, pas la formule exacte de cette fonction (nous l'avons déjà !).

On omet donc d'abord les facteurs multiplicateurs ou diviseurs. Ici, le facteur 2.

Pourquoi ? Voyons un exemple : un algorithme a un coût en n2*5.

Cas 1 : on tient compte du facteur 5 pour nos comparaisons sur le même algorithme.

Pour n = 2 données, on obtient un coût de 2*2*5 = 20.

Pour n = 4 données, on obtient un coût de 4*4*5 = 80.

On voit donc que lorsqu'on double les données (on passe de 2 à 4), le coût est lui multiplié par 4 (on passe de 20 à 80).

Cas 2 : on ne tient pas compte du facteur 5 pour nos comparaisons sur le même algorithme.

Pour n = 2 données, on obtient un coût de 2*2 = 4.

Pour n = 4 données, on obtient un coût de 4*4 = 16.

On voit donc que lorsqu'on double les données (on passe de 2 à 4), le coût est lui multiplié par 4 (on passe de 4 à 16).

Conclusion : inutile de tenir compte des facteurs multiplicateurs lorsqu'il s'agit de trouver le comportement d'un même algorithme lorsqu'on change la taille de ses données.

Il nous reste donc (n-1)*n.

Pour les grands nombres, on peut omettre le -1 du n-1. En terme d'évolution globale, il n'y a pas vraiment de différence entre 1 milliard et 1 milliard moins 1...

On voit donc qu'on obtient n*n, soit n2.

Le coût est donc quadratique.

Complexité du tri par sélection

On retiendra donc que la complexité du tri par sélection est Θ(n2) : le coût est quadratique.

Si on s'en tient aux comparaisons comme critère de sélection, on peut donc dire que le tri par insertion est meilleur. Nous avons montré qu'il était également quadratique dans le pire des cas mais qu'il était linéaire dans le meilleur des cas.

Attention, néanmoins : on pourrait choisir d'autres critères. Comme les déplacements d'éléments. Et dans ce cas, le tri par sélection pourrait être vu comme meilleur que le tri par insertion !

Pourquoi avoir choisi la comparaison pluto que le déplacement ? Le déplacement consiste la plupart du temps à simplement modifier une adresse mémoire, la comparaison demande deux accès mémoire.

4 - Preuve de correction

Nous avons donc démontré

  • la terminaison du tri par sélection : nous sommes maintenant certain qu'il va s'arrêter pourvu qu'on lui en laisse le temps
  • le coût quadratique dans tous les cas : nous savons que si on multiplie la taille des données par 10, le temps d'exécution va approximativement être multiplié par 100. Ceci en considérant la comparaison comme étant le critère de rapidité.

Oui mais... Est-ce que notre algorithme marche à chaque fois. Après tout, nous avons fait quelques essais, rajouté quelques doctests. Mais il y a peut-être des cas (même rares) qui risquent de créer un raté. Non ?

Imaginez : vous avez la responsabilité d'un grand nombre de vie en travaillant sur un algorithme de pilotage automatique. L'un des processus que vous avez créé utilise un tri par sélection. S'il disfonctionne, c'est la perte de contrôle de l'appareil. Vous avez fait des tests. Vous savez que ça marche. Mais... Laisseriez-vous l'appareil décoller sans être certain que ça fonctionne toujours ?

Tests

A toujours avoir en tête : on ne peut pas prouver la correction d'un algorithme (et de la fonction programmée correspondante) en réalisant juste un très grand nombre de tests : nous ne parviendrions qu'à prouver que l'algortihme fonctionne dans tous les cas testés.

Cela n'est pas équivalent à affirmer qu'il est réellement correct dans tous les cas.

Attention, tous les cas veut dire : tous les cas dont les entrées vérifient bien les spécifications d'entrée.

Voyons maintenant la preuve de correction de cet algorithme.

Preuve de correction et invariant

Pour prouver que l'algorithme est correct, nous allons devoir trouver un invariant : il s'agit du nom qu'on donne à une propriété vérifiable et qui permettra de prouver que le résultat final après exécution est bien le résultat attendu.

La démonstration se fait en trois temps.

L'initialisation

On montre que l'invariant est vrai avant le passage dans une boucle.

Si on note la propriété invariante P, on montre donc que P0 est vraie.

Le plus souvent, cette partie est triviale. Mais pas toujours...

La conservation

On montre que l'invariant reste vrai après chaque passage dans une boucle.

Cela revient à montrer que si l'invariant est vrai à l'étape k-1, il reste vrai à l'étape k :

Pk-1 == VRAI Pk == VRAI

La terminaison

On exploite les deux phases précédentes pour montrer qu'une fois toutes les boucles effectuées, l'invariant reste vrai et que l'algorithme a bien répondu à son objectif.

Le problème est qu'il n'existe pas de méthode automatique pour trouver le bon invariant. Il faut chercher à chaque nouveau problème qui se pose...

Regardons le cas du tri par sélection.

Le principe est simple : on décompose le problème en un sous-tableau trié et un sous-tableau non-trié.

On remplit le sous-tableau trié en ramenant les minimums successifs qu'on trouve dans le sous-tableau non trié.

On considère que notre invariant Pk pourrait être la propriété suivante : les k éléments du sous-tableau [0;k] sont triés.

Dans le sous-tableau trié (par ordre croissant ici), on doit donc avoir tableau[x] < tableau[x+1].

12° Travaillons sur l'initialisation.

Questions

  • Si on n'est pas encore rentré dans la boucle, combien a-t-on d'éléments dans notre sous-tableau trié ?
  • Peut-on considérer que l'invariant est vérifié pour P0 ?

...CORRECTION...

Le sous-tableau trié est vide. Il ne contient rien. Cela revient à avoir [].

On peut sans peine se convaincre qu'un sous-tableau ne contenant aucun élément est bien trié.

On peut donc dire que l'invariant est vrai avant l'exécution de la première boucle FOR.

Passons maintenant à la conservation. Pour rappel, voici l'algorithme :

Algorithme de tri par sélection

    debut est l'index (flèche en vert clair dans l'animation) de la case à remplir

    POUR debut variant de 0 à (longueur - 1)

      index_minminimum(tableau, debut)

      on cherche l'index de la plus petite valeur présente dans la partie non triée (index debut et plus)

      intervertir(tableau, debut, index_min)

      on intervertit les valeurs situées aux index debut et index_min

    Fin POUR

    Renvoyer VIDE (∅)

13° Quelle va être la première valeur prise par debut ? Que va contenir tableau[debut] après la première boucle ?

...CORRECTION...

    POUR debut variant de 0 à (longueur - 1)

Lors du premier tour, debut vaut donc 0.

On cherche donc le minimum sur tout le tableau car on active minimum(tableau, 0).

Ensuite, on intervertit et on place donc ce minimum à l'index 0.

tableau[0] contient donc la plus petite valeur présente dans le tableau.

Montrons maintenant la conservation. On fait l'hypothèse qu'à la fin de l'étape debut = k-1, on dispose

  • d'un sous-tableau d'élément trié sur les index 0 à k-1 et
  • d'un sous-tableau non trié sur les index k et plus.

14° Montrer qu'avec un tour de boucle en plus, Pk-1 implique que Pk est vrai.

...CORRECTION...

Sur notre nouvelle boucle, on a donc debut = k.

L'hypothèse de départ Pk-1 implique que le sous-tableau de 0 à k-1 est trié.

On cherche donc l'élément à placer sur l'index k en cherchant le plus petit élément dans le sous-tableau non-trié à l'aide de la fonction minimum et à le placer sur l'index k.

On peut donc dire qu'à l'issue de ce tour de boucle :

  • Les éléments de 0 à k-1 sont toujours triés puisqu'on n'y touche pas !
  • L'élément sur l'index k est plus grand que ceux de 0 à k-1, sinon il aurait déjà été dans le sous-tableau trié.
  • Les éléments de 0 à k sont donc triés.

On vient donc bien de montrer la conservation de l'invariant à chaque tour de boucle.

Pk-1 == VRAI Pk == VRAI

La dernière étape est ici assez rapide :

L'invariant Pk est la propriété selon laquel le sous-tableau [0; k] est trié.

Avec l'initialisation, nous avons montré que l'invariant P0 est vrai avant la boucle POUR.

Avec la conservation, nous avons montré qu'après k tours de boucle, on pouvait dire que le sous-tableau trié contient k éléments.

Passons à la terminaison :

On remarque qu'à la fin d'un tour de boucle, la relation entre k et la variable de boucle debut est k = debut + 1 :

A la fin du tour de boucle pour

  • debut valant 0, on a 1 élément trié (k vaut 1).
  • debut valant 1, on a 2 éléments triés (k vaut 2).
  • debut valant 2, on a 3 éléments triés (k vaut 3).
  • ect...

Puisqu'à la fin, debut vaut longueur - 1, le nombre k d'élément contenus dans le sous-tableau trié est donc
k = debut + 1
k = longueur - 1 + 1
k = longueur

Tout le tableau est donc bien trié puisque k correspond au nombre d'éléments triés.

Les réflexions ci-dessus permettent donc de prouver la correction de l'algorithme du tri par insertion.

Cet algorithme fonctionne donc dans tous les cas valides, c'est à dire tous les cas où l'ENTREE (le tableau) respecte bien les préconditions fournies.

5 - Python : Assertion de vérification

Nous allons finir en utilisant des assertions pour vérifier que notre invariant est bien un invariant valable.

Comme l'invariant est la propriété d'un sous-tableau d'être trié, nous allons créer une fonction est_trie qui vérifie cela.

On remarque bien la présence, ligne 25, d'une assertion à la fin de la boucle POUR de façon à vérifier si l'invariant est toujours vérifié.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
import random as rd serie1 = [rd.randint(0, 100) for x in range(20)] def intervertir(tableau, a, b) : '''Procédure qui intervertit les valeurs stockées aux index a et b :: param tableau(list) :: un tableau non vide ne contenant que des entiers :: param a(int) :: un index valide pour le tableau :: param b(int) :: un index autre valide pour le tableau :: return(None) :: "procédure" .. Effet de bord :: le tableau est modifié par effet de bord ''' temp = tableau[a] tableau[a] = tableau[b] tableau[b] = temp def minimum(tableau, debut) : '''Renvoie l'index de la valeur minimale trouvé dans le sous-tableau commençant à l'index début :: param tableau(list) :: un tableau non vide ne contenant que des entiers :: param debut(int) :: un index valide pour le tableau :: return(int) :: renvoie l'index de la valeur minimale :: exemple :: >>> minimum([10,20,-50,100,20,12], 3) 5 ''' index_minimum = debut # Au début, on prend le premier élément, l'index debut, pas 0 ! for index in range(debut+1, len(tableau)) : if tableau[index] < tableau[index_minimum] : index_minimum = index return index_minimum def tri_selection(tableau) : '''Trie le tableau sur place en utilisant le tri par sélection :: param tableau(list) :: un tableau non vide ne contenant que des entiers :: return(None) :: "procédure" :: exemple :: >>> tab_test = [40,50,20] >>> tri_selection(tab_test) >>> tab_test [20, 40, 50] ''' for debut in range(len(tableau)) : index_min = minimum(tableau, debut) intervertir(tableau, debut, index_min) assert est_trie(tableau, debut) def est_trie(tableau,k) : '''Renvoie True si le sous-tableau [0;k] est trié dans l'ordre croissant''' if len(tableau) < 2 : return True for index in range(k) : if tableau[index] > tableau[index+1] : return False return True if __name__ == '__main__' : import doctest doctest.testmod()

15° Ligne 53 : que va-t-il se passer sur le sous-tableau [0;k]

  • est bien trié
  • est mal trié

...CORRECTION...

Si le tableau est bien trié, il ne se passe rien : l'assertion est vérifiée mais le système n'active rien de particulier.

Par contre, si l'assertion est évaluée à FAUX, une interruption (Exception) va stopper le programme et afficher le message fourni après la virgule.

16° Tester le programme avec les commandes suivantes pour vérifer que l'assertion n'active rien, ce qui prouve que l'invariant est bien constamment vérifié après chaque tour de boucle.

>>> serie1 [57, 73, 68, 46, 97, 61, 86, 15, 43, 32, 91, 92, 51, 35, 80, 95, 18, 96, 50, 93] >>> tri_selection(serie1) >>> serie1 [15, 18, 32, 35, 43, 46, 50, 51, 57, 61, 68, 73, 80, 86, 91, 92, 93, 95, 96, 97]

6 - FAQ

Pourquoi justifiez la terminaison d'une boucle FOR ?

Un peu pour l'exercice. Il existe deux cas où une boucle POUR peut mal tourner :

  • On demande par exemple de commencer à 1, de s'arrêter à 10 et de décrémenter de 1 à chaque tour. Ca donne 1, 0, -1 ... et ça ne s'arrêtera jamais...
  • On touche à la variable de boucle dans la boucle.

Ici, vous n'avez ni l'un ni l'autre mais ça vous permettra de vous souvenir qu'il faut un peu surveiller les boucles POUR quand même.

J'ai également 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)

Et c'est lié au fait qu'avec un tableau de 1 million d'éléments, la méthode dichotomique ne prend qu'une vingtaine d'étapes au pire

Oui.

>>> math.log2(1E6) 19.931568569324174

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.

Log et Ln, 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.

Lorsqu'on parle de ln, on parle du logarithme népérien en mathématiques. Vous le verrez en terminale.

Sauf que dans les documents informatiques, on parle souvent du logarithmique base 2. On devrait le noter log2 ou log2. Mais souvent, la complexité ou le coût apparaît sous la forme lg (voir au dessous) mais aussi parfois ln. Pourquoi ? Tout simplement car log2(x) = ln (x) / ln (2). ln 2 n'est donc qu'un coefficient multiplicateur. C'est un peu comme un coût en 0.5n3 qu'on noterait juste n3.

Attention donc au contexte dans lequel apparaît un logarithme.

Petit résumé des notations

On voit juste log : c'est certainement log10.

On voit juste lg : c'est certainement log2.

On voit juste ln : c'est le logarithme népérien.

Activité publiée le 01 09 2020
Dernière modification : 12 09 2020
Auteur : ows. h.