Algo Preuve Sélection

Identification

Infoforall

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

Résumé 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

Rappel : Preuve de terminaison

La preuve de terminaison d'un algorithme permet d'affirmer qu'il s'arrête de façon certaine (c'est à dire qu'il ne boucle pas infiniment) sur toutes les entrées valides qu'on lui fournit (c'est à dire les entrées respectant les préconditions).

Pour faire la preuve de terminaison, il faut montrer que :

  • ses boucles s'expriment sous la forme TANT QUE VARIANT > 0
  • avec un VARIANT de boucle pouvant s'écrire comme une suite un strictement décroissante d'entiers.

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 bornée POUR peut donc s'écrire :

TANT QUE debut + 1 + n < longueur

TANT QUE 0 < longueur - debut - 1 - n

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

TANT QUE 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 :

TANT QUE un > 0

avec un est une suite strictement décroissante d'entiers car sa raison est -1.

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 peut alors s'écrire :

TANT QUE 0 + n < longueur

TANT QUE 0 < longueur - n

TANT QUE 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. Exemple : si on multiplie les données par 8, on ne rajoute que 3 opérations.
  • 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 8, le temps d'exécution est multiplié par 8)
  • 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 8, le temps d'exécution est multiplié par 64, 10*10)
  • 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 passe de 10 à 80 données (x8), le temps d'exécution est multiplié par 1021 !)

...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 dans tous les cas.

Si on s'en tient aux comparaisons comme critère de sélection, on peut donc dire que le tri par insertion est meilleur : le coût du tri par insertion est quadratique dans le pire des cas mais 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 !

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

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

  • qu'il fournit toujours la bonne réponse (réalise sans erreur le travail pour lequel il est conçu)
  • sur toutes les entrées valides qu'on lui fournit (les entrées respectant les préconditions).

Pour faire la preuve de correction, il faut trouver un INVARIANT, une propriété P vérifiable qui reste vraie tout le long du déroulement de l'algorithme. 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.

  1. L'initialisation P0 est VRAI
  2. On montre que l'INVARIANT est VRAI avant le premier passage dans une boucle.

    Si on note la propriété invariante P, on montre donc que P0 est VRAI. 0 doit s'entendre comme "avant le moindre passage dans la boucle".

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

  3. La conservation Pk Pk+1
  4. On montre que l'INVARIANT reste VRAI après chaque passage dans une boucle.

    1. On suppose que Pk est vérifié : vous avez fait k tours de boucle et on suppose qu'on obtient une certaine configuration qui respecte l'INVARIANT.
    2. On montre alors qu'avec un tour de boucle en plus, Pk+1 est vérifié obligatoirement.
    3. On peut donc écrire Pk Pk+1
  5. La terminaison
  6. On montre que l’algorithme a bien traité toutes les donneés une fois sorti des boucles : il faut montrer qu'il s'arrête où il faut.

    On exploite les deux phases précédentes pour montrer qu'avec le nombre finale N de boucles effectuées, l'algorithme a bien répondu à son objectif en s'arrêtant juste où il faut.

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

Autre difficulté : le numéro de l'étape ne correspond pas nécessairement à la valeur de la variable de boucle si elle commence à 0 : à la fin du premier tour de boucle, k vaut 1 mais la variable de boucle 0. A la fin du deuxième tour de boucle, k vaut 2 mais la variable de boucle 1...

Le cas du tri par sélection peut se résumer à ceci : on décompose le problème en

  1. un sous-tableau trié (à gauche) et
  2. un sous-tableau non-trié (le reste, à droite).

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

Invariant du tri par sélection

Au départ, le sous-tableau des éléments triés est vide. On rajoute 1 élément dans ce tableau à chaque tour de boucle.

On considère que notre invariant pourrait être la propriété Pk suivante  : après k tours de boucle, k éléments sont triés dans le sous-tableau [0;k-1] de gauche.

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

P0 signifie qu'on a 0 éléments triés.

Le sous-tableau trié est donc 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. P0 est vérifié.

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 ? Combien va-t-on avoir d'éléments k triés ?

Quelle va être la deuxième valeur prise par debut ? Combien va-t-on avoir d'éléments triés k dans le sous-tableau de droite ?

En déduire la relation entre le nombre de tours de boucle finalisé k et la valeur de la variable de boucle debut.

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

On voit donc qu'à la fin de la boucle avec debut à 0, on obtient 1 élément trié.

On peut donc écrire k = debut + 1.

Quelques exemples pour se convaincre de la formule.

Avant la boucle (k=0), il n'y a aucun élément trié.

Après le premier tour de boucle (celui où debut vaut 0) on a 1 élément trié : k = 1.

Après le deuxième tour de boucle (celui où debut vaut 1) on a 2 éléments triés : k = 2.

ect ...

On voit bien qu'on retrouve k = debut + 1.

Montrons maintenant la conservation.

On fait l'hypothèse de la véricité de Pk est vraie. Après k tours de boucle, le sous-tableau trié possède donc k éléments et nous avons donc

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

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

...CORRECTION...

Commençons par définir l'état du système à la fin de la boucle k.

A la fin de la boucle k, nous avions k éléments triés dans [0, k-1] et une variable debut contenant k-1 puisque k = debut + 1.

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

Si on refait un tour de boucle, on incrémente debut qui passe à la valeur k.

On cherche donc l'élément à placer sur l'index k en cherchant le plus petit élément dans le sous-tableau non-trié [k, fin] à 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.

On écrira donc Pk Pk+1

La dernière étape est ici assez rapide :

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

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

Avec la conservation, nous avons montré que l'invariant restait vrai après chaque tour de boucle.

Passons à la terminaison :

Nous avions remarquer 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...

Or la boucle bornée POUR est POUR debut variant de 0 à (longueur - 1).

A la fin, debut vaut donc 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.