Sous liste de somme maximum

I) Présentation

1) Objectif

  Etant donnée une liste s non vide d'entiers relatifs , on veut calculer la somme somme_max(s) maximum que l'on puisse obtenir en ajoutant un nombre quelconque de termes consécutifs de s.

On peut donc définir somme_max(s) par: somme_max(s) = max { Σ k = i j s [ k ] / 0 i j < len ( s ) }

Par exemple, avec s =  [-1, 4, -1,  2 , -1, 3, -5, 3, 2], somme_max(s) = 4 - 1 + 2 - 1 + 3 = 7

2) Méthodes

On parcourt la liste, mais avec des idées différentes:

a) En regardant vers l'avant

  On parcourt la liste s et pour chaque élément s[i] on calcule toutes les sommes possibles de termes consécutifs commençant par s[i].

b) En regardant vers l'arrière

  Au lieu de parcourir la liste s et calculer toutes les sommes possibles de termes consécutifs commençant par un élément s[i] de la liste, on va parcourir la liste s en calculant la plus grande somme de termes consécutifs de la liste se terminant par s[i] (inclus).

  Pour un entier i ∈ {0,..., n - 1}, on note f(i) la plus grande somme de termes (consécutifs) de la liste s se terminant par s[i] inclus). On pose f(-1) = 0 .

  Soit i ∈ {0,..., n - 1} (avec n = len(s)).  On justifie facilement que si f(i - 1) > 0, alors f(i) = f(i - 1) + s[i] et que si f(i - 1) ≤ 0, alors f(i) = s[i] .

II) Algorithmes

  On propose pour commencer l'algorithme suivant, exploitant la première méthode: regarder vers l'avant

def somme_max_1(s):
    """ Somme maximum de termes consécutifs de s"""
    n = len(s)
    maxi = s[0]
    for i in range(n):
        for j in range(i, n):
            somme = 0
            for k in range(i, j + 1):
                somme = somme + s[k]
            if somme > maxi:
                maxi = somme                
    return maxi

  Le coût C 1 ( n ) de l'algorithme est ici le nombre d'affectations, opérations élémentaires et comparaisons, exprimé en fonction de n = len ( s ) .

Q1) Prouver que la complexité C 1 ( n ) de cet algorithme est C 1 ( n ) = O ( n 3 )

On améliore l'algorithme précédent. Le cœur de l'algorithme:

        for j in range(i, n):
            somme = 0
            for k in range(i, j + 1):
                somme = somme + s[k]
            if somme > maxi:
                maxi = somme

est très maladroit. On calcule beaucoup de fois les mêmes sommes.

Q2) Reprendre ce cœur d'algorithme et écrire une fonction somme_max_2(s) résolvant le problème avec une complexité   C 2 ( n ) = O ( n 2 ) .

Q3) Ecrire une fonction somme_max_3(s) résolvant le problème en exploitant la seconde méthode proposée. (Regarder vers l'arrière)

Q4) Prouver que alors que la complexité C 3 ( n ) est   C 3 ( n ) = O ( n ) .

On cherche à voir concrètement l'efficacité de l'une ou l'autre des versions en calculant le temps nécessaire pour obtenir le résultat par une des trois fonctions écrites sur une liste de test du type [ E ( 100 * sin ( i 2 ) ) / i { 0 , ... , n - 1 } ] avec E(x) = partie entière de x.

On donne la fonction duree(n) par:

from math import *
import time

def duree(f, n):
    """ Durée d'exécution de f(n)"""
    t = time.perf_counter()
    res = f([floor(100*sin(i*i)) for i in range(n)])
    t = time.perf_counter() - t
    print("f = {0} ; n = {1} ; s_max = {2} ; durée = {3:.4} s"
            .format(f.__name__, n, res, t))

Par exemple, duree(somme_max_2, 2000) peut renvoyer (la durée peut être différente):

f = somme_max_2 ; n = 2000 ; s_max = 1157 ; durée = 0.3023 s

Q5) Justifier les calculs de complexité des trois fonctions par des tests adéquats.

Q6) Donner un ordre de grandeur du plus grand entier Ni (avec i = 1, 2, 3) pour lequel duree(somme_max_i, Ni) s'effectue en moins de 3 secondes sur votre PC.

© 2014 - Eric Obermeyer      Powered by      Corrigé