Aller au contenu

1NSI : Algorithmique : Extrema (Minimum et Maximum) et Moyennes⚓︎

Contenus Capacités Attendues Commentaires
Parcours Séquentiel
d'un Tableau		 Écrire un algorithme de
recherche d’une occurrence sur
des valeurs de type
quelconque.
Écrire un algorithme de
recherche d’un extremum, de
calcul d’une moyenne.		 On montre que le coût est linéaire

Algorithme de Recherche de Minimum/Maximum⚓︎

Recherche de Minimum ❤

def recherche_min(l:list):
    '''renvoie le minimum de la liste l'''
    mini = l[0]           # (1)
    for el in l:
        if el < mini:
            mini = el
    return mini
  1. On initialise le minimum avec la première valeur du tableau (surtout pas avec \(0\) ou «moins l'infini» !)

Utilisation 

>>> recherche_min([12, 8, 14, 15])
8
Complexité/Coût
On note \(n\) la taille des données en entrée : dans notre cas une bonne mesure de cette taille correspond à la taille de la liste n=len(l) (càd \(n\)=combien de nombres dans la liste?) Le coût/complexité \(C(n)\) de cet algorithme de recherche de minimum est le nombre d'opérations réalisées, ou bien de manière (ici) équivalente, le nombre d'itérations \(C(n)\) dans la boucle for de cet algorithme.
On a (clairement, car, s'il y a n éléments dans la liste l, alors il y a n itérations dans la boucle for) :

Complexité/Coût de la Recherche de Minimum

La complexité/coût de l'algorithme de recherche de minimum est linéaire, càd en \(O(n)\):

\(C(n) = n\)

Recherche de Maximum ❤

def recherche_max(l:list):
    '''renvoie le maximum de la liste l'''
    maxi = l[0]           # (1)
    for el in l:
        if el > maxi:
            maxi = el
    return maxi
  1. On initialise le maximum avec la première valeur du tableau (surtout pas avec \(0\) ou «moins l'infini» !)

Utilisation 

>>> recherche_max([12, 8, 14, 15])
15
Complexité/Coût
On note \(n\) la taille des données en entrée : dans notre cas une bonne mesure de cette taille correspond à la taille de la liste n=len(l) (càd \(n\)=combien de nombres dans la liste?) Le coût/complexité \(C(n)\) de cet algorithme de recherche de maximum est le nombre d'opérations réalisées, ou bien de manière (ici) équivalente, le nombre d'itérations \(C(n)\) dans la boucle for de cet algorithme.
On a (clairement, idem que précédemment) :

Complexité/Coût de la Recherche de Maximum

La complexité/coût de l'algorithme de recherche de maximum est linéaire, càd en \(O(n)\):

\(C(n) = n\)

Algorithme de calcul de Moyenne⚓︎

Calcul de Moyenne (non coefficientée) ❤

def moyenne(l:list)->float:
    '''renvoie la moyenne (non coefficientée) de l'''
    somme = 0
    for el in l:
        somme += el
    return somme / len(l)

Utilisation 

>>> moyenne([12, 8, 14, 15])
12.25
Complexité/Coût
On note \(n\) la taille des données en entrée : dans notre cas une bonne mesure de cette taille correspond à la taille de la liste n=len(l) (càd \(n\)=combien de nombres dans la liste?) Le coût/complexité \(C(n)\) de cet algorithme de recherche de minimum est le nombre d'opérations réalisées, ou bien de manière (ici) équivalente, le nombre d'itérations \(C(n)\) dans la boucle for de cet algorithme.
On a (clairement, idem que précédement) :

Complexité/Coût de Calcul de la moyenne (non coefficientée)

La complexité/coût de l'algorithme de calcul de la moyenne est linéaire, càd en \(O(n)\):

\(C(n) = O(n)\)

Calcul de Moyenne coefficientée ❤

def moyenne_coeff(l:list, c:list)->float:
    '''renvoie la moyenne (non coefficientée) de l'''
    assert len(l)==len(c), "ERREUR : l et c doivent être de même longueur"
    num = 0
    denom = 0
    for i in range(len(l)):
        num += c[i]*l[i]
        denom += c[i]
    return num / denom

Utilisation 

>>> moyenne_coeff([12, 8, 14, 15], [2, 4, 1, 3])
11.5
Complexité/Coût
On note \(n\) la taille des données en entrée : dans notre cas une mesure possible de cette taille correspond à la taille de la liste n=len(l) (càd \(n\)=combien de nombres dans la liste l?). Le coût/complexité \(C(n)\) de cet algorithme de recherche de minimum est le nombre d'opérations réalisées, ou bien de manière (ici) équivalente, le nombre d'itérations \(C(n)\) dans la boucle for de cet algorithme.
On a (clairement, idem que précédemment) :

Complexité/Coût de Calcul de la moyenne coefficientée

La complexité/coût de l'algorithme de calcul de la moyenne coefficientée est linéaire, càd en \(O(n)\):

\(C(n) = O(n)\)

Remarque : Pour être plus justes, il aurait faullu également tenir compte de la taille de la liste c donnée en entrée, et considérer que la taille des données en entrée vaut len(l)+len(c)=n+n=2*n. On aurait alors pu dire que le nombre d'opérations de l'algorithme vaut alors 2*n également (\(n\) itérations de la boucle for, dans laquelle chaque itération réalise 2 opérations). On retrouve encore que la complexité/coût de l'algorithme de calcul de la moyenne coefficientée est linéaire, càd en \(O(n)\)

Algorithme de recherche d'Occurrence⚓︎

Recherche d'Occurrence ❤

def recherche_occurrence(el, l:list)->list:
    '''renvoie la liste (éventuellement vide)
    des indices de el dans l'''
    liste_indice = []
    for i in range(len(l)):
        if l[i] == el:
            liste_indice.append(i)
    return liste_indice

Utilisation

>>> recherche_occurrence(5, [12,5,8,14,3,5,15])
[1, 5]
>>> recherche_occurrence(2, [12,5,8,14,3,5,15])
[]
Complexité/Coût
On note \(n+1\) la taille des données en entrée : dans notre cas une bonne mesure de cette taille correspond à la taille de la liste n=len(l) auquel on ajoute \(1\) élément (càd \(n\)=combien de nombres dans la liste?) Le coût/complexité \(C(n+1)\) de cet algorithme de recherche de minimum est le nombre d'opérations réalisées, ou bien de manière (ici) équivalente, le nombre d'itérations \(C(n+1)\) dans la boucle for de cet algorithme.
On a \(C(n+1) = n\) donc

\[\begin{align} C(n) &= n-1 \\ C(n) &\approx n \end{align} \]

Complexité/Coût de Calcul de la moyenne (non coefficientée)

La complexité/coût de l'algorithme de calcul de la moyenne est linéaire, càd en \(O(n)\):

\(C(n) \approx n\)