Algo Parcours

Identification

Infoforall

2 - Parcours séquentiel d'un tableau


Nous allons maintenant voir ce qu'est l'algorithmique.

Après avoir vu cette partie en 1er, vous pourrez répondre à ces questions

  • A quoi sert l'algorithmique ?
  • Comment savoir si un algorithme fonctionne ?
  • Comment garantir qu'un algorithme s'arrête ?
  • Comment comparer des algorithmes entre eux pour prendre le "meilleur" ?

Evaluation Bonus pour les plus rapides : deux questions

Documents de cours : open document ou pdf

1 - Algorithme

Définition d'algorithme

Généralités

Un algorithme est un ensemble fini d'instructions précises permettant de résoudre une classe de problèmes.

Si l'algorithme ne fonctionne que pour UN cas particulier, on ne parlera pas d'algorithme.

Une manière de calculer 5 x 4 n'est pas un algorithme. Par contre, une façon de calculer a x b pourrait être vue comme un algorithme.

ENTREE(S)/SORTIE

Un algorithme reçoit des données d'ENTREE, effectue des actions sur ces données et fournit une réponse qu'on nomme la SORTIE.

ENTREE(S) ⇒ Algorithme ⇒ SORTIE

Exemples

[5, 10, 50, 0, 20] ⇒ Algorithme du MAXIMUM ⇒ 50

[5, 10, 50, 0, 20] ⇒ Algorithme de la SOMME ⇒ 85

[5, 10, 50, 0, 20] ⇒ Algorithme de la SEQUENCE CROISSANTE ⇒ [5, 10, 50]

Algorithme et fonction

L'algorithme est constitué de l'idée abstraite des actions qu'on va devoir réaliser.

Une vision de l'esprit, mais une vision très détaillée.

On sépare réflexion et exécution.

Gérard Berry parle des algorithmes comme étant des méthodes à appliquer sans réflechir, en suivant machinalement le déroulement et les ordres.

La réflexion est utilisée par l'informaticien lors de la création de l'algorithme.

Lors du déroulement de l'algorithme, on exécute les instructions. Point. Aucune forme d'initiative ne doit encore apparaître.

  • Le passage de
    • l'idée abstraite de l'algorithme sur papier à
    • son exécution concrète en machine à l'aide d'un programme
  • se nomme l'implémentation.

Que connaissez-vous pour l'instant qui accepte des valeurs en entrée et qui renvoie une réponse en sortie ?

Et oui : les fonctions.

[5, 10, 50, 0, 20] ⇒ Algorithme du MAXIMUM ⇒ 50

L'algorithme du MAXIMUM est ainsi déjà implémenté en Python à travers la fonction native max() :

>>> max([5, 10, 50, 0, 20]) 50

Pourquoi est-il important d'optimiser les algorithmes alors que les machines actuelles sont très puissantes ? A cause de l'augmentation énorme du volume de données à traiter.

Vous êtes chef de service. On vous propose de changer l'équipement informatique pour un ordinateur Tip Top ou d'engager un.e nouvel.le informaticien.ne Tip Top. Quelqu'un qui a pris Informatique dès la 1er. Si si. Alors ? Votre choix ?

Imaginons qu'on veuille identifier quelqu'un dans une base de données comportant n fiches.

Cas 1 : informaticien moyen mais ordinateur Tip-Top

  • L'algorithme créé par l'informaticien a besoin de n3 opérations pour identifier la personne dans la base de données qui comporte n fiches.
  • L'ordinateur est capable de faire 200 Giga comparaisons par seconde.

Rappel : 1 G vaut dire 1 Giga soit 1 milliard ou 1.109.

On peut en déduire le temps mis par l'ordinateur pour identifier les personnes en fonction de la taille de la base de données :

t = (n3) / (200.109)

En Python :

t = n**3 / 200E9

01° Calculer les temps mis pour réaliser cette tâche si la base de données possède

  • 5000 fiches (5.103),
  • 5 millions de fiches (5.106),
  • 5 milliards de fiches (5.109).

