Théorie de la complexité

Algorithmes et théorie de la complexité

Dans cette section, nous allons présenter la discipline qu’est l’algorithmique. Pour commencer, nous donnerons une définition de ce qu’est un algorithme. Nous aborderons également la théorie de la complexité, qui est le domaine dans lequel s’inscrit ce manuscrit. Puis, nous discuterons des paradigmes les plus utilisés dans l’élaboration d’algorithmes. 

Qu’est-ce qu’un algorithme ?

Il n’est pas aisé de donner une définition de ce qu’est un algorithme. L’origine du mot viendrait d’une déformation du nom du mathématicien perse AlKhw¯arizm¯ari. Une analogie qui est souvent faite est celle de la recette de cuisine qui consiste en une suite d’instruction pour transformer les ingrédients en un plat. Concrètement un algorithme fait la même chose, il donne une suite d’instruction à effectuer pour transformer une entrée en une sortie, chaque instruction forme une étape de l’algorithme.

Un algorithme connu de beaucoup, est le célèbre algorithme d’Euclide que nous apprenons tôt à l’école pour déterminer le plus grand commun diviseur PGCD entre deux nombres entiers. Donald Knuth, qui est l’un des pionniers dans le domaine de l’algorithmique, définit 5 caractéristiques qu’un algorithme doit avoir [29][pp. 5-6] Pour illustrer ses propos, Knuth utilise l’exemple de l’algorithme d’Euclide, nous allons procéder de la même façon en donnant l’algorithme d’Euclide sous la forme suivante..

Données : Deux entiers m et n Résultat : Le PGCD de m et n, qui est le plus grand entier positif qui divise à la fois n et m. 1 tant que n 6= 0 faire 2 Faire la division euclidienne de m par n, soit r le reste obtenu de cette dernière. 3 m ← n 4 n ← r 5 retourner m Algorithme 1 : Algorithme d’Euclide Dans son livre, Knuth avait décomposé l’algorithme en 3 étapes. La première, E1 est l’étape de calcul du reste r de la division euclidienne de m par n qui correspond à la ligne 2. La deuxième, E2 est l’étape du test de r qui se fait par la combinaison de la ligne 4 suivie par la ligne 1, cette étape vérifie si le reste est 0 et dans ce cas l’algorithme s’arrête.

La troisième E3 est l’étape de réduction, dans cette étape nous réduisons le problème de calculer le PGCD entre m et n par le problème de calculer le PGCD entre n et r. Cela revient à modifier la variable m par la valeur de n, puis de modifier la variable n par le reste r, ce que nous faisons aux lignes 3 et 4. Nous pouvons dès à présent énumérer les 5 caractéristiques qu’un algorithme possède selon Knuth. — Finitude. Un algorithme doit toujours s’arrêter après un nombre fini d’étapes.

L’intérêt d’utiliser un algorithme est évidemment de trouver une solution à un problème, et il est donc nécessaire que ce dernier se termine en un temps fini pour espérer pouvoir obtenir la solution. Dans notre exemple, l’algorithme d’Euclide se termine toujours, si n et m sont 33 eux même finis. En effet, après l’étape de réduction n = r et 0 ≥ r < m, si on note par n0 = n, n1 = r, . . . les valeurs prises par n après chaque modification, cette suite est alors strictement décroissante et positive et sera donc bien amenée à se terminer par 0 au bout d’un certain nombre fini d’étapes.

Théorie de la complexité

Un des éléments importants dans plusieurs de ces définitions est qu’un algorithme doit pouvoir résoudre un problème avec efficacité. Nous devons donc définir des méthodes pour pouvoir mesurer l’efficacité d’un algorithme, et c’est ce que la théorie de la complexité nous permet de faire. Le but de la théorie de la complexité est ainsi de permettre de quantifier les performances d’un algorithme. Concrètement, nous nous intéressons au nombre d’opérations élémentaires effectuées par l’algorithme au cours de son exécution.

Ce nombre d’opérations doit de plus dépendre de la taille de l’entrée, par exemple, si l’entrée est une séquence, nous pouvons considérer son nombre d’éléments comme la taille de l’entrée. Bien souvent, nous nous intéresserons au comportement asymptotique de ce nombre d’opérations exprimé sous forme d’une fonction de coût f(n) quand la taille de l’entrée n est grande. En pratique, les fonctions de coûts qui vont nous intéresser permettent d’obtenir des estimations de la durée d’exécution ou de la mémoire utilisée d’une implantation de l’algorithme sur une machine RAM dont nous discuterons par la suite dans la section 3.2.

Il y a trois grands types de comportement qui sont principalement étudiés en théorie de la complexité : — L’analyse dans le meilleur des cas, qui comme son nom le laisse à penser, consiste à regarder le comportement de l’algorithme dans le cas où il reçoit l’entrée qui lui est la plus favorable. — L’analyse dans le pire cas, qui à l’opposée du premier type consiste à regarder le comportement de l’algorithme lorsque celui-ci reçoit l’entrée qui lui est la moins favorable. — L’analyse dans le cas moyen, qui revient à faire la moyenne de tous les coûts sur l’ensemble des entrées possibles.

Bien souvent, nous considérons que l’entrée est générée selon une distribution qui nous donne ainsi sa probabilité d’apparition. Nous définissons alors la complexité dans le cas moyen en regardant le comportement asymptotique de l’espérance du coût. Par défaut, nous choisissons souvent la distribution uniforme ce qui revient à la définition d’origine. Il peut cependant être intéressant de considérer d’autres distributions, et c’est ce que nous faisons par la suite dans le Chapitre 6.