Qu'apportent comme résultats les algorithmes de recherche ? Comment les classer et déterminer leur application ? Parlons-en !

I. Introduction

A. Qu'est-ce que l'algorithmie ?

Je ne prétendrai pas avoir une définition définitive et complète de ce qu’est un algorithme, mais je vais essayer de donner une définition qui cadre avec les différentes situations auxquelles j’ai fait face et qui m’ont permis d’appliquer le concept d’algorithme.

Un algorithme est une suite ordonnée et finie d’étapes ou d’instructions pour réaliser un objectif. Il ressort de cette définition que les algorithmes se trouveraient un peu partout. Du domaine scientifique à la vie de tous les jours.

Nous sommes souvent confrontés à des situations qui font appel à des algorithmes dans tous les domaines de nos vies. Mais ce qui est encore plus important, c’est le besoin de mieux faire les choses, de faire mieux qu’avant. Les interrogations qui en découlent nous poussent à faire de l’optimisation de ces mêmes algorithmes. Mais hélas dans nos vies quotidiennes, nous ne sommes pas portés à faire des études approfondies de cet outil et nous tenterons dans cet article de détailler les subtilités de ce dernier.

B. Qu’est-ce qu’une structure de données ?

D’une manière simple, je peux définir une structure de données comme un récipient, un objet qui est sensé recevoir d’autres données (en informatique), un contenant.

Ce genre d’objet est courant dans notre vie. De nos maisons à nos lieux de travail, en passant par de nombreuses autres étapes, nous sommes souvent amenés à utiliser des structures qui doivent contenir quelque chose.

En informatique, nous avons aussi de nombreuses structures qui jouent pratiquement le même rôle que dans la vie de tous les jours et surtout permettent d’organiser des données en entrée et en sortie d’un algorithme.

II. Les Algorithmes

Les algorithmes constituent tout un domaine en informatique et fait l’objet de nombreuses études. C’est un domaine qui mobilise un nombre important de chercheurs, car il existe autant d’algorithmes à étudier qu’il existe de manières de faire les choses.

Nous n’avons pas la prétention de détailler de manière très approfondie les types d’algorithmes et leurs implications, tant le sujet est large. Mais nous parlerons des grandes lignes concernant les algorithmes et resterons sur des applications assez courantes des algorithmes.

A. Les différentes sortes d’algorithmes et leurs applications

Pour fonctionner, les algorithmes ont besoin des ressources de l’ordinateur. Ces ressources sont : le temps CPU et la mémoire. Le temps CPU pour permettre d’exécuter les instructions d’un algorithme et la mémoire pour contenir ou manipuler les données consommées ou produites par l’algorithme.

Nous introduisons un outil très puissant qui s’appelle l’analyse de la complexité. En effet cet outil permet de quantifier les deux grandeurs décrites précédemment : le temps et la mémoire, afin de comparer les algorithmes entre eux pour les classifier.

Nous n’allons pas dans cet article faire une étude approfondie sur l’analyse de la complexité d’un algorithme, mais nous allons plutôt récupérer les résultats d’analyse des différents algorithmes enfin de les classer et de déterminer leurs applications.

La classification se basera principalement sur le critère temps.

• Les algorithmes de complexité en temps constant : ce sont des algorithmes qui ne consomment qu’une unité de temps CPU. Nous avons énormément de cas où la complexité d’un algorithme est de 1.

Pour écrire dans une case mémoire, la complexité est d’une unité. De même pour lire une case mémoire.

Dans le cas où nous traitons un tableau d’objet, la lecture et l’écriture ne consomment qu’une unité de temps CPU. Cela veut dire aussi que l’algorithme ne contient qu’une seule étape dans son déroulement.

Nous avons là les grandes lignes des complexités des algorithmes. Mais nous souhaitons avoir des cas pratique où l’on pourrait ressortir ces différents algorithmes.

B. Quelques exemples d’optimisation des algorithmes

La classification se basera principalement sur le critère temps.

• Les algorithmes de complexité en temps constant : ce sont des algorithmes qui ne consomment qu’une unité de temps CPU. Nous avons énormément de cas où la complexité d’un algorithme est de 1.

Pour écrire dans une case mémoire, la complexité est d’une unité. De même pour lire une case mémoire.

Dans le cas où nous traitons un tableau d’objet, la lecture et l’écriture ne consomment qu’une unité de temps CPU. Cela veut dire aussi que l’algorithme ne contient qu’une seule étape dans son déroulement.

• Les algorithmes de complexité en temps logarithmique ( log2 n ) : les algorithmes sont souvent mis en œuvre dans le cas des recherches dichotomiques, des parcours d’arbres binaires ou toute autre opération sur ces arbres binaires de recherches.

