Algorithmes et 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. — Définitude. Chaque étape doit être définie de manière précise. Chaque cas doit ainsi être traité de manière rigoureuse et sans ambiguïté. De manière générale, les étapes sont constituées d’actions élémentaires autorisées. Ce qui est le cas par exemple avec les jeux d’instructions dans un langage informatique, une étape ne peut être définie qu’avec des mots autorisés par ce langage. Dans notre exemple, à l’étape de recherche du reste, le lecteur est supposé comprendre le sens de l’opération de division euclidienne entre deux entiers m et n, cela veut aussi dire qu’à tout instant, au cours de cette étape, il faut que m et n soit des entiers auquel cas la division euclidienne n’est pas bien définie. Ici c’est toujours le cas, puisque c’est vrai à l’initialisation et que l’étape de réduction ne change pas la nature de n et m. — Entrée. Un algorithme peut avoir un certain nombre d’entrées. Une entrée est une quantité qui est donnée à l’initialisation avant même que l’algorithme ne commence ou bien, de manière dynamique au cours de l’exécution. Ces entrées sont choisies dans des ensembles spécifiques. Dans notre exemple, les deux entrées sont n et m qui sont deux éléments de l’ensemble des entiers naturels N. — Sortie. Un algorithme a au moins une sortie. Une sortie est une quantité qui a une relation particulière avec les entrées. Dans le cas de l’algorithme d’Euclide, la sortie est le PGCD des entrées. Pour prouver que c’est bien cette sortie que nous obtenons, il suffit de voir que le PGCD de m et n et le PGCD de n et r sont les mêmes. — Efficacité. Les opérations effectuées par l’algorithme doivent être efficaces, dans le sens où elles doivent être suffisamment basiques pour pouvoir être effectuées en un temps fini par quelqu’un utilisant juste un crayon et une feuille de papier. Les opérations utilisées dans l’algorithme d’Euclide ne consistent qu’à faire la division entre deux entiers, tester si une variable est nulle, et modifier des variables par des nouvelles valeurs entières. De ce fait ces opérations sont efficaces dans ce sens, puisque les nombres entiers peuvent être écrits sur un papier sous une forme finie, et nous connaissons une méthode elle même finie pour diviser deux nombres entre eux. Si nous remplacions cette division d’entier par une division sur des nombres réels arbitraires qui peuvent avoir un nombre de décimal infini, l’opération deviendrait alors inefficace puisqu’il est impossible de représenter ces nombres de manière finie sur un papier.

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. Remarque. Il est possible de faire une analogie avec les statistiques. Le pire cas est ainsi un maximum de la fonction de coût, sur toutes les entrées nous savons que nous ne dépasserons pas le coût du pire cas. De manière similaire, le meilleur cas est un minimum, pour toute entrée nous avons un coût au moins aussi grand que le meilleur cas. Évidemment, le cas moyen est une moyenne par définition. Bien qu’en pratique il est possible de rencontrer peu fréquemment le pire cas, l’analyse de ce dernier peut rester important pour des applications critiques qui jouent le rôle d’une garantie sur le temps d’exécution de l’algorithme une fois implanté sur une ressource critique. La notation de Landau Nous allons faire un rappel sur la notation de Landau qui est grandement utiliser en théorie de la complexité. Nous allons, par la suite, nous intéresser à des fonctions définies sur les entiers positifs à valeurs réelles et croissantes. 35 Majoration, notation O Nous l’avons utilisée précédemment pour discuter de la complexité du tri rapide. La notation O permet de définir une majoration d’une fonction par une autre à une constante près. Plus formellement, on dit qu’une fonction f(n) = O(g(n)), s’il existe un rang n0 et une constante c ∈ R, tels que pour tout n > n0, on a l’inégalité f(n) < c × g(n) qui est vérifiée. Minoration, notation Ω À l’opposé de la majoration, il est possible de définir une minoration d’une fonction par une autre à une constante près. Dans ce cas, on dit que f(n) = Ω(g(n)) si et seulement si g(n) = O(f(n)). Borne, notation Θ On dit qu’une fonction est bornée par une autre fonction à une constante près si cette première est à la fois majorée et minorée par cette deuxième. Autrement dit, nous avons f(n) = Θ(g(n)) si et seulement si f(n) = Ω(g(n)) et f(n) = O(g(n)). Négligeable, notation o On dit que la fonction f est négligeable devant la fonction g si pour toute constante réelle c ∈ R, il existe un rang n0 ∈ N tel que pour tout n > n0 l’inégalité f(n) < c × g(n) est vérifiée. Nous notons alors que f(n) = o(g(n)). Nous pouvons également remarquer que, si f(n) = o(g(n)), alors f(n) = O(g(n)). Domine, notation ω On dit que f domine g si l’on a g(n) = o(f(n)). On note alors que f(n) = ω(g(n)). Nous pouvons ainsi faire une remarque similaire à celle qui a été faite pour la notation o, à savoir que si f(n) = ω(g(n)), alors f(n) = Ω(g(n)). Équivalent, notation ∼ On dit que f est équivalent à g, si et seulement si, f(n) = g(n) + o(g(n)). On note alors f(n) ∼ g(n). Une fois de plus, nous pouvons faire une remarque similaire aux précédentes, si f(n) ∼ g(n) alors f(n) = Θ(g(n)). D’après les trois remarques précédentes, on peut dire que ces trois premières définitions sont des cas particuliers plus faibles de ces trois dernières définitions. Lorsque l’on cherche à faire l’analyse sur la complexité d’un algorithme, nous procéderons souvent ainsi, premièrement, nous choisirons le type de comportement qui nous intéresse comme par exemple le pire cas, ensuite nous choisissons une fonction de coût comme, par exemple, le nombre de comparaisons total pendant l’exécution de l’algorithme, et enfin, nous utilisons la notation de Landau pour comparer cette fonction avec des fonctions plus simples.