Complexité des algorithmes [cx] Exercices de cours PDF

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

Complexitedes algorithmes [cx]

Exercices de cours

Karine Zampieri, Stephane Riviere, Beatrice Amerein-Soltner

UniscielalgoprogVersion 21 mai 2018

Table des matieres

1 Apprehender le cours

2 Appliquer le cours

2.1 Recherche du maximum

2.2 Schema de H

orner. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.3 Tours de Hano

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 alg - Exercices de cours (Solution)Mots-ClesComplexite des algorithmes

Diculte• • ◦(1 h)

1 Unisciel algoprog { cx00exerc-texte, May 21, 20182

1 Apprehender le cours

2 Appliquer le cours

2.1 Recherche du maximumObjectif

Cet exercice evalue la complexite en nombre de comparaisons de la recherche du maxi- mum dans unTableaudenit comme suit :Denitions PseudoCode

ConstanteTMAX<- ... TypedefITableau= Entier[TMAX]

Ecrivez une fonctionmaximumTab(t,n)qui calcule et renvoie la plus grande valeur desn premieres valeurs d'unITableaut .Solution Parametres

Entrants :UnITableaut et un entiern

Resultat de la fonction :Un entier (type des elements du tableau)Validez votre fonction avec la solution.

Solution alg@[UtilsTBOpers.alg]FonctionmaximumTab( DRt: Entier[TMAX ] ; n : Entier) :EntierVariablevmax: EntierVariableix: EntierDébut|vmax <- t [ 1 ]

Solution simple

Il y an-1comparaisons.

Unisciel algoprog { cx00exerc-texte, May 21, 20183Montrez qu'il est optimal.

Solution simple

Tout element hormis le maximum induit une comparaison, sinon, on ne peut pas savoir qu'il n'est pas le maximum. Il y an-1tels elements. Tout algorithme de recherche du maximum dans un tableau quelconque doit donc faire au moinsn-1comparaisons. Unisciel algoprog { cx00exerc-texte, May 21, 20184

2.2 Schema de H

ornerUtiliseComplexites en temps

Duree estimee15 minSchema de H

orner Le schema deHornerevalue la valeur d'un polyn^ome pour une valeur de la variable.

Il est base sur la reecriture :

P(x) =a0+a1x+...+anxn

=a0+x(a1+x(a2+...+x(an-1+x(an))...)) Ecrivez une fonctionevalHorner(p,n,x)qui calcule et renvoie la valeur d'un polyn^omep (tableau de reels) d'ordren(entier) enx(reel).Validez votre fonction avec la solution.

Solution alg@[evalHorner.alg]FonctionevalHorner( p : Réel[ 0.. NMAX] ; n : Entier;x : Réel) : RéelVariablers: RéelVariableix: EntierDébut|rs <- 0.0

Solution simple

L'analyse de complexite du schema deHornerest exacte et ne depend pas de la con- guration des donnees. On faitn+2aectations,n+1additions etn+1multiplications.

La complexite est donc enΘ(n).

Unisciel algoprog { cx00exerc-texte, May 21, 20185

2.3 Tours de Hano

UtiliseComplexites en temps

Duree estimee20 minObjectif

L'algorithme desTours de Hanoiest deni par :

Pour deplacerndisques de la tige A vers la tige C : 1. O nd eplacel es(n-1)plus petits de la tige A vers la tige B. 2. O nd eplacel ep lusg rosd isqued el at igeA v ersl at igeC. 3. O nd eplacel es(n-1)plus petits de la tige B vers la tige C.

L'algorithme s'ecrit comme suit :Actionhanoi( n : Entier;orig , dest , inter : Cha îne) Début|Si(n > 0 ) Alors| |hanoi ( n - 1 , orig , inter , dest )

deplacer orig dest hanoi n - 1 , inter dest orig |FinSiFin On noteH(n)le nombre de passages d'un disque d'un piquet a un autre.

Donnez la relation de recurrence.Solution simple

On a clairement :

?H(0) = 0

H(n) = 2H(n-1) + 1Resolvez la recurrence.

Solution simple

On a :

H(n) = 2H(n-1) + 1

2H(n-1) = 22H(n-2) + 2

2H(n-2) = 23H(n-3) + 22

2 n-1H(1) = 2nH(0) + 2n-1

Par sommation des equations membre a membre :

H(n) = 2nH(0) + 1 + 2 +...+ 2n-1= 2n-1

Unisciel algoprog { cx00exerc-texte, May 21, 20186Deduisez la complexite de la procedure.

Solution simple

Si l'on compte la gestion des appels recursifs et la comparaison a zero, operations en Θ(1), la complexite de l'algorithme, toutes operations confondues est enΘ(2n).Concluez.

Solution simple

On peut donc dire :

•La complexite est exponentielle donc l'algorithme est impraticable pour les grandes valeurs den. •L'algorithme est optimal car on peut montrer qu'il faut au moins2n-1passages pour resoudre le probleme. •On aura rapidement des problemes de memoire relatifs a la gestion de la recursivite.quotesdbs_dbs28.pdfusesText_34

[PDF] algorithme de horner python

[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

[PDF] Complexité des algorithmes [cx] Exercices de cours

Complexitedes algorithmes [cx]

Exercices de cours

UniscielalgoprogVersion 21 mai 2018

Table des matieres

1 Apprehender le cours

2 Appliquer le cours

2.1 Recherche du maximum

2.2 Schema de H

2.3 Tours de Hano

Diculte• • ◦(1 h)

1 Apprehender le cours

2 Appliquer le cours

2.1 Recherche du maximumObjectif

ConstanteTMAX<- ... TypedefITableau= Entier[TMAX]

Entrants :UnITableaut et un entiern

Solution simple

Il y an-1comparaisons.

Solution simple

2.2 Schema de H

Duree estimee15 minSchema de H

Il est base sur la reecriture :

P(x) =a0+a1x+...+anxn

Solution simple

La complexite est donc enΘ(n).

2.3 Tours de Hano

UtiliseComplexites en temps

Duree estimee20 minObjectif

L'algorithme desTours de Hanoiest deni par :

Donnez la relation de recurrence.Solution simple

On a clairement :

H(n) = 2H(n-1) + 1Resolvez la recurrence.

Solution simple

On a :

H(n) = 2H(n-1) + 1

2H(n-1) = 22H(n-2) + 2

2H(n-2) = 23H(n-3) + 22

Par sommation des equations membre a membre :

H(n) = 2nH(0) + 1 + 2 +...+ 2n-1= 2n-1

Solution simple

Solution simple

On peut donc dire :