Algorithme ?

1. Qu’est-ce qu’un algorithme ?

Un article du Monde du 27 Janvier 2017 relevait cette définition d’un algorithme proposée par la CNIL ( Commission Nationale de l’Informatique et des Libertés ).

Cette définition incorrecte et problématique amena la CNIL à la modifier

On peut largement préférer la définition proposée par le site Interstice :

Le mot « algorithme » vient du nom du grand mathématicien persan Al Khwarizmi (vers l’an 820), qui introduisit en Occident la numération décimale (rapportée d’Inde) et enseigna les règles élémentaires des calculs s’y rapportant. La notion d’algorithme est donc historiquement liée aux manipulations numériques, mais elle s’est progressivement développée pour porter sur des objets de plus en plus complexes, des textes, des images, des formules logiques, des objets physiques, etc.
Un algorithme, très simplement, c’est une méthode. Une façon systématique de procéder pour faire quelque chose : trier des objets, situer des villes sur une carte, multiplier deux nombres, extraire une racine carrée, chercher un mot dans le dictionnaire… 

https://interstices.info/quest-ce-quun-algorithme/

Un des problèmes majeur de l’algorithmique est de s’assurer avant de le mettre en oeuvre qu’un algorithme va répondre au problème auquel il est censé apporter une solution.

Pour cela, on peut utiliser les notions liées d’invariant et de variant d’algorithme ( ou de boucle ).

Un algorithme est démontré correct par rapport à une spécification à l’aide :
– d’un invariant qui est une propriété préservée par l’algorithme,
-d’un variant qui est une quantité qui décroît à chaque itération de l’algorithme et assure sa terminaison.

2. Variant et invariant d’un algorithme.

Considérons l’algorithme de tri par sélection d’une liste ci-dessous :

def tri_selection(a):
    liste=a.copy()
    for i in range(len(liste)-1):
        indice_min=i
        for j in range(i,len(liste)):
            if liste[j]<liste[indice_min]:
                indice_min=j
        liste[i],liste[indice_min]=liste[indice_min],liste[i]
    return liste

Quel est l’invariant de cet algorithme ?
Quel est le variant ?
Qu’est ce qui assure la terminaison de cette algorithme et qu’il est correct ?

L’invariant est :
les i premiers éléments sont classés par ordre croissant.
Le variant est :
Il reste n-i éléments à classer ( n désignant la longueur de la liste ). Il est clairement décroissant.
La terminaison :
A la fin de l’algorithme, il ne reste plus d’éléments à classer et la liste complète est donc bien classée.

Exercice 1

Déterminer l’invariant, le variant de l’algorithme et la terminaison pour le tri bulle ou tri par propagation.

2. Tris par insertion

Exercice 2

1. En vous référant à l’article https://interstices.info/les-algorithmes-de-tri/, déterminer les conditions qui assurent que l’algorithme par insertion est bien un algorithme de tri.
2. Ecrire une fonction tri_insertion() permettant de trier une liste par ordre croissant.

3. Efficacité et complexité d’un algorithme.

Pour déterminer lequel des 3 algorithmes de tris que l’on a mis en place est le plus efficace, on peut comparer :

• leur temps d’exécution,
• leur complexité en calcul ( le nombre de comparaisons ( de test ) et d’échanges de valeurs ( affectation de variables ) qu’il y a eu.

Pour comparer leur efficacité en terme de temps, on peut utiliser le module timeit de Python.
On peut ajouter les commandes suivantes à la fin du script comportant vos différentes fonctions sur les listes.

import timeit

temp=timeit.timeit('tri_selection(liste_aleatoire(100))',number=10, globals=globals())
print(temp)

Cette commande affiche le temps mis pour trier 10 listes par la méthode tri_selection, chaque liste étant une liste aléatoire de longueur 100.

Exercice 3

Créer une fonction analyse_temp affichant le temps mis par vos 3 algorithmes de tris pour trier 100 listes aléatoires de longueur 10, 100, 1000, 10000.