Next PDF List

Leçon 926 : Analyse des algorithmes : Complexité.Exemples.Julie Parreaux2018 - 2019[1]Beauquier ,Berstel et Chr etienne,Éléments d"algorithmique.[2]Carton, Langages formels, calculabilité et complexité.[3]Cormen, Algorithmique.[4]Fr oidevaux,Gaudel et Soria, Types de données et algorithmes.Références pour la leçonÉtude d"Union-Find pour la complexitéAlgorithme de DijkstraDéveloppements de la leçonPlan de la leçon1 Quantifier la complexité 21.

1) Qu"est-ce que la complexité? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21. 2) Mesurer la complexité [3, p.40] . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21.

3) Différentes approches de la complexité [4, p.19] . . . . . . . . . . . . . . . . . . . .32 Techniques de calcul de la complexité 32.

1) Le calcul direct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32. 2) La résolution de récurrence [1, p.20] . . . . . . . . . . . . . . . . . . . . . . . . . .32.

3) Le calcul de la complexité moyenne par l"espérance . . . . . . . . . . . . . . . . .33 Raffinement de l"étude de la complexité : la complexité amortie 43.

1) Méthode de l"agrégat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43. 2) Méthode comptable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43.

3) Méthode du potentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .44 Amélioration de l"étude de la complexité 44.

1) Borne minimale de la complexité sur une classe de problème . . . . . . . . . . . .54. 2) Utilisation de structures de données adaptées . . . . . . . . . . . . . . . . . . . . .54. 3) Compromis espace/temps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5) Ouverture51MotivationDéfenseLors de la conception, puis de l"étude d"un algorithme, deux notions sont extrêmementimportantes :la corr ectionde l"algorithme : fait-il ce que l"on souhaite ?l"ef ficacitéde l"algorithme : à quelle vitesse s"exécute-t-il ?;est-il optimal ?La complexité (temporelle ou spatiale) intervient alors pour comparer deux algorithmes cor-rects répondant à la même question.Ce qu"en dit le juryIl s"agit ici d"une leçon d"exemples.

Le candidat prendra soin de proposer l"analyse d"al-gorithmes portant sur des domaines variés, avec des méthodes d"analyse également variées :approche combinatoire ou probabiliste, analyse en moyenne ou dans le pire cas.Si la complexité en temps est centrale dans la leçon, la complexité en espace ne doit pas êtrenégligée.

La notion de complexité amortie a également toute sa place dans cette leçon, sur unexemple bien choisi, comme union find (ce n"est qu"un exemple).

1) Quantifier la complexitéDéfinir la complexité d"un algorithme n"est pas facile.

Intuitivement la complexité d"un al-gorithme est un indicateur de la difficulté pour résoudre le problème traité par l"algorithme.Mais cette vue de l"esprits n"est pas simple à quantifier.

Nous allons alors définir la complexitécomme une fonction qui en fonction des entrées sur notre programme donnera la consomma-tion d"une certaine ressource.1.

1) Qu"est-ce que la complexité?-Définition: donnée d"entrée d"un algorithme (= ensemble des variables externes à l"algo-rithmes sur lesquelles on exécute celui-ci)-Exemple: un algorithme de tri sur un tableau prend un tableau en entrée-Définition: taille d"une entrée :f:fentreeg !Nk-Exemples: mot : nombre de caractère; tableau : nombre de cellule ou l"espace mémoireutilisé-Définition: complexité comme fonctionfdes entrées vers une ressources qui peut êtretemporelle, spatiale, le nombre d"accès à un disque externe,-Remarque: en pratique on compte des unités de bases (peut être des cellules mémoires,des fonctions que l"on considère de bases)-Exemples: complexité temporelle : tri bulle :n(n1)2; complexité disque dur : rechercheB-arbrehoùhhauteur;complexité tempor elle: plus longue sous-séquence commune1.

2) Mesurer la complexité [3, p.40]On ne peut pas toujours calculer la complexité exacte (avec les constantes) car générale-ment, elle dépend de l"implémentation que nous utilisons.Pour cette même raison le calcul dela complexité exacte peut s"avérer inutile.2-DéfinitionNotation de Landau (OetQ) + abus de notation-Proposition: Équivalence des notations + illustration-Exemples: Tri bulleO(n2); B-arbreO(logn)-Proposition: L"ordre de croissance1.

3) Différentes approches de la complexité [4, p.19]-Définition: Complexité pire cas, meilleur cas en moyenne(avec les pr obabilités)-Remarque: Distribution uniforme : simplification de l"écriture mais pas toujours vraiAt-tention-Définition: complexité constante2 Techniques de calcul de la complexitéMaintenant que nous avons donné un cadre à notre théorie de la complexité, nous souhai-tons calculer les complexités d"algorithmes usuels.

