C11 : Exercices

Exercice sur les tris

C11.E1 : Tri à bulle

Le tri à bulle consiste à parcourir un tableau, par exemple de gauche à droite, en comparant les éléments côte à côte et en les permutant s’ils ne sont pas dans le bon ordre.

Il faut ensuite recommencer.

On s’arrête dès que le tableau est trié, c'est à dire si aucune permutation n’a été faite au cours d’une passe.

C11.E2 : Fonction de fusion de deux listes triées

Trois algorithme de fusion de deux listes triées sont envisageables :

En fonction de la version que vous avez programmée dans l'activité C11.3, proposer le code des deux autres versions.

Exercices sur "diviser pour régner"

C11.E11 : Somme des nombres d'une liste

1) Proposer une fonction qui permet de calculer la somme des nombres d'une liste de nombre en vous appuyant sur un algorithme "diviser pour régner".

2) Le coût de cet algorithme est-il meilleur que celui de l'algorithme itératif ?

C11.E12 : Exponentiation rapide

On souhaite reprogrammer l'opérateur ** sous la forme d'une fonction (sans utiliser cet opérateur).

1) La première approche consiste à utiliser l'algorithme suivant :

def puissance_v1(x, n):
    p = 1
    for _ in range(n):
        p = p * x
    return p

Combien de multiplications cet algorithme effectue-t-il pour \(n = 100\) ?

2) Un méthode plus efficace consiste à considérer que :

2.a. Justifier succinctement que la méthode est du type "diviser pour régner".

2.b. Proposer une fonction récursive qui prend x et n en paramètres et renvoie \(x^n\).

2.c. Combien de multiplication cet algorithme effectue-t-il pour \(n = 100\) ?

3) Écrire le code d'un programme qui permet de visualiser sur un graphique le temps mis par chacun de ces deux algorithmes en fonction de \(n\).

Afficher la correction

1)

Pour \(n = 100\), l'algorithme effectue \(100\) multiplications.

2.a)

La méthode est du type "diviser pour régner" car on retrouve :

  • - Le découpage en sous-problèmes (diviser) : ici, d'un côté le cas où n est pair et de l'autre celui où n est impair ;
  • - La résolution du sous-problème (ici récursivement) jusqu'à ce qu'il soit suffisamment simple : ici le cas où n = 0 ;
  • - La combinaison des résultats.

2.b)

def puissance_rec(x, n):
    if n == 0:
        return 1
    elif n % 2 == 1:
        return x * puissance_rec(x, n-1)
    else:
        xn2 = puissance_rec(x, n//2)
        return xn2 * xn2

2.c)

Pour \(n = 100\), l'algorithme effectue 9 multiplications : successivement pour n égale 100, 50, 25, 24, 12, 6, 3, 2 et 1.

Pour s'en convaincre, on peut exécuter le code suivant :

nb_mult = 0

def puissance_rec(x, n):
    global nb_mult
    if n == 0:
        return 1
    elif n % 2 == 1:
        nb_mult += 1
        return x * puissance_rec(x, n-1)
    else:
        xn2 = puissance_rec(x, n//2)
        nb_mult += 1
        return xn2 * xn2

print("2**100 = " + str(puissance_rec(2, 100)))
print("Nombre de multiplications effectuées = " + str(nb_mult))

3)

from time import perf_counter
from random import randint
import matplotlib.pyplot as plt

# ===== Méthode diviser pour régner =====
def division(liste):
    return liste[:len(liste)//2], liste [len(liste)//2:]

def fusion(a, b):
    return a + b

def somme_rec(liste):
    if len(liste)==1:
        return liste[0]
    else:
        l1, l2 = division(liste)
        return fusion(somme_rec(l1),somme_rec(l2))

# ===== Méthode itérative =====
def somme(liste):
    s = 0
    for elt in liste:
        s = s + elt
    return s

# ===== Fonctions pour les tracés =====
def mesure_temps_iteratif(n):
    L = [randint(0,100) for _ in range(n)]
    nb_repetitions=100
    temps_final = float('inf')
    for _ in range(nb_repetitions):
        debut = perf_counter()
        # ----- Code à mesurer -----
        somme(L)
        # --------------------------
        temps = perf_counter() - debut
        if temps < temps_final:
            temps_final = temps
    return temps_final

def mesure_temps_diviser_regner(n):
    L = [randint(0,100) for _ in range(n)]
    nb_repetitions=100
    temps_final = float('inf')
    for _ in range(nb_repetitions):
        debut = perf_counter()
        # ----- Code à mesurer -----
        somme_rec(L)
        # --------------------------
        temps = perf_counter() - debut
        if temps < temps_final:
            temps_final = temps
    return temps_final

# ===== Programme principal =====
# Construction du tableau pour les abscisses
tab_n = [n for n in range(1, 1000, 50)]
# Construction des tableaux pour les ordonnées
tab_tps_iteratif = [mesure_temps_iteratif(n) for n in tab_n]
tab_tps_diviser_regner = [mesure_temps_diviser_regner(n) for n in tab_n]
# Tracé du graphique
plt.plot(tab_n, tab_tps_iteratif, 'r. ', label='itératif')
plt.plot(tab_n, tab_tps_diviser_regner,'b+ ', label='diviser pour régner')
plt.xlabel('taille des données')
plt.ylabel('temps en µs')
plt.grid(True)
plt.legend()
plt.show()

Le résultat donne :