Évaluation de Polynômes, Méthode de Horner Exponentiation rapide Recherche dans un tableau Comment mesurer l'efficacité d'un algorithme ? Ce cours
| Previous PDF | Next PDF |
[PDF] I Méthode Horner
pour k allant de 1 à n faire 5 Q := Q ∗ x + an−k 6 fin 7 Sorties : Q qui est égal à P(x) sous la forme d'un polynôme de Horner 8 Algorithme 1 : Algorithme de
[PDF] 1 Polynômes 2 Algorithme de Horner
roots ou roots(p) donne les racines (dans C) de p • p(a) ou polyval(p,a) évalue le polynôme p au point a (en utilisant l'algorithme d'Horner)
[PDF] Algorithme de Hörner pour les polynômes - Aurélien Poiret
Pour aller plus loin : Grâce à l'algorithme de Hörner, on peut aussi obtenir la division euclidienne de P par X − α Exercice No 4 : 1 Montrer que la division
[PDF] Complexité temporelle des algorithmes - Inria
Évaluation de Polynômes, Méthode de Horner Exponentiation rapide Recherche dans un tableau Comment mesurer l'efficacité d'un algorithme ? Ce cours
[PDF] Algorithmes classiques - CNRS
De quelle fonction mathématique de n ce temps d'exécution T(n) est-il « grand O » ? e Complétez l'invariant de boucle de l'algorithme de Horner : « Au début de
[PDF] Chapitre 4 Polynômes : évaluation et interpolation - Annuaire IMJ-PRG
Algorithme 1: Evaluation de Horner L'algorithme est de complexité linéaire en n Exercice 4 1 1 Programmez l'évaluation d'Horner en Python et en xcas, verifiez
[PDF] Schéma de Horner et algorithme de Newton - Grenoble Sciences
Exercice 5-7 : Schéma de Horner et algorithme de Newton a) Appliquons l' algorithme de Horner pour les trois valeurs proposées; nous obtenons les tableaux
[PDF] exposé sur le film intouchable
[PDF] texte au hasard d une rencontre 1ére année
[PDF] objet et methode de l'anthropologie
[PDF] analyse anthropologique définition
[PDF] intouchables résumé
[PDF] démarche anthropologique définition
[PDF] enquête de terrain anthropologie
[PDF] enquête anthropologique
[PDF] observation participante anthropologie
[PDF] écrire des dialogues scénario
[PDF] méthode de la sécante exemple
[PDF] méthode de dichotomie exercices corrigés
[PDF] mots argot jeunes
[PDF] méthode de la sécante matlab
![[PDF] Complexité temporelle des algorithmes - Inria](https://pdfprof.com/Listes/18/5293-183_complexity.pdf.pdf.jpg "[PDF] Complexité temporelle des algorithmes - Inria")
IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Introduction à l"algorithmique
et la complexité(et un peu de CAML)Complexité temporelle des algorithmes
Nicolas Nisse
Université Côte d"Azur, Inria, CNRS, I3S, France Cours dispensés en MPSI (option Info) au CIV, depuis 2011-N. Nisse
Complexité temporelle 1/17
IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Outline1Introduction à la complexité temporelle2Somme desnpremiers entiers3Évaluation de Polynômes, Méthode de Horner
4Exponentiation rapide
5Recherche dans un tableau
N. NisseComplexité temporelle 2/17
IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Comment mesurer l"efficacité d"un algorithme ?
Ce cours veut (espère) vous apprendre à
év aluerl"efficacité
des algor ithmeset à conce voirdes algorithmes efficacesLorsqu"on demande :
"Mais c"est quoi un algor ithmeefficace ???" , les réponses sont généralement: un algorithme qui "prend" lemoins de temps; un algorithme qui réalise lemoins d"opérations; un algorithme qui utilise lemoins de mémoire.Discutons de ces réponses :
le "temps" (en secondes/minutes/heures...) d"exécution d"un algorithmedépend de la machine sur lequel il est exécuté(sur votre portable, ça ira sûrement moins vite que sur des "super-ordinateurs" avec plein de RAM et de multi-processeurs...). Celadépend aussi du langage de programmation: un algorithme traduit en C++ ira probablement plus vite qu"un algorithme codé en Python... Bref, le "temps" n"est pas une mesure objectiv e pour représenter la qualité d"un algorithme. "le nombre d"opérations": c"est une très bonne idée, mais c"est quoi une opération ??? Par ailleurs, les opérations réalisées par un algorithme dépendent de ce à quoi l"algorithme est appliqué ??? Nous allons préciser tout ça da nsla suite du cours . "le moins de mémoire" : là encore, c"est une bonne idée. On appelle ça la comple xité spatiale . Cependant, nous ne parlerons pas de cet aspect dans ce cours (le temps manque, on peut pas parler de tout :( ).N. Nisse
Complexité temporelle 3/17
IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Exemple du dictionnaire "français-espagnol" (1/2)Considérons le problème qui, étant donné un dictionnaireD(disons "français-espagnol"),
consiste à traduire un motM(du français à l"espagnol).entrées du pbm. :Det M. 1 eressai de définition de complexité :Comme mesure "d"efficacité"des algorithmes pour résoudre ce problème, nous allons compter le nombre de mots du dictionnaire qu"il faut lire avant de finalement trouver la traduction deM.La complexité est le nombre d"opérations : ici, le nombre de mots lus avant traduction Étudions la complexité de l"algorithme suivant:Algo 1 :
Commencer par le premier mot de D; tant qu"on ne rencontre pas le motM, on passe au mot suivant ; lorsqu"(enfin) on trouveM, on traduit. Quelle est la complexité (nombre de mots lus) de cet algorithme ? Si on veut traduireM=abaisser, il faudra sûrement lire une dizaine de mots pour le traduire en "bajar". Pour traduireM=zigzaguer, il faudra lire presque tous les mots deDpour le traduire en "zigzaguear". Alors, quelle est la réponse ???On considère le PIRE CAS : la comple xitéla
plus grande parmi toutes les entrées possibles ! 2meessai de définition de complexité :La comple xitéest le nombre d"opér ationsdans le pire
cas (pour la pire entrée) Mais alors, quelle est la complexité d"Algo 1 ?Le "pire cas" est donc de traduire le dernier mot deD... mais donc, ça dépend du nombre de mots dansD(de la "taille" deD)??N. Nisse
Complexité temporelle 4/17
IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Exemple du dictionnaire "français-espagnol" (2/2)Définition de complexité :
La comple xitéest le nombre d"opérationsdans lepire cas(pour la pire entrée)en fonction de la taille de l"entrée. Dans le cas de l"Algo 1, c"est donc la "taille" deD(nombre de mots dansD). Essayons un autre algorithme(celui que vous utilisez naturellement),comparons le à Algo1.Algo 2 (dichotomie) :
Prenons le mot M0du mileu deD. SiM0=M, on traduit le mot. Sinon, si MQui de Algo 1 ou Algo 2 est le plus efficace ?
Si on veut traduire (encore)M=abaisser, Algo 1 est plus rapide que Algo 2... et pourtant... quelle est la complexité de Algo 2 ? PrenonsDavecnmots.Dans le pire cas, on a vu que Algo 1 doit lirenmots. Pour Algo 2, àchaque mot lu, on "élimine" la moitié du dictionnaire. Quel que soit le motMrecherché, on ne
lira qu"au plusdlognemots(si vous ne voyez pas pourquoi... on y reviendra dans la suite du cours, cf. Slide 13).
Un algorithmeAsera plus efficace (en pire cas) qu"un algorithmeA0si la complexité (pire cas) deAest moindre que la complexité (pire cas) deA0. Dans notre exemple, Algo 2 est donc plus efficace que Algo 1 (même si certaines entrées (ex: "abaisser") sont résolues plus efficacement par Algo 1 que par Algo 2).N. Nisse
Complexité temporelle 5/17
IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Complexité temporelle
On mesure la
comple xitétemporelle d"un algor ithmeen comptant le nomb re d"opér ationsélémentaires
réalisées par cet algor ithme.Opérations élémentaires :
P ardéf aut,il s"agit de chaque
opér ationar ithmétique( +;;=;), affectation ou comparaison . En général, lecontexteprécisera quelles opérations sont à considérer (par ex., compter seulement le nombre de comparaisons). Étant donnés un problèmeP, une instance (entrée)Idu problème et un algorithmeA, soit c(A;I)le nombre d"opérations élémentaires effectuées parApour résoudrePsur l"instance I. Notons quec(A;I)est généralement unef onctionde la taille jIjde l"instanceI. Complexité en pire cas d"un algorithmeA:c(A) =maxfc(A;I)jIinstance dePg. Complexité du problèmeP:c(P) =minfc(A)jAalgorithme pourPg.La complexité en pire cas est "un peu pessimiste" (le "pire cas" est peut-être pathologiquement
compliqué alors que la plupart des cas peuvent être résolus efficacement), il peut être plus
intéressant (mais souvent plus compliqué) de considérer la comple xitéen mo yenne (il ne sera que très peu question de cela dans ce cours) SoitIl"ensemble de toutes les instances (entrées) possibles pour le problèmeP. Complexité en moyenne d"un algorithmeA:cmoy(A) =åI2Ic(A;I)=jIj.
N. Nisse
Complexité temporelle 6/17
IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Notation "O"
Considérons un algorithmeApour résoudre un problèmeP.Comme nous l"avons dit, étudier la complexité deArevient à déterminer, pour chaque instance
(entrée)Idu problème, le nombre (en fonction de la taillendeI) "d"opérationsélémentaires" effectuées parApour résoudrePpour l"instanceI(et déterminer le pire cas :
une instance qui requière le plus grand nombre d"opérations).En fait, ce qui nous intéresse, c"est :
"l"ordre de grandeur", en fonction den, du nombre "d"opérations élémentaires".La complexité d"un algorithme sera (sauf mention contraire) exprimée sous la forme :O(f(n)).Rappel rapide : Notation "O"
Soientf= (fn)n2Netg= (gn)n2N, deux fonctionsN!R. On notef=O(g)ssi9c2R+,9n02N, tels que8nn0,jf(n)j cjg(n)j.On notef=
(g)ssig=O(f). Exemples(à vous de les prouver)2n4+1010n2+n4=5+47=O(n4); 4124+0:000001logn=O(logn);15pn+log12n=O(pn); 134n367=O(0:00001n).On notef=O(1)sif=O(g)avecg(n) =1 pour toutn2N. C"est-à-dire,f=O(1)si9c2R+
tel quejf(n)j cpour toutn2N(sifest "bornée" par une constante).N. Nisse
Complexité temporelle 7/17
IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Outline1Introduction à la complexité temporelle2Somme desnpremiers entiers3Évaluation de Polynômes, Méthode de Horner
4Exponentiation rapide
5Recherche dans un tableau
N. NisseComplexité temporelle 8/17
IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Somme desnpremiers entiers
Nous avons déjà vu (et prouvé) ces algorithmes. Étudions leur complexitéc(algo).Comptons :d"abord, une affectation, puis
pour chaque itération de la boucle : une addition et une affectation. C-à-d. c(sommeIteratif(n)) =1+nå i=1(1+1) =1+2n=O(n).Par récurrence :c(sommeRecursif(0)) =O(1);Pourn>0, une comparaison, puis une
addition et l"exécution de sommeRecursif(n1).Donc :c(sommeRecursif(n)) =1+2n=O(n)On ne s"intéresse généralement qu"à l"ordre de grandeur (grand "O") de la complexité !!
Au passage, on voit qu"écrire un même algorithme de manière itérative ou récursive ne changea
prioripas la complexité.Est-ce que vous pouvez faire mieux pour calculer la somme desnpremiers entiers ?Let sommen=n(n+1)=2;;comple xité: O(1)!!!N. NisseComplexité temporelle 9/17
IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Somme desnpremiers entiers
Nous avons déjà vu (et prouvé) ces algorithmes. Étudions leur complexitéc(algo).Comptons :d"abord, une affectation, puis
pour chaque itération de la boucle : une addition et une affectation. C-à-d. c(sommeIteratif(n)) =1+nå i=1(1+1) =1+2n=O(n).Par récurrence :c(sommeRecursif(0)) =O(1);Pourn>0, une comparaison, puis une
addition et l"exécution de sommeRecursif(n1).Donc :c(sommeRecursif(n)) =1+2n=O(n)On ne s"intéresse généralement qu"à l"ordre de grandeur (grand "O") de la complexité !!
Au passage, on voit qu"écrire un même algorithme de manière itérative ou récursive ne changea
prioripas la complexité.Est-ce que vous pouvez faire mieux pour calculer la somme desnpremiers entiers ?Let sommen=n(n+1)=2;;comple xité: O(1)!!!N. NisseComplexité temporelle 9/17
IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Outline1Introduction à la complexité temporelle2Somme desnpremiers entiers3Évaluation de Polynômes, Méthode de Horner
4Exponentiation rapide
5Recherche dans un tableau
N. NisseComplexité temporelle 10/17
IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Évaluation de Polynômes, Méthode de HornerRappel : le degré du polynôme estO(n). (précisément, ci-dessous,n1)calcul de "y^i"ajout de "ai * y^i"Algorithme "naïf"(slide 11, Chap. 2.)
Comptons :d"abord,2 aff ectations, puis pour chaque itération de la boucle "i" :une aff ectationpuis une boucle "j" de(i+1)itérations avec :une aff ectationet une multiplicationà chaque itér ation,puis
une aff ectation,une addition et une multiplication . C-à-d. c(evalPolynom(n)) =2+n1å i=0(1+(iåj=12)+3) =O(n2).L"objectif de ce cours est d"étudier (et apprendre à concevoir) des algorithmes "efficaces"(a vec
la complexité la plus petite).L"algorithme de Horner(ci-dessous) est "meilleur" que l"algorithme "naïf" précédent.Algorithme de Horner :Terminaison :
j"espère qu"elle est évidente pour v ous...Correction :
in variantde boucle : après l"itér ationi, resultat_courant=n1å j=nitab:(j)yni+jComplexité :c(Horner(n)) =2+nå
i=23=O(n).Pour évaluer un polynôme de degrén, il faut "au moins" lire sesn+1 coefficients. Donc
l"algorithme de Horner, de complexitéO(n), est optimal.N. Nisse
Complexité temporelle 11/17
IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Outline1Introduction à la complexité temporelle2Somme desnpremiers entiers3Évaluation de Polynômes, Méthode de Horner
4Exponentiation rapide
5Recherche dans un tableau
N. NisseComplexité temporelle 12/17
IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Exponentiation : calcul dexc
Considérons le problème qui prendx2Retc2Nen entrées, et veut calculerxc.Algorithme itératif "naïf"(slide 8, Chap. 2.)
c(exponentiation(n;c)) =1+cå i=12=O(c).Algorithme récursif "naïf"(slide 16, Chap. 2.) c(exponentiationRec(n;0)) =O(1). c(exponentiationRec(n;c))=2+c(exponentiationRec(n;c1)) =O(c).Pour faire mieux (plus rapide), nous proposons une illustration de la
méthode dite "diviser pour régner" (v oirle chapitre suiv antpour plus de précisions). Calcul dencà partir du calcul denbc=2c=nk. sicest pair (c=2k), alorsnc= (nk)2. sicest impair (c=2k+1), alorsnc=n(nk)2.N. NisseComplexité temporelle 13/17IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Exponentiation rapide : calcul dexcTerminaison/Correction :laissées au lecteur (récurrence sur c+argument du slide précédent).
Complexité :Supposons d"abord quec=2k. Posonsckle nombre d"opérationsélémentaires pour calculerexpRapide x2k.
Alorsckck1+3. (application deexpRapide x2k1, une
comparaison, et au plus 2 multiplications). Doncck=O(k).Donccomplexity(expRapide x2k) =O(k) =log2(2k).
Déterminonscomplexity(expRapide x c)pourcquelconque.Soitktel que 2kc2k+1. Prouvons que
complexity(expRapide x2k)complexity(expRapide x c)complexity(expRapide x2k+1) Cette étape est généralement évidente (là, c"est le cas)DoncO(k)complexity(expRapide x c)O(k+1).
D"oùcomplexity(expRapide x c) =O(k) =O(logc)L"algo. d"exponentiation rapide calculexcen tempsO(logc).(les mêmes arguments permettent de prouver que l"algorithme par dichotomie trouve un mot en
O(logn)essais dans un dictionnaire avecnmots (cf. Slide 5).)N. Nisse
Complexité temporelle 14/17
IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Outline1Introduction à la complexité temporelle2Somme desnpremiers entiers3Évaluation de Polynômes, Méthode de Horner
4Exponentiation rapide
5Recherche dans un tableau
N. NisseComplexité temporelle 15/17
IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Recherche dans un tableau
Soitk2N. SoitTl"ensemble des tableaux avecnéléments (des entiers non nulsk). Étant donnéstab2Tet un entierxk. La question est de déterminer la première position dexdans le tableautab(ou décider quexn"est pas dans le tableau).TerminaisonCet algor ithmene ter minepas !! (sauf si
tab:(0) =x). En effet, j"ai oublié d"incrémenteridonc l"algo compare toujours xàtab:(0). Pour corriger, il faut ajouter i:=!i+1 juste avant "done;".Correction
laissée au lecteurComplexité
Dans le pire cas
,xn"est pas dans le tableau et il faut tester chaque élément pour le savoir :O(n).Une fois n"est pas coutume, étudions lacomple xitéen mo yennecmoy=å tab2Tc(recherche(tab;x))jTj.Notons quejTj=kn. Pour 1in, soitti= (k1)i1knile nombre de tableaux dont la première occurrence dexest à la
imeposition, et soittn+1= (k1)nle nombre de tableaux ne contenant pasx. En réorganisant la somme, on obtient
c moy=1k n((nå i=1iti)+ntn+1) =1k n((nå i=1i(k1)i1kni)+n(k1)n) =1k (nå i=1i(k1k )i1)+n(k1k )n:Posonsf(y) =nå
i=0yj=1yn+11y(poury6=1), on note quenå i=1i(k1k )i1=f0(k1k )n!¥k2(en notant que(k1k )n!0).On en déduit quecmoy=O(k).
N. Nisse
Complexité temporelle 16/17
IntroSomme des npremiers entiersÉv aluationde P olynômes,Méthode de Hor nerExponentiation r apideRecherche dans un tab leau
Recherche dans un tableau trié (e.g., dictionnaire)Enfin, si l"on suppose que
le tab leauest TRIÉ , un algorithme de recherche dichotomique per metde trouverxavec une complexitéO(logn)en pire cas.(Le Chapitre suivant est dédié au tri).Prouvez la terminaison et la correction de l"algorithmerecherche2.
Prouvez que sa complexité dans le pire cas estO(logn). Pour cela, on pose c(n)la complexité (pire cas) de l"algorithme pour un tableau de taille n. On note ensuite u k=c(2k), puis il faut prouver que uk=O(1)+uk1et u0=O(1). On en déduit que u k=O(k)et on conclut comme dans le cas de l"exponentiation rapide (slide 14) : pour 2 kn<2k1, ukc(n)