Pour cela, nous allons présenter quelquestechniques de calcul élémentaires.2.

1) Le calcul directOn peut parfois calculer directement la complexité en dénombrant les opérations que l"ondoit calculer.Ef ficacedans le cas d"algorithmes itératifsExemple: Recherche de maximum dans un tableau / CYK (Algorithme 1)O(n3)[2, p.198] /Marche de Jarvis (Algorithme 2)O(hn)[1, p.389]2.

2) La résolution de récurrence [1, p.20]On peut parfois exprimer la complexité pour une donnée de taillenpar rapport à unedonnée de taille strictement inférieure.

Résoudre l"équation ainsi obtenue nous donne la com-plexité.Ef ficacedans le cas d"algorithmes récursifs.-Propositionsuite récurrente linéaire d"ordre 1 +ExemplesFactorielle et Euclide-Propositionsuite récurrente linéaire d"ordre 2 +ExempleFibonacci-Proposition: Master theorem +ExemplesTri fusion et Strassen-Remarque: Ne capture pas toutes les équations par récurrences.2.

3) Le calcul de la complexité moyenne par l"espérance-Remarque: on a une distribution uniforme donccmoy=1jDnjåx2Dnf(x)-Exemple: tri rapide randomisé-Remarque: on fait souvent l"hypothèse d"avoir une distribution uniforme sur les donnéesde l"entrée, cependant c"est généralement faux et cela nous introduit des erreurs.33 Raffinement de l"étude de la complexité : la complexité amortieLa complexité amortie n"est pas une complexité moyenne!La complexité amortie est uneamélioration de l"analyse dans le pire cas s"adaptant (ou calculant) aux besoins de performancedes structures de données.-Définition: la complexité amortie :camo=maxop1, ,opkåki=1c(opi)k-Exemple: table dynamique où on souhaite la complexité d"un élément qu"on insère ennombre d"allocation et d"écriture [3, p.428]3.

1) Méthode de l"agrégatDans cette méthode, le coût amortie est le même pour toutes les opérations de la séquencemême si elle contient différentes opérations-Principe: On calcul la complexité dans le pire cas pour cette séquence.

La complexitéamortie d"une opération est donc cette complexité divisée par le nombre d"opérations dela séquence [3, p.418].-Exemples: table dynamique, Union find + KruskalDEV , balayage de Gram3.

2) Méthode comptableCette méthode se différencie de la précédente en laissant la possibilité que toutes les opé-rations ait un coup amortie différent.-Principe: On attribut à chaque opération un crédit et une dépense(qui peuvent êtr edifférent de leur coût réel).

Ces crédits sont plus importants pour les opérations coû-teuses afin de rattraper leur dépenses importantes.

Cependant, elles doivent vérifierla propriété suivante :åki=1cred(opi)åki=1dep(opi)0. On a alors :camo(op) =creel(op) +cred(op)dep(op).-Exemples: table dynamique, KMP3.

3) Méthode du potentielCette méthode a été popularisé lors de la preuve de la complexité amortie de la structurede données Union Find, implémentée à l"aide d"une forêt et des heuristiques qui vont bien.Elle est moins facile que les autres à mettre en place.-Principe: Au lieu d"assigner des crédits à des opérations, on va associer une éner-gie potentiellejà la structure elle-même.

Cette énergie vérifie les propriétés sui-vantes :j(structure vide) =0 et8T,j(T)0.

On a alorscamo(op) =creel(op) +j(T)j(T0)lorsque l"opérationoppermet de passer deTàT0[3, p.424].-Exemples: table dynamique4 Amélioration de l"étude de la complexitéPlusieurs pistes existe afin d"améliorer la complexité d"un algorithme : utiliser une struc-ture de données plus adaptée, utiliser un peu plus de mémoire ou au contraire se souvenirde moins de choses, Cependant, quelques fois nous sommes capable de mettre une borneminimale sur la complexité d"une famille de problème : quand nous avons atteint cette borneon sait que nos algorithmes sont optimaux.44.

1) Borne minimale de la complexité sur une classe de problème-Proposition: Borne minimal d"un algorithme de tri-Exemple: Tri par insertionO(n2)O(nlogn); Tri fusionO(nlogn)atteint cette borne-Remarque: même si on atteint la borne optimale asymptotique, on peut vouloir optimiserles constantes (tri rapide est en moyenne plus rapide que le tri fusion).4.

