Plan - xavierduprefr

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 chaque terme de l’itération; Le coût d’une instruction conditionnelle est majoré par le maximum des coûts de chacune des

Chapitre 2 Complexité algorithmique

Le cout^ d’une op eration el ementaire est egale a 1 Exemple 1 : Que vaut le cout^ de l’algorithme A somme = n + 1 #instr1 somme = somme n#instr2 somme = somme=2#instr3 Cout(^A)=Cout(^inst1)+Cout(^instr2)+Cout(^instr3)=3 Programmation en Python{2 eme ann ee MP3{ CPGE GSR 2014-201510/ 30

Plan - xavierduprefr

3 coût de l'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 de leurs dimensions Un opération élémentaires est une affection, un calcul, une comparaison som = 0 pour i allant de 1 à n inclus

Problème du plus court chemin : Algorithmes et complexité

ALGORITHME de DIJKSTRA (Reaching ; label-setting) Trouver des plus courts chemins de s vers tout autre noeud (c-à-d un arbre des plus courts chemins) dans un réseau qui ne contient pas d’arc de coût négatif L’algorithme maintient une distance di pour chaque noeud i avec un statut permanent (=plus court chemin) ou temporaire (=borne sup sur

Optimisation linéaire - EPFL

Algorithme du simplexe Michel Bierlaire 21 Développement de la méthode du simplexe • On veut aller le plus loin possible le long de d, en restant admissible • On cherche θ* tel que θ* = max { θ≥0 ¦ x+ θd ∈P} • Comment calculer θ* ? • Comme d est admissible, la seule manière de

Algorithme de Dijkstra : terminaison, correction et complexité

plexité d’un algorithme 1 Présentation de l’algorithme 2 Preuve de sa terminaison 3 Preuve de sa correction 4 Étude de sa complexité Remarques sur le développement 2 Étude de l’algorithme de Dijkstra Présentation de l’algorithme a Objectif : chemin le plus court à origine unique Pour a 2V, on veut calculer d : V f+¥gtel que

COURS ALGORITHMIQUE ET PROGRAMMATION INFORMATIQUE

• On souhaite calculer et afficher , à partir d’un prix hors taxe saisi, la TVA ainsi que le prix TTC • Le montant TTC dépend de : • Du prix HT • Du taux de TVA de 20,6 MAP - UNS 17 EXEMPLE D’ÉNONCÉ D’UN PROBLÈME • On souhaite calculer et afficher , à partir d’un prix hors taxe saisi, la TVA ainsi que le prix TTC

zNotations asymptotiques : 0 et Θ zComplexité des algorithmes

Complexités d’un algorithme zUn algorithme à partir d’une donnée établit un résultat zLa taille de la donnée est mesurée par un entier n {complexité temporelle une fonction de n qui mesure le temps de calcul pour une donnée de taille n {complexité en mémoire une fonction de n qui mesure la place mémoire

Complexité Techniques de calcul et de réduction

Lilian BUZER version b année 2003-2004 Complexité

[PDF] taux de rendement production trp

[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] calcul mental cm1 pdf

[PDF] progression calcul mental cm2

Plan - xavierduprefr

Plan :

1. rappel sur les séances précédentes

2. calcul d'une variance

3. coût de l'algorithme

4. le jeu du penduSéance 3 : coût d'un algorithme

Au cours des séances précédentes, nous avons vu :

1. les calculs (+ - * / %)

2. les tests ( < > <= >= == != )

3. les boucles (boucle pour (for), boucle tant que (while))

4. les fonctions ou

comment découper un algorithme en tâches élémentaires1. rappel On dispose de n observations : 2. calcul de la varianceX1,...XnLa moyenne est définie par : X=1 n∑i=1 n

XiLa variance est définie par :

V=1 n∑i=1 n Xi-X21. l'algorithme est définie par la formule de la variance

2. le découpage est fonction semble plutôt intuitif :

1. fonction moyenne

2. fonction variance

3. écriture des fonctions

2. fonction moyenneX=1

n∑i=1 n

Xifonction moyenne

entrées : un tableau de n variables réelles sorties : un nombre réel som = 0 pour i allant de 1 à n inclus som = som + élément i som = som / n retourne som Question subsidiaire : que se passe-t-il lorsque la fonction effectue la moyenne de 0 élément ?

division zéro par zéro : faut-il prévoir ce cas ? si n est nul alors retourne 0 sinon...

2. fonction variance

fonction variance entrées : un tableau de n variables réelles sorties : un nombre réel som = 0 pour i allant de 1 à n inclus som = (élément i - moyenne (éléments)) * (élément i - moyenne (éléments)) som = som / n retourne som Question subsidiaire : que se passe-t-il lorsque la fonction effectue la moyenne de 0 élément ?

division zéro par zéro : faut-il prévoir ce cas ? si n est nul alors retourne 0 sinon...V=1

n∑i=1 n Xi-X2

2. récapitulatif

fonction variance som = 0 pour i allant de 1 à n inclus som = (élément i - moyenne (éléments)) * (élément i - moyenne (éléments)) som = som / n retourne somV=1 n∑i=1 n Xi-X2 X=1 n∑i=1 n

Xisom = 0

pour i allant de 1 à n inclus som = som + élément i som = som / n retourne somfonction moyenne

Coût de l'algorithme ?

3. coût de l'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 de leurs dimensions. Un opération élémentaires est une affection, un calcul, une comparaison. som = 0 pour i allant de 1 à n inclus som = som + élément i som = som / n retourne somfonction moyenneExemple : coût de la fonction moyenne ? nombre d'entrée : 1 tableau dimension des entrées : n résultat : 2 n + 2 approximation : O(n)

3. approximation ?

Le coût d'un algorithme est souvent une approximation. On est plus intéressé par savoir ce qu'il se passe lorsque la taille des entrées évolue plutôt que d'avoir une estimation précise. coût : O(n) si la taille double, le temps de calcul double coût : O(n²) si la taille double, le temps de calcul quadruple Les estimations précises ne sont nécessaires que dans des cas extrêmes : - décompression du signal sonore sur un téléphone mobile - traitement d'image sur un missible à tête chercheuse Un autre point : le temps d'exécution d'un algorithme dépend : - du langage de programmation utilisé assembleur > C++ > Python - de la machine utilisée

Pour toutes ces raisons, le coût précis d'un algorithme n'est plus estimé, il est mesuré.

3. coût de la fonction variance

fonction variance som = 0 pour i allant de 1 à n inclus

som = (élément i - moyenne (éléments)) * (élément i - moyenne (éléments))

som = som / n retourne somsom = 0 pour i allant de 1 à n inclus som = som + élément i som = som / n retourne somfonction moyenne O (n)

4 n * 2 O (n) + 2 = O (n²)

Peut-on faire mieux ?

- O(n²) - O(n log n) - O(n)

3. coût de la fonction variance

fonction variance som = 0 moy = moyenne (éléments) pour i allant de 1 à n inclus som = (élément i - moy) * (élément i - moy) som = som / n retourne somsom = 0 pour i allant de 1 à n inclus som = som + élément i som = som / n retourne somfonction moyenne O (n) O(n)

3. coût de la fonction variance

La réduction du coût d'un algorithme est appelée une optimisation. L'optimisation présentée est informatique : l'algorithme ne change pas, il est écrit différemment. L'optimisation peut être autre comme mathématique : l'algorithme change.V=1 n∑i=1 n Xi-X2=1 n∑i=1 n Xi

2-1

n∑i=1 n

Xi

4. le jeu du pendu

Règles :

- objectif : deviner un mot - proposer une lettre - montrer les lettres du mot qui correspondent à la lettre choisie - au bout de 10 lettres proposées, le joueur est perdu à moins de donner le bon mot

1. algorithme

2. découpage en fonctions

3. écriture des fonctions

4. le jeu du pendu

1. tirer aléatoirement un mot

2. demander une lettre au joueur

3. passer en revue les lettres du mot et retourner celles égales à la lettre demandée

4. afficher les lettres dévoilées

5. vérifier que le jeu est fini, si oui arrêter, sinon, retourner à l'étape 2

quotesdbs_dbs28.pdfusesText_34

[PDF] Plan - xavierduprefr

Plan :

1. rappel sur les séances précédentes

2. calcul d'une variance

3. coût de l'algorithme

4. le jeu du penduSéance 3 : coût d'un algorithme

1. les calculs (+ - * / %)

2. les tests ( < > <= >= == != )

3. les boucles (boucle pour (for), boucle tant que (while))

4. les fonctions ou

XiLa variance est définie par :

2. le découpage est fonction semble plutôt intuitif :

1. fonction moyenne

2. fonction variance

3. écriture des fonctions

2. fonction moyenneX=1

Xifonction moyenne

2. fonction variance

2. récapitulatif

Xisom = 0

Coût de l'algorithme ?

3. coût de l'algorithme

3. approximation ?

3. coût de la fonction variance

4 n * 2 O (n) + 2 = O (n²)

Peut-on faire mieux ?

3. coût de la fonction variance

3. coût de la fonction variance

2-1

Xi

4. le jeu du pendu

Règles :

1. algorithme

2. découpage en fonctions

3. écriture des fonctions

4. le jeu du pendu

1. tirer aléatoirement un mot

2. demander une lettre au joueur

3. passer en revue les lettres du mot et retourner celles égales à la lettre demandée

4. afficher les lettres dévoilées

5. vérifier que le jeu est fini, si oui arrêter, sinon, retourner à l'étape 2