Formation la complexité des algorithmes

Formation la complexité des algorithmes, tutoriel & guide de travaux pratiques en pdf.

Qu’est-ce qu’un algorithme ?

La notion d’algorithme est une notion difficile : il n’est pas si ´évident que cela de la definir. L’approche théorique de la notion d’algorithme passe par le concept de “machine de Turing”, modèle simplifié, idéalisation mathématique, d’un ordinateur “réel”. On appelle alors algorithme tout programme tournant sur une machine de Turing. Une fonction f est alors dite calculable s’il existe un algorithme (c’est-`a-dire une machine de Turing) qui soit capable de calculer f(x) pour tout x raisonnable. Cette idéalisation de l’ordinateur, possède une certaine universalité. D’autres approches de la notion d’algorithme conduisent `a la même classe de fonctions calculables. Nous nous contenterons ´évidemment dans ce cours d’une approche plus concrète : nous appellerons algorithme toute fonction ´écrite dans un langage de programmation tel que Caml. Signalons quelques problèmes posés par notre définition :

• La dépendance du langage utilisé. Cette d´dépendance n’est qu’apparente. Si l’on peut ecrire un algorithme calculant une fonction f en, mettons, Pascal, on pourra aussi en ecrire un en Caml. En revanche, certains algorithmes peuvent ˆêtre plus performants dans un langage que dans un autre langage. Problème intéressant, mais au-delà de la portée de ce cours. Un algorithme sera dorénavant une fonction Caml.
• Le codage des objets manipulés par un algorithme peut avoir de l’importance. On supposera toujours que l’on a affaire `a des codages raisonnables. Il est clair que coder un entier en base 1 ou en base 2 conduira sans doute `a des comportements différents des algorithmes : en base 2, 20 s’´ecrit 10100, et en base 1, il s’écrit 11111111111111111111. Que pensez vous de l’´ecriture de 1000000 ?
• On ne peut pas coder des ensembles infinis d’objets, ni même certains objets qui sont “infinis” par essence : par exemple, les réels non d´décimaux posent un problème. Ainsi, on ne peut pas coder l’ensemble des nombres réels, mais seulement un sous-ensemble fini de celui-ci. Les algorithmes de calcul numerique doivent tenir compte de ce fait.

Complexité

Naïvement, la complexité d’un algorithme est le “nombre d’opérations” nécessaires a l’algorithme pour effectuer son travail. Cette complexité donne une idée du temps n´nécessaire a l’algorithme pour s’exécuter. La notion de complexité n’a réellement de sens que dans le cadre des machines de Turing. Aussi, nous contenterons-nous d’´évaluer le nombre d’opérations d’un certain type judicieusement choisi n nécessaires a l’execution d’un algorithme. Ainsi :
• Dans un algorithme de tri comparatif, une opération significative sera sans doute une comparaison.
• Dans un algorithme de multiplication ou d’addition d’entiers longs, ce sera peut-etre une op´eration sur les bits.
• Dans une multiplication de polynomes a coefficients reels, ce sera surement une somme ou un produit de r´eels.
• Dans le cas d’une fonction recursive, il pourra etre interessant de calculer le nombre d’appel recursifs. • Dans un algorithme d´eplac¸ant beaucoup de donnees, le nombre d’operations d’affectation sera certainement revelateur du temps de calcul.
Lors de l’etude d’un algorithme, il n’est pas toujours evident de degager quelles sont les operations importantes. L’experimentation est parfois utile.
Exponentiation dichotomique 3

Taille des données

La complexité d’un algorithme calculant f(x) d´dépend bien entendu de la donnée x fournie au départ `a cet algorithme. Cette d´dépendance peut parfois être très complexe. Cela dit, elle est parfois fonction uniquement de la taille de x, que l’on définit comme le nombre de bits n´nécessaires au codage de x. Cette taille d´dépend donc du codage choisi pour les données. Mais tous les codages raisonnables fourniront en général des tailles comparables. Ainsi, par exemple, le codage d’un entier N en base 2 demande k fois plus de bits qu’un codage en base 10, mais le facteur k est indépendant de N. ✍ Que vaut la constante k ci-dessus ? ✍ Ainsi, en travaillant `a constante multiplicative pr`es, on pourra s’affranchir de discuter trop sur le codage des données. Ainsi, lorsque nous dirons qu’un objet X est de taille 1, cela signifiera que tous les objets du même type que X ont une taille bornée. A titre indicatif :

• Un entier Caml, un réel Caml sont des données de taille 1.
• Un entier naturel “long” n est une donnée de taille logn.
• Un tableau de n entiers est de taille n (mais un tableau de n entiers longs [x1,···,xn] serait de taillePn i=1 logxi, taille pouvant ˆêtre bornée par exemple par nmaxi logxi).
• Une matrice m × n d’entiers est de taille m.n
• Un polynôme de degré N `a coefficients entiers est de taille N.
• Un graphe G possédant M sommets et N arêtes est de taille M + N si l’on choisit de le coder par un tableau ´étiqueté par les sommets de G, dont les ´éléments sont des listes formées des sommets adjacents au sommet courant. Mais il sera de taille M2 si on choisit de coder G par une matrice A de taille M × M, dont le coefficient ai,j vaut 1 s’il y a une arête du sommet i vers le sommet j, et 0 sinon.