2) Utilisation de structures de données adaptéesUne piste pour améliorer un algorithme : utiliser une bonne structure de données-Exemple: tri par tas +Remarque: dépend de la manière dont on implémente la structure-Exemple: représentation d"un graphe +Remarque: utilisation de ces représentation-Exemple: Prim (liste d"adjacence) + Floyd Warshall (matrice d"adjacence)On peut changer de str ucturede données-Exemple: DijstraDEV4.

3) Compromis espace/temps-Principe: On peut vouloir améliorer le temps au détriment de l"espace ou vise-versa.-exemple: Fibonaccirécursif : O(n2)en temps etO(1)en espace(amélioration de l"espace)pr ogrammationdynamique : O(n)pour le temps et l"espace(amélioration dutemps)utilisation de deux variables : O(n)pour le temps etO(1)pour l"espace(gag nantsur les deux tableaux)-Principe: le mémoïsation [3, p.338] +Exemple: découpage de barreOuvertureÉvaluer la complexité d"un algorithme (hors implémentation) n"est pas une tâche facile.Souvent plusieurs astuces sont nécessaire pour trouver la meilleure borne sur notre complexitépossible.

Quelque fois, un approximation grossière de notre complexité (évaluation de la com-plexité pour le tri par tas) suffit.Quelques notions importantesNotation de LandauOn ne peut pas toujours calculer la complexité exacte (avec les constantes) car générale-ment, elle dépend de l"implémentation que nous utilisons.

Pour cette même raison le calcul dela complexité exacte peut s"avérer inutile.

On quantifie alors la complexité asymptotiquement.On utilise pour cela la notation de Landau [3, p.40].Définition.Soitf,g:N!R+.

On noteO(g) =ffj 9n0,c2N,8nn0,0f(n)cg(n)gMajorant asymptotiqueQ(g) =ffj 9n0,c1,c22N,8nn0,0c1g(n)f(n)c2g(n)gEncadrement asymptotiqueW(g) =ffj 9n0,c2N,8nn0,0cg(n)f(n)gMinorant asymptotique5Remarque(Abus de notation).On écriraf=O(g)(respectivementf=Q(g)) pourf2O(g)(respectivementf2Q(g)).Par définition, on af=O(g)si et seulement sig=W(f).Proposition.Soient f,g:N!R+, on af=O(g)et g=O(f)],f=Q(g)g=Q(f),f=Q(g)Par exemple, on an2+n=O(n3).

De plus,n2+n=O(n2)etn2=O(n2+n).

Par laproposition précédente, on an2+n=Q(n2), maisn2+n6=Q(n3).Remarque.Ces notations sont transitives et réflexives.Proposition.L"ordre de croissance des O est : O(1); O(logn); O(n); O(nlogn); O(n2); O(nk);O(kn); O(n!).Cet échelle de cr oissanceest utile pour compar erl"efficacité de deux algorithmes corr ectsrésolvant le même problème.Quelques analyses d"algorithmesNous donnons ici une liste d"exemples d"algorithmes pour lesquels nous calculons leurcomplexitéenmettantenplacelesdifférentesméthodesétudierdanslaleçonsurlacomplexité.Ce sont de bonnes illustrations du calcul de complexité.L"algorithme Cocke-Younger-KasamiL"algorithme CYK (Cocke-Younger-Kasami) [2,p.198] est un algorithme qui décide en temps cubique si un mot est engendré par une gram-maire en forme normale quadratique.

Il donne alors un certificat que tout langage algébriqueest dans la classe P : comme toute grammaire algébrique est équivalente à une grammaire enforme normale quadratique, tout langage algébrique peut être décidé en temps cubique.Il fautfaire attention au fait que la grammaire est fixée et qu"elle ne fait pas partie de l"entrée car lamise en forme normale d"une grammaire algébrique peut être exponentielle en sa taille.Définition.Le problème du mot pour une grammaire algébrique :entrée : une grammaire algébriqueG= (S,T,R),w2Sun motsortie : oui siw2LGle langage engendré parG; non sinonRemarque: En général répondre à ce problème est coûteuxO(jwj3jGjjwj).Définition.SoitGune grammaire algébrique.

