horner.pdf - Schéma de Hörner
La derni`ere ligne du tableau précédent ne nous livre pas seulement la valeur de P(a). En effet si construit en utilisant les trois premiers cœfficients de
Méthode de Horner pour calculer limage dun point par un polynôme
25 janv. 2006 Je suis tr`es surpris de constater que la méthode (ou schéma) de Horner n'est pas tr`es utilisée par les lycéens. Le principe est pourtant ...
La méthode de Hörner
1 sept. 2018 Bien entendu il existe d'autres méthodes
Algorithmes compensés en arithmétique flottante : précision
Nous proposons une version compensée du schéma de Horner : la précision du résultat compensé produit par cet algorithme est la même que s'il avait été
Exercice 1. Utiliser le schéma de Horner pour évaluer p(x) et ses
Utiliser le schéma de Horner pour évaluer p(x) et ses dérivées successives p (x) p (x)
Complexité des algorithmes [cx] Exercices de cours
2.2 Schéma de Hörner. Utilise Complexités en temps ?. Durée estimée 15 min ?. Schéma de Hörner. Le schéma de Hörner évalue la valeur d'un polynôme pour
Schéma de Horner et algorithme de Newton
Pour aller plus loin il vaut mieux programmer le schéma de Horner (voir le livre § 5.7.4) et la méthode de Newton. Nous trouvons ensuite p(x(1))=0
Les polynômes
Schéma de Horner et dérivées. Évaluation parall`ele. Racines de polynômes. Évaluation d'un polynôme. Introduction : Soit un polynôme P(x) on veut évaluer
Variations sur le schéma de Horner.
Variations sur le schéma de Horner. (Programmation avec Maple). Préparation `a la nouvelle épreuve d'informatique de l'École Polytechnique.
Introduction à lalgorithmique et la complexité (et un peu de CAML
Évaluation de Polynômes Méthode de Horner. Exponentiation rapide. Recherche dans un tableau. Outline. 1. Introduction à la complexité temporelle.
[PDF] La méthode de Hörner - Mathwebfr
1 sept 2018 · La méthode de HÖRNER va nous permettre de trouver les coefficients du polynôme Q tel que : P (x)=(x ?a)Q(x)
[PDF] Schéma de Hörner - Amiens Python
1 Le schéma de Hörner pour le calcul de valeurs 1 1 Un exemple Soit la fonction polynôme P définie par P(x)=2x3 ? 7x 2 + 4x ? 1
[PDF] Méthode de Horner pour calculer limage dun point par un polynôme
25 jan 2006 · Comme je l'ai indiqué dans le titre le schéma de Horner permet de calculer l'image d'un polynôme P en un point ? donné
[PDF] I Méthode Horner
I Méthode Horner 1 Le principe Prenons l'exemple de P(x)=3x5 ? 2x4 + 7x3 + 2x2 + 5x ? 3 Pour calculer P(x) le calcul classique nécessite
[PDF] méthode de Horner
12 déc 2011 · La méthode dite de Horner (William George Horner 1786-1837) est une méthode très pratique utilisée pour factoriser un polynôme
[PDF] 4 Polynômes - Apprendre-en-lignenet
Le schéma de Horner utilise un tableau pour calculer P(r) où P est un polynôme Sa force est que tout en calculant P(r) on peut obtenir une factorisation
Méthode de Horner (ou schéma de Horner) - Mathforu
Cours de maths complet sur la méthode de Horner ou Schéma de Horner Très peu utilisée elle est pourtant simple rapide et permet aussi de factoriser les
[PDF] Calcul dune image dun polynôme par la méthode de Horner
4 nov 2015 · c) Comment remplit-on le tableau suivant dont on a détaillé 3 étapes ? Que calcule-t-il ? 3 -5 7 8
[PDF] Exercice 1 Utiliser le schéma de Horner pour évaluer p(x) et ses
Utiliser le schéma de Horner pour évaluer p(x) et ses dérivées successives p (x) p (x) etc en x = -4 où p(x) = x3 + 4x2 + x - 6 Exercice 2
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)Complexité temporelle 17/17
quotesdbs_dbs22.pdfusesText_28[PDF] seuil de rentabilité cours pdf
[PDF] méthode des couts variables exercices corrigés
[PDF] exercice seuil de rentabilité corrigé pdf
[PDF] levier opérationnel calcul
[PDF] représentation graphique du seuil de rentabilité
[PDF] calcul du seuil de rentabilité avec plusieurs produits
[PDF] indice de sécurité calcul
[PDF] exercice seuil de rentabilité bts
[PDF] choix d'investissement exercices
[PDF] rentabilité des investissements cours
[PDF] calcul drci+formule
[PDF] calcul de rentabilité d'un investissement industriel
[PDF] etude de rentabilité d'une entreprise
[PDF] ratio de rentabilité commerciale