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.
Nom de l'algo : Max
Données d'entrées : un tableau A
Résultat : le rang de plus grande valeur de A
max ← 0
pour i allant de 1 à longueur de A - 1 faire
si A[i] > A[max] alors
max ← i
finsi
fait
retourner maxOn 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 :
;; V1
#(38.0 -61.0 -33.0 44.0 -100.0 -81.0 -89.0 44.0 -5.0 34.0 -63.0 -98.0 -1.0 -99.0 21.0 97.0 84.0 83.0 46.0 -56.0 -26.0 99.0 -60.0 -96.0 -38.0 92.0 -86.0 -5.0 83.0 73.0 -4.0 99.0 92.0 -29.0 -89.0 99.0 -74.0 -96.0 -34.0 -100.0)
;; V2
#(-67.0 74.0 100.0 -99.0 -90.0 100.0 -5.0 -98.0 36.0 -79.0 67.0 32.0 -88.0 -91.0 -100.0 -79.0 -89.0 98.0 67.0 -22.0 47.0 -49.0 -96.0 -85.0 -92.0 88.0 16.0 63.0 61.0 86.0 -78.0 81.0 85.0 -81.0 36.0 -25.0 59.0 -95.0 81.0 -9.0 1.0)
;; AIE-1
#(29.0 -100.0 -28.0 51.0 69.0 -94.0 89.0 -72.0 -96.0 17.0 98.0 100.0 -31.0 2.0 88.0 85.0 -8.0 99.0 -37.0 -57.0 63.0 -87.0 33.0 -99.0 -96.0 59.0 75.0 90.0 -40.0 96.0 -76.0 -76.0 -100.0 90.0 11.0 67.0 -100.0 -46.0 -84.0 75.0 90.0 75.0 79.0 75.0 33.0)
;; AIE-2
#(-93.0 91.0 31.0 -99.0 -58.0 100.0 62.0 -79.0 10.0 -42.0 -94.0 63.0 -92.0 -56.0 57.0 -92.0 97.0 -49.0 40.0 -38.0 -57.0 -72.0 38.0 94.0 -33.0 100.0 41.0 -31.0 91.0 52.0 69.0 4.0 -15.0 92.0 -26.0 100.0 -99.0 69.0 87.0 -93.0 -98.0 99.0 97.0 15.0)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.
Nom de l'algo : Segments maximaux 1
données d'entrées: tableau A
résultats : le triplet imax, jmax, vmax contenant les indices de début et de fin du segment maximal ainsi que la valeur vmax du segment maximal.
imax ← 0
jmax ← 0
Vmax ← a[0]
pour i allant de 0 à longueur de A - 1 faire
pour j allant de i à taille de A -1 faire
V ← 0
pour k allant de i à j faire
V ← v + A[k]
fait
si V > Vmax alors
V ← Vmax
imax ← i
jmax ← j
finsi
fait
fait
retourner imax, jmax, vmaxcombien 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)
(module segmax1
(main segread))
(define (segread args)
(let* ((the-file (cadr args))
(the-vector (with-input-from-file the-file read)))
(let ((les-resultats (segmax1 the-vector)))
(print "imax = " (vector-ref les-resultats 0)
" jmax = " (vector-ref les-resultats 1)
" vmax = " (vector-ref les-resultats 2)
" longueur du tableau = "
(vector-ref les-resultats 3))
)))
(define (segmax1 A)
(let ((L (vector-length A))
(imax 0)
(jmax 0)
(vmax (vector-ref A 0)))
(do ((i 0 (+ 1 i)))
((= i L)
(vector imax jmax vmax L))
(do ((j 0 (+ 1 j)))
((= j L))
(let ((V 0))
(do ((k i (+ k 1)))
((> k j)
(if (> V vmax)
(begin
(set! vmax V)
(set! imax i)
(set! jmax j))))
(set! V (+ V (vector-ref A k)))
))))))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 :
Nom de l'algo : Segment maximaux 2
données d'entrées : tableau A
résultats : le triplet imax, jmax, vmax contenant les indices de début et de fin du segment maximal ainsi que la valeur vmax du segment maximal.
creer un tableau B de longueur longueur de A +1
B[0] ← 0
pour i allant de 0 à longueur de A - 1 faire
B[i+1] ← B[i] + A[i]
fait
imax ← 0
jmax ← 0
Vmax ← B[1]
pour i allant de 0 à longueur de A-1 faire
pour j allant de i à taille de A-1 faire
V ← B[j+1] - B[i]
si V > Vmax alors
Vmax ← V
imax ← i
jmax ← j
finsi
fait
fait
retourner imax, jmax, vmaxLe programme O(n2)
(module segmax2
(main segread))
(define (segread args)
(let* ((the-file (cadr args))
(the-vector (with-input-from-file the-file read)))
(let ((les-resultats (segmax2 the-vector)))
(print "imax = " (vector-ref les-resultats 0)
" jmax = " (vector-ref les-resultats 1)
" vmax = " (vector-ref les-resultats 2)
" longueur du tableau = "
(vector-ref les-resultats 3))
)))
(define (segmax2 A)
(let* ((L (vector-length A))
(B (make-vector
(+ 1 L) 0)))
(do ((i 0 (+ i 1)))
((= i L))
(vector-set! B (+ i 1)
(+ (vector-ref A i)
(vector-ref B i))))
(let ((imax 0)
(jmax 0)
(vmax (vector-ref B 1)))
(do ((i 0 (+ 1 i)))
((= i L)
(vector imax jmax vmax L))
(do ((j i (+ 1 j)))
((= j L))
(let ((V
(- (vector-ref B
(+ j 1))
(vector-ref B
i))))
(if (> V vmax)
(begin
(set! vmax V)
(set! imax i)
(set! jmax j)))))))
))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 :
Nom de l'algo: Segment maximaux 3
données d'entrées: tableau A
résultats : le triplet imax, jmax, vmax contenant les indices de début et de fin du segment maximal ainsi que la valeur vmax du segment maximal.
créer un tableau B de longueur longueur de A +1
créer un tableau C de longueur longueur de A +1
créer un tableau D de longueur longueur de A +1
B[0] ← 0
pour i allant de 0 à longueur de A - 1 faire
B[i+1] ← B[i] + A[i]
fait
C[0] ← 0
pour i allant de 1 à longueur de A - 1 faire
si B[C[i-1]] >= B[i]
alors C[i] = i
sinon C[i] = C[i-1]
finsi
fait
pour i allant de 0 à longueur de A - 1 faire
D[i] ← B[i+1] - B[C[i]]
fait
jmax ← Position(Max(D))
imax ← C[jmax]
Vmax ← D[jmax]
retourner imax, jmax, vmaxLe programme O(n1)
(module segmax3
(main segread))
(define (segread args)
(let* ((the-file (cadr args))
(the-vector (with-input-from-file the-file read)))
(let ((les-resultats (segmax3 the-vector)))
(print "imax = " (vector-ref les-resultats 0)
" jmax = " (vector-ref les-resultats 1)
" vmax = " (vector-ref les-resultats 2)
" longueur du tableau = "
(vector-ref les-resultats 3))
)))
(define (PosMaxTab A)
(let ((Lvec (vector-length A)))
(do ((i 0 (+ i 1))
(imax 0 (if (> (vector-ref A i)
(vector-ref A imax))
i imax)))
((= i Lvec)
imax))))
(define (segmax3 A)
(let* ((L (vector-length A))
(B (make-vector (+ 1 L) 0))
(C (make-vector (+ 1 L) 0))
(D (make-vector (+ 1 L) 0)))
(do ((i 0 (+ i 1)))
((= i L))
(vector-set! B (+ i 1)
(+ (vector-ref A i)
(vector-ref B i))))
(do ((i 1 (+ i 1)))
((= i L))
(vector-set!
C i
(if (>= (vector-ref
B
(vector-ref C (- i 1)))
(vector-ref B i))
i
(vector-ref C (- i 1)))))
(do ((i 0 (+ i 1)))
((= i L))
(vector-set!
D i
(- (vector-ref B (+ i 1))
(vector-ref B (vector-ref C i)))))
(let* ((jmax (PosMaxTab D))
(imax (vector-ref C jmax))
(Vmax (vector-ref D jmax)))
(vector imax jmax Vmax L)
)))Exercice : a-t-on besoin de tous ces tableaux ?
Que fait :
Nom de l'algo: mystere-1
entrée: A
sortie: imax, jmax, vmax
créer un tableau B de longueur (longueur de A) + 1
B[0] ← 0
pour i allant de 1 à longueur de A faire
B[i] ← A[i-1] + B[i-1]
si B[i] < 0 alors B[i] ← 0 finsi
si B[i-1] = 0 et B[i] != 0 alors idebut = i -1 finsi
si B[i] > vmax
alors Vmax ← b[i] , jmax ← i-1, imax ← idebut finsi
fait
retourner imax, jmax, vmax