Next PDF List

Design and Analysis ofAlgorithmPierre-Alain FouquePierre-Alain.Fouque@univ-rennes1.frUniversité de Rennes 1Version novembre 2020IntroductionBien que le vocableinformatiqueait été inventé dans les années soixante, onpeut prétendre paradoxalement que l"informatique est à la fois une technique trèsrécente et une science très ancienne.C"est bien sûr une technique fort jeune : les premiers ordinateurs dignes de cenom ont vu le jour à la fin de la deuxième guerre mondiale.

Et c"est une techniquequi consiste souvent en la mise en œuvre d"outils malheureusement tout aussiimparfaits qu"éphémères : langages de programmation, systèmes d"exploitation,méthodes de conduite de projets logiciels, pour ne citer que ceux-ci.Par contre, en tant que science, l"informatique peut être considérée comme trèsancienne, car elle ne saurait être dissociée du développement des mathématiques,qu"elle a accompagné depuis les premiers balbutiements jusqu"à l"époque contem-poraine.

En effet, à l"aube des temps historiques et des civilisations naissantes, leshommes ont appris à compter; pour ce faire, ils ont inventé (ou découvert) lesnombres et leur codage, puis les opérations arithmétiques élémentaires telles quel"addition ou la multiplication.

Cet apport de génie a seul permis le réel décollagede l"activité économique (et donc culturelle), par le biais de l"élevage et de l"emploide la monnaie - il fallait bien compter les troupeaux et vendre ses productions.Or, codage des nombres et opérations arithmétiques de base forment justement lecœur de nos ordinateurs.Ce cours constituent précisément une introduction à l"aspect scientifique del"informatique.

