[PDF] Séance 3 : coût dun algorithme

View - Download Séance 3 : coût dun algorithme

Previous PDF

Next PDF

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

2

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] 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] fiches calcul mental cm2

[PDF] calcul mental cm1 pdf