...CORRECTION...

Pour n = 5000 fiches :

  • t = (5E3)**3 / 200E9 = 0,625 s

Pour n = 5 millions de fiches :

  • t = (5E6)**3 / 200E9 = 625000000 s
  • t = (5E6)**3 / (200E9*3600*24*365) = 19.8 ans

Pour n = 5 milliards de fiches :

  • t = (5E9)**3 / 200E9 = 6,25.1017 s
  • t = (5E9)**3 / (200E9*3600*24*365) = 19 818 619 990 ans !

Cas 2 : informaticien Tip-Top mais ordinateur beaucoup moins performant

  • L'algorithme créé par l'informaticien a besoin de n2 comparaisons pour identifier la personne dans la base de données qui comporte n fiches.
  • L'ordinateur est capable de faire 30 Mega comparaisons par seconde...

Rappel : 1 M vaut dire 1 Mega soit 1 million ou 1.106.

On peut en déduire le temps mis par l'ordinateur pour identifier les personnes en fonction de la taille de la base de données :

t = (n2) / (30.106)

En Python :

t = n**2 / 30E6

02° Calculer les temps mis pour réaliser cette tâche si la base de données possède

  • 5000 fiches (5.103),
  • 5 millions de fiches (5.106),
  • 5 milliards de fiches (5.109).

...CORRECTION...

Pour 5000 fiches :

  • t = (5E3)**2 / 30E6 = 0,83 s

Pour 5 millions de fiches :

  • t = (5E6)**2 / 30E6 = 833333 s
  • t = (5E6)**2 / (30E6*3600*24) = 9.6 jours

Pour 5 milliards de fiches :

  • t = (5E9)**2 / 30E6 = 833333333333 s
  • t = (5E9)**2 / (30E6*3600*24*365) = 26 424 ans !

On voit donc bien que l'ordinateur ultra performant n'a en réalité aucun chance face à celui moins performant sur lequel fonctionne un programme efficace.

Comparaison visuelle des deux cas
Comparaison visuelle des deux cas

Voici un script Python permettant de générer les courbes ci-dessus.

...PYTHON...

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
# 1 - Importation des modules nécessaires import math import matplotlib.pyplot as plt # 2 - Constantes # 3 - Déclaration des fonctions # 4 - Programme principal # Création des tableaux de données valeurs_n = [ n for n in range(10000) ] # Abscisse temps_1 = [ n**3 /200E9 for n in valeurs_n ] # Ordonnée temps_2 = [ n**2 /30E6 for n in valeurs_n ] # Ordonnée xmax = max(valeurs_n ) ymax = max(temps_1 ) # Création des courbes plt.plot(valeurs_n, temps_1, label="Cas 1", color='orange') plt.plot(valeurs_n, temps_2, label="Cas 2", color='red') plt.xlabel("Nbr de fiches") plt.ylabel("Temps d'exécution (s)") plt.title("Comparaison des temps d'exécution") plt.legend(loc='upper center') plt.axis([0, xmax, 0, ymax]) plt.grid() plt.show() # Affichage à l'écran des courbes

Et ça date de quand l'algorithmique ? Des années 2000 ? Des années 1940 ?

Certains pensent que l'un des algorithmes les plus anciens est l'algorithme d'Euclide. Cet algorithme permet de trouver le plus grand commun diviseur (PGCD) de deux entiers a et b.

Par exemple, pour a = 15 et b = 20, il s'agit de 5.

En effet,

  • 15 peut se décomposer en 3*5 et
  • 20 peut se décomposer en 4*5.
Euclide
Gravure d'Euclide (depuis https://fr.wikipedia.org/wiki/Euclide#/media/Fichier:Euklid-von-Alexandria_1.jpg) - Domaine Public

Un algorithme efficace permettant de trouver automatiquement ce PGCD date de -300 et se trouve dans les écrits du mathématicien Euclide d'Alexandrie. Il a été découvert de façon autonome en Inde et en Chine quelques siècles plus tard.