Bien que cet aspect recouvre plusieurs théories distinctes (quoiqueinterconnectées), telles que logique et calculabilité, conception et sémantique deslangages de programmation, compilation, validation des programmes, etc., sa par-tie la plus essentielle est l"algorithmique, dont nous donnons tout d"abord la défi-nition extraite du petit Larousse :ALGORITHMEn.m. (ar.al-kh¯arezmi, surnom d"un mathématicienarabe).math.etinform.Suite finie d"opérations élémentaires consti-tuant un schéma de calcul ou de résolution d"un problème.ALGORITHMIQUEadj.

De la nature de l"algorithme.n.f.

Sciencedes algorithmes, utilisés notamment en informatique.On étudiera ici principalement lesalgorithmesetstructures de données, i.e.la structuration de l"information en machine, les plus communément employés eninformatique, mais dont certains sont utiles dans d"autres domaines des sciencesde l"ingénieur.Le but d"un tel cours est triple :d"abord, faire comprendre que l"informatique ne se limite pas à la simpleécriture de programmes, mais qu"elle nécessite une réflexion mathématique3approfondie afin de déterminer le bon algorithme et la bonne structure dedonnées permettant de résoudre le problème auquel on est confronté; enparticulier, on songera à toujours se faire une idée de lacomplexitéspatialeet temporelle d"un algorithme : informellement, il s"agit de l"espace mémoireet du temps nécessaire à son exécution;ensuite, fournir à l"ingénieur une connaissance suffisante des principauxtypes d"algorithmes et de structures de données pour qu"il évite de "réin-venter la roue", et puisse se référer aisément à ce qui existe déjà, c"est-à-direaux différentes "Bibles" de l"algorithmique : citons en particulier la fameusetrilogieThe Art of Computer Programming[5, 6, 7] de Donald E.

Knuth,la première étude mathématique moderne sur le sujet, et qui reste une ré-férence des plus utiles; dans la même veine, on peut également mentionnerThe Design and Analysis of Computer Algorithms[1] de Aho, Hopcroft etUllman;Introduction à l"algorithmique[3] de Cormen, Leiserson et Rivestest peut-être le nec plus ultra actuel; on pourra encore consulter les livresde Gonnet et Baeza-Yates ou de Sedgewick [4, 9].

En ce qui concerne l"algo-rithmique numérique,Numerical Recipes(en C, FORTRAN ou PASCAL)[8] est la référence fondamentale;enfin, indiquer les limitations de l"usage de l"ordinateur : tous les problèmesne sont pas solubles par ordinateur, ou bien à cause d"une complexité spa-tiale ou temporelle rédhibitoire des algorithmes qui leur correspondent, oubien même parce qu"ils sontindécidables, c"est-à-dire réellement trop com-pliqués pour être résolus par un procédé automatique.Les algorithmes décrits plus loin seront présentés de manière informelle enfrançais, ou dans un pseudo-code proche de la syntaxe du C et facilement com-préhensible, ou encore sous la forme d"un programme C.

Outre les calculs decomplexité, on insistera au travers de nombreux exercices sur la nécessité de pro-grammer les algorithmes, ce qui est une bonne méthode pour s"assurer les avoirbien compris.Table des matièresIntroduction31 Complexité71.

1) Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71.1. 1) Comparaison asymptotique de fonctions réelles . . . . . . .71.1. 2) Complexité d"un algorithme . . . . . . . . . . . . . . . . . .81. 2) Exemples d"algorithmes de complexité différente . . . . . . . . . .91.2. 1) Suite de Fibonacci . . . . . . . . . . . . . . . . . . . . . . .101.2. 2) Problème du tri . . . . . . . . . . . . . . . . . . . . . . . . .131. 3) Tri par insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . .141.3. 1) Description de l"algorithme . . . . . . . . . . . . . . . . . .141.3. 2) Implémentation en C . . . . . . . . . . . . . . . . . . . . . .151.3. 3) Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . .161. 4) Qu"est ce qu"un algorithme efficace? . . . . . . . . . . . . . . . . .171. 5) Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .192 Récursivité212. 1) Fonctions numériques récursives . . . . . . . . . . . . . . . . . . . .212.1. 1) Suite de Fibonacci . . . . . . . . . . . . . . . . . . . . . . .232.1. 2) Fonction d"Ackermann . . . . . . . . . . . . . . . . . . . . .242. 2) Procédures récursives . . . . . . . . . . . . . . . . . . . . . . . . . .242.2. 1) Tri fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . .252.2. 2) Tri rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . .262.2. 3) Complexité des algorithmes de tri . . . . . . . . . . . . . .292.2. 4) Tours de Hanoï . . . . . . . . . . . . . . . . . . . . . . . . .292. 3) Complément : définitions inductives . . . . . . . . . . . . . . . . .302.

4) Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .343 Structures de données élémentaires353.

1) Tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .353. 2) Listes chaînées . . . . . . . . . . . . . . . . . . . . . . . . . . . . .373.2.

1) Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . .373.2.2 implémentation en C . . . . . . . . . . . . . . . . . . . . . .383.2.

3) Opérations courantes sur les listes . . . . . . . . . . . . . .403. 3) Piles et files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .433. 4) Application : évaluation des expressions arithmétiques préfixées . .443.

5) Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4854 Recherche en table494.

