{"id":1226,"date":"2020-06-09T22:43:13","date_gmt":"2020-06-09T20:43:13","guid":{"rendered":"http:\/\/labodemaths.fr\/WordPress3\/?p=1226"},"modified":"2020-09-09T19:17:06","modified_gmt":"2020-09-09T17:17:06","slug":"algorithme","status":"publish","type":"post","link":"https:\/\/labodemaths.fr\/WordPress3\/algorithme\/","title":{"rendered":"Algorithme ?"},"content":{"rendered":"\n

1. Qu’est-ce qu’un algorithme ?<\/h2>\n\n\n\n

Un article du Monde du 27 Janvier 2017<\/a> relevait cette d\u00e9finition d’un algorithme propos\u00e9e par la CNIL ( Commission Nationale de l’Informatique et des Libert\u00e9s ).<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Cette d\u00e9finition incorrecte et probl\u00e9matique amena la CNIL \u00e0 la modifier<\/a> <\/p>\n\n\n\n

On peut largement pr\u00e9f\u00e9rer la d\u00e9finition propos\u00e9e par le site Interstice :<\/p>\n\n\n\n

Le mot \u00ab algorithme \u00bb vient du nom du grand math\u00e9maticien persan Al Khwarizmi (vers l\u2019an 820), qui introduisit en Occident la num\u00e9ration d\u00e9cimale (rapport\u00e9e d\u2019Inde) et enseigna les r\u00e8gles \u00e9l\u00e9mentaires des calculs s\u2019y rapportant. La notion d\u2019algorithme est donc historiquement li\u00e9e aux manipulations num\u00e9riques, mais elle s\u2019est progressivement d\u00e9velopp\u00e9e pour porter sur des objets de plus en plus complexes, des textes, des images, des formules logiques, des objets physiques, etc.
Un algorithme, tr\u00e8s simplement, c\u2019est une m\u00e9thode. Une fa\u00e7on syst\u00e9matique de proc\u00e9der pour faire quelque chose : trier des objets, situer des villes sur une carte, multiplier deux nombres, extraire une racine carr\u00e9e, chercher un mot dans le dictionnaire\u2026 <\/p>https:\/\/interstices.info\/quest-ce-quun-algorithme\/<\/a><\/cite><\/blockquote>\n\n\n\n

Un des probl\u00e8mes majeur de l’algorithmique est de s’assurer avant de le mettre en oeuvre qu’un algorithme va r\u00e9pondre au probl\u00e8me auquel il est cens\u00e9 apporter une solution.<\/p>\n\n\n\n

Pour cela, on peut utiliser les notions li\u00e9es d’invariant et de variant d’algorithme ( ou de boucle ).<\/p>\n\n\n\n

Un algorithme est d\u00e9montr\u00e9 correct par rapport \u00e0 une sp\u00e9cification \u00e0 l’aide :
– d’un invariant qui est une propri\u00e9t\u00e9 pr\u00e9serv\u00e9e par l’algorithme,
-d’un variant qui est une quantit\u00e9 qui d\u00e9cro\u00eet \u00e0 chaque it\u00e9ration de l’algorithme et assure sa terminaison.<\/p>\n\n\n\n

2. Variant et invariant d’un algorithme.<\/h2>\n\n\n\n

Consid\u00e9rons l’algorithme de tri par s\u00e9lection d’une liste ci-dessous :<\/p>\n\n\n\n

def tri_selection(a):\n    liste=a.copy()\n    for i in range(len(liste)-1):\n        indice_min=i\n        for j in range(i,len(liste)):\n            if liste[j]<liste[indice_min]:\n                indice_min=j\n        liste[i],liste[indice_min]=liste[indice_min],liste[i]\n    return liste\n<\/code><\/pre>\n\n\n\n
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 ?<\/p>\n\n\n\n
L’invariant<\/strong> est :
les i premiers \u00e9l\u00e9ments sont class\u00e9s par ordre croissant.
Le variant<\/strong> est :
Il reste n-i \u00e9l\u00e9ments \u00e0 classer ( n d\u00e9signant la longueur de la liste ). Il est clairement d\u00e9croissant.
La terminaison<\/strong> :
A la fin de l’algorithme, il ne reste plus d’\u00e9l\u00e9ments \u00e0 classer et la liste compl\u00e8te est donc bien class\u00e9e.<\/p>\n\n\n\n
Exercice 1<\/h3>\n\n\n\n
D\u00e9terminer l’invariant, le variant de l’algorithme et la terminaison pour le tri bulle  ou tri par propagation.<\/p>\n\n\n\n
2. Tris par insertion<\/h2>\n\n\n\n
Exercice 2<\/h3>\n\n\n\n
  1. En vous r\u00e9f\u00e9rant \u00e0 l’article https:\/\/interstices.info\/les-algorithmes-de-tri\/<\/a>, d\u00e9terminer les conditions qui assurent que l’algorithme par insertion est bien un algorithme de tri.<\/li>
  2. Ecrire une fonction tri_insertion() permettant de trier une liste par ordre croissant.<\/li><\/ol>\n\n\n\n
    3. Efficacit\u00e9 et complexit\u00e9 d’un algorithme.<\/h2>\n\n\n\n
    Pour d\u00e9terminer lequel des 3 algorithmes de tris que l’on a mis en place est le plus efficace, on peut comparer :<\/p>\n\n\n\n