• Les algorithmes linéaires (n) : ces algorithmes sont mis en œuvre dans la recherche séquentielle d’un élément dans un tableau non trié.

• Les algorithmes en (n log n) : ce sont de bons algorithmes mis en œuvre dans les tris (nous verrons quelques exemples).

• Les algorithmes en n^k : ces algorithmes ne sont vraiment utilisables que lorsque k < 2.

Si 2 ≤ k ≤ 3, alors l’algorithme est utilisable que pour des problèmes de taille moyenne. Et lorsque k dépasse 3, on ne peut traiter que des petits problèmes.

• Les algorithmes en temps exponentiel (2n) : ces algorithmes sont peu utilisables sauf pour des problèmes de très petites tailles. Ces sont des algorithmes qualifiés d’inefficaces

Nous allons nous intéresser à des cas simples de l’étude de complexité et de l’optimalité. Les deux cas à étudier sont les algorithmes de recherche et les algorithmes de tris.

Algorithmes de recherche

Une des utilisations les plus communes de l’informatique est le stockage de collections de données présentant des caractéristiques communes, et la recherche parmi ces données, d’éléments satisfaisants certains critères. Si le nombre de données est important, comme c’est souvent le cas, les opérations de recherche, de tris et de stockage ne doivent pas être réalisés en consommant beaucoup de temps. 

D’où la nécessité de connaitre la complexité de l’algorithme et son optimalité.

Il existe pour les algorithmes de recherche ceux qui sont naïfs avec une grande complexité et ceux un peu plus intelligents.

Algorithmes de Recherche séquentielle

La recherche séquentielle s’applique à une collection de données représentée par une liste. La recherche séquentielle convient à des situations où il y a peu d’éléments et elle est aussi utile dans des situations où il existe beaucoup d’éléments, mais dans ce cas nous cherchons toujours les mêmes éléments.

Nous distinguons deux cas : la recherche dans une liste non triée et la recherche dans une liste triée

Recherche dans une liste non triée :

Posons de façon naïve cette solution pour la recherche d’un élément dans une liste  λ :

Pour i compris entre 1 et longueur(λ), comparer X et ième(λ, i)

« longueur » et « ième » sont des opérations de la collection (liste) et λ est la collection de données.

Nous allons étudier sa complexité en moyenne pour déterminer sa complexité dans le pire de cas.

Supposons qi la probabilité que l’élément X apparaisse dans la liste à la place i de la liste (i = 1, … ,n) et p est la probabilité pour que l’élément n’appartienne pas à la liste.

Nous déduisons une relation simple : p + q1 +…+ qn = 1

Alors le nombre moyen de comparaisons pour une recherche dans une liste est :

Moy(n) = 1.q1 + 2.q2 +…+ n.qn + (n+1).p

Supposons que l’élément que l’on cherche, est toujours dans la liste cela implique : p = 0

Alors l’équation devient Moy(n) = 1.q1 + 2.q2 +…+n.qn  

Cette quantité est grande lorsque nous avons un ordre suivant qn ≥…≥ q2 ≥ q1 , c’est-à-dire que les éléments à chercher sont en fin de liste.

Elle est petite dans le cas où q1 ≥ q2 ≥…≥ qn , c’est-à-dire que les éléments à chercher sont en début de liste.

Donc pour une recherche séquentielle, la complexité dans le pire de cas est de Θ(n), elle est linéaire. Mais pour les éléments se trouvant au début de la liste, la recherche peut aller encore plus vite.

C’est pour cela que, pour un grand nombre de recherches, il est intéressant de réorganiser la liste à chaque recherche. Alors dans ce cas on parle de la recherche auto-adaptative.

Algorithmes de Recherche séquentielle dans une liste triée :

Supposons qu’il existe un ordre total sur les éléments de la liste.  Supposons que les éléments de la liste sont triés en ordre croissant. Pour chercher X, il nous faudra parcourir séquentiellement les éléments du tableau jusqu’à ce que l’on trouve X ou un élément strictement supérieur à X (dans ce cas on sait que l’élément X ne se trouve pas dans la liste, puisque les éléments sont triés dans l’ordre croissant).

Dans le pire de cas, il faut faire n ou  (n + 1) comparaisons, comme pour une recherche séquentielle.

Mais examinons la complexité en moyenne de cet algorithme, comme nous l’avions fait avec la recherche séquentielle dans une liste non triée.

Notons qi la probabilité que X (l’élément recherché) soit égale au iième de la liste, pour i = 1, …, n ; Notons pj la probabilité que X soit strictement compris ente le jième et le (j + 1)ième élément de la liste, pour j = 1, …, n – 1

