Terminaison et complexité - Fiche de révision - Numérique et sciences informatiques

Ancienneté et modernité des algorithmes

Les algorithmes 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 avec le crible d’Eratosthène, l’algorithme d’Euclide ou encore l’algorithme d’Archimède .

Le mot « algorithme » vient du mathématicien Muhammad Al-Khwarizmi, fondateur de l’algèbre.
Au XIX^e siècle, le métier à tisser mécanique a été inventé par 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.
Alan Turing 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.

Un programme informatique est une implémentation possible d’un algorithme.
Les algorithmes désignent aussi toutes les décisions prises par des machines sur la base d’analyse de volumes colossaux de données.
En sciences numériques, les problèmes algorithmiques sont abordés de manière formalisée selon un cadre théorique qui établit un certain nombre de critères d’évaluation des algorithmes.

L’algorithme doit se terminer.
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 :
for où le nombre itérations est explicitement défini. La sortie de boucle est donc certaine, à l’issue du parcours d’un nombre initialement fixé de valeurs.
while où 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é.
Il faut prendre soin de toujours définir des conditions de sortie.
L’existence d’un variant de boucle est nécessaire à la terminaison de l’algorithme.
La démarche pour prouver la correction d’un algorithme consiste à trouver un invariant de boucle.
L’invariant de boucle n’est pas altéré par l’itération.

La notion de complexité traduit ici les performances prévisibles d’un algorithme donné.
Ces ressources peuvent être temporelles et spatiale.
En général la complexité algorithmique désigne d’abord la complexité temporelle.

Si un algorithme est chargé de déterminer si un élément est présent dans une liste non ordonnée d’éléments, il parcourt toute la liste, élément par élément, jusqu’à trouver l’élément, s’il est présent.
Il effectue 3 recherches : au milieu, au début et à la fin de la liste.
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.

Ce qui nous intéresse surtout, c’est la capacité de l’algorithme à traiter de gros volumes de données.
L’ordre de grandeur de notre algorithme est donc directement lié à la taille $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}()$ .
Pour les algorithmes plus complexes, étant composés de plusieurs termes, on retient uniquement celui d’ordre le plus élevé.
Les principaux ordres de grandeur algorithmiques :

Ordre	Complexité
$\text{O}(\text{1})$	temps constant, quel que soit le volume des données traitées
$\text{O}(\text{log}\,n)$	logarithmique
$\text{O}(n)$	linéaire
$\text{O}(n\,\text{log}\,n)$	pseudo-linéaire
$\text{O}(n^2)$	quadratique
$\text{O}(2^n)$	exponentielle

Les algorithmes de recherche nous permettent d’illustrer les possibilités d’optimisation des algorithmes.
Un algorithme de recherche systématique, nous permet de parcourir toute une 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é.
La complexité en temps de cet algorithme est de l’ordre de $n$ .
Un algorithme de recherche par parcours séquentiel nous permet de vérifier si un élément est présent dans une liste, é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.
Cet algortihme reste de l’ordre de $\text{O}(n)$ .
Un algorithme naïf explore la liste, élément après élément, jusqu’à trouver ce qu’il cherche.