Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Accélération d’algorithme
Article mis en ligne le 7 mars 2006
dernière modification le 25 novembre 2014

par Laurent Bloch

Auteurs : William Saurin, Laurent Bloch

Recherche du maximum d’ un ensemble de valeurs

Dans un tableau A on cherche à déterminer la plus grande valeur. Pour cela on peut décider de conserver l’indice de la valeur maximale dans un variable qu’on apellera max et parcourir le tableau, chaque fois que A[max] sera plus petit que la valeur courante du tableau on fera passer max à la valeur courante de i.

On passe par la ligne si A[i] > A[max] alors autant de fois qu’ il y a d’éléments du tableau - 1 ;

Recherche de segments maximaux O(n3)

Un tableau A contient des nombres positifs et négatifs. En fait ce sont les coefficients d’hydrophobicité des acides aminés consécutifs d’une protéine transmembranaire. En voici quatre exemples, pour vos essais :

Dans ce tableau A on cherche à determiner quels sont les positions i et j telles que la somme A[i] + A[i+1] + ... +A[j] est la plus grande possible. La séquence des acides aminés de rang i à j correspond probablement à une partie de la protéine qui est dans la membrane.

Allons y lentement.

On peut imaginer partir de chaque valeur possible de i et calculer toutes les sommes pour toutes les cases successives, chaque fois qu’on a une valeur plus élevée que la plus haute obtenue pour l’instant on met à jour des variables imax et jmax.

combien de fois faisons nous V ← v + A[k] ?

combien de fois faisons nous si V > Vmax alors ?

combien de fois faisons nous V ← 0 ?

Le programme O(n3)

Aller plus vite ? O(n2)

On peut aussi commencer par sommer les cases successives du tableau que l’on enregistrera dans un tableau annexe B de la sorte dans la case de rang i+1 de B on aura la somme de valeurs des cases A[0], A[1], A[2], ... jusqu’à A[i]. La valeur B[0] est donc nécessairement 0. Dans ce cas la valeur de B[j+1] - b[i] est la valeur de la somme des cases A[i] + a[i+1] + ... + a[j]. On voit qu’il est alors possible d’éliminer la boucle interne de l’algorithme Segments maximaux 1.

On obtient l’algorithme :

Le programme O(n2)

Aller plus vite ? O(n1)

Considérons le tableau B de la section précédente. Le segment maximal est celui dont les cases extrêmes sont i et j tel que pour lesquels B[j+1] - B[i] est maximal ! En quelque sorte si nous considérons le graphe de la fonction décrite par B, ce qui nous intéresse c’est le plus grand dénivelé entre une valeur de B[j+1] et B[i].

Si lorsque nous examinons successivement toutes les valeurs de B, et que au moment où nous examinons B[j+1] nous sachions quel est le imax tel que B[imax] est la plus petite valeur de B observée entre les cases 0 et j de B alors il est clair que B[j+1] -B[imax] est la valeur du segment de A dont les sommes des valeurs se terminant en A[j] est la plus élevée.

Décidons donc de créer un tableau C de même longueur que B et tel qu’en C[k] on trouve la position imax telle que B[imax] est la plus petite valeur de B entre les cases 0 et k. Dans ce cas on sait que B[j+1] -B[C[j]] est la valeur du segment maximal se terminant en A[j], il commence en C[j]. Le segment maximal de A est donc celui compris entre C[j] et j tel que B[j+1] -B[C[j]] est maximal. L’algorithme devient donc calculer B, calculer C, calculer D qui contient en j les valeurs de B[j+1] -B[C[j]], trouver la valeur la position de la valeur maximale de D, c’est la position de fin du segment maximal, à cette position en C on trouve la position de début du segment et en D a cette position la valeur du segment. L’algorithme s’écrit :

Le programme O(n1)

Exercice : a-t-on besoin de tous ces tableaux ?

Que fait :