Régulièrement en informatique, les données sont organisées en tableau de valeurs.
On peut alors se demander si une valeur est dans le tableau :
liste_prenom = ['Antoine' , 'Bertrand', 'Camille']
print('Camille' in liste_prenom)
print('Nicolas' in liste_prenom)
On peut aussi vouloir parcourir toutes les valeurs, pour les afficher par exemple :
# Méthode classique : on itère sur les indices
for i in range(len(liste_prenom)):
print(liste_prenom[i])
# Méthode pur python : on itère directement sur les éléments
for prenom in liste_prenom :
print(prenom)
On va ci-dessous présenter trois algorithmes :
Nous allons travailler sur des données gégographiques.
Pour cela importons le fichier "paysMonde.csv" qui contient (pour chaque pays du monde, source : https://www.populationdata.net/) :
(vous pouvez l'ouvrir avec un tableur afin de visualiser les données).
with open("paysMonde.csv") as fichier :
tableau_complet = fichier.readlines()
print(tableau_complet)
C'est compliqué... Arrangeons cela :
tableau_valeurs = []
# On parcourt toutes les lignes du tableau
for ligne in tableau_complet :
# On coupe chaque ligne au niveau des ";""
tableau_valeurs.append(ligne.split(";"))
# On convertit les valeurs en entier ou float
# A partir de la ligne 1 car la 0 est les entêtes
for ligne in tableau_valeurs[1:] :
ligne[0] = int(ligne[0])
ligne[2] = int(ligne[2])
ligne[3] = float(ligne[3])
ligne[4] = float(ligne[4])
# On créée les sous-tables
noms = []
populations = []
superficies = []
densites = []
for ligne in tableau_valeurs[1:] :
noms.append(ligne[1])
populations.append(ligne[2])
superficies.append(ligne[3])
densites.append(ligne[4])
# On n'affiche que les 10 premiers
print(noms[:10])
On se donne un tableau de type quelconque et on cherche si une valeur donnée est dedans.
L'algorithme est simple :
i allant de 0 à longueur(table) - 1 :table[i] vaut valeur_cherchée :VraiFauxEn Python :
def cherche_valeur(liste, valeur) :
"""
Cherche la valeur indiquée dans la liste proposée
liste est une série de valeurs numériques triées
valeur est une valeur numérique à chercher
Renvoie True si la valeur est présente, False sinon
"""
for element in liste :
if element == valeur :
return True
return False
Est-ce que le pays "France" est dans la liste des noms :
cherche_valeur(noms,'France')
Est-ce que le pays "Cancanie" est dans la liste des noms :
cherche_valeur(noms,'Cancanie')
Cela a l'air de fonctionner sur des chaînes de caractères... Testons sur des entiers :
# On cherche la population du Cambodge
cherche_valeur(populations,16754937)
# On cherche une population n'existant pas
cherche_valeur(populations,1)
Et sur les flottants ?
# On cherche la densité de l'Australie
cherche_valeur(densites,3.27)
Et si on se trompe de type ?
cherche_valeur(noms, 12)
Rappelons qu'étudier la correction d'un algorithme nécessité d'étudier :
La terminaison est facile ici dans la mesure où notre algorithme est construit autour d'une boucle Pour parcourant l'ensemble des valeurs du tableau.
On peut prendre comme variant de boucle $longueur(tableau) - i$ où $i$ est le nombre de tours de boucles réalisé. Ce variant est bien un entier positif strictement décroissant.
Pour la correction partielle, on peut prendre comme invariant de boucle :
$$Après \: la \: boucle \: de \: rang \: k, \: la \: variable \: 'resultat' \: est \: 'Vraie' \: si \: la \: valeur \: est \: dans \: les \: k \: premièrs \: éléments \: du \: tableau$$On considère ici une variable $resultat$ qui contient est fausse par défaut et qui bascule à vrai dès que la valeur a été trouvée.
Prouvons que cet invariant est toujours vrai :
True). Sinon, il laisse la valeur à $Faux$ Donc après cette itération, $resultat$ contient bien la valeur attendue (héréditié).On a donc prouvé la correction partielle.
Combien d'opération fait notre algorithme dans le pire des cas (si la valeur cherchée est en fin de tableau) ?
Appelons $n$ la taille du tableau.
L'algorithme parcourt tous les éléments : cela fait $n$ itérations.
Pour chacune d'entre elles, il teste l'égalité entre l'élément et la valeur cherchée : $1$ opération.
On a donc en tout $n$ opérations : la complexité est linéaire $\mathcal{O}(n)$.
On peut s'en rendre compte en mesurant le temps de calcul de la fonction :
# Données de taille 100
liste = list(range(100))
valeur = 99
%timeit cherche_valeur(liste, valeur)
# Données de taille 100*100 => Temps 100 fois plus long ?
liste = list(range(100*100))
valeur = 100*100-1
%timeit cherche_valeur(liste, valeur)
On se donne désormais un tableau d'éléments que l'on peut classer et l'on cherche un extremum (la minumum ou le maximum).
On pourrait classer les textes en utilisant l'ordre alphabétique mais on va s'en tenir aux tableaux de nombres (populations, superficies et denistes).
L'algorithme est simple (on cherche le minimum) :
minimum est l'élélment 0i allant de 1 à longueur(table) - 1 :table[i] < minimum :minimum = table[i]minimumPour le maximum, on a juste à renverser le symbole d'ordre < dans le test.
En Python :
def cherche_minimum(liste) :
"""
Cherche le minimum dans la liste proposée
liste est une série de valeurs numériques
Renvoie la valeur du minimum
"""
minimum = liste[0]
for element in liste[1:] :
if element < minimum :
minimum = element
return minimum
def cherche_maximum(liste) :
"""
Cherche le maximum dans la liste proposée
liste est une série de valeurs numériques
Renvoie la valeur du maximum
"""
minimum = liste[0]
for element in liste[1:] :
if element > minimum :
minimum = element
return minimum
Quelle est la population minimale ?
cherche_minimum(populations)
Quelle est la densité maximale ?
cherche_maximum(densites)
C'est bien mais un peu frustrant : on aimerait bien retrouver le nom du pays ayant la population minimale ou la densité maximale. Pour cela il faudrait récupérer la valeur de l'extremum et l'indice de cette valeur :
def cherche_indice_minimum(liste) :
"""
Cherche le minimum et son indice dans la liste proposée
liste est une série de valeurs numériques
Renvoie l'indice et la valeur du minimum dans un tuple
"""
indice_min = 0
for i in range(1, len(liste)) :
if liste[i] < liste[indice_min] :
indice_min = i
return indice_min, liste[indice_min]
def cherche_indice_maximum(liste) :
"""
Cherche le maximum et son indice dans la liste proposée
liste est une série de valeurs numériques
Renvoie l'indice et la valeur du maximum dans un tuple
"""
indice_max = 0
for i in range(1, len(liste)) :
if liste[i] > liste[indice_max] :
indice_max = i
return indice_max, liste[indice_max]
Quel est le pays le moins peuplé ?
indice, pop = cherche_indice_minimum(populations)
print(noms[indice])
Quel est le pays le plus densément peuplé ?
indice, dens = cherche_indice_maximum(densites)
print(noms[indice])
On s'intéresse à la première version de l'algorithme (sans les indices).
Comme on est face à une boucle Pour, la terminaison est identique à celle de la première partie.
Pour la correction partielle, on peut prendre comme invariant de boucle :
$$Après \: la \: boucle \: de \: rang \: k, \: la \: variable \: 'minimum' \: contient \: la \: valeur \: minimale \: des \: k+1 \: premièrs \: éléments \: du \: tableau$$Prouvons que cet invariant est toujours vrai :
On a donc prouvé la correction partielle.
Combien d'opération fait notre algorithme dans le pire des cas (l'extremum est en fin de tableau) ?
Appelons $n$ la taille du tableau.
L'algorithme parcourt tous les éléments : cela fait $n$ itérations.
Pour chacune d'entre elles, il compare l'élément en cours et l'extremum actuel : $1$ opération.
On a donc en tout $n$ opérations : la complexité est linéaire $\mathcal{O}(n)$.
On peut s'en rendre compte en mesurant le temps de calcul de la fonction :
# Données de taille 100
liste = list(range(100))
%timeit cherche_maximum(liste)
# Données de taille 100*100 => Temps 100 fois plus long ?
liste = list(range(100*100))
%timeit cherche_maximum(liste)
On se donne désormais un tableau de nombres et l'on souhaite calculer sa moyenne.
L'algorithme est :
somme prend la valeur 0elements de table :somme prend la valeur somme + elementsomme / longeur(table)En Python :
def moyenne(liste) :
"""
Calcule la moyenne de la liste proposée
liste est une série de valeurs numériques
Renvoie la moyenne
"""
somme = 0
for element in liste :
somme += element
return somme / len(liste)
Quelle est la population moyenne ?
moyenne(populations)
Quelle est la superficie moyenne ?
moyenne(superficies)
Comme on est face à une boucle Pour, la terminaison est identique à celle de la première partie.
Pour la correction partielle, on peut prendre comme invariant de boucle :
$$Après \: la \: boucle \: de \: rang \: k, \: la \: variable \: 'somme' \: contient \: la \: somme \: des \: k \: premièrs \: éléments \: du \: tableau$$Prouvons que cet invariant est toujours vrai :
On a donc prouvé la correction partielle.
Combien d'opération fait notre algorithme dans le pire des cas (l'extremum est en fin de tableau) ?
Appelons $n$ la taille du tableau.
L'algorithme parcourt tous les éléments : cela fait $n$ itérations.
Pour chacune d'entre elles, il ajoute l'élément en cours à la somme : $1$ opération.
Une fois sortie de la boucle, il divise somme par len(table) : $1$ opération.
On a donc en tout $n + 1$ opérations : la complexité est linéaire $\mathcal{O}(n)$.
On peut s'en rendre compte en mesurant le temps de calcul de la fonction :
# Données de taille 100
liste = list(range(100))
%timeit moyenne(liste)
# Données de taille 100*100 => Temps 100 fois plus long ?
liste = list(range(100*100))
%timeit moyenne(liste)