Annale

L'épreuve écrite (sur feuille) de terminale peut comporter des exercices portant sur le programme de première.

C'est le cas de la partie A de l'exercice 5 de ce sujet de 2021 dont vous retrouverez l'énoncé ci-dessous et que vous traiterez.

Objectifs

Dans un tableau d'entiers, représenté par une liste python tab, on dira que le couple d'indices (i, j) avec $i < j$ forme une inversion lorsque $tab[i] > tab[j]$.

Exemples.

• Avec tab = [1, 5, 3, 7], le couple (1, 2) forme une inversion car $tab[1] > tab[2]$ (en effet tab[1] = 5 et tab[2] = 3).
• Avec tab = [1, 5, 3, 7], le couple (1, 3) ne forme pas une inversion car $tab[1] \leqslant tab[3]$ (en effet tab[1] = 5 et tab[3] = 7).
• Le tableau [1, 6, 2, 7, 3] présente trois inversions: les couples d'indices (1, 2), (1, 4), (3, 4).
• Le tableau [7, 6, 5, 3] présente six inversions, les couples: (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3).

Traitement d'exemples

• Expliquer pourquoi le couple (1, 3) est une inversion dans le tableau [4, 8, 3, 7].

Solution

On a 1 < 3 mais tab[1] > tab[3] (en effet tab[1] = 8 et tab[3] = 7).

• Justifier que le couple (2, 3) n'est pas une inversion du tableau précédent.

Solution

On a 2 < 3 et tab[2] < tab[3] (en effet tab[2] = 3 et tab[3] = 7).

Partie A: méthode itérative.

Le but de cette partie est d'écrire une fonction itérative nombre_inversion qui prend en paramètre un tableau d'entiers et renvoie le nombre d'inversions de ce tableau.

Pour cela, on commence par écrire une fonction f1 qui sera ensuite utilisée pour écrire la fonction nombre_inversion.

Une fonction intermédiaire

On définit la fonction f1 comme suit:

def f1(tab, i):
    """
    tab: liste d'entiers
    i: indice d'un élément de tab
    """
    nb_elements = len(tab)
    compteur = 0
    for j in range(i+1, nb_elements):
        if tab[j] < tab[i]:
            compteur += 1
    return compteur

Des appels

Indiquer ce que renvoie f1(tab, i) dans les cas suivants:

• Cas 1: tab = [1, 5, 3, 7] et i = 0.
• Cas 2: tab = [1, 5, 3, 7] et i = 1.
• Cas 3: tab = [1, 5, 2, 6, 4] et i = 1.

Cas 1

Le résultat est 0.

On a en effet tab[1] > tab[0], tab[2] > tab[0] et tab[3] > tab[0]. Le test tab[j] < tab[i] vaut donc toujours False et le compteur n'est jamais incrémenté.

Cas 2

Le résultat est 1.

On a en effet tab[2] < tab[1] (compteur est incrémenté) et tab[3] > tab[1] (compteur est inchangé).

Cas 3

Le résultat est 2.

On a en effet:

• tab[2] < tab[1] (compteur est incrémenté).
• tab[3] > tab[1] (compteur est inchangé).
• tab[4] < tab[1] (compteur est incrémenté).

Le rôle

Expliquer ce que permet de déterminer cette fonction.

Solution

Cette fonction compte un nombre d'inversions: elle compte le nombre d'inversions de la forme (i, j) où i est fixé (c'est le second paramètre de la fonction) et où j prend les valeurs strictement supérieures à i (à savoir les valeurs i+1, i+2, ..., len(tab)-1).

Remarque

Un autre code pour la fonction f1:

def f1(tab, i):
    """
    tab: liste d'entiers
    i: indice d'un élément de tab
    """    
    return len([1 for j in range(i+1, len(tab)) if tab[j] < tab[i]])

Nombre d'inversions

En utilisant la fonction f1, écrire une fonction nombre_inversion(tab) qui prend en paramètre un tableau tab d'entiers et renvoie le nombre d'inversions de ce tableau.

Exemples d'appels.

>>> nombre_inversion([1, 5, 7])
0
>>> nombre_inversion([1, 6, 2, 7, 3])
3
>>> nombre_inversion([7, 6, 5, 3])
6

Solution

def nombre_inversion(tab):
    compteur = 0
    for i in range(0, len(tab)-1):
        compteur += f1(tab,i)
    return compteur

Une autre solution

def somme(tab):
    """
    tab: liste d'entiers
    renvoie la somme des éléments de tab
    """
    s = 0
    for k in tab: s += k
    return s

def nombre_inversion(tab):
    return somme([f1(tab,i) for i in range(0, len(tab)-1)])

Complexité

Quel est l'ordre de grandeur de la complexité en temps de l'algorithme obtenu ?

Indication

Pour répondre à cette question: exprimer, en fonction de n, le nombre de tests if tab[j] < tab[i] effectué lors de l'appel de la fonction nombre_inversion sur un tableau de longueur n.

Voir le chapitre "Complexité" plus tard dans l'année pour aller plus loin.

Solution

L'appel f1(tab, i) effectue les tests if tab[j] < tab[i]: pour j prenant les valeurs i+1, i+2, ..., n-1, c'est à dire n-i-1 tests.

Un appel à nombre_inversion effectue des appels à f1 pour i prenant les valeurs 0, 1, 2, ..., n-2. Le nombre de tests if tab[j] < tab[i]: réalisés est donc: $S = (n-0-1) + (n-1-1) + (n-2-1) + (n-3-1) + \dots + (n - (n-2) -1)$, soit $S = (n-1) + (n-2) + (n-3) + ... + 1$.

Ce nombre $S$ est égal à $\frac{1}{2}n(n-1)$ (voir le chapitre "complexité" ou votre cours de mathématiques sur les suites arithmétiques).

Le nombre d'opérations élémentaires pour effectuer cette fonction est exprimé par un polynôme du second degré en n (où n est la taille de liste donnée en argument). C'est ce que l'on nomme une "complexité quadratique".

Partie B: méthode récursive.

Plusieurs questions de cette partie relève du programme de terminale. Ne traitez donc pas cette partie de l'exercice.