Enfin p0 (et pn ), la probabilité que X soit strictement inférieur (resp. supérieur) au premier (resp. dernier) élément de la liste.

Les deux événements étant disjoints, nous avons clairement : p0 + p1 + … + pn + q1 + … + qn = 1.

De cette relation, nous déduisons le nombre de relation tel que :

Plaçons-nous dans l’hypothèse d’équiprobabilité p0  =  p1 = … = pn et q1 = q2 = … = qn   et considérons quelques cas de figures.

Recherche d’éléments présents dans la liste : tous les pj  sont nuls.

Alors q1 = q2 = … = qn = 1/n , d’où le Moy(n) = (n + 1)/2

Dans ce cas on obtient le même nombre moyen de comparaisons que pour la recherche séquentielle dans une liste non triée.

Recherche d’éléments qui ne sont pas dans la liste : tous les qi sont nuls.

Alors p0  =  p1 = … = pn = 1/n+1, d’où Moy(n) = (n + 2)/2

Lorsque l’élément recherché ne se trouve pas dans la liste, on diminue de moitié le nombre de comparaisons par rapport à la recherche séquentielle dans une liste non triée. Tout simplement parce que l’algorithme s’arrête lorsqu’il rencontre un élément strictement supérieur à l’élément recherché.

Recherche d’éléments qui ont une chance sur deux d’appartenir à la liste : c’est le cas où Σ qi = Σ pj = 1/2

Ce qui est un résultat légèrement meilleur que celui que l’on obtient dans les mêmes conditions pour une liste non triée.

Malgré des légères différences de complexité dans les deux méthodes de recherche séquentielle, nous constatons qu’elle tient très peu compte du fait que la liste soit triée dans l’ordre croissant. Et sa complexité est en Θ(n) comme lorsque les éléments ne sont pas triés.

Algorithmes de Recherche dichotomique

La recherche dichotomique ou la recherche par dichotomie est une façon très efficace d’effectuer la recherche d’un élément X dans une liste.

Cette méthode de recherche utilise pleinement le fait qu’une liste soit triée.

Le principe de la recherche par dichotomie d’un élément X dans une liste triée L consiste à comparer X avec l’élément M du milieu de la liste L :

• Si X = M, on a trouvé une solution, la recherche s’arrête

• Si X > M, il est impossible que X se trouve avant M dans la liste L, et il ne reste à traiter que la moitié (droite) de la liste L

• Si X<M, X ne peut se trouver que dans la moitié gauche de L.

La recherche continue ainsi en diminuant de moitié le nombre d’éléments de la liste après chaque comparaison. Si en recherchant X dans toutes les partitions de la liste, aucun résultat n’est retourné alors nous concluons que X n’est pas dans la liste.

Nous allons étudier deux versions des algorithmes de recherche dichotomique : une version récursive et une version itérative.

La version récursive de la recherche par dichotomie

En suivant le principe de la dichotomie, nous sommes naturellement conduits à écrire la procédure récursive suivante :

procedure dicho (X: Element; t: array [1…n] of Element; g, d: 0…n+1; var res:0…n)

{ cette procédure récursive recherche par dichotomie l’élément X dans le tableau t dont les éléments sont triés en ordre croissant ; le résultat de la procédure est contenu dans la variable res : c’est 0 si X n’appartient pas au tableau , et c’est i ϵ {1, …, n} si X se trouve à l’indice du tableau. g et d étant des indices placés en début et en fin du tableau}

var m : 1…n
begin if g ≤ d then begin
	m := (g + d) div 2
	if X = t[m] then res := m
		else if X < t[m]

Pour réaliser cette recherche sur une liste de n éléments, on appelle cette procédure avec les paramètres g = 1 et d = n.

Ici la structure de la liste représentée par un tableau est très importante tout simplement parce que les algorithmes de recherche dichotomique ont besoin d’un accès direct aux éléments de la liste.

Avec une procédure récursive, nous avons besoin de prouver que l’algorithme est correct. Alors nous avons un point principal à vérifier pour tirer une conclusion :

* On doit montrer que l’algorithme termine toujours (soit avec res > 0, soit avec res = 0)

Nous devons prouver que les appels récursifs sont toujours en nombre fini, c’est-à-dire que la suite (gi, di) qui sont les bornes des différents sous-tableaux avec lesquels on appelle récursivement la procédure dicho, est finie.

Supposons que les (gi , di) construits pour 0 ≤ i ≤ k, avec g0  = 1 et d0 = n et mk = (gk + dk) div 2. Plusieurs cas sont à considérer :

• Si gk > dk , ou si X = t[mk] alors la procédure termine et il n’y a plus d’appel récursif.