Vers 800, Muhammad Ibn Mūsā al-Khuwārizmī dit Al-Khwarizmi, mathématicien, né dans dans l'actuel Ouzbékistan et mort à Badgad, publie de nombreux textes. Les traductions permettront l'introduction de l'algèbre en Europe. Il a notamment répertorié et classifié de nombreux algorithmes (créés par d'autres). Il y montre leurs terminaisons (le fait qu'ils s'arrêtent bien à tous les coups) ou pas.

Al-Khwarizmi
Timbre Al-Khwarizmi - Domaine Public

Son nom est bien entendu à l'orgine d'algorithme.

Depuis, bien des gens ont travaillé et travaillent toujours pour trouver, créer ou améliorer les algorithmes.

L'un des grands noms de l'algorithmie est Donald Knuth, informaticien et mathématicien américain de renom. Il est un des pionniers de l'algorithmique et a fait de nombreuses contributions dans plusieurs branches de l'informatique théorique (fondements logiques et mathématiques de l'informatique).

https://fr.wikipedia.org/wiki/Donald_Knuth#/media/Fichier:KnuthAtOpenContentAlliance.jpg
Donald Knuth - CC BY-SA 2.5

L'algorithmique est donc un domaine d'études très riche en recherches passées et futures. Si vous aimez les maths, l'informatique et les casses-têtes, c'est un domaine fait pour vous !

Si vous voulez vous amuser, n'hésitez pas aller consulter l'excellent site de France-IOI.

2 - Recherche d'un élément dans un tableau

Nous allons maintenant tenter de réaliser un algorithme qui signale si un élément existe dans un tableau (et renvoie son indice) ou renvoie -1 sinon.

Cette méthode se nomme également méthode par balayage ou recherche linéaire.

En anglais, on parle de linear search.

Vous allez comprendre pourquoi en utilisant l'animation suivante : créer un tableau avec l'un des boutons aléatoires, choisir une valeur à chercher et appuyer sur le bouton lançant l'animation.

Valeur cherchée :

Indice i 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Case t[i] 60 89 15 56 82 1 86 97 24 86 75 6 14 69 98 31 37 89 91 56
Algorithme de recherche séquentielle

BUT : trouver la position de la première occurrence de l'élément recherché bien dans un tableau.

PRINCIPE (en 4 étapes) :

  1. On commence par la case d'indice 0
  2. Tant que la case ne possède pas le contenu cherché et qu'il reste des cases, on passe à la case suivante
  3. Si la valeur finale de l'indice est valide : la réponse est bien l'indice. Sinon, la réponse est -1 car on a atteint la fin du tableau sans trouver.
  4. On renvoie la réponse

Description des entrées / sortie

  • ENTREES :
    • t : un tableau contenant n éléments.
    • x : l' élément qu'on recherche dans le tableau
    • (optionnelle selon les langages d'implémentation) longueur, le nombre d'éléments dans le tableau t
  • SORTIE : un entier valant
    • soit l'indice où se trouve la première (et peut-être) seule occurrence de l'élément cherché.
    • une réponse voulant dire que l'élément x n'est présent dans le tableau. VIDE ou -1

Exemple :

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

Indice i 0 1 2 3 4 5 6
Case t[i] 13 18 89 1024 45 -12 18

Voici trois exemples de réponses attendues :

Recherche de 89 (présent une fois) :

t = [13, 18, 89, 1024, 45, -12, 18]  ⇒   RECHERCHER   ⇒ 
et 2
x = 89

Recherche de 18 (présent deux fois) :

t = [13, 18, 89, 1024, 45, -12, 18]  ⇒   RECHERCHER   ⇒ 
et 1
x = 18

Recherche de 100 (non présent) :

t = [13, 18, 89, 1024, 45, -12, 18]  ⇒   RECHERCHER   ⇒ 
et -1
x = 100

Description de l'algorithme

On fait le choix de répondre -1 en cas de valeur non trouvée.

    i0

    TANT QUE i < longueur ET que t[i] est différent de x

      ii + 1

    Fin TANT QUE

    SI i < longueur

      reponsei

    SINON

      reponse-1

    Fin Si

    Renvoyer reponse

03° Utiliser les instructions suivantes pour revoir comment fonctionne un tableau :

>>> t = [5, 10, 7] >>> len(t) ??? >>> t[0] ??? >>> t[1] ??? >>> t[2] ??? >>> t[3] ???

...CORRECTION...

>>> t = [5, 10, 7] >>> len(t) 3 >>> t[0] 5 >>> t[1] 10 >>> t[2] 7 >>> t[3] ElémentError: list index out of range

04° Quel est le seul cas où un ET logique répond VRAI ?

...CORRECTION...

Un ET logique est VRAI si et seulement si toutes les conditions sont évaluées à VRAI.

Cela veut dire que dès qu'une condition est fausse, le ET est évalué à FAUX.

05° Voici la ligne du TANT QUE :

TANT QUE i < longueur ET que t[i] est différent de x

Question 1 : trouver à quelle conditions du TQ correspondent respectivement les deux phrases suivantes :

  • "Il reste encore des cases à explorer"
  • ET
  • "la case ne contient pas la bonne valeur".

Question 2 : s'agit-il des conditions de poursuite de la boucle TANT QUE ou des conditions d'arrêt ?

...CORRECTION...

  • "Il reste encore des cases à explorer" équivalent à i < longueur
  • ET
  • "la case ne contient pas la bonne valeur" équivalent à t[i] est différent de x.

Il s'agit de la condition de poursuite de la boucle.

Il faut d'ailleurs que les deux sous-conditions soient VRAI : pour continuer, il faut bien

06° Deux questions.

Question 1 : Ecrire le déroulé de l'algorithme s’il travaille sur le tableau ci-dessous en recherchant 1024. Vous devriez trouver qu'il renvoie 3.

t[13, 18, 89, 1024, 45, -12, 18]

Voici le début d'une rédaction possible (avec en gris des indications supplémentaires qu'il est inutile de marquer sur votre feuille de cours) :

i vaut 0.

longueur vaut 7 car le tableau a 7 cases numérotées de 0 à 6.

x vaut 1024 car c'est ce qu'on cherche.

Début du TANT QUE ? Oui car 0 < 7 et que t[0] est différent de 1024

Du coup, i ← 1

Poursuite du TANT QUE ? Oui car 1 < 7 et que t[1] est différent de 1024

Du coup, ...

Question 2 : Quelle est la condition évaluée à FAUX qui a provoqué l'arrêt du TANT QUE :

  • la valeur de la variable indice i devenue trop grande ou
  • le contenu qui correspond à la valeur voulue ?

...CORRECTION...

t[13, 18, 89, 1024, 45, -12, 18]

i vaut 0.

longueur vaut 7.

x vaut 1024.

Début du TANT QUE ? Oui car 0 < 7 et que t[0] est différent de 1024

Du coup, i ← 1

Poursuite du TANT QUE ? Oui car 1 < 7 et que t[1] est différent de 1024

Du coup, i ← 2

Poursuite du TANT QUE ? Oui car 2 < 7 et que t[2] est différent de 1024

Du coup, i ← 3

Poursuite du TANT QUE ? Non car la condition t[3] différent de 1024 est évaluée à FAUX !

Arrêt de la boucle TANT QUE.

Puisque i < 7, on renvoie sa valeur, à savoir 3.

Ici, on s'arrête donc puisqu'on a trouvé la valeur 1024 voulue dans le tableau.

07° Appliquer l'algorithme à la main avec une recherche sur 1025. Vous devriez trouver qu'il renvoie -1. Quelle est la condition évaluée à FAUX qui a provoqué l'arrêt du TANT QUE :

  • la valeur de la variable indice i devenue trop grande ou
  • le contenu qui correspond à la valeur voulue ?

...CORRECTION...

t[13, 18, 89, 1024, 45, -12, 18]

i vaut 0.

longueur vaut 7.

x vaut 1025.

Début du TANT QUE ? Oui car 0 < 7 et que t[0] est différent de 1025

Du coup, i ← 1

Poursuite du TANT QUE ? Oui car 1 < 7 et que t[1] est différent de 1025

Du coup, i ← 2

Poursuite du TANT QUE ? Oui car 2 < 7 et que t[2] est différent de 1025

Du coup, i ← 3

Poursuite du TANT QUE ? Oui car 3 < 7 et que t[3] est différent de 1025

Du coup, i ← 4

Poursuite du TANT QUE ? Oui car 4 < 7 et que t[4] est différent de 1025

Du coup, i ← 5

Poursuite du TANT QUE ? Oui car 5 < 7 et que t[5] est différent de 1025

Du coup, i ← 6

Poursuite du TANT QUE ? Oui car 6 < 7 et que t[6] est différent de 1025

Du coup, i ← 7

Poursuite du TANT QUE ? Non car la condition 7 < 7 est évaluée à FAUX !

Arrêt de la boucle TANT QUE.

Puisque i < 7 est FAUX, on renvoie -1.

Ici, on s'arrête donc puisqu'on a atteint une valeur impossible pour l'indice.

08° 18 apparaît deux fois dans le tableau. La valeur renvoyée par cet algorithme sur une recherche sur 18 donne :

  • A : 0
  • B : 1
  • C : 6
  • D : (1,6)

Rappel du contenu

Indice i 0 1 2 3 4 5 6
Case t[i] 13 18 89 1024 45 -12 18

...CORRECTION...

On lit le contenu progressivement de façon séquentielle.

En lisant l'algorithme, on voit qu'on renvoie la première occurrence trouvée, soit 1.

09° Compléter la fonction Python rechercher() pour qu'elle soit une implémentation correcte de notre algorithme de recherche.

Le prototype de la fonction (remarquez bien que cela ressemble pas mal à notre schéma ENTREES/SORTIE)

1
def rechercher(t:Tableau, x:Element) -> Integer:

La fonction à compléter :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
def rechercher(t, x): '''Renvoie l'indice de la première occurrence de x dans t, -1 si non présent :: param t(list) :: un tableau contenant le même type d'éléments que le paramètre x :: param x(au choix) :: l'élément qu'on cherche à trouver dans le tableau :: return (int) :: l'indice de la case ou -1 :: exemples :: >>> test = [10,20,30,40,50] >>> rechercher(test, 20) 1 >>> rechercher(test, 60) -1 ''' pass tab_test = [13, 18, 89, 1024, 45, -12, 18] a = rechercher(tab_test, 18) b = rechercher(tab_test, 1024) c = rechercher(tab_test, 1025)

Comme vous pouvez le voir, sous la fonction à réaliser, on a rajouté des instructions pour créer un tableau et mémoriser quelques appels dans des variables. Vous pourrez visualiser le résultat pour voir si votre fonction répond correctement.

...CORRECTION...

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
def rechercher(t, x): '''Renvoie l'indice de la première occurrence de x dans t, -1 si non présent :: param t(list) :: un tableau contenant le même type d'éléments que le paramètre x :: param x(au choix) :: l'élément qu'on cherche à trouver dans le tableau :: return (int) :: l'indice de la case ou -1 :: exemples :: >>> test = [10,20,30,40,50] >>> rechercher(test, 20) 1 >>> rechercher(test, 60) -1 ''' 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 tab_test = [13, 18, 89, 1024, 45, -12, 18] a = rechercher(tab_test, 18) b = rechercher(tab_test, 1024) c = rechercher(tab_test, 1025)

Le problème des boucles non bornées ? On peut créer sans le vouloir une boucle infinie ! Dans tout programme sérieux, on vérifiera donc la terminaison de la boucle, c'est à dire le fait qu'on finisse nécessairement par sortir de la boucle au bout d'un moment.

Phase d'initialisation du TANT QUE

Attention à l'une des erreurs typiques lors de l'utilisation d'une boucle non bornée TANT QUE : le fait d'oublier de donner une valeur par défaut permettant de rentrer dans la boucle à la variable qui gère la boucle.

15 16 17 18
i = 0 longueur = len(t) while i < longueur and t[i] != x: i = i + 1

On voit bien que les lignes 15 et 16 permettent de rentrer une première fois dans la boucle.

Sans ces lignes, ça ne peut pas fonctionner.

Conclusion : Ne négligez pas cette phase d'initialisation.

Bonus pour les plus rapides 1° Pas si facile que ça : fournir un algorithme de recherche un peu différent : cette fois, on veut renvoyer l'indice de la dernière occurrence dans le tableau.

Recherche de 18 (présent deux fois) :

t = [13, 18, 89, 1024, 45, -12, 18]  ⇒   RECHERCHER   ⇒ 
et 6
x = 18

Il faudra vous demander s'il faut utiliser une boucle bornée ou non bornée, comment parvenir à stocker les réponses successives...

Bonus pour les plus rapides 2° Réaliser l'implémentation de votre algorithme.

3 - Suites

Suite arithmétique

Suite

Une suite est une famille d'éléments indexée 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 : 1, 2, 4, 8, 16, 32... Le terme 1 est le premier, et il pourrait posséder l'indice 0. Mais on pourrait aussi donner la suite 20, 10, 5, 2, 1 puis 0.

Formules pour les suites arithmétiques

Une suite arithmétique est une suite dans laquelle chaque terme un permet de trouver le terme suivant un+1 en lui ajoutant une valeur appelée raison r.

Par exemple, la suite de nombres 5, 15, 25, 35... caractérise une suite arithmétique de raison 10 et de valeur initiale 5 :

  • 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 connait le terme un et la raison r :

Formule 1
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
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 croissante
  • Avec une raison de -3 : 10, 7, 4, 1, -2, -5...

Théorème

Toute suite uN d’entiers positifs strictement décroissante ne peut prendre qu’un nombre fini de valeurs.

10° Ecrire l'une des formules permettant de calculer les termes de la suite arithmétique de raison 12 dont le premier terme vaut 100. Donner les valeurs des termes u0, u1, u2, u3 et u4.

...CORRECTION...

un = 100 + n*12

u0 = 100

u1 = 112

u2 = 124

u3 = 136

u4 = 148

11° Ecrire l'une des formules permettant de calculer les termes de la suite arithmétique de raison -5 dont le premier terme vaut 20. Donner les valeurs des termes u0, u1, u2, u3 et u4.

...CORRECTION...

un = 20 + n*(-5) = 20 - n*5

u0 = 20

u1 = 15

u2 = 10

u3 = 5

u4 = 0

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

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

Variant de boucle

Pour prouver qu'une boucle non bornée (TANT QUE) s'arrête, il faut montrer qu'il existe un variant de boucle tel que

  1. la condition de poursuite de la boucle peut s'écire sous la forme TANT QUE VARIANT > 0 et
  2. le VARIANT soit
    • une suite un
    • à valeurs entières
    • strictement décroissante (la valeur doit diminuer d'au moins 1 à chaque tour de boucle)
    • positives si on veut que la boucle s'effectue au moins une fois

Si ces conditions sont vraies, le variant de boucle va nécessairement décroitre 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.

Conclusion à connaître par coeur :

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 les deux propositions suivantes sont vraies :

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

(A et B) implique alors que l'algorithme se termine.

Exemple

Prenons ce court programme :

1 2 3
x = 3 while x < 100: x = x + 10

Etape 1 : avant de rentrer dans la boucle

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 : que se passe-t-il à chaque tour de boucle ?

Ligne 3 : on voit qu'on augmente x de 10 à chaque tour de boucle. La raison vaut donc +10. 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 un > 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 uN exprimé de cette façon :

L2
while uN > 0:    avec uN = (97 - 10*n)

Etape 4 : conclusion

On voit que le variant est une suite d'entiers dont la raison est r = -10 : on perd 10 à chaque fois. La suite est donc décroissante.

Nous obtenons donc bien

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

Les deux affirmations précédentes prouvent la terminaison de cette boucle.

13° 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 un > 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 de rentrer dans la boucle

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 : que se passe-t-il à chaque tour de boucle ?

Ligne 8 : on voit qu'on augmente x de 1 à chaque tour de boucle. La raison vaut donc +1. Nous avons donc affaire à une suite xN arithmétique de raison r = +1 et de valeur initiale x0 de 0.

xN = x0 + r*n

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 un > 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 de boucle uN exprimé de cette façon :

L7
while uN > 0:    avec uN = seuil - 5*n

Etape 4 : conclusion

Le variant est une suite d'entiers dont la raison est r = -5 : on perd 5 à chaque fois. La suite est donc décroissante.

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.

14° 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 un > 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 de rentrer dans la boucle

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 : que se passe-t-il à chaque tour de boucle ?

Ligne 8 : on voit qu'on diminue x de 1 à chaque tour de boucle. La raison vaut donc -1. Nous avons donc affaire à une suite xN arithmétique de raison r = -1 et de valeur initiale x0 = 0.

xN = x0 + r*n

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 un > 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 uN exprimé de cette façon :

L7
while uN > 0:    avec uN = seuil + 5*n

Etape 4 : conclusion

On voit que le variant est une suite d'entiers dont la raison est r = +5 : on gagne 5 à chaque fois. La suite est donc croissante.

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 cet 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 ?

15° Prouver la terminaison (ou non) du programme de recherche linéaire. 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 un > 0

Subtilité : une boucle TANT QUE qui possède deux conditions de poursuite reliées par un ET va s'arrêter dès que l'une des conditions est fausse.

Travaille TANT QUE condition_1 ET condition_2

La boucle s'arrête

  • soit si condition_1 devient fausse
  • soit si condition_2 devient fausse

On peut donc parfois prouver la terminaison à l'aide d'une seule des conditions.

Nous allons donc tenter de travailler uniquement avec la condition liée à la longueur. On verra si cela suffit, ou pas.

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 0 : simplification

La condition de poursuite du TANT QUE se compose de deux conditions associées via un ET. On ne peut continuer que si les deux conditions sont vraies. Cela veut dire qu'on s'arrête dès qu'une des deux conditions est fausse.

On ne gardera que cela :

16
while i < longueur:

Etape 1 : avant de rentrer dans la boucle

Ligne 14 : 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 : que se passe-t-il à chaque tour de boucle ?

Ligne 17 : on voit qu'on augmente i de 1 à chaque tour de boucle. La raison vaut donc +1. Nous avons donc affaire à une suite iN arithmétique de raison r = +1 et de valeur initiale i0 = 0.

iN = i0 + r*n

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 :

L16?
while un > 0:

On commence la démonstration en récupérant la condition de boucle et en remplaçant i par iN.

L16
while iN < longueur:

On remplace iN en utilisant (2) :

L16
while n < longueur:

Pour obtenir un symbole "supérieur", on écrit b > a plutôt que a < b :

L16
while n < longueur:
L16
while longueur > n:

Pour obtenir un zéro à droite, on doit passer les termes de droite à gauche :

L16
while longueur > + n:
L16
while (longueur - n) > 0:

Nous obtenons alors le VARIANT de boucle uN exprimé de cette façon :

L16
while uN > 0:    avec uN = longueur - 1 * sn

Etape 4 : conclusion

On voit que le variant est une suite d'entiers dont la raison est r = -1 : on perd 1 à chaque fois. La suite est donc décroissante.

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.

5 - Coût et Complexité

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.

Il s'agit de voir comment va évoluer le nombre d'instructions ou le nombre d'évaluations à effectuer lorsque le nombre de données d'entrée n évolue.

On comprend bien qu'il vaut mieux que ce nombre d'instructions soit lié à n qu'à n2 ou pire 2n.

Allures des différentes fonctions
Allures des différentes fonctions

On voit qu'un algorithme dont le nombre d'instructions est lié à 2n donne rapidement un nombre énorme d'instructions à effectuer.

Le but est donc de créer des algorithmes qui demandent le moins d'opérations possibles.

Tentons de trouver la complexité de notre algorithme de recherche.

Le plus facile est de tenter de trouver le coût dans le pire des cas. Puisque la méthode consiste à lire les éléments un par un dans l'ordre, le pire des cas est ici que l'élément cherché n'existe pas dans le tableau car il faudra alors parcourir tout le tableau avant de répondre.

J'ai rajouté un print() de façon à connaitre le nombre de tours de boucle réalisés pour répondre.

1 2 3 4 5 6 7 8 9 10 11 12 13
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 print(i) if i < longueur: reponse = i else: reponse = -1 return reponse

16° Placer la fonction en mémoire dans Thonny. Utiliser les commandes suivantes dans la console.

On remarquera que lors de tous les tests, on fait une recherche sur un élément inexistant de façon à devoir parcourir tout le tableau : il s'agit bien du pire des cas.

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

Question : lorsqu'on fournit à cet algorithme un tableau de n éléments, la complexité de cet algorithme de recherche est-elle liée

  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, c'est à dire que la complexité est fonction de n.

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

Nous allons donc classer les coûts dans l'ordre suivant (du meilleur au pire) :

  • Le coût constant
  • Le coût logarithmique
  • Les coûts polynomiaux
    • Le coût racinaire (un cas polynomiale, n1/2)
    • Le coût linéaire (un cas polynomiale, n1)
    • Le coût quadratique (un cas polynomiale, n2)
    • Le coût cubique (un cas polynomiale, n3)
    • Les autres coûts polynomiaux (ceux dont la complexité est en n4 et plus)
  • Le coût exponentiel (les fonctions en 2n, en en, 3n...)
  • Le coût factoriel
Définition simplifiée de la notation 𝓞 : borne supérieure du coût de l'algorithme

Parfois, on ne peut pas trouver facilement le comportement exact d'un algorithme. Son comportement peut être très variable en fonction des entrées fournies par exemple.

Cette notation va permettre de préciser que notre algorithme se comporte au pire de cette façon.

On obtient une indication un peu 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).

Cette notation sert donc notamment à exprimer une sorte de coût maximum.

Parfois, on connait mieux l'algorithme que cela. On peut prévoir comment il réagit vraiment et pas juste donner une borne supérieure à son comportement.

On utilise alors la notation 𝞗 (on prononce Theta).

Notation 𝞗 : ordre de grandeur du coût

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.

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.

17° 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).

18° 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) = 10 n + 4000 n

Cet algorithme à coût cubique : f(n) = 300 n3 + 9000 n2 + 10 n

Cet algorithme à coût quadartique : 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.

7 - FAQ

On ne peut pas faire pareil avec une boucle bornée FOR ?

Nous avions déjà vu ceci :

Toute boucle bornée POUR / FOR d'un algorithme peut être programmée à l'aide

  • d'un for (version naturelle) ou
  • d'un while

Certaines boucles non bornées TANT QUE / WHILE peuvent être programmées l'aide

  • d'un while (version naturelle) ou
  • d'un for associé à un return (dans une fonction) ou un simple break.

Du coup, notre algorithme de recherche peut être implémenté de deux façons :

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

Ou en encore plus simple en utilisant un for :

1 2 3 4 5 6
def rechercher(t, x): '''Renvoie l'indice de la première occurrence de x dans t, -1 si non présent''' for i in range( len(ta) ): if t[i] == x: return i return -1

Le contre : c'est du bidouillage puisqu'on utilise un boucle BORNEE pour obtenir l'effet d'une boucle NON BORNEE. Et notre fonction possède deux portes de sortie.

Le pour : le code peut paraître plus facile à comprendre.

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)

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 innaccessible à un observateur humain.

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