On dit que :-Gest sous forme normale si les règles sont sous la formeA!BCD ZoùA2T(alphabet de travail)et B, ,Z2S[T.-Gest sous forme normale de Chomsky si les règles sont sous la forme :A!apour,A2V,a2SV\S=AE;S!eetA!BCpourA2VetB,C2Vn fSgThéorème.Le problème du mot pour une grammaire algébrique sous forme forme normale de Chom-sky est décidable et un algorithme de programmation dynamique le décide en temps O(jwj3jGj)et enmémoire O(jwj3).Démonstration.Cet algorithme est un algorithme de programmation dynamique.

Soitw=a1 anun mot.

6) On note :1 ijn,w[i,j] =ai aj1 ijn,Ei,j=fSdes variables telles quew[i,j]2LG(S)g.L "algorithmecal-cul tous cesEi,j.Nous allons maintenant énon-cer quelques propriétés d"appar-tenance à ces ensemblesEi,j:-w2LG(S0)siS02E1,n-Sappartient àEi,isi etseulement siS!aiest unerègle deG(w[i,i] =aiet ona une grammaire en formenormale quadratique)-Sappartient àEi,j(i

Le but de cet algo-rithme n"est pas de déterminer les sommets de l"enveloppe convexe mais ces arêtes.

Or[p,q]est une arête de l"enveloppe si et seulement si tous les points de l"ensemble sont du mêmecôté de la droite.

On peut alors décider en tempsO(n)si un segment est une arête de l"enve-loppe.

Comme on aO(n2)segment à examiner, on obtient une complexité enO(n3)pour cetalgorithme naïf.La marche de Jarvis améliore cet algorithme en remarquant que le point suivantpk+1d"uneenveloppe convexe est le point minimal dans l"ensemble pour l"ordre polaire relativement à ladroite[pk,!pk1pk).

On obtient alors l"algorithme suivant :Complexité: On a donc une complexité enO(hn)qui est intéressante sihest petit devantnmais enO(n2)dans le pire cas.L"algorithme du tri rapide randomiséLe tri rapide (Algorithme 3) est un tri en place dont lacomplexité moyenneest enO(nlogn)(elle estoptimale)et dont la complexitéau pir ecas estenO(n2).

Il applique le paradigme diviser pour régner en séparant l"entrée en deux sous tableau7Algorithm 2Algorithme calculant une enveloppe convexe par la marche de Jarvis.1:functionJarvis(S).S: ensemble des points2:p1le point d"ordonnée minimale deS(et d"abscisse si plusieurs).Complexité :O(n)3:p2le point minimal deSn fp1gpour l"ordre polaire relativement à la droite[pi,!i).Complexité :O(n)4:k 25:whilepk6=p1do.Complexité :O(h)oùhest le nombre de points dans l"enveloppeconnexe6:Calculerqle point minimal deSpour l"ordre polaire relativement à la droite[pk,!pk1pk).Complexité :O(n)7:k k+18:pk q9:end while10:end functiondont les valeurs sont respectivement inférieures (ou supérieures) à un pivot.

L"algorithme detri se rappelle alors sur ces deux sous tableau.Algorithm 3Algorithme du tri rapide.1:functionTri-Rapide(A).A: tableauà trier2:ifA.taille2then3:pivot A[0]4:i 05:j A.taille16:whilei

On remarque que lacorrection du nouvel algorithme ne change pas car elle ne dépend pas du pivot choisi maisuniquement des actions autour de celui-ci.L"algorithme du balayage de GrahamLe balayage de Graham résout le problème de l"en-veloppe connexe en conservant une pile de candidat aux sommets de cette dite enveloppe [3,p.948].

Chacun des points est empiler une fois, puis tous ceux qui ne sont pas un sommet del"enveloppeserontdépilé.L"algorithmeutilisedeuxsous-fonctionssommetquiretournelehautde la pile sans le modifier etsous-sommetqui retourne le deuxième élément de la pile sans lamodifier.Algorithm 5Algorithme calculant une enveloppe convexe par le balayage de Graham.1:functionGraham(S).S: ensemble des points2:p0le point d"ordonnée minimale deS(et d"abscisse si plusieurs)3:p1, ,pmles points deStriés par angle polaire relativement àp0(si égalité, on gardele plus loin)4:P AE.Pest une pile5:Empiler(p0,P)6:Empiler(p1,P)7:Empiler(p2,P)8:fori=3 àmdo9:whilel"angle formé les les pointssous-sommet(P),sommet(P)etpifond un tour àgauchedo10:Dépiler(P)11:end while12:Empiler(pi,P)13:end for14:end functionThéorème(Correction).SiGrahamest exécuter sur un ensemble S de points tel quejSj 3, alors, àla fin de la procédure la pile P contient les du bas vers le haut les sommets de l"enveloppe convexe prisdans l"ordre inverse des aiguilles d"une montre.Arguments de la preuve.-Les points qui sont r etirelors du tri ne sont pas dans l"enveloppeconvexe.Invariant : "A chaque itération de la boucle Pour, la pilePdevient de bas en haut, les som-mets de l"enveloppe convexeQi1pris dans l"ordre inverse des aiguilles d"une montre."oùQiest l"ensemble desipremiers éléments donné par le tri.InitialisationLa pile contientQ2(trois points) qui sont bien leur enveloppe connexe prisdans l"ordre inverse des aiguilles d"une montre.ConservationAprès la boucletant queon fait apparaître l"invariant de l"itération précé-dente(la pile contient la même cho se).

On montre ensuite que l"enveloppe convexedeQj[ fpigest la même que celle deQisoitpien fait partie, soit il es