• Si gk ≤ dk et X < t[mk], il y a un appel récursif et gk+1 = gk et dk+1 = mk – 1 ;

On a alors dk+1 – gk+1 < dk – gk

• Si gk ≤ dk  et X > t[mk], il y un appel récursif et gk+1 = mk + 1 et dk+1 = dk, on a encore

dk+1 – gk+1 < dk – gk

Ainsi la suite des écarts (di - gi) est strictement décroissante. Il existe donc un entier p tel que :

• Soit gp > dp ,et dans ce cas la procédure termine avec res = 0 ;

• Soit X = t[mp] avec mp = (gp + dp) div 2, et dans ce cas la procédure termine avec res = mp > 0.

Analyse et calcul du nombre de comparaisons

Dans toute recherche d’élément dans une liste, l’opération fondamentale reste la comparaison entre l’élément cherché et les éléments de la liste.

Nous allons par la suite analyser puis calculer la complexité au pire, au mieux et en moyenne de la procédure dicho.

Nous allons prendre comme exemple une liste triée de 12 éléments. Or la recherche dichotomique sur une telle liste est (ou peut-être) décrite par un arbre binaire.

Nous avons sur cette image les t[i] pour i = 1, …, 12 et fj pour j = 1, …, 12.

Les feuilles f0, f1, …, f12 représentent les cas de terminaison sans succès et les nœuds internes représentent les comparaisons de l’élément cherché avec les éléments t[i].

Voici de quelle façon on parcourt cet arbre :

• Si X = t[i] on arrête la procédure

• Si X > t[i] (resp. X < t[i]), la procédure se poursuit en comparant X et le fils droit (resp. gauche) de t[i]

Or le parcours en profondeur d’un arbre binaire, dans le pire de cas lorsque nous atteignons les feuilles, se fait en log (n).

Nous admettons sans démonstration que les algorithmes de recherche par dichotomie ont une complexité dans le pire de cas de l’ordre de Θ(log n).

Algorithmes de Tris

Les méthodes de tri sont très importantes dans le monde informatique dans l’informatique de gestion où un grand nombre d’applications consistent à trier les fichiers.

Mais intéressons-nous à son formalisme. La question fondamentale est qu’est-ce qu’un Tri ?

La spécification du tri

Supposons une liste de taille n (soit n éléments) ; à chaque élément est associé une clé qui appartient à un ensemble totalement ordonné ;

Le tri est alors une permutation de cette liste d’origine telle que les clés sont croissantes quand on parcourt la liste séquentiellement.

Décrivons plus formellement notre définition.

Le tri peut être vu comme un enrichissement du type abstrait Liste, c’est-à-dire comme une opération en plus dans la liste des opérations que l’on peut effectuer sur le type Abstrait Liste.

Alors nous avons : tri : Liste -> Liste

Nous avions constaté qu’il existe une relation étroite entre les clés des éléments de la liste et le tri de la liste.

Or les clés peuvent être spécifiées de cette manière :

Sorte : Clé

Utilise : Booléen

opération _≤_  (inferieur à): Clé x Clé -> Booléen

Axiomes :

                 x ≤ x = vrai

                (x ≤ y = vrai) & (y ≤ x = vrai) → x = y

                (x ≤ y = vrai) & (y ≤ z = vrai) → x ≤ z = vrai

avec

                x, y, z : Clé

Nous venons au travers de ces quelques lignes de formaliser que les clés appartiennent bien à un ensemble totalement ordonné.

Nous nous munissons d’une nouvelle opération clé,  tel que :

Clé : Element -> Clé

A tout élément d’une Liste, l’opération rend sa clé.

Donc une liste triée sera formalisée de cette manière :

Opération

                triée : Liste -> Booleen

Axiomes

                triée(liste-vide) = vrai

                triée(cons(e, liste-vide)) = vrai

                λ ≠ liste-vide → triée(cons(e, λ)) = (clé(e) ≤ clé(premier(λ))) Ʌ triée(λ)

avec  

                e : Element ; λ : Liste ; cons : un opérateur qui construit une liste

Donc nous arrivons à la conclusion suivante : le tri d’une liste λ consiste à trouver une liste λ’, dont les éléments sont une permutation des éléments de λ.

Qu’est-ce qu’une permutation : deux listes λ et λ’ sont des permutations l’une de l’autre, si et seulement si, le nombre d’occurrences de tout élément est égal dans les deux listes.

D’une manière un peu plus formelle, définissons la notion de permutation et de nombre d’occurrences.

Opérations

                perm : Liste x Liste → Booléen

                nb-occ : Elément x List → Entier

Axiomes

                nb-occ(x, liste-vide) = 0

      &nb