Calcul de coût dalgorithme
Calcul de coût d'algorithme. Concepts : Analyse de coût. Méthodes : Décomposition du coût ordres de grandeur. Présentation. Le concept de coût associé à un
Séance 3 : coût dun algorithme
1. les calculs (+ - * / %). 2. les tests ( < > <= >= == != ) 3. les boucles (boucle pour (for) boucle tant que (while)). 4. les fonctions ou comment
L3 Info Cours 1 : notion de coût dun algorithme
Savoir comment évaluer la complexité d'une solution algorithmique : Le calcul du coût d'un algorithme s'obtient donc en composant les coûts.
Chapitre 2 Complexité algorithmique
22 oct. 2014 Evaluer la compléxité d'un algorithme. Des exemples de calculs de complexité ... Comment évaluer le coût d'exécution d'un algorithme donné ?
L3 Info Cours 2 : algorithmes récursifs analyse en moyenne
Algorithmique et Analyse d'Algorithmes Comment évaluer l'efficacité d'un algorithme plus finement que dans le pire cas ? ... Calcul de coût direct.
Un algorithme général de calcul de létat déquilibre dun oligopole
Keywords : Equilibrium Oligopoly
cours 2:Complexité des algorithmes récursifs
On parle alors de méthode récursive. Exemple : Le calcul de la factorielle de N. N != N*(N-1)*(N-2)*
Coût de lalgorithme dEuclide et CAPES interne 2000
Cela nous mène à préciser comment l'estimation peut être affinée en 3) Un majorant du temps de calcul de l'algorithme d'Euclide avait déjà été donné.
Complexité des algorithmes : nombres_instructions élémentaires
Le coût final du conditionnel est : T (conditionnel)=1+max(22)=3. 18 / 51. Page 27. Calculer le nombre d'instructions ´el´ementaires.
TD1.1 Analyse dalgorithmes calculs de coûts
TD1.1 Analyse d'algorithmes calculs de coûts. Objectifs. À la fin de cette séance
[PDF] Calcul de coût dalgorithme
19 sept 2012 · Pour calculer le coût d'un algorithme on utilise les règles de composition suivantes : Le coût d'une itération est égal à la somme des coûts de
[PDF] Séance 3 : coût dun algorithme
Le coût d'un algorithme est une estimation du nombre d'opérations élémentaires effectué par un algorithme Cette estimation dépend du nombre de ses entrées et
[PDF] L3 Info Cours 1 : notion de coût dun algorithme
? Savoir démontrer la correction des algorithmes ? Savoir comment évaluer la complexité d'une solution algorithmique : - analyser la complexité au pire en
[PDF] Calculs de complexité dalgorithmes
Complexités d'un algorithme ?Un algorithme à partir d'une donnée établit un résultat ?La taille de la donnée est mesurée par un entier n
[PDF] Algorithmique et complexité de calcul
Exercice : Décrire cet algorithme Montrer qu'il demande un espace dans O(k) et un temps dans O(nk) si on compte chaque addition à coût unitaire
[PDF] Algorithmique I - Cours et Travaux Dirigés L3 Ecole Normale
2 1 Algorithme de Strassen Le coût de l'algorithme est alors : Question 2 3 Comment calculer le produit d'une matrice de Tœplitz n × n par un
[PDF] ALGORITHMIQUE
Exemple de progression pour aborder l'algorithmique en seconde Voici l'algorithme qui correspond au programme de calcul Comment les définir ?
[PDF] cours_exemples_exercices algorithmiquepdf - fustel-yaoundenet
2 2 pour qu'il calcule l'expression 3N 2 2 Exercice III 3 Écrire un algorithme permettant de calculer l'expression xy x2 où x et y représentent deux
[PDF] livre-algorithmespdf - Exo7 - Cours de mathématiques
Voyons comment l'écriture binaire des nombres peut nous aider L'écriture binaire d'un nombre c'est son écriture en base 2 Comment calculer un nombre qui
[PDF] Arles– Info 1ère année – Matière AP (Module Algorithmique) TD 3
affichage digital effectue un calcul semblable toutes les minutes) Exercice V : Ecrire un algorithme qui permet de calculer le prix d'un troupeau
Comment savoir le coût d'un algorithme ?
Méthode de calcul de coût Le calcul du coût d'un algorithme s'obtient donc en composant les coûts des différentes opérations composant l'algorithme. On écrit f = O(g) pour f ? O(g). On dit que g est une borne supérieure asymptotique pour f .Quel est le coût d'un algorithme de recherche du maximum d'un tableau de nombres ?
le coût d'un algorithme A(T) est son nombre d'affectation. Ainsi, pour chaque cas de Pn,k, l'algorithme effectue k affectations. On obtient donc ainsi que le coût d'un algorithme A(T) est de kPn,k. coutA(T) = 1 nComment faire un algorithme PDF ?
Un algorithme, ou code "bien écrit" doit avoir les propriétés suivantes :
1Être facile à lire, pas soi-même mais aussi par les autres.2Avoir une organisation logique et évidente.3Être explicite, montrer clairement les intentions du développeur.4Être soigné et robuste au temps qui passe.Résumé des étapes de la méthode
1Lisez bien le sujet, et reformulez-le.2Faites la liste des dimensions du sujet.3Cherchez une bonne représentation visuelle du problème.4Générez des exemples, et résolvez-les entièrement à la main.5Décrivez la solution naïve, puis essayez de l'améliorer.
Calcul de coût d"algorithme
Concepts :Analyse de coût
Méthodes :Décomposition du coût, ordres de grandeurPrésentation
Le concept decoûtassocié à un algorithmeAformalise la notion intuitive d"efficacitéd"un pro-
gramme, c"est à dire sa capacité à fournir le résultat escompté dans un temps minimal, on parle égale-
ment de performances du programme. Du point de vue pratique, l"analyse du coût permet de déterminer
quelles seront les ressources en temps de calcul, en mémoire et éventuellement en entrées/sorties néces-
saires pour exécuter le calcul associé à l"algorithme.Pour définir le coût, on se donne unmodèle de machineavec une mémoire que l"on suppose en gé-
néral infinie et munie d"opérations dont le temps d"exécution (coût élémentaire) est constant (ou majoré
par une constante). L"exécution de l"algorithme sur une donnéedest modélisé par une séquence finie
d"opérations de la machine; le coût de l"exécutionC(A;d)sur la donnéedest donc le nombre d"exécu-
tions de chaque opération au cours de l"exécution. Éventuellement on restreindra le nombre d"opérations
étudiées en choisissant celles dont l"interprétation sera la plus intéressante (opération la plus coûteuse).
Comme l"algorithme va être exécuté sur un grand ensemble de données, il est nécessaire de spécifier
l"espace des donnéesDet d"en fournir une description algébrique. Pour analyser le coût d"un algorithme,
on cherche alors à donner des facteurs expliquant le coût en fonction de paramètres de la donnée. En
particulier, on s"intéresse au lien entre lataillede la donnée et le coût de l"algorithme.Co\^{u}t du calcul : $C$
Entier EntierTaille de la donnée : $d$
Espace des donnéesEspace des résultats
Machine (modèle)Algorithmed
CDéfinition 1 (Coût au pire)
Le coût au pire de l"algorithmeAest défini par la fonction den:Co^utA(n) = maxd2DnC(A;d):
On peut également définir le coût au mieux en fonction denen prenant le minimum des coûts.
Comportement asymptotique
Ce qui est intéressant dans l"analyse du coût est le comportement asymptotique en fonction den(notion de passage à l"échelle). Pour cela on compare la fonction de coût à des fonctions de référence
appeléesfonctions d"échelle. Typiquement les fonctions puissancexn, exponentielles2nou logarith-
miqueslogk(n)sont des fonctions d"échelle. Pour exprimer la comparaison asymptotique on utilise la
notation de Landau :Coût d"algorithme
Définition 2 (Borne asymptotique approchée : fonction) Pour une fonction donnéegon note(g)l"ensemble de fonctions : (g) =fftelles que9c1;c2>0;9n0>0;8n>n0;c1:g(n)6f(n)6c2:g(n)g; on écritf= (g)pourf2(g)et on dit quegest une borne asymptotique approchée pourf. Définition 3 (Borne supérieure asymptotique : fonctionO) Pour une fonction donnéegon noteO(g)l"ensemble de fonctions :O(g) =fftelles que9c>0;9n0>0;8n>n0;f(n)6c:g(n)g;
on écritf=O(g)pourf2 O(g)et on dit quegest une borne supérieure asymptotique pourf. Définition 4 (Borne inférieure asymptotique : fonctionPour une fonction donnéegon note
(g)l"ensemble de fonctions : Omega(g) =fftelles que9c>0;9n0>0;8n>n0;c:g(n)6f(n)g; on écritf= (g)pourf2 (g)et on dit quegest une borne inférieure asymptotique pourf.Règles de calcul du coût
Pour calculer le coût d"un algorithme on utilise les règles de composition suivantes : Le coût d"uneitérationest égal à lasommedes coûts de chaque terme de l"itération; Le coût d"uneinstruction conditionnelleestmajorépar lemaximumdes coûts de chacune des branches de l"instruction conditionnelle;Le coût d"unappel de procédureest égal à lasommedu coût de l"appel (évaluation des paramètres)
et du coût du corps de la procédure.Lorsque le programme est récursif, on exprime le coût de l"algorithme en fonction du coût des appels
récursifs. On obtient ainsi une équation derécurrencesur la fonction de coût.Coût en moyenne
Lorsque, pour une taille de donnée fixée, le coût peut prendre plusieurs valeurs entre les bornes coût
maximum et coût minimum. Il est interessant de savoir si, en général, pour une donnée arbitraire on est
plutôt près du coût au mieux ou au pire coût. Pour formaliser le raisonnement, on munit l"espace des
données de taillend"une probabilité (usuellement la loi uniforme) et on calcule la distribution du coût,
c"est à dire on calcule la probabilité que le coût de l"algorithme prenne la valeur1;2;;n;. Comme
il est souvent très difficile de calculer la probabilité de chaque valeur de coût on se contente de sa valeur
moyenne.Définition 5 (Coût moyen (cas uniforme))
Le coût moyen de l"algorithmeAest défini par la fonction den:Co^utmoyenA(n)) =1Card(Dn)X
d2DnC(A;d):Coût d"algorithmes récursifs
algorithme sur des données de taillencomme une fonction du coût de l"exécution du même algorithme
sur des des données de tailles plus petites quen.La fonction de coût vérifie ainsi une équation derécurrence. On peut classer les équations de récur-
rence en fonction de leur forme (linéaire, de partition, ...) et donner les asymptotiques. On noteraT(n)
le coût de l"algorithme pour une donnée de taillen.Algorithmique version du 19 septembre 20122/ 5
Coût d"algorithme
Équations linéaires simples
T(0) = 0;
T(n) =T(n1) +f(n);pourn>1;
oôfest une fonction (en général positive). En itérant la relation à partir den= 0on obtient facilement :
T(n) =f(0) +f(1) ++f(n) =nX
i=0f(n):On rappelle que
n X i=11 =n= (n);nX i=1i=n(n+ 1)2 = (n2);nX i=1i2=n(n+ 1)(2n+ 1)6
= (n3); n X i=1i3=n2(n+ 1)24
= (n4)et de manière plus généralenX i=1i k=O(nk+1):Exercice : faire la preuve en comparant
Pn i=1iketRn 1xkExemples
Étudier le tri par sélection, le tri par insertion (cf TD) avec cette méthode.Équations linéaires multiples
T(0) =t0;T(1) =t1T(k1) =tk1;
T(n) =a1T(n1) +a2T(n2) +akT(nk);pourn>k:
Ces équations de récurrence linéaires se développent à partir d"une base de solutions de la forme :
T(n) =pX
i=1m i1X j=0c i;jnjnj;avecf1;2;;pglespracines du polynôme P(x) =xka1xk1a2xk2 a0;de multiplicités respectivesfm1;;mpg Les constantesci;jsont fixées par les conditions initiales. De manière générale simaxest la racine de module maximal et de multiplicitémalorsT(n) =O(nm1jmaxjn):
C"est à dire que la fonction croit de manière très rapide, au moins exponentiellement. Exercice :Calculer la valeur deT(n)pour l"équation de récurrenceT(0) =T(1) = 1;
T(n) =T(n1) +T(n2);pourn>2:
On appelle la suiteT(n), la suite de Fibonacci (Léonardo de Pise mathématicien Italien du XII-XIIIième
siècle).Algorithmique version du 19 septembre 20123/ 5Coût d"algorithme
Équations de partition
On suppose que la fonction de coût suit l"équation suivanteT(1) = 1;
T(n) =aT(nb
) +c(n);pourn>1; aveca>1,b >1etc(n)une fonction positive den. Attention cette formulation contient déjà une approximation (la fraction nb n"a pas de raison d"être entière)Ce type d"équation apparaît naturellement lorsque la résolution d"un problème de taillense fait en
résolvantaproblèmes de taillenb . Pour simplifier on suppose quen=bket on notetk=T(bk). On a facilement l"équation de récurrence sur lestken remarquant que t k=atk1+c(bk) at k1=a2tk2+ac(bk1) a2tk2=a3tk3+a2c(bk2)
a k1t1=akt0+ak1c(b0)t k=akt0+Pk1 i=0aic(bki) En utilisant le fait quet0= 1et queak=nlogba, le résultat se met sous la formeT(n) =nlogba+log
bn1X i=0a ic(blogbni):En fonction du problème étudié, soit le premier terme l"emporte "le coût de partition" n"est pas prépon-
dérant, soit c"est le deuxième terme qui l"emporte et toute la complexité du calcul est dans le partition-
nement.Calcul de coût 1. Spécifier les opérateurs de base de v otremodèle de machine (coût constant) ; 2. Décrire l"espace des données et sa se gmentation(définir la taille d"une donnée) ; 3.Écrire l"e xpressiondu coût à l"aide des règles de composition des coûts élémentaires des
opérateurs de base; 4. Pour une donnée de taille ncalculer le coût maximal (coût au pire) et le coût minimal (coût au mieux) de l"algorithme; 5. Étudier l"ensemble des données conduisant au pire ou au meilleur coût (e xemples); 6. Donner l"ordre de gra ndeurdu coût (a vecles fonctions OouOmega) pour le coût au pire d"une donnée de taillensur une échelle permettant de comparer les algorithmes (classiquement on utilise l"échelle déduite de l"échelle polynomiale, des logarithmes (en base 2) et des exponentielles (puissances de2);Lectures suggéréesAlgorithmique, Cormen, Leiserson, Rivest et Stein Dunod 2011 (pour la version française) chapitres
2 et 3faire les exercices du chapitre 3Algorithmique version du 19 septembre 20124/ 5
Coût d"algorithme
Pour les aspects mathématiques discrètes et application au calcul de coût on consultera le livre :
Concrete Mathematics, Second Edition by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik ou sa version française Mathématiques concrètes.Références
[1] Thomas Cormen,CharlesLeiserson,RonaldRivest,andCliffordStein.Algorithmique-3èmeédition - Cours avec 957 exercices et 158 problèmes. Dunod, 3e édition edition, 6 2010. [2] Ronald Graham, Donald E. Knuth, a ndOren P atashnik.Mathématiques concrètes. International Thomson publishing France, 2e éd edition, 1998. [3]Robert Sedge wickand K evinW ayne.Algorithms (4th Edition). Addison-Wesley Professional, 2011.Algorithmique version du 19 septembre 20125/ 5
quotesdbs_dbs22.pdfusesText_28[PDF] trp production definition
[PDF] taux de rendement de production
[PDF] calcul trp production
[PDF] trp calcul
[PDF] faire des statistiques sur excel 2010
[PDF] calculer les cotés d'un triangle rectangle avec les angles
[PDF] longueur mediane triangle equilateral
[PDF] calcul mental 5eme
[PDF] séquence mesure de longueur cm1
[PDF] grandeurs et mesures cm1
[PDF] calcule mentale rapide
[PDF] calcul mental cm1 ? imprimer
[PDF] fiches calcul mental cm2
[PDF] calcul mental cm1 pdf