1) Adressage direct . . . . . . . . . . . . . . . . . . . . . . . . . . . .494. 2) Recherche séquentielle . . . . . . . . . . . . . . . . . . . . . . . . .504. 3) Recherche dichotomique . . . . . . . . . . . . . . . . . . . . . . . .514. 4) Tables de hachage . . . . . . . . . . . . . . . . . . . . . . . . . . .534. 5) Récapitulatif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .554. 6) Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .555 Arbres575. 1) Terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .575. 2) Parcours d"arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . .615. 3) Arbres binaires de recherche . . . . . . . . . . . . . . . . . . . . . .635.3. 1) Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . .635.3. 2) Opérations sur les arbres binaires de recherche . . . . . . .645. 4) Files de priorité et tas . . . . . . . . . . . . . . . . . . . . . . . . .665.4. 1) Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . .675.4. 2) Opérations sur les tas . . . . . . . . . . . . . . . . . . . . .675.4. 3) Implémentation . . . . . . . . . . . . . . . . . . . . . . . . .705. 5) Arbres équilibrés . . . . . . . . . . . . . . . . . . . . . . . . . . . .705. 6) Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .716 Graphes736. 1) Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .736. 2) Représentation des graphes . . . . . . . . . . . . . . . . . . . . . .746.2. 1) Matrice d"adjacence . . . . . . . . . . . . . . . . . . . . . .746.2. 2) Listes de successeurs . . . . . . . . . . . . . . . . . . . . . .756. 3) Parcours de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . .766.3. 1) Parcours en largeur d"abord . . . . . . . . . . . . . . . . . .766.3. 2) Parcours en profondeur d"abord . . . . . . . . . . . . . . . .776. 4) Applications des parcours de graphe . . . . . . . . . . . . . . . . .786.4. 1) Tri topologique . . . . . . . . . . . . . . . . . . . . . . . . .786.4. 2) Calcul des composantes fortement connexes . . . . . . . . .786. 5) Recherche de chemins les plus courts dans un graphe . . . . . . . .816.5. 1) Calcul des chemins à partir de la matrice d"adjacence . . .816.5. 2) Algorithme de Aho-Hopcroft-Ullman . . . . . . . . . . . . .836.

6) Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .857 Analyse syntaxique877.

1) Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .877.1. 1) Algorithme naïf de pattern-matching . . . . . . . . . . . . .887.1. 2) Algorithme de Rabin-Karp . . . . . . . . . . . . . . . . . .887. 2) Pattern-matching à base d"automates finis . . . . . . . . . . . . . .897.2. 1) Définition des automates finis déterministes . . . . . . . . .897.2. 2) Automate de recherche de motif . . . . . . . . . . . . . . .917.2. 3) Calcul de l"automate de recherche . . . . . . . . . . . . . .917.

3) Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .928 Conclusion : les limites de l"algorithmique93Bibliographie95Chapitre 1ComplexitéLa principale motivation de l"algorithmique est de résoudre des problème infor-matiques, i.e. de traitement automatique de l"information, de la manière la plusefficace possible.

Or, même si intuitivement on croit comprendre ce qu"efficacesemble signifier, la réalité est loin d"être aussi simple.

La théorie de la complexités"attache à la formalisation du concept d"efficacité d"un algorithme.

Dans ce pre-mier chapitre, nous nous efforcerons de saisir ce que l"on entend par complexitéd"un algorithme ainsi que les conséquences pratiques qui découlent de conclusionsd"ordre théorique.1.

1) Définitions1.1.

1) Comparaison asymptotique de fonctions réellesCommençons par un rappel de quelques notations : pour deux fonctions réellesf(n)etg(n), on écrira :f(n) =O(g(n))(1.1)si et seulement s"il existe deux constantes strictement positivesn0etctelles que :0f(n)cg(n)pour toutnsupérieur àn0.

On note encore :f(n) = Ω(g(n))(1.2)quandg(n) =O(f(n)), et :f(n) = Θ(g(n))(1.3)quand on a à la fois les propriétés (1.1) et (1.2), i.e.9(c,c′)2(R∗+)29n02N8nn0cg(n)f(n)c′g(n)Notons que la formule (1.3) ne signifie pas quef(n)est équivalente àg(n)(notéf(n)g(n)), qui se définit comme :limn→∞f(n)g(n)g(n)= 0910DESIGN & ANALYSIS OF ALGORITHMSChapitre 1Cependant, sif(n)g(n)on af(n) = Θ(g(n)).

Enfin, il est clair quef(n) =Θ(g(n))si et seulement sig(n) = Θ(f(n)).

Intuitivement, la notationΘrevient à"oublier" le coefficient multiplicatif constant deg(n).Voici quelques exemples de comparaisons de fonctions :n2+ 3n+ 1 = Θ(n2) = Θ(50n2)n/ln(n) =O(n)50n10=O(n10,01)2n=O(exp(n))exp(n) =O(n!)n/ln(n) = Ω(pn)On peut ainsi établir une hiérarchie (non exhaustive) entre les fonctions :log(n)pnnnlog(n)n2n32nexp(n)n!Voici une comparaison numérique de ces fonctions.

