====== Correction exercice 1 du TP1 ======

On suppose que l'on a une liste L, de longueur n = len(L) > 0, de nombres.

<WRAP box>
===== Question 1 =====

Écrire une fonction moyenne qui
  * prend en argument une telle liste,
  * renvoie en retour la moyenne

$$m = \frac{1}{n} \sum_{i=0}^{n-1} \text{L}[i]$$
</WRAP>

On peut d'abord écrire une réponse sous forme d'un algorithme en pseudo-code.

<code lang-none linenums>
FONCTION moyenne
ENTRÉE: liste L de nombres
SORTIE: moyenne des items de de L
DÉBUT
    initialiser un accumulateur à 0
    POUR CHAQUE item de L FAIRE
        ajouter item à l'accumulateur
    FIN
    calculer accumulateur / nombre d'items de L
    RENVOYER le résultat
FIN
</code>

Ce qui traduit en Python devient :

<code python linenums>
def moyenne(L):
    acc = 0
    for item in L:
        acc += item # raccourci équivalent à acc = acc + item
    m = acc / len(L)
    return m
</code>

<WRAP tip>Si on exécute ce programme, il ne se passe rien. On s'est contenté de définir la fonction ''moyenne'' mais celle-ci n'est jamais explicitement appelée !
</WRAP>

Pour le test, on pourrait -- après exécution -- écrire en console

<code python>
>>> moyenne([4, 12, 9, 7, 6])
7.6
</code>

On peut aussi ajouter à la suite du programme :

<code python linenums:8>
m = moyenne([4, 12, 9, 7, 6])
print(m)
</code>

Vous pouvez d'ailleurs visualiser l'exécution de ce programme sur [[https://pythontutor.com/visualize.html#code=def%20moyenne%28L%29%3A%0A%20%20%20%20acc%20%3D%200%0A%20%20%20%20for%20item%20in%20L%3A%0A%20%20%20%20%20%20%20%20acc%20%2B%3D%20item%20%23%20raccourci%20%C3%A9quivalent%20%C3%A0%20acc%20%3D%20acc%20%2B%20item%0A%20%20%20%20m%20%3D%20acc%20/%20len%28L%29%0A%20%20%20%20return%20m%0A%20%20%20%20%0Am%20%3D%20moyenne%28%5B4,%2012,%209,%207,%206%5D%29%0Aprint%28m%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false|Python tutor]].

<WRAP box>
=== coût temporel de la fonction ===

Préciser le nombre d’opérations (additions et division) nécessaires pour faire ce calcul en fonction de la taille de L -- c'est à dire le nombre d'élément de L, soit encore ''n = len(L)''.
</WRAP>

<code python linenums>
def moyenne(L):
    acc = 0          # 1 fois
    for item in L:   # n fois
        acc += item  # n fois
    m = acc / len(L) # 1 fois
    return m         # 1 fois
</code>

Certaines lignes sont exécutées une seule fois, d'autres sont exécutées plusieurs fois : n fois avec n étant le nombre d'items de L.

Python étant un langage de haut niveau, il fait beaucoup de choses cachées pour nous faciliter la vie. Il est donc difficile de savoir si toutes les lignes s'exécutent à la même vitesse. Par exemple, en ligne 5, le calcul ''acc / len(L)'' est plus compliqué qu'il y parait : d'abord il faut calculer ''len(L)''. Combien de temps cela prend-il ?

Pour raisonner, on va néanmoins faire comme si toutes les lignes avaient la même durée d'exécution. Nous avons donc ici 2n + 4 lignes exécutées.

Mais, comme on a été obligé de faire une grosse hypothèse, on n'est pas totalement sûr que ce ne soit pas plutôt 3n + 2 ou 2n + 7 ou... C'est pourquoi, ce qui est surtout important, c'est la forme du résultat. Ici c'est une fonction affine en n. On a un coût **linéaire**.

<WRAP box>
===== Question 2 =====

On rappelle que la variance de la liste L considérée comme une série statistique est la moyenne des carrés des écarts à la moyenne, c’est-à-dire -- 2 formules équivalentes :

$$V = \frac{1}{n} \sum_{i=0}^{n-1} (\text{L}[i] - m)^2 = \frac{1}{n}\left(\sum_{i=0}^{n-1} \text{L}[i]^2 \right) - m^2$$

En supposant que la fonction moyenne est déjà écrite donc utilisable, écrire deux fonctions ''variance1'' et ''variance2'' qui pour une liste de nombres retourne sa variance en utilisant chacune des deux caractérisations de la variance données ci-dessus.
</WRAP>

Dans la fonction ''moyenne'', nous avons traduit $\sum_{i=0}^{n-1} \text{L}[i]$ par la boucle ''for''. Il suffit d'adapter le calcul pour la première formule de variance :

<code python linenums:10>
def variance1(L):
    acc = 0
    m = moyenne(L)
    for item in L:
        acc += (item - m)**2
    v = acc / len(L)
    return v
</code>

Dans la deuxième formule, il faut  $\sum_{i=0}^{n-1} \text{L}[i]^2$, l'adaptation est là aussi rapide :

<code python linenums:18>
def variance2(L):
    acc = 0
    for item in L:
        acc += item**2
    v = acc / len(L) - moyenne(L)**2
    return v
</code>

<WRAP info>**méthode plus élégante mais plus difficile**

La variance peut être vue comme la moyenne des carrés des éléments de L moins la moyenne de L au carré. Si on veut calculer la moyenne des carrés des éléments de L, il faut produire une liste contenant les carrés des éléments de L et prendre leur moyenne. On a alors :

<code python>
# autre version possible
def variance(L):
    return moyenne([item**2 for item in L]) - moyenne(L)**2
</code>
</WRAP>

<WRAP box>
=== Coût temporel de la fonction ===

Préciser le nombre d’opérations élémentaires nécessaires pour une liste de longueur n pour chacune des deux fonctions
</WRAP>

Je ne reprends que le cas de ''variance1'' :

<code python linenums:10>
def variance1(L):
    acc = 0                   # 1
    m = moyenne(L)            # 2n + 3 (vu avant)
    for item in L:            # n
        acc += (item - m)**2  # n
    v = acc / len(L)          # 1
    return v                  # 1
</code>

Le coût est donc en 4n +6, soit un coût linéaire.

<WRAP tip>
Pour calculer la variance avec cette formule, on a besoin de calculer ''moyenne(L)''. On pourrait imaginer de faire ceci :

<code python linenums:10>
def variance1(L):
    acc = 0
    for item in L:
        acc += (item - moyenne(L))**2 # on recalcule n fois la moyenne !
    v = acc / len(L)
    return v
</code>
Comme vous le voyez, la moyenne est recalculée n fois et comme chaque calcul de moyenne coûte 2 n + 3, cela nous donne un coût en n(2n +3) donc un coût en n². C'est beaucoup moins bien ! Il est donc utile de bien organiser ses calculs pour éviter de recalculer sans cesse la même chose et de perdre du temps.
</WRAP>