Terminaison et complexité

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.

Définition

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$ (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 IX^e 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 XIX^e 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 XX^e 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 XX^e siècle, entraine 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.

• Un même algorithme peut donc être appliqué de différentes manières, et dans différents langages informatiques.

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

Un algorithme est une série d’instructions destinés à résoudre le problème. L’algorithme doit donc se terminer à un moment. Les séquences d’instruction des algorithmes se composent notamment de boucles et de branchements conditionnels. Il est donc nécessaire de s’assurer qu’aucune erreur de conception ou d’implémentation n’empêche l’algorithme de se terminer.

Dans le cas des boucles on distingue les boucles de type for et les boucles de type while.

• Les boucles de type for

Avec les boucles de type for 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 for … in 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 range à partir de la longueur de la liste.

Pour être encore plus explicite on peut demander d’afficher la valeur de la variable index correspondant à la position de l’élément dans la liste.

On obtient l’affichage suivant : 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.

Définition

Variant de boucle :

Un variant de boucle est une expression dont la valeur varie à chaque itération

• Les boucles de type while

Avec les boucles de type while 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 :

Attention

Si on omet la dernière ligne qui incrémente la valeur de la variable i, elle conservera indéfiniment sa valeur initiale. La condition testée au niveau de l’instruction while 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 while 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 while 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.

À retenir

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.

Définition

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.

• L’invariant de boucle n’est pas altéré par l’itération.

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.

• Vérifions-le, étape par étape :
• Avant l’entrée dans la boucle, la variable mini est initialisée avec la première valeur de la liste. Elle est donc bien inférieure ou égale à cette valeur.
• Pour chaque tour de boucle la condition est vraie à l’entrée dans la boucle. Elle l’est aussi à la sortie de chaque tour de boucle, puisque sa valeur est chaque fois comparée à un nouvel élément de la liste :
• si l’élément courant est plus grand, la variable mini reste inchangée et est donc déjà inférieure ou égale à toutes les valeurs déjà rencontrées ;
• si l’élément courant est plus petit, la variable mini prend sa valeur pour devenir inférieure ou égale à toutes les valeurs déjà rencontrées en sortie de boucle.
• Lorsque l’ensemble des itérations est terminé, la liste a été parcourue en totalité et la variable mini est bien inférieure ou égale à toutes les valeurs de la liste.
• La propriété choisie est bien un invariant de boucle. Notre algorithme est donc correct.

Astuce

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.

À retenir

• L’existence d’un variant de boucle est nécessaire à la terminaison de l’algorithme.
• L’existence d’un invariant de boucle est nécessaire à la correction de l’algorithme.

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

Définition

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 :

• la complexité temporelle fait référence au temps mis par un programme informatique pour résoudre le problème ;
• la complexité spatiale fait référence à l’étendue de l’espace mémoire de l’ordinateur nécessaire pour résoudre le problème.

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.

• En général la complexité algorithmique désigne d’abord la complexité temporelle.

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.

• Si l’élément se situe au milieu de la liste, notre algorithme doit parcourir la moitié de celle-ci pour trouver l’élément.
• Si l’élément se situe au début de la liste, notre algorithme doit effectuer une seule lecture.
• Si l’élément se situe en fin de liste, notre algorithme doit parcourir toute la liste avant de le trouver.
• Les trois recherches effectuées en milieu, en fin et en début de liste montrent qu’avec cet algorithme le nombre de tours de boucle dépend de la position du nombre recherché dans la liste. Le pire cas de figure est évidemment lorsque le nombre recherché est le dernier de la liste ou absent de la liste, puisque dans les deux cas l’algorithme devra parcourir la totalité de la liste pour le constater.

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 $\text{n}$ la taille du problème considéré, il nous importe de savoir ce qui se passe quand $\text{n}$ devient très grand.

Exemple

Dans notre exemple, $\text{n} = 10$ et dans le pire cas de figure notre algorithme doit effectuer 10 tours de boucle. Si $\text{n} = 10.000$ notre algorithme devra effectuer dans le pire cas de figure 10.000 tours de boucle.

L’ordre de grandeur de notre algorithme est donc directement lié à la taille $\text{n}$ de notre liste. Sa complexité est linéaire car directement proportionnelle à $\text{n}$.

Il existe une notation spécifique pour l’exprimer : appelée « grand $\text{O}$ », elle s’écrit $\text{O}()$. La lettre $\text{n}$ désigne la taille du problème considéré.

Dans le cas présent, l’ordre de grandeur est celui de $\text{n}$. On écrira donc $\text{O}(\text{n})$.

Quand n 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 $\text{n}$. La notation grand $\text{O}$ 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 $\text{n}\times\text{n}$, soit $\text{n}^2$. Il est de complexité quadratique et l’on exprime en ordre de grandeur par $\text{O}(\text{n}^2)$.

• Cela signifie que si la liste comporte mille éléments, le programme effectuera un million de tours de boucle.

Pour les algorithmes plus complexes, étant composés de plusieurs termes, on retient uniquement celui d’ordre le plus élevé.

Exemple

Pour $\text{n}^2+7\times\text{n}+400$ l’ordre de grandeur est $\text{n}^2$.

Si $\text{n}=1$ ou $\text{n}=10$ la valeur de la constante 400 est bien plus importante, mais à mesure que $\text{n}$ grandit, son importance décroit. Il en va de même pour $7\times\text{n}$. On ne retient que $\text{n}^2$.

Si un coefficient multiplicateur est présent, il est pareillement négligé. Ainsi $3\times\text{n}$ et $7\times\text{n}$ sont tous deux d’ordre n, que l’on écrira $\text{O}(\text{n})$.

Pour $3\times\text{n}+\text{log}2(\text{n})+5$ l’ordre de grandeur est $\text{n}\times\text{log}(\text{n})$.

Pour l’ordre de grandeur on ne précise pas non plus la base logarithmique qui devient négligeable quand $\text{n}$ grandit.

Les principaux ordres de grandeur algorithmiques, peuvent être classés selon leur complexité en temps croissante :

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.

Rappel

Il existe une méthode très simple pour obtenir notre résultat en une ligne de code. Le mot-clé in 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 :

• Notre algorithme parcourant systématiquement la totalité de la liste, la complexité en temps de cet algorithme est de l’ordre de $\text{n}$.

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’interrompe 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 break 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 :

• En revanche s’il n’y a pas de correspondance, notre algorithme devra toujours parcourir l’intégralité de la liste élément par élément.

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 $\text{O}(\text{n})$.

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.

Algorithme de recherche par dichotomie

Le fait qu’une liste soit triée facilite grandement les recherches.

Imaginez un dictionnaire dont les mots ne seraient pas triés par ordre alphabétique : il faudrait en lire chaque page dans l’espoir de finir par trouver le mot dont on cherche la définition. C’est ce que fait notre algorithme naïf : il explore la liste, élément après élément, jusqu’à trouver ce qu’il cherche.

Avec un dictionnaire trié par ordre alphabétique, il est beaucoup plus facile et rapide de trouver un mot. Il suffit de l’ouvrir au milieu et de regarder si le mot recherché se situe sur la page recherchée. S’il ne l’est pas, l’ordre alphabétique nous permet de savoir s’il est situé dans la première ou dans la seconde moitié du dictionnaire. On choisit la moitié adaptée, que l’on sépare à nouveau en deux en son milieu, et on répète le processus jusqu’à finir par trouver le mot recherché.

• C’est le principe de la recherche dichotomique.

Rappel

Les chaines de caractères peuvent être ordonnées. De la même manière dont Python est capable d’évaluer l’expression $2 < 3$ comme vraie (True) et l’expression $4 < 3$ comme fausse (False), il est capable d’évaluer une égalité ou une inégalité entre deux chaines de caractères, sur la base de l’ordre alphabétique, également appelé ordre lexicographique. Ainsi l’expression $\text{clavier} < \text{imprimante}$ est vraie (True) mais l’expression $\text{webcam} < \text{souris}$ est fausse (False).

• Cette capacité du langage à comparer l’ordre lexicographique des chaines de caractères nous permet d’implémenter facilement la recherche dichotomique.

Nous allons à chaque fois déterminer l’élément situé au milieu de la portion de liste qui nous intéresse. Nous commencerons par la liste complète. Si la valeur de la liste en son milieu correspond à l’élément recherché, nous l’avons trouvé et l’algorithme se termine. Sinon nous comparons la valeur de l’élément milieu avec celui que nous recherchons pour déterminer quelle moitié de liste conserver :

• si l’élément milieu est supérieur dans l’ordre lexicographique au mot recherché, nous conservons la première moitié de liste ;
• si l’élément milieu est inférieur dans l’ordre lexicographique au mot recherché, nous conservons la seconde moitié de liste.

Nous répétons l’opération en réduisant chaque fois la liste de moitié jusqu’à trouver l’élément recherché ou jusqu’à ce qu’il ne soit plus possible de réduire davantage la liste. Quand la liste ne peut plus être réduite, si l’élément n’a toujours pas été trouvé cela signifie qu’il ne figurait nulle part.

Nous testons le bon fonctionnement de notre algorithme.

Pour visualiser de manière détaillée le fonctionnement de notre algorithme et le nombre de tours de boucle effectués, nous insérons dans notre code un compteur et un affichage des valeurs des différentes variables.

Nous relançons les mêmes requêtes que précédemment.

Produit l’affichage suivant :

Évaluons aussi le cas de la recherche infructueuse.

Produit l’affichage suivant :

Nous observons que notre algorithme dichotomique est plus performant que nos précédents algorithmes systématique et séquentiel. Sa complexité est $\text{O}(\text{log}(\text{n}))$ au lieu de $\text{O}(\text{n})$ (non démontré ici). On peut constater sur cet exemple simple que la recherche dichotomique réduit très vite la taille des portions de liste, que la recherche soit ou non fructueuse.

Cette optimisation a été rendue possible parce que la liste est triée. Nous avons exploité une caractéristique particulière de notre problème qui nous a permis de prendre des « raccourcis » en nous évitant d’avoir à chercher dans des pans entiers de la liste.

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.