On notera en particulier lacroissance très rapide des fonctions exponentielles (2n,exp(n)etn!).

A titre decomparaison, on estime le nombre de particules dans l"univers à1080!log(n)3.36.610pn3.11032n101001000nlog(n)33664104n2100104106n31031061092n103103010300exp(n)2104104310434n!3.6106101581025681.1.

2) Complexité d"un algorithmeAfin de fournir une mesure intrinsèque de l"efficacité d"un algorithme, indépen-dante de l"environnement d"exécution, nous allons en définir la complexité.

Pourcela, on considère qu"un algorithme reçoit des données initiales qu"il manipule afinde fournir un résultat.

Parmi les opérations effectuées, on en considère les plusimportantes, celles qui sont représentatives de l"effort de calcul à produire.

Infor-mellement, la complexité d"un algorithme est une fonction exprimant le nombred"opérations nécessaires en fonction de la taille des données à traiter.Une telle définition pose plus de problèmes qu"elle n"en résout.

Il convient eneffet tout d"abord dedéfinir ce que l"on entend par taille des données.De manière générale, la taille d"un objet doit refléter l"espace nécessaire à soncodage dans la mémoire d"un ordinateur.

Ainsi, un entiernse code en binaire avecblog2(n)c+ 1bits; une bonne mesure de la taille d"un entier est par conséquentson logarithme en base 2.

Bien entendu, on pourrait considérer d"autres codages,par exemple en unaire, pour lesquels la quantité de mémoire nécessaire est biensupérieure mais de telles approches ne sont pas naturelles.

Comme autre exemple,si l"on a un algorithme recevant un tableau d"entiers comme donnée initiale, leChapitre 1DESIGN11nombre d"éléments de ce tableau en mesure correctement la taille.

Bien entendu,ceci sous-entend que les entiers occupent un espace de taille fixe en mémoire, parexemple 4 octets.Le second point important à résoudre est lechoix des opérations élémen-taires que l"on veut comptabiliser.

Si l"on souhaite obtenir une estimation decomplexité représentative des temps de calcul effectifs, il faut choisir les opérationsqui seront le plus souvent réalisées et qui nécessiteront en pratique le plus de tempsde calcul.

Par exemple, pour les algorithmes de tri, on mesure traditionnellementle nombre de comparaison entre éléments du tableau à trier.

Tout comme pourla taille des données initiales, on va donner une mesure approximative, simplifiée,à l"aide des notationsO,ΩetΘ.

En effet, seul le comportementasymptotiquedes algorithmes nous intéresse.

Par exemple, si nous comptabilisons3n28n+ 4opérations pour traiter des données de taillen, nous dirons simplement que l"algo-rithme est enΘ(n2); le terme enn, et a fortiori le terme constant, deviennent eneffet négligeables devant le terme quadratique lorsquendevient grand.

De plus,le coefficient du terme dominant (3 dans notre exemple) est de peu d"intérêt enpratique.

Considérons par exemple un algorithme effectuant des additions et desmultiplications; on admet en général qu"une multiplication est plus complexe etprend plus de temps qu"une addition mais comment chiffrer cette différence? Doiton considérer que l"une est 50 fois plus lente que l"autre comme c"était le cas sur lespremiers microprocesseurs ou au contraire dire que les temps de calcul sont com-parables (comme sur certains processeurs modernes)? Cet exemple montre queles coefficients numériques apportent peu d"information en pratique.

Par contre,une complexité enΘ(n2)nous apprend par exemple que quelque soit l"ordinateuremployé, quelque soit le langage utilisé, le temps de calcul sera en gros multipliépar 4 si l"on double la taille des données initiales.Enfin, si l"on considère l"ensembles des données initiales de taille fixée, il estclair que le nombre d"opérations peut fortement varier d"une donnée à l"autre.On imagine sans peine qu"avec certains algorithmes un tableau déjà trié sera bienplus facile à ordonner qu"un tableau aléatoire.

