Déjà plus de
1 million
d'inscrits !
Terminaison et complexité
Déjà plus de
1 million
d'inscrits !
Introduction :
Les algorithmes sont aujourd’hui omniprésents dans tous les secteurs et dans notre vie quotidienne. Dans ce chapitre, nous préciserons d’abord la grande ancienneté des algorithmes avant de nous intéresser aux notions de terminaison et de correction, puis de complexité algorithmique, que nous illustrerons ensuite par des études de cas d’algorithmes de recherche.
Ancienneté et modernité des algorithmes
De nos jours le terme algorithme est étroitement associé à l’informatique. Il n’est toutefois pas né avec les sciences numériques, mais avec les mathématiques dont les origines sont bien plus anciennes.
Algorithme :
Un algorithme est une séquence d’instructions décrivant de manière précise les étapes de la résolution d’un problème mathématique.
C’est une définition très large, qui peut s’appliquer aussi bien aux mathématiques, à l’informatique, et même à des recettes de cuisine ou au montage d’un meuble en kit.
Antériorité des algorithmes à l’informatique
Les algorithmes sont très antérieurs à l’informatique. Ils sont employés depuis l’Antiquité pour résoudre des problèmes. Les mathématiciens babyloniens ont transcrit sur tablettes, des procédures de calcul et de résolution d’équations. Les mathématiciens grecs employaient déjà des algorithmes : on peut citer le crible d’Eratosthène pour trouver des nombres premiers, l’algorithme d’Euclide pour déterminer le plus grand commun diviseur de deux nombres entiers ou encore l’algorithme d’Archimède pour le calcul du nombre (pi).
Les mathématiciens grecs n’employaient cependant pas le terme d’algorithme qui est d’apparition plus récente.
Préhistoire informatique et algorithmes
Le mot algorithme est une déclinaison latinisée du nom du grand mathématicien perse du IXe siècle Al-Khwârizmî, à qui on doit notamment les premiers manuels d’algèbre et de méthodes de résolution d’équation.
Au XIXe siècle, le métier à tisser mécanique a été inventé par le mécanicien français Joseph Marie Jacquard, premier système se programmant avec des cartes perforées. Quelques années plus tard, la mathématicienne britannique Ada Lovelace publie le tout premier algorithme destiné à être exécuté par la machine analytique inventée par Charles Babbage.
L’informatique se développe au XXe siècle, sous l’égide de plusieurs mathématiciens, parmi lesquels le britannique Alan Turing. Il formalise les concepts d’algorithmes et d’ordinateur et participe ensuite au développement des premières machines capables de stocker électroniquement des données.
Algorithmes informatiques
Le développement fulgurant des ordinateurs pendant la seconde partie du XXe siècle, entraîne celui des langages informatiques utilisés pour traduire la logique algorithmique, en instructions compréhensibles par l’ordinateur.
L’algorithme indique une méthode à appliquer pour résoudre un problème. Un programme informatique est une implémentation possible d’un algorithme.
Dans le langage courant, algorithme et programme sont souvent interchangeables. Avec les développements récents mais spectaculaires de l’intelligence artificielle, les algorithmes désignent aussi dans le langage courant toutes les décisions prises par des machines sur la base d’analyse de volumes colossaux de données.
Les méthodes de création et d’évaluation des algorithmes ont accompagné les progrès technologiques. En sciences numériques, les problèmes algorithmiques sont abordés de manière formalisée selon un cadre théorique bien défini. Ce cadre établit un certain nombre de critères d’évaluation des algorithmes.
Terminaison et correction algorithmiques
Il est nécessaire de pouvoir s’assurer qu’un algorithme effectue bien ce qui est attendu, qu’il finit bien par s’arrêter et qu’il effectue son travail dans un délai raisonnable. Nous allons dans ce chapitre nous intéresser aux notions de terminaison et de correction des algorithmes, et nous étudierons ensuite leur complexité dans la dernière partie.
Terminaison d’un algorithme
L’algorithme doit donc se terminer à un moment. Les séquences d’instruction des algorithmes se composent notamment de boucles et de branchements conditionnels.
Dans le cas des boucles, on distingue les boucles de type
et les boucles de type .Avec les boucles de type
le nombre de tours de boucle, appelés itérations, est explicitement défini. La sortie de boucle est donc certaine, à l’issue du parcours d’un nombre initialement fixé de valeurs.On obtient l’affichage suivant :
Pour faire émerger plus explicitement la notion de variant de boucle, nous réécrivons le code qui précède avec la notation indicielle, en remplacement de la notation
typique de Python.On obtient le même affichage que précédemment. La variable index va prendre successivement toutes les valeurs générées par la séquence
à partir de la longueur de la liste.Pour être encore plus explicite on peut demander d’afficher la valeur de la variable
correspondant à la position de l’élément dans la liste.On obtient l’affichage suivant :
La variable index prend bien les valeurs successives correspondant à chaque élément de la liste considérée. Notre algorithme comporte bien un variant de boucle.
Variant de boucle :
Un variant de boucle est une expression dont la valeur varie à chaque itération
Avec les boucles de type
le nombre d’itérations peut être indéterminé ; il existe par conséquent un risque que l’algorithme ne se termine jamais s’il est mal conçu ou mal implémenté.Le programme suivant affiche les nombres de 1 à 10 :
Si on omet la dernière ligne qui incrémente la valeur de la variable
, elle conservera indéfiniment sa valeur initiale. La condition testée au niveau de l’instruction restera toujours vraie. Le programme réalise alors une infinité de boucles, souvent désignée boucle infinie, qui nécessite un arrêt forcé pour reprendre la main.On peut facilement créer une boucle infinie avec un test incorrect par rapport au variant de boucle. Si nous décidons de modifier notre programme pour n’afficher que les nombres pairs en modifiant la valeur d’incrémentation, nous créons aussi une boucle infinie.
En effet, notre programme ne calcule que des nombres pairs, et la condition évalue au niveau de l’instruction
une non-égalité avec le nombre impair 11. Cette condition ne sera donc jamais fausse et le programme ne se terminera pas. On corrigera aisément ce code en indiquant une valeur paire ou en remplaçant la non-égalité par une inégalité d’infériorité.Quand les expressions évaluées par l’instruction
sont simples, il est assez facile de se prémunir contre une boucle infinie. Mais avec une expression plus complexe, la condition de sortie de boucle peut très bien ne pas se réaliser dans certains cas. Il faut donc prendre soin de toujours définir des conditions de sortie qui doivent finir par se réaliser quelles que soient les données fournies à l’algorithme.Si la boucle n’a pas d’élément variant comme dans notre premier exemple (omission de l’incrémentation) ou que les valeurs prises par l’élément variant ne correspondent pas à l’évaluation de l’expression conditionnelle à l’origine de la boucle, la terminaison ne peut pas se produire.
Un algorithme doit se terminer. Mais la terminaison d’un algorithme ne garantit pas la correction du résultat qu’il fournit.
Correction d’un algorithme
La démarche pour prouver la correction d’un algorithme consiste à trouver un invariant de boucle.
Invariant de boucle :
Un invariant de boucle est une propriété qui est vraie avant l’exécution d’une itération et qui reste vraie après cette exécution.
Découvrons plus concrètement cette notion avec un algorithme qui recherche et retourne la valeur minimale parmi une liste de valeurs.
Nous testons cet algorithme avec une liste non ordonnée de valeurs.
Nous constatons qu’il se termine et il semble fonctionner correctement. Recherchons une propriété qui resterait vraie avant et après itération.
L’algorithme procède élément par élément et ajuste la valeur de sa variable locale mini en fonction des valeurs rencontrées. Si une valeur est inférieure, elle devient le nouveau minimum. On peut donc considérer qu’à chaque instant la variable mini est toujours inférieure ou égale aux valeurs déjà rencontrées.
Le fait que la valeur de la variable mini puisse varier au cours de l’algorithme n’est pas un problème, car notre invariant de boucle n’est pas sa valeur mais une propriété qui lui est rattachée : le fait qu’elle soit à tout moment inférieure ou égale aux valeurs déjà rencontrées.
S’il est relativement aisé de trouver un invariant de boucle pour des algorithmes simples, la tâche peut s’avérer plus difficile avec des algorithmes plus élaborés.
La troisième notion à prendre en compte est celle de complexité des algorithmes, qui fait l’objet de la prochaine partie.
Complexité algorithmique
Tous les algorithmes ne mobilisent pas les ressources de la machine de la même manière. La notion de complexité traduit ici les performances prévisibles d’un algorithme donné.
Complexité :
La complexité fait référence à la quantité de ressources nécessaire à la résolution d’un problème.
Dimensions temporelle et spatiale de la complexité
Ces ressources peuvent être temporelles et spatiale :
Avec les ordinateurs modernes dotés de vastes espaces mémoire, la question de la complexité spatiale est devenue un peu moins cruciale. Elle ne doit pas être totalement négligée pour autant.
Scénarios optimistes et pessimistes
La performance d’un algorithme ne dépend pas seulement de la manière dont il a été conçu, mais aussi des données qui lui sont soumises.
Imaginons un algorithme chargé de déterminer si un élément est présent dans une liste non ordonnée d’éléments. Notre algorithme parcourt toute la liste, élément par élément, jusqu’à trouver l’élément, s’il est présent.
En voici une illustration concrète.
En général quand on évalue la complexité d’un algorithme on considère en priorité le pire cas de figure et le cas moyen. Le meilleur cas de figure est plutôt considéré comme une éventuelle bonne surprise.
Ordre de grandeur
Nous pourrions compter les instructions individuelles et le nombre de fois où elles sont répétées pour évaluer notre algorithme. Mais ce qui nous intéresse surtout, c’est la capacité de l’algorithme à traiter de gros volumes de données. Si on désigne par la taille du problème considéré, il nous importe de savoir ce qui se passe quand devient très grand.
Dans notre exemple, et dans le pire cas de figure notre algorithme doit effectuer tours de boucle. Si notre algorithme devra effectuer dans le pire cas de figure tours de boucle.
L’ordre de grandeur de notre algorithme est donc directement lié à la taille de notre liste. Sa complexité est linéaire car directement proportionnelle à .
Il existe une notation spécifique pour l’exprimer : appelée « grand », elle s’écrit . La lettre désigne la taille du problème considéré.
Dans le cas présent, l’ordre de grandeur est celui de . On écrira donc .
Quand devient très grand, le nombre d’instructions dans chaque tour de boucle importe de moins en moins, et devient négligeable par rapport à la valeur de . La notation grand est une simplification pour pouvoir évaluer un ordre de grandeur et comparer des algorithmes entre eux.
Considérons un programme qui imbrique des boucles.
Vous pourrez facilement constater en fixant différentes longueurs à la liste que le nombre de tours de boucles est , soit . Il est de complexité quadratique et l’on exprime en ordre de grandeur par .
Pour les algorithmes plus complexes, étant composés de plusieurs termes, on retient uniquement celui d’ordre le plus élevé.
Pour l’ordre de grandeur est .
Si ou la valeur de la constante est bien plus importante, mais à mesure que grandit, son importance décroit. Il en va de même pour . On ne retient que .
Si un coefficient multiplicateur est présent, il est pareillement négligé. Ainsi et sont tous deux d’ordre , que l’on écrira .
Pour l’ordre de grandeur est .
Pour l’ordre de grandeur on ne précise pas non plus la base logarithmique qui devient négligeable quand grandit.
Les principaux ordres de grandeur algorithmiques, peuvent être classés selon leur complexité en temps croissante :
Ordre | Complexité |
temps constant, quel que soit le volume des données traitées | |
logarithmique | |
linéaire | |
pseudo-linéaire | |
quadratique | |
exponentielle |
Algorithmes de recherche
Nous allons nous intéresser aux algorithmes de recherche pour illustrer les possibilités d’optimisation des algorithmes. Nous disposons d’une liste triée et nous désirons vérifier si un élément est présent dans cette liste.
Notre liste est un lexique de termes informatiques, triés par ordre alphabétique.
Il existe une méthode très simple pour obtenir notre résultat en une ligne de code. Le mot-clé
du langage Python permet d’évaluer l’appartenance d’un élément à une structure de données.Nous allons étudier différentes manières plus ou moins efficaces d’obtenir le même résultat.
Algorithme de recherche systématique
La première méthode est la plus simple. Nous parcourons toute la liste et nous évaluons pour chaque élément, s’il correspond à celui recherché. À l’issue du parcours nous indiquons par un booléen si l’élément recherché a ou non été trouvé.
Nous vérifions que notre algorithme se termine et fonctionne correctement.
Nous aurions également pu écrire cet algorithme avec la notation indicielle des listes :
Toutefois n’ayant pas besoin d’accéder à la position de l’élément dans la liste par son indice, on préfèrera la première solution qui permet un code plus lisible.
Notre algorithme actuel s’appuie sur la puissance de calcul de l’ordinateur dans une logique de « force brute » où toutes les possibilités sont systématiquement testées. Chaque élément de la liste est parcouru individuellement, du premier jusqu’au dernier.
Ajoutons un compteur pour mieux visualiser les tours de boucle opérés par notre algorithme, ainsi qu’un message quand une correspondance est trouvée entre l’élément recherché et la valeur courante dans la liste.
Testons à nouveau notre code.
Produit l’affichage suivant :
On obtient exactement le même nombre de tours de boucles pour une recherche non fructueuse.
Produit l’affichage suivant :
Il est relativement simple de l’améliorer.
Algorithme de recherche par parcours séquentiel
L’objectif de notre algorithme est de déterminer si un élément est présent dans une liste. Notre algorithme évalue si c’est le cas pour chaque élément, mais même après avoir trouvé une correspondance, il continue ses tours de boucle jusqu’à atteindre la fin de la liste.
Nous allons le modifier pour qu’il s’interrompt aussitôt dès qu’il trouve une correspondance. Pour bien visualiser les tours de boucle, nous continuons d’employer un compteur et un afficheur de message.
Nous effectuons la même recherche que précédemment.
Produit l’affichage suivant :
On constate que le dernier tour de boucle n’a pas été effectué, l’instruction
ayant interrompu la boucle. Dans le cas présent, on a seulement économisé un tour de boucle, mais si l’élément recherché se situe en début de boucle, l’économie est plus substantielle.Produit l’affichage suivant :
Cependant si on se place dans le pire cas de figure, notre algorithme ne fait guère mieux que précédemment. Il reste donc de l’ordre de .
Les deux algorithmes implémentés jusqu’à présent fonctionnent : ils se terminent et fournissent la réponse attendue. Mais ils ne prennent pas en compte une caractéristique importante de notre liste : le fait qu’elle soit triée. Cette particularité peut pourtant nous faire gagner beaucoup de temps.
L’optimisation algorithmique nécessite un examen attentif du problème à résoudre, et parfois un peu de créativité pour simplifier le problème initial en exploitant judicieusement une propriété remarquable de notre problème.
Conclusion :
Les algorithmes, nés dans l’Antiquité avec les mathématiques, ont connu un fort développement spécifique au XXe siècle avec l’apparition des sciences numériques. Les algorithmes informatiques sont évalués sous les angles de leur terminaison, de leur correction et de leur complexité.
Aujourd’hui omniprésents, les algorithmes peuvent avoir un fort impact sociétal. Ceux qui les conçoivent portent donc la responsabilité de produire des algorithmes fiables et dépourvus de défaut.