Suivant le cas auquel on s"inté-resse, on parle decomplexité dans le cas le pirelorsque l"on mesure la complexitémaximale pour une taille fixée des données initiales, on parle decomplexité enmoyennelorsque l"on mesure le nombre moyen d"opérations nécessaires et enfindecomplexité dans le meilleur caspour parler du cas le plus favorable.

Nous neconsidérerons pas ce dernier cas dans la suite de ce cours car il n"a pas beaucoupd"intérêt en pratique.Nous avons jusqu"à maintenant uniquement abordé la complexité ditetempo-relle, i.e. une mesure du temps de calcul nécessaire pour résoudre un problème.Dans certains cas, il est également intéressant d"étudier la complexitéspatialed"unalgorithme, i.e. une mesure de la quantité de mémoire nécessaire à son exécution.Toutes les remarques faites précédemment s"applique donc de manière semblable.1.

2) Exemples d"algorithmes de complexité différenteAfin de se faire une idée plus concrète de ce qu"est la complexité d"un algo-rithme, nous allons aborder différents problèmes et proposer divers algorithmes decomplexités temporelle et spatiale différentes.12DESIGN & ANALYSIS OF ALGORITHMSChapitre 11.2.

1) Suite de FibonacciLa suite(Fn)n≥0des nombres de Fibonacci est définie par la récurrence sui-vante :Fn={1sin= 0ou1Fn-1+Fn-2sinonLe problème que l"on se pose est de calculer len-ième nombreFnde Fibonacci(en fait, nous ne calculerons pas ici les nombres de Fibonacci dont la taille croîtrapidement mais plutôt leur valeur modulo la représentation des entiers en ma-chine).

Un premier algorithme très simple consiste à programmer récursivementune fonction qui calculeFnen fonction deFn-1etFn-2:int fibo1(int n)if (n<=1) return 1;else return fibo1(n-1)+fibo1(n-2);Afin d"estimer la complexité d"un tel calcul, évaluons le nombre d"appelsCnà la fonctionfibo1effectués pour calculerFn.

On aC0=C1= 1etCn=1+Cn-1+Cn-2pour toutn2.

Une telle récurrence peut se résoudre en posantDn= (Cn+ 1)/2; la suitefDngn∈NvérifieD0=D1= 1etDn=Dn-1+Dn-2,i.e. exactement les mêmes relations que la suite de Fibonacci.

Par conséquent,Cn= 2Fn1.On peut d"autre part résoudre la récurrence linéaire définissant les nombresde Fibonacci de manière exacte; en utilisant une technique d"algèbre classique,on résout tout d"abord l"équationx2=x+ 1issue de la formule de récurrence.Soitx+=1+√52etx-=1-√52les deux racines.

On sait alors queFns"écrit, enfonction den, sous la formeFn=λx+n+µx-n, les valeurs des paramètresλetµétant déterminés au moyen des valeurs initialesF0etF1de la suite.

On obtientfinalementFn=1p51 +p52n+11p52n+1On en déduit que la complexité du calcul de la suite de Fibonacci par lafonctionfibo1estΘ(ωn)oùω= (1+p5)/2est le nombre d"or.

Une telle fonctioncroît extrêmement vite; l"algorithme ne pourra donc être utilisé que pour de trèspetites valeurs den.Une observation attentive de l"algorithme précédent montre que le temps decalcul est très important car les valeursFkpourk < nsont très souvent recalculées.Une idée simple consiste alors à stocker lesFksuccessifs dans un tableau.

Onobtient la fonction suivante :int fibo2(int n)int *t;int i;int resultat;Chapitre 1DESIGN13t=(int *)malloc((n+1)*sizeof(int));t[0]=1; t[1]=1;for(i=2;i<=n;i++) t[i]=t[i-1]+t[i-2];resultat=t[n];free(t);return resultat;Une telle fonction a une complexité linéaire enncar on ne calcule qu"uneseule fois les valeursFkpourk < n.

Par contre, la complexité spatiale, i.e. laqu