Algorithmique et complexit de calcul

Avril 2008
Pr. Mohsine Eleuldj Dpartement Gnie Informatique Ecole Mohammadia dIngnieurs Universit Mohammed V Agdal eleuldj@[Link]
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 1

Complexit de calcul

Algorithme 1 Problme Algorithme 2 Algorithme 3 Indcidable (problme de larrt)

Classification :
Linaire Quadratique Polynomial

NP NP-complet

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

Algorithmique et complexit de calcul

Objectifs tude des techniques de conception et d'analyse des algorithmes. comparaison et classification des algorithmes. Ce nest pas un catalogue d'algorithmes pour la rsolution de problmes spcifiques. Plan I Prliminaires II Analyse de l'efficacit des algorithmes III Diviser pour rgner IV Algorithmes voraces V Programmation dynamique VI Transformation du domaine VII Algorithmes probabilistes VIII Prconditionnement
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 3

Chapitre I : Prliminaires
Contenu 1 Notion dalgorithme 2 Efficacit des algorithmes 3 Nature de lanalyse 4 Pourquoi des algorithmes efficaces 5 Calcul des nombres de Fibonacci

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

1 Notion dalgorithme
Origine : le mot "algorithme" est associ au clbre auteur Perce Abou Jaafar Mohammed Ibn Moussa Al Khawarizmi connu pour son livre "Al Jabr oua El Mokabala" crit l'an 825. Dfinition : un algorithme est une mthode systmatique pour rsoudre un problme donn. L'excution ne doit pas laisser la place l'interprtation, lintuition ni la crativit. Definition : lAlgorithmique est ltude des techniques de conception et danalyse des algorithmes Exemples : Multiplication des nombres entiers Division Calcul du PGCD Certaines recettes de cuisines
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 5

Exemple : multiplication des nombres

53 x 17 371 53 901 53 26 13 6 3 1 17 34 72 136 272 544 901

Analyse des ressources Mthode classique : tables de multiplications + addition Mthode russe : multiplication par 2 et division par 2 (dcalages droite et gauche dans une reprsentation en base 2) + addition
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 6

Reprsentation des algorithmes

Langue naturelle

Pseudo-code

Langage de programmation

Langue naturelle : ambigut Langage de programmation : complexit de lecture (dtails de programmation Pseudo-code : description des algorithmes

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

Algorithme de multiplication russe

fonction russe (A,B) tableau X,Y X[1] A, Y[1] B, i 1 { initialisation } tant que X[i] > 1 faire { former les 2 colonnes } X[i + 1] X[i] div 2 Y[i + 1] Y[i] * 2 i i+1 P 0 { addition des entres appropries } tant que i > 0 faire si (X[i] mod 2 = 1) alors P P + Y[i] i i-1 retourner P Exercice : Faire la trace pour l'exemplaire (17,53). Modifier cet algorithme pour avoir une seule boucle et en utilisant seulement des variables scalaires.
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 8

Autre algorithme de multiplication russe

fonction autre_russe (A,B) entier x,y x A, y B, P 0 tant que x 1 faire si (x mod 2 = 1) alors P x x div 2 y y*2 retourner P

{initialisation} P + y {ajouter la valeur approprie}

Exercice : Faire la trace pour l'exemplaire (35, 17).

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

Autre algorithme de multiplication

fonction pas_russe (A,B) tableau X,Y X[1] A, Y[1] B, i 1 { initialisation } tant que X[i] > 1 faire { former les 2 colonnes } X[i + 1] X[i] - 1 Y[i + 1] B i i+1 P 0 { additionner les entres appropries } tant que i > 0 faire si X[i] > 0 alors P P + Y[i] i i-1 retourner P Exercice : Faire la trace pour l'exemplaire (53,17). Ecrire l'algorithme classique de multiplication
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 10

Etapes de rsolution dun problme

1 Trouver diffrents algorithmes (selon mthodes de conception) 2 Analyser leur efficacit (en terme de temps, espace mmoire,...) 3 Choisir le meilleur algorithme (selon la taille de l'exemplaire, puissance du matriel, ordre,...)

Algorithme 1 Problme Algorithme 2 Algorithme 3

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 11

2 Efficacit des algorithmes

Dfinition : Un exemplaire x est lentre dun algorithme, |x| = taille de l'exemplaire x Exemples - Tri : |x| est le nombre d'entiers ordonner - Multiplication : |x| est le nombre de chiffres (ou bits) des facteurs Approches danalyse - Empirique : programmation + excution avec plusieurs exemplaires - Thorique : dterminer la quantit de ressources (temps, mmoire,...) en fonction de la taille des exemplaires Avantages de l'approche thorique - Indpendance de l'ordinateur et langage de programmation - Gain dans la programmation et l'excution des algorithmes inefficaces - Taille des exemplaires n'est pas une contrainte
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 12

3 Nature de lanalyse
Efficacit dun algorithme dpend - taille de lexemplaire - espace mmoire - Comparaison des algorithmes selon diffrentes analyses - meilleur cas (optimiste) - moyenne - pire cas (pessimiste)

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

13

Tri par insertion

Procdure insert (T[1..n]) pour i 2 jusqu' n faire x T[i] j i-1 tant que j > 0 et T[j] > x faire T[j + 1] T[j] j j-1 T[j + 1] x Exercice : Faire la trace pour T = [3,1,4,0,5], U = [0,3,4,6,9] et V = [9,6,4,3,0]

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

14

Trace de insert(T)
i 2 3 4 x 1 4 0 j 1 0 2 3 2 1 0 5 5 4 j > 0 et T[j] > x oui non non oui oui oui non non 13045 10345 01345 01345
15

T 31405 13405

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

Trace de insert(U) et insert(V)

i 2 3 4 5 x 3 4 6 9 j 1 2 3 4 3 4 U 03469 i 2 x 6 j 1 0 2 1 0 4 3 3 2 1 0 5 0 4 3 2 1
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

V 96430

69 430

64930 46930

46390 43690 34690

34609 34069 30469 03469

16

Tri par slection

Procdure select (T[1..n]) pour i 1 jusqu' n-1 faire minj i, minx T[i] pour j i + 1 jusqu' n faire si T[j] < minx alors minj j minx T[j] T[minj] T[i] T[i] minx Exercice : Faire la trace pour T = [3,1,4,0,5], U = [0,3,4,6,9] et V = [9,6,4,3,0]
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 17

Trace de select(T)
i 1 j 2 3 4 5 2 3 4 5 3 4 5 4 5 minj 1 2 2 4 4 2 2 2 2 3 4 4 4 4 minx 3 1 1 0 0 1 1 1 1 4 3 3 4 4 01345
18

T 31405

01435

01435

01345

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

Trace de select(U) et select(V)

i 1 j 2 3 4 5 2 3 4 5 3 4 5 4 5 minj 1 1 1 1 1 2 2 2 2 3 3 3 4 4 minx 0 0 0 0 0 1 3 3 3 4 4 4 6 6 03469 03469 4 03469 3 03469 2 U 03469 i 1 j 2 3 4 5 3 4 5 4 5 5 minj 1 2 3 4 4 2 3 4 4 3 3 3 4 4 minx 9 6 4 3 0 6 4 3 3 4 4 4 6 6 96430
19

V 96430

06439

03469

96430

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

Analyse de insert et select

Trace U : meilleur cas pour insert V : pire des cas pour insert V : meilleur cas pour select U : pire des cas pour select Conclusion analyse au pire cas de insert et select nous allons voir que insert et select sont de l'ordre de n2, o n = |x|

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

20

4 Pourquoi des algorithmes efficaces ?

Supposition A : un algorithme M : une machine A : un algorithme plus efficace que A M : une machine plus puissante que M Question : A sur M ou A sur M ? Autrement si n : taille de lexemplaire t(n) : temps d'excution de A sur M t'(n) : temps d'excution de A sur M' t"(n) : temps d'excution de A sur M Question : t(n) < t(n) ou t(n) < t(n) ?
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 21

Application numrique
t(n) = 10-4 x 2n s t'(n) = t(n) x 10-2 = 10-6 x 2n s t"(n) = 10-2 x n3 s (M 100 plus rapide que M) (A plus efficace que A)
temps de calcul(s) 10 10 10 10 10 10
6 5 4 3 2

t(n) t'(n)

n 10 20 30 38 45 200 1500

t(n) 1/10 s 2 mn 10 jours 1 anne -

t'(n) 2 ms 1s 3 heures 4 mois 1 anne -

t"(n) 10 s 1mn 5 mn 10 mn 20 mn 1 jour 1 anne

1 jour t"(n) 1 heure

1 minute

Taille de l'exemplaire
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 22

Calcul des nombres de Fibonacci (1/3)

Dfinition f0 = 0, f1 = 1 fn = fn-1 + fn-2 pour n 2 De Moivre fn = 1/5 [ n - (-)-n ] o = (1 + 5)/2 le nombre d'or Cette formule n'est pas pratique pour calculer la valeur exacte de fn

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

23

Calcul des nombres de Fibonacci (1/3)

fonction fib1(n) si n < 2 alors retourner n sinon retourner fib1(n-1) + fib1(n-2) fonction fib2(n) i 1, j pour k

0 1 jusqu' n faire j i+j i j-i retourner j

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

24

Calcul des nombres de Fibonacci (3/3)

fonction fib3(n) i 1, j 0, k 0, h 1 tant que n > 0 faire si n est impair alors t jh j ih + jk + t i ik + t t h2 h 2kh + t k k2 + t n n div 2 retourner j Exercice : Faire la trace de fib1, fib2 et fib3 la trace pour n = 5
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 25

Excution de fib1, fib2 et fib3

102 3/2 ms 1/2 ms 104 150 ms 1 ms 106 15 s 3/2 ms 108 25 mn 2 ms

n fib1 fib2 fib3

10 8 ms 1/6 ms 1/3 ms

20 1s 1/3 ms 2/5 ms

30 2 mn 1/2 m 1/2 ms

50 21 j 3/4 ms 1/2 ms

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

26

Chapitre 2 : Analyse de lefficacit des algorithmes

Contenu 1 Notations asymptotiques 2 Analyse des algorithmes itratifs 3 Rsolution dquations de rcurrences 4 Analyse des algorithmes rcursifs

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

27

1 Notations asymptotiques
Remarque : L'analyse thorique de l'efficacit d'un algorithme se fait une constante prs pour ne pas tenir compte de : - langage de programmation - compilateur et systme d'exploitation - puissance de lordinateur Notation "l'ordre de" Soit f : N ---> R* O(f(n)) = {t : N R* / ( c R+) ( n0 N) ( n n0) [t(n) c f(n)]} Dfinitions O(f(n)) est appel l'ordre de f(n) t(n) O(f(n)) t(n) est dans l'ordre de f(n) t(n) : temps d'excution d'un algorithme algorithme est de l'ordre de f(n)
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 28

t(n) O(f(n))

temps

c f(n) t(n)

n0

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

29

Exercices
a) Quel est lordre de lalgorithme qui prend un temps born suprieurement par : t(n) = 3 s - 18n ms + 27n2 s b) Prouver que : f(n) O(g(n)) et g(n) O(h(x)) f(n) O(h(n)) c) Dduire que g(n) O(h(n)) O(g(n)) O(h(n)) d) Soient f, g : N R+, montrer que : O(f(n) + g(n)) = O(max(f(n) , g(n))) e) Soient f et g: N R+, prouver que : limn f(n) / g(n) = c R+ O(f(n)) = O(g(n)) limn f(n) / g(n) = 0 O(f(n)) O(g(n)) f) Prouver que : log n O(n) et n O(log n) g) Soit x R / 0 < x < 1. Utiliser et = pour mettre en rang les ordres des fonctions suivantes: n log n, n8, n1+x, (1 + x)n, (n2 + 8n + log3n)4 et n2/log n
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 30

Rponse (1/3)
Exemple 1 : Soit un algorithme qui prend un temps born suprieurement par : t(n) = 3 s - 18n ms + 27n2 s. Trouvons une fonction f aussi simple que possible tel que cet algorithme prenne un temps dans l'ordre de f(n). Prenons c = 27 x 10-6 et n0 = 500/3 Soit n > n0 _ n > 500/3 _ 18n > 3000 _ 18n x 10-3 > 3 _ 3 - 18n x 10-3 < 0 _ 3 - 18n x 10-3 + 27n2 x 10-6 _ 27n2 x 10-6 = cn2.
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 31

Rponse (2/3)
Exemple 2 : a) Prouver que : f(n) O(g(n)) et g(n) O(h(x)) _ f(n) O(h(n)) b) Dduire que g(n) O(h(n)) _ O(g(n)) C O(h(n)) Preuve : f(n) O(g(n)) _ ($ c' R+) ($ n' N) (" n > n') (f(n) _ c'g(n)) g(n) O(h(x)) _ ($ c" R+) ($ n" N) (" n > n") (g(n) _ c"h(n)) Soit c = c'c" et n0 = sup(n',n") alors (" n > n0) f(n) _ c'g(n) _ c'c"h(n) donc f(n) O(h(n)). Soit f(n) O(g(n)) d'aprs (a) f(n) O(h(n)) donc f(n) O(h(n)). Exemple 3 : Soient f, g : N --> R+, montrer que : O(f(n) + g(n)) = O(max(f(n) , g(n))).
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 32

Rponse (3/3)
Applications : n3+ 3n2+ n + 8 O(n3 + (3n2 + n + 8)) = O(max(n3 , 3n2 + n + 8)) = O(n3). Il faut s'assurer que f(n) et g(n) soient positives car sinon on trouvera la contradiction suivante : O(n2) = O(n3 + (n2 - n3)) = O(max(n3 , n2 - n3))) = O(n3). Montrer que O(n2) _ O(n3). Exercice 1: Soient f et g: N ---> R+. Prouver que : limn-->_ f(n) / g(n) = l R+ _ O(f(n)) = O(g(n)) limn-->_ f(n) / g(n) = 0 _ O(f(n)) C O(g(n)) Exercice 2 : Prouver que log n O( _n) et _n O(log n) Exercice 3 : Soit x R / 0 < x <1. Utiliser C (inclusion) et = pour mettre en rang les ordres des fonctions suivantes: n log n, n8, n1+x, (1 + x)n, (n2 + 8n + log3n)4 et n2/log n.
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 33

Autres notations asymptotiques

Remarque : la notion d'ordre est l'estimation d'une limite suprieure du temps d'excution d'un algorithme sur un exemplaire de taille donne. Nous allons estimer une limite infrieure. Omega de f(n) (f(n)) = {t : N R* / ( c R+) ( n0 N) ( n n0) [t(n) c f(n)]} Exercice : Soient f, g : N R*, montrer que : f(n) O(g(n)) g(n) (f(n)) Ordre exact de f(n) (f(n)) = O(f(n)) (f(n))

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

34

t(n) (f(n)) = O(f(n)) (f(n))

temps

c1 f(n) t(n) c2 f(n)

n0

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

35

2 Analyse des algorithmes itratifs

Soit t(n) : temps d'excution de l'algorithme pour un exemplaire de taille n Algorithmes analyss Calcul de Fibbonacci Tri par selection Tri par insersion Calcul du PGCD

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

36

Analyse de fib2
fonction fib2(n) i 1, j 0 pour k 1 jusqu' n faire ji+j b ij-i retourner j
a

c d

t(n) = a + c + d = a + (1 k n b) + d = a + bn + d = a + bn o a=a+d t(n) O(n)

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 37

Analyse de fib3
fonction fib3(n) i 1, ... tant que n > 0 faire ... n n div 2 retourner j
a

c d

t(n) = a + c + d = a + bk + d

o k est le nombre d'itrations k = nombre de bits dans la reprsentation binaire de n k = log2 n + 1 t(n) O(log n)

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

38

Analyse de select
Procdure select (T[1...n]) pour i 1 jusqu' n-1 faire minj i, minx T[i] pour j i+1 jusqu' n faire si T[j] < minx alors minj j b minx T[j] T[minj] T[i] T[i] minx

c e d

t(n) = 1 i n-1 [ a + i+1 j n (b) + d ] = (a + d + bn)(n - 1) - bn(n-1)/2 t(n) O(n2)

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 39

Analyse de l'algorithme d'Euclide

calcul du PGCD de deux nombres fonction Euclide(m,n) tant que m > 0 faire t <-- n mod m n <-- m m <-- t retourner n Montrons tout d'abord que : " n, m / n _ m _ n mod m < n/2 Cas 1 : m > n/2 _ 1 _ n/m < 2 _ [n/m] = 1_ n mod m = n - m _ n - n/2 = n/2 Cas 2 : m _ n/2 _ n mod m < m Soit k le nombre d'itrations de la boucle pour l'exemplaire (m,n). Soient mi et ni les valeurs de m et n aprs la ime itration. On dduit que mk = 0 et le systme suivant : ni = mi-1 mi = ni-1 mod mi-1 n0 = n et m0 = m On peut vrifier que ni > mi pour i _ 1. mi = ni-1 mod mi-1 < ni-1/2 = mi-2/2 Supposons que k est impair. Soit d tel que k = 2d + 1 alors : mk-1 < mk-3/2 < mk-5/22 < ... < m0/2d Or mk-1 _ 1 _ m0/2d _ 1 _ d log m > k 2log m+1 le cas o k est pair est trait de la mme t(n) O(log m).
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 40

Analyse de fib1
fonction fib1(n) si n < 2 alors retourner n sinon retourner fib1(n-1) + fib1(n-2)

t(n) est la solution du systme de rcurrence : t(0) = t(1) = a t(n) = t(n-1) + t(n-2)

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

41

3 Rsolution de rcurrences rcurrence homogne

a0tn + a1tn-1 + .. + aktn-k = 0 (1)

cherchons une solution de la forme tn = xn (quation caractristique) a0xn + a1xn-1 + .. + akxn-k = 0 (2) cherchons une solution non nulle (2) devient : a0xk + a1xk-1 + .. + ak = 0 supposons que les k racines : r1, r2, ..., rk (relles ou complexes) sont distinctes alors : tn = 1 i k ci(ri)n o ci (1 i k) constantes dtermines par les conditions initiales
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 42

Calcul du nombre de Fibonacci

f0 = 0 et f1 = 1 fn = fn-1 + fn-2 (1) (2)

Posons fn = xn, alors (2) devient : xn = xn-1 + xn-2 x2 - x - 1 = 0 = 1 + 4 = 5 r1 = (1- 5)/2 et r2 = (1+ 5)/2 fn = c1 r1n + c2 r2n En utilisant les conditions initiales (1) on trouve : c1 + c2 = 0 c1r1 + c2r2 = 0 c1 = -1/5 et c2 = 1/5 fn = 1/5 [-((1- 5)/2)n + ((1+5)/2)n] (Mthode de Moivre)
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 43

Analyse de fib1
t(0) = t(1) = a t(n) = t(n - 1) + (n - 2) (1) (2)

D'aprs le calcul prcdent on dduit que : t(n) = c1 r1n + c2 r2n o r1 = (1 - 5)/2 et r2 = (1 + 5)/2 En utilisant les conditions initiales (1), on trouve le systme : c1 + c2 = 0 c1r1 + c2r2 = 0 c1 = -a (1 + 5)/25 et c2 = a (1 + 35)/25 t(n) O(c2n) o |c2| > 1 algorithme exponentiel
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 44

3 Rsolution de rcurrences rcurrences non homognes

Illustrons ce type de rcurrence l'aide de l'exemple suivant o lon se ramne une rcurrence homogne tn - 2tn-1 = 3n (1) En multipliant (1) par 3 et en la considrant pour n+1 on trouve: (2) 3tn - 6tn-1 = 3n+1 tn+1 - 2tn = 3n+1 (3) En faisant la diffrence de (2) et (3), on trouve : tn+1 - 5tn + 6n-1 = 0 L'quation caractristique de cette quation est : x2 - 5x + 6 = 0 (x - 2) (x - 3) = 0 tn = c12n + c23n En utilisant (1), on trouve que tn = -c12n + 3n+1
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 45

3 Rsolution de rcurrences rcurrences non homognes

Illustrons cette technique l'aide de l'exemple suivant o nous faisons une transformation de variable : T(n) = 4T(n/2) + n, n > 1 avec n = 2k (1) Posons tk = T(2k). L'quation (1) devient : tk = 4tk-1 + 2k En multipliant par 2 et en considrant l'quation pour n+1, on trouve : 2tk = 8tk-1 + 2k+1 (2) (3) tk+1 = 4tk + 2k+1 (2) (3) donne : tk+1 - 2tk = 4tk - 8tk-1 tk+1 - 6tk + 8tk-1 = 0 L'quation caractristique de cette quation est : x2 - 6x + 8 = 0 (x - 2) (x - 4) = 0 _ donc tk = c12k + c24k donc T(n) = c1n + c2n2 En utilisant (1) on trouve que c1= -1 et par consquent : T(n) = -n + c2n2
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 46

Tours de Hano
Problme Soint trois aiguilles (1, 2 et 3) et m disques, tous de taille diffrente. Au dpart tous les disques sont placs du plus grand au plus petit dans laiguille 1. Comment dplacer les disques laiguille 2 sans jamais mettre de disque pardessus un disque plus petit dans les aiguilles ?

Exercice 1 Comment allez-vous faire pour dplacer 3 disques ? 2 Dcrire un algorithme de la solution. 3 Faire la trace pour m = 3. 4 Dterminer le nombre de dplacements en fonction de m. 5 Dduire lefficacit de lalgorithme. 6 Estimer le temps si m = 64 et si un dplacement prend 1 seconde. 7 Dmontrer loptimalit de lalgorithme.
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 47

Trace pour m = 3

3
48

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

Tours de Hano

procdure Hano (m,i,j) si m > 0 alors Hano (m-1,i,6-i-j) crire (i,"-->",j) Hano (m-1,6-i-j,j) Soit t(m) le temps dexcution t(1) = 1 t(m) = 2 t(m-1) + 1
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 49

Tours de Hano
Soit t(m) : temps d'excution de l'algorithme sur un exemplaire de taille m. t(1) = 1 t(m) = 2t(m-1) + 1 Calculons t(m) t(m)

= 2[ 2 t(m-1) + 1 ] + 1 = 22 t(m-2) + 2 + 1 = 22[ 2 t(m-3) + 1 ] + 2 + 1 = 23 t(m-3) + 22 + 2 + 1 = .......... = 2k t(m-k) + 2k-1 + ... + 2 + 1 = .......... = 2m-1 t(1) + 2m-2 + ... + 2 + 1 = 2m-1 + 2m-2 + ... + 21 + 20 = (2m - 1) / (2 - 1) = 2m - 1 donc t(m) O(2m). Exercice : Trouver une version non rcursive de la procdure Hano. Trouver l'ordre de l'algorithme.
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 50

Hanoi(3,1,2) Hanoi(2,1,3) Hanoi(1,1,2) Hanoi(0,1,3) 1 2 Hanoi(0,3,2) 1 3 Hanoi(1,2,3) Hanoi(0,2,1) 2 3 Hanoi(0,1,3) 1 2 Hanoi(2,3,2) Hanoi(1,3,1) Hanoi(0,3,2) 3 1 Hanoi(0,2,1) 3 2 Hanoi(1,1,2) Hanoi(0,1,3) 1 2 Hanoianoi(0,3,2)
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

Trace laide dappels rcursif

51

Trace laide dun arbre

H(3,1,2)

H(2,1,3)

1 2

H(2,3,2)

H(1,1,2)

1 3

H(1,3,1)

H(1,3,1)

3 2

H(1,1,2)

H(0,1,3) 1 2 H(0,3,2)

H(0,2,1) 2 3 H(0,1,3)

H(0,3,2) 3 1 H(0,2,1)

H(0,1,3) 1 2 H(0,3,1)

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

52

Chapitre 3 : Diviser-pour-rgner
diviser-pour-regner (Divide and conquer) est une technique de conception d'algorithme compose de trois tapes : - Dcomposition de l'exemplaire en sous-exemplaires plus petits, - Rsolution des sous-exemplaires et - Combinaison des sous-solutions. Plan 1 Fouille dichotomique 2 Multiplication des grands nombres 3 Multiplication matricielle 4 Exponentiation discrte

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

53

Schma des algorithmes DPR

fonction DPR(x) si x est suffisamment petit alors retourner ADHOC(x) dcomposer x en sous-exemplaires x1, x2, ..., xk pour i 1 jusqu' k faire yi <-- DPR(xi) combiner les yi pour obtenir une solution y retourner y

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

54

Rsolution des rcurrences DPR

Thorme : Soient a, b, c 0 et n = ck. La solution de la rcurrence b aT(n/c) + bn pour n = 1 pour n > 1

T(n) = est :

O(n) T(n) O(n log n) O(nlog a)

si a < c si a = c si a > c, o le logarithme en base c

T(n) : temps d'excution d'un algorithme DPR sur lexemplaire n

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 55

Fouille dichotomique
Problme : localisation de la valeur x dans un tableau T[1..n] tri (dictionnaire ou annuaire tlphonique) fonction squentielle (T[1..n],x) pour i 1 jusqu' n faire si T[i] > x alors retourner i-1 retourner n fonction dichotomique(T[i..j],x) si i = j alors retourner i k (i+j+1) div 2 si x < T[k] alors retourner dichotomique(T[i..k-1],x) sinon retourner dichotomique(T[k..j],x) Exercice : Montrer que t(n) O(log n)
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 56

Arithmtique des grands entiers

Utilisation : calcul de trs grande prcision. En 1986, est calcul avec 30 millions de chiffres. Ce calcul a ncessit 30 heures de calcul sur un ordinateur Cray-2. Problme : calcul de u*v avec u et v composs de n=2k chiffres Solution : Algorithme de multiplication classique O(n2) Algorithme de multiplication DPR ?

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

57

Multiplication DPR (1/2)

n/2 x

n/2 z

u = 10sw + x v = 10sy + z

o 0 x, z < 10s et s = n/2

u*v = 102s wy + 10s(wz + yx) + xz

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

58

Multiplication DPR (2/2)

fonction multA(u,v: grands-entiers) : grand-entier n max(u,v) si n est petit alors multiplier u et v par l'algorithme classique retourner le rsultat sinon s n div 2 w u div 10s, x u mod 10s y v div 10s, z v mod 10s retourner multA(w,y) 102s + (multA(w,z) + multA(y,x)) 10s + multA(x,z). Exercice : Montrer que t(n) O(n2)
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 59

Amlioration de la multiplication DPR (1/2)

u = 10sw + x v = 10sy + z o 0 x, z < 10s et s = n/2

Soient r, p et q tels que : r = (w + x)(y + z) = wy + wz + xy + xz p = wy q = xz u * v = 102s wy + 10s(wz + yx) + xz = 102sp + 10s (r - p - q) + q

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

60

Amlioration de la multiplication DPR (2/2)

fonction multB(u,v: grands-entiers) : grand-entier n max(u,v) si n est petit alors multiplier u et v par l'algorithme classique retourner le rsultat sinon s n div 2 w u div 10s, x u mod 10s y v div 10s, z v mod 10s r multB(w+x , y+z) p multB(w,y) q multB(x,z) retourner 102sp + 10s(r-p-q) + q Exercice : t(n) O(n1,59)
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 61

Multiplication matricielle DPR

Soient A, B deux matrices carres d'ordre n. C = AB = (cij) 1 i, j n avec cij = 1kn aikbkj Algorithme classique de multiplication de matrices appartient O(n3) Algorithme DPR (Strassen) Soient A = a11 a12et B =b11 b12 a21 a22 b21 b22 Soient m1, m2 m3, m4, m5, m6 m7 tels que : m1 = (a21 + a22 - a11)(b22 - b12 + b11) m2 = a11b11 m3 = a12b21 m4 = (a11 - a21)(b22 - b12) m5 = (a21 + a22)(b12 - b11) m6 = (a12 - a21 + a11 - a22)b22 m7 = a22(b11 + b22 - b12 - b21) Exercice : Montrer t(n) O(n2,7)
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 62

Protocole de cryptage (1976)

Fouad Ali
A / A alatoire A<p a = gA mod p x = bA mod p

p grand premier g / 2 g p-1

Bahia
B / B alatoire B<p b = gB mod p y = aB mod p

Ali et Bahia partagent linformation x = y sans que Fouad puisse la dtecter

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 63

Exponentiation discrte (1/3)

fonction expod1(g,A,p) a 1 pour i 1 jusqu' A faire a retourner a mod p

ag

Remarque : xy mod p = ((x mod p) (y mod p)) mod p fonction expod2(g,A,p) a 1 pour i 1 jusqu' A faire a retourner a

a g mod p

Exercice : Analyser et comparer le temps d'excution de expod1 et expod2 en fonction de A et p. Pour simplifier supposer que g=p/2.
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 64

Exponentiation discrte (2/3)

Exemple : calcul de x23 x23 = ((((x x)x))x) x23 = (((x2)2x)2x)2x 22 multiplications 7 multiplications fonction expoditer(x,n) a x, b 1 tant que n > 0 faire si n est impair alors b ab a a2 n n div 2 retourner b
65

fonction expodrec(x,n) si n = 0 alors retourner 1 si n est impair alors a expodrec(x,n-1) retourner a x sinon a expodrec(x,n/2) retourner a2
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

Exponentiation discrte (3/3)

fonction expod4(g,A,p) a g, b 1 tant que A > 0 faire si A est impair alors b a b mod p a a2 mod p A A div 2 retourner b

fonction expod3(g,A,p) si A = 0 alors retourner 1 si A est impair alors a expod3(g,A-1,p) retourner a g mod p sinon a expod3(g,A/2,p) retourner a2 mod p

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

66

Exercice
Soit la matrice a) Montrer que

F= Fn =

1 [0 11 ]

fn-1 fn fn fn+1

o fn est le nime nombre de Fibonacci. b) Dduire un algorithme de type diviser-pour-rgner pour le calcul de Fn. c) comparer cet algorithme avec fib3 en prenant comme matrices intermdiaires : . i j k h A = j i+j et B = h h+k

]
67

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

Retour lalgorithme fib3

fonction expod4(F,n) A F, B I tant que n > 0 faire si n est impair alors B AB A A2 n n div 2 retourner B fonction expod5(n) k 0, h 1, i 1, j 0 tant que n > 0 faire si n est impair alors t hj j hi + kj + t i ki + t t h2 h 2hk + t k k2 + t n n div 2 retourner j
68

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

Chapitre 4 : Algorithmes voraces

Gnralement assez simples rapides rsolution des problmes d'optimisation solutions approximatives (heuristique) Contenu Schma gnral Remise de monnaie Plus courts chemins Remise de monnaie Coloration dun graphe Feux de signalisation
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 69

Optimisation de la slection avec contrainte

20 Kg 15 Kg

10 Kg

Capacit = 40 Kg 8 Kg

Solution vorace = 20 + 15 = 35 < 40

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 70

Schma des algorithmes voraces

fonction vorace (C : ensemble) : ensemble {C est l'ensemble de tous les candidats} S {ensemble solution} tant que solution (S) et C faire x l'lment de C qui maximise slect(x) C C - {x} si ralisable (S {x}) alors S S {x} si solution (S) alors retourner S sinon retourner pas de solution

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

71

Exemple 1 : Remise de monnaie

Problme : remettre la monnaie en donnant le moins de pices possible. Solution : C : ensemble fini de pices 1, 5, 10, 20, 50 et 100 DH Solution(S) : total des pices choisies correspond au montant rendre Ensemble ralisable : total des pices n'excde pas la somme rendre fonction de slection : la plus grande pice qui reste dans C Fonction objective : nombre de pices utilises dans la solution

Exercice : Dcrire un algorithme vorace. Montrer quil fournit toujours une solution optimale lorsqu'elle existe

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

72

Exemple 1 : Algorithme vorace

fonction Remise_Monnaie (Montant) : tableau C {1,5,10,20,50,100} S0 tant que (Montant > 0) et (C ) faire x max{y/ y C} C C - {x} NP Montant div x {Nombre de pices de type x} S[x] NP Montant Montant - NP*x si (Montant = 0) alors retourner S sinon retourner pas de solution Exercice : Montrer lOptimalit (ide (Ci 2 Ci+1))
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 73

Exemple 1 : qualit de la solution

Soit C = C {12} = {1, 5, 10, 12, 20, 50, 100} Montant = 16 =12 + 1 + 1 + 1 + 1 (5 pices) = 10 + 5 + 1 (3 pices) solution non optimale est la solution optimale

Soit C" = C - {1} = {5, 10, 12, 20, 50, 100} Montant = 15 = 12 + ??? = 10 + 5 pas de solution une solution existe

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

74

Solution dun algorithme vorace

Solution optimale

Algorithme vorace

Solution approximative non optimale Pas de solution alors quelle existe

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

75

Exemple 2 : Plus courts chemins

Soit G = (N,A) un graphe orient o N = {1,2,..,n} ensemble des nuds et A est l'ensemble d'arcs. A chaque arc est associ une longueur non ngative. Essayons de dterminer la longueur du plus court chemin de 1 vers les autres sommets. L : matrice d'ordre n tel que L[i,j] 0 si l'arc (i,j) existe et L[i,j] = s'il n'existe pas.

fonction Dijkstra(L[1..n,1..n]) : tableau [2..n] C {2,3,..,n} pour i 2 jusqu' n faire D[i] L[1,i] rpter n-2 fois v l'lment de C qui minimise D[v] C C - {v} pour chaque lment w de C faire D[w] min (D[w] , D[v] + L[v,w]) retourner D
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 76

Exemple 2 : Trace de lalgorithme

1 10 5 10 4 100 50 30

2 5 3

20 50

tape 2 2 3

v 5 4 3

C D {2,3,4,5} [50,30,100,10] {2,3,4} [50,30,20,10] {2,3} [40,30,20,10] {2} [35,30,20,10]

Exercice : Dterminer lordre de lalgorithme de Dijkstra. Modifier le afin de trouver le chemin le plus court entre tous les couples de sommets.
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 77

Exemple 3 : Minimisation de l'attente

Soient un serveur, n clients et ti : temps de service requis par le client i = 1,2,..,n minimiser : T = S1 i n (temps pass dans le systme par le client i) Exemple : t1 = 4, t2 = 7 , t3 = 3. ordre 123 132 213 231 312 321 T 4 + (4 + 7) + (4 + 7 +3) = 29 4 + (4 + 3) + (4 + 3 + 7) = 25 7 + (7 + 4) + (7 + 4 + 3) = 32 7 + (7 + 3) + (7 + 3 + 4) = 33 3 + (3 + 4) + (3 + 4 + 7) = 24 ordre optimal 3 + (3 + 7) + (3 + 7 + 4) = 27

Exercice : Montrer que lalgorithme exhaustif O(n!). Dcrire l'algorithme vorace et analyser son efficacit. Dmontrer que sa solution est optimale.
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 78

Exemple 3 : Algorithme vorace

fonction Ordonnancement (n,t) : tableau C {1,2,3,,n} pour i=1 n faire j min{ti/ i C} C C - {j} S[x] j retourner S Exercice : Quel est lordre de lalgorithme ?

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

79

Exemple 3 : Optimalit de lalgorithme (1/2)

Soit I = (i1,i2,..,in) une permutation quelconque dans {1,2,..,n}. Soit T(I) le temps total pass dans le systme pour les clients i1,i2,..,in. T(I) = ti1 + (ti1 + ti2) + ... + (ti1 + ti2 + .. tin) = nti1 + (n-1)ti2 + ... + tin = S1kn (n - k + 1)tik Supposons qu'il existe dans I, deux entiers a et b tel que a < b et tia > tib. Inversons l'ordre de ces deux clients et on obtient l'ordre I'. Ordre de service I I' 1 2 ... a ... b n i1 i2 ... ia ... ib ... In i1 i2 ... ib ... ia ... in

T(I') = (n-a+1)tib + (n-b+1)tia + S1<k<n et ka et b (n-k+1)tik

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 80

Exemple 3 : Optimalit de lalgorithme (2/2)

T(I) - T(I') = (n-a+1)tia + (n-b+1)tib - (n-a+1)tib - (n-b+1)tia = (b-a)tia + (a-b)tib = (b-a) (tia - tib)

Comme b - a > 0 et tia - tib > 0, on dduit que : T(I) - T(I') > 0 et par consquent T(I) > T(I').

Nous pouvons amliorer tout ordre de service o un client est servi avant un autre ncessitant moins de temps optimalit de lalgorithme

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

81

Exemple 4 : Coloration dun graphe

Soit G = (N,A) un graphe non orient. Colorer le graphe tels que deux sommets relis doivent tre diffrentes. de couleurs
3 1 2 4 5

L'algorithme vorace : - Choisir une couleur et un sommet comme point de dpart

- Considrer les autres sommets et essayer de les colorer par cette couleur - Lorsqu'on ne peut plus faire de progrs choisir une nouvelle couleur et un nouveau point de dpart non color - Colorer tout ce qui est possible avec cette deuxime couleur
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

- ainsi de suite.

82

Exemple 4 : Coloration dun graphe

2-coloration

3-coloration

Remarques Un algorithme bas sur une heuristique vorace permet la possibilit de trouver une "bonne" solution mais pas la certitude lalgorithme exhaustif qui produit une solution optimale est exponentiel
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 83

Exemple 5 : Feux de signalisation

E D

Considrons 5 artres : A, B, C, D et E. D et E sont des artres sens unique Changements de direction (13) AB, AC, AD, BA, BC, BD, DA, DB, DC, EA, EB, EC et ED
B C A

AB et EC sont possibles alors que AD et EB peuvent provoquer une collision Modlisation laide dun graphe sommets correspondent aux changements de direction artes joignent les couples de sommets dont les itinraires se croisent
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 84

Exemple 5 : Trace de lalgorithme

AB AC AD

BA

BC

BD

AC

DA

DA

DB

DC

BD
EA EB EC ED

EB

4-colorable

Graphe complet

Solution optimale car le sous-graphe compos des sommets AC, DA, BD et EB est un graphe complet de 4 sommets et ncessite par consquent quatre couleurs. Les sommets de la mme couleur correspondent aux itinraires sans collision. Les quatre couleurs correspondent aux quatre phases ncessaires du systme de signalisation
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 85

Exercices
Exercice 1 : Rsoudre le problme de signalisation pour le carrefour suivant :
D

C B

Exercice 2 : Trouver un algorithme vorace pour rsoudre le problme du commis voyageur en supposons que le graphe est complet.

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

86

Chapitre 5 : Programmation dynamique

diviser-pour-rgner : mthode descendante programmation dynamique : mthode ascendante + utilisation espace mmoire (afin d'viter de calculer la mme chose plus d'une fois)

Contenu Coefficient du binme Principe doptimalit Multiplication chane de matrices Plus courts chemins

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

87

Exemple 1 : Coefficient du binme

Coefficient binomial C(n,k) = C(n-1,k-1) + C(n-1,k) si 0 < k < n = 1 autrement

fonction C(n,k) si k=0 ou k=n alors retourner 1 sinon retourner C(n-1 , k-1) + C(n-1 , k)

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

88

Exemple 1 : Trace de lalgorithme

C(5,2)

Trace pour (5,2) =10

C(4,1) C(4,2)

C(3,0)

C(3,1)

C(3,1)

C(3,2)

C(2,0) C(2,1)

C(2,0)

C(2,1)

C(2,1) C(2,2)

C(1,0) C(1,1)

C(1,0)C(1,1) C(1,0) C(1,1)

Remarques : beaucoup de valeurs C(i,j) sont calcules plusieurs fois. Exercice : Montrer que le nombre d'appels rcursifs provoqus par C(n,k) est gal : 2

( )-2
n k
89

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

Exemple 1 : Triangle de Pascal

0 1 2 3 4 5 0 1 1 1 1 1 1 1 1 2 3 4 5 2 3 4 5

...

k-1

1 3 6 10 1 4 10 1 5

. .
n-1 n 1 1 C(n-1,k-1) C(n-1,k) C(n,k)

Exercice : Dcrire cet algorithme. Montrer quil demande un espace dans O(k) et un temps dans O(nk) si on compte chaque addition cot unitaire. Exercice : Parmi les algorithmes du calcul des nombres de Fibonacci, lequel est un algorithme de programme dynamique ?
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 90

Principe doptimalit
La programmation dynamique est souvent utilise pour rsoudre des problmes d'optimisation qui satisfont le principe d'optimalit suivant : Principe d'optimalit : Dans une squence optimale de dcisions ou de choix, chaque sous-squence doit tre optimale. Exemple : le problme du plus court chemin vrifie le principe doptimalit Exercice : Le principe d'optimalit s'applique-t-il au problme du plus long chemin simple entre deux villes ? Un chemin simple va directement de ville en ville sans passer deux fois par la mme ville (sans cycle).

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

91

Exemple 2 : Multiplication chane de matrices

M = M1M2...Mn Comme la multiplication matricielle est associative M = (...((M1M2)M3) ... )Mn = M1(M2(M3(... (Mn-1Mn) ...))) = ((M1M2)(M3M4) ... ) = ... Le choix d'une mthode peut influencer sur le temps de calcul. Exercice : Montrer que le calcul de AB, o A est d'ordre pxq et B est d'ordre qxr, par la mthode directe ncessite pqr multiplications de nombres scalaires.

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

92

Exemple 2 : Application
Exemple : Soient quatre matrices A, B, C et D d'ordre (13x5), (5x89), (89,3) et (3, 34) respectivement. Il y a cinq manires diffrentes de calculer ABCD : ((AB)C)D (AB)(CD) (A(BC))D A((BC)D) A(B(CD)) qui ncessite " " " " " " " " 10582 54201 2856 4055 26418 multiplications " " " "

La mthode la plus efficace est 9,5 fois plus rapide que la plus lente

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

93

Exemple 2 : Nombre de Catalan

Soit T(n) : nombre de manires diffrentes d'insrer des parenthses dans M M = (M1M2...Mi) (Mi+1 .. Mn) Nous avons T(i) manires de mettre les parenthses dans la partie gauche de Mi et T(n-i) manires de mettre les parenthses dans la partie droite. Par consquent T(n) = S1in-1 T(i) T(n-i) et T(1) = 1
n 1 2 3 4 5 10 T(n) 1 2 2 5 14 4862

T(n) s'appelle nombre de Catalan.

Exercice : Montrer que T(n) = 1/n

2n 1 n1

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

94

Exemple 2 : Algorithme de programmation dynamique

Soit mij (1 i j n) la solution optimale pour la partie Mi...Mj du produit M. La solution du problme est m1n. Supposons que la dimension de Mi est di-1 x di pour i = 1,2,..,n. Construisons la table mij l'lment mj tel que j-i = s. Cas 1 : s = 0 Cas 2 : s = 1 Cas 3 : 1 < s < n diagonale par diagonale : la diagonale s contient mij = 0, i = 1,2,..,n mi,i+1 = di-1 di di+1 , i = 1,2,..,n-1 mi,i+s = min i k i+s-1 (mik + mk+1,i+s + di-1dkdi+s)

Le troisime cas reprsente le fait que pour calculer (Mi Mi+1...Mi+s) on essaye toutes les possibilits(Mi...Mk)(Mk+1...Mi+s) pour en choisir la meilleure.
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 95

Exemple 2 : Trace de lalgorithme

Reprenons l'exemple prcdent : d = (13,5,89,3,34) s = 1 : m12 = 5785, m23 = 1335 et m34 = 9078 s = 2 : m13 = min(m11 + m23 + d0d2d3 , m12 + m33 + d0d2d3) = min(1530 , 9256) = 1530 m24 = min(m22 + m34 + d1d2d4 , m23 + m44 + d1d3d4) = min(24208 , 1845) = 1845 s = 3 : m14 = min(m11+ m24+ d0d1d4 , m12+ m34+ d0d2d4 , m13+ m44 + d0d3d4) = min(4055 , 54201 , 2856) = 2856 j=1 i=1 i=1 i=3 i=4
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

j=2 5785 0

j=3 1530 1335 0

j=4 2856 1845 9078 0

96

Exercices
Exercice 1 : Ecrire l'algorithme qui calcule m1n. Comment peut-on modifier l'algorithme si l'on veut savoir comment calculer M de faon optimale ? Exercice 2 : Montrer que lalgorithme (n3).

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

97

Exemple 3 : Plus courts chemins

Soit G = (N,A) un graphe orient o N = {1,2,..,n}. Soit L une matrice qui donne la longueur de chaque arc. Trouvons le plus court chemin entre chaque paire de sommets. Le principe de l'optimalit s'applique car si k est un sommet intermdiaire sur le plus court chemin entre i et j alors la portion du trajet de i k ainsi que celle de k j doivent aussi tre optimales. A l'itration k on trouve un chemin qui ne passe que par {1,2,..,k}. Dk[i,j] = min(Dk-1[i,j], Dk-1[i,k] + Dk-1[k,j]) Procdure Floyd (L[1 .. n,1 .. n]) : tableau [1 .. n,1 .. n] DL pour k = 1 h faire pour i = 1 n faire pour j = 1 n faire D[i,j] min(D[i,j] , D[i,k] + D[k,j]) retourner D Exercice : Montrer que t(n) O(n3)
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 98

Exemple 3 : Trace de lalgorithme

1 15 5 5 50 30 2 15 3 5 15 4

D0 = L =

0 50 30 15

5 0

15 5 0 15 5 0

et

D4 =

0 5 15 10 20 0 10 5 30 35 0 15 15 20 5 0
99

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

Chapitre 6 : Transformation du domaine

Soit f : Dt D une fonction calculer. Une transformation consiste en : - domaine R - injection F : D R - fonction g : Rt R tel que : f = F-1 ogoF
R t g R D t f D
1

Contenu Multiplication symbolique de deux polynmes Transforme de Fourrier Transforme de Fourier inverse
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 100

Exemples de transformation du domaine

Produit de deux nombres positifs D = +*, f(u,v) = u*v , R = et F (u)= ln u et g(x,y) = x+y
(u,v) ln (ln u,ln v) g f u*v e ln u + ln v

Addition en reprsentation romaine (XVI + CIV) Changement de coordonnes (cartsiennes/ polaires) Calcul dans un ordinateur (E/S en dcimal et calcul en binaire) Calcul diffrentiel (transforme de Laplace).
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 101

Multiplication symbolique des polynmes

Soient p(x) = ad-1xd-1 + ad-2xd-2 + + a0 et On veut calculer r(x) = p(x) q(x) q(x) = bd-1xd-1 + bd-2 xd-2+ + b0

algorithme classique O(d2) en comptant les oprations scalaires comme lmentaires.

Transformation du domaine f : multiplication symbolique : valuation en 2d - 1 points O(d2) g : multiplication ponctuelle) F-1 : interpolation
p (x ),q (x )

r(x )

p ( x i) ,q ( x i) i= 0 ,1 ,...,2 d - 2

r ( x i) = p ( x i) q ( x i) i= 0 ,1 ,...,2 d - 2
102

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

Exemple de la multiplication de deux polynmes

p(x) = 2x - 1 et q(x) = x - 1 r(x) = p(x)q(x) = (2x 1)(x 1) = 2x2 3x + 1

p et q peuvent tre reprsentes l'aide de leur coefficients ou en 2 valeurs p = (-1,1) et q = (-1,0) r = pq = (1,0)

r(x) nest pas compltement dfini r est de degr 2 il doit tre dfini de faon unique l'aide de 3 valeurs p = (-1,1,3) et q = (-1,0,1) r = pq = (1,0,3)

par la mthode de Lagrange (ou rsolution dun systme linaire ou ) on trouve : r (x) = 2x2 3x + 1
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 103

Transforme de Fourier (discrte)

Applications (optique, acoustique, tlcommunications, traitement du signal) Soient n = 2k , k > 0, w / wn = 1 (racine de lunit) Exemples w = 4, n = 8 et le calcul se fait modulo 257 w = (1+i) /2, n = 8 et le calcul est en arithmtique complexe Dfinition Soit a = (a0,a1, .. ,an-1) vecteur qui dfinit pa(x) = an-1xn-1 + .. + a0 Transforme de Fourier de a relativement w est : Fw(a) = (pa(1), pa(w),..., pa(wn-1)) Exercice
i Algorithmique et complexit de i calcul, M. Eleuldj, EMI, Avril 2008

Calculer F (a) et F (a) avec a=(1,-1,-5,3) et b=(-2,6,-4,1)

104

Algorithme pour la Transforme de Fourrier

Supposons n > 1 et posons t = n/2 Soient b = (a0,a2,...,an-2) et c = (a1,a3,...,an-1) tels que : pa(x) = pb(x2) + x pc(x2). En particulier : pa(wi) = pb(bi) + wi pc(bi) o b = w2 bt = 1 on peut de parler de Fb(b) et Fb(c) De plus bt+i= bi pa(wt+i) = pb(bi) + wt+i pc(bi) comme nous allons voir que wt = -1 pa(wt+i) = pb(bi) - wi pc(bi)
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 105

Algorithme FFT
fonction FFT (a[0...n-1] , w) : tableau [0...n-1] tableau A[0...n-1] {pour recevoir le rsultat} si n=1 alors A[0] <-- a [0] sinon t <-- n/2 tableaux b, c, B, C[0...t-1] pour i <-- 0 t-1 faire b[i] <-- a[2i] , c[i] <-- a[2i+1] B <-- FFT(b , w2) C <-- FFT(c , w2) b <-- 1 pour i <-- 0 t-1 faire A[i] <-- B[i] + b C[i] A[t+i] <-- B[i] - b C[i] b <-- bw retourner A
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

Exercice 1 : Montrer que FFT O(n logn).

106

Trace de FFT
a = (1,-1,-5,3), w=i FFT(a,i) t=2, b = (1,-5) et c = (-1,3) B=FFT(1,5) t=1, b=(1) et c=(-5) B=FFT(b,1)=(1) C=FFT(c,1)=(-5) A=(-4,6) C=FFT(c,-1) t=1, b=(-1) et c=(3) B=FFT(b,1)=(-1) C=FFT(c,1)=(3) A=(2,-4) A=(-2, 6-4i, -6, 6+4i)
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 107

Transforme de Fourrier inverse

Dfinition : le nombre w est appel une n-ime racine principale de l'unit si : i) w 1 (sauf si n=1) ii) wn = 1 iii) S1jn-1 wjp = 0 pour 1 p < n Remarques : l'inverse de w est wn-1 si p = n/2, la deuxime condition implique : S1jn-1 wjn/2 = n/2(1 + wn/2) = 0 wn/2 = -1. Exercice : Montrer que w-1 est une n-ime racine principale de l'unit. Soient n et w des puissances positives de 2 et soit m = wn/2 + 1. Prouver que w est une n-ime racine principale de l'unit dans l'arithmtique modulo m. Prouver que n-1 existe, en montrant que n-12008 = m - (m-1)/n. Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 108

Transforme de Fourrier inverse

Thorme : Soient A la matrice n x m / A = (aij) et aij = wij. Comme w est une nime racine principale de l'unit et n-1 existe alors A est inversible, son inverse tant la matrice B / B = (bij) et bij = n-1 w-ij et AB = In o In est la matrice identit. Une autre formulation de la dfinition de la transforme de Fourier est : Fw(a) = a A Exercice : Dfinir A et B pour n = 4. Corollaire : 0 i < j < n wi wj. Cette proprit est essentielle l'interpolation du polynme produit

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

109

Algorithme FTT inverse

La transforme de Fourier inverse de a relativement w est : F-1w(a) = (n-1pa(1) , n-1pa(w-1) ,...n-1, n-1pa(w-(n-1)) = n-1 Fw-1(a) = n-1 Fwn-1(a). Exercice 4 : Montrer que F-1w(Fw(a)) = a pour tout vecteur a fonction FFTinverse (a[0 .. n-1] , w) : tableau[0 .. n-1] tableau F[0 .. n-1] F <-- FFT(a , wn-1) pour i <-- 0 n-1 faire F[i] <-- n-1F[i] retourner F FFT inverse O(n) Exercice : Faire la trace FFTinverse( Algorithmique et complexit de calcul,pour M. Eleuldj, EMI, Avril 2008 (-2, 6-4i, -6, 6+4i)
110

Application la multiplication symbolique des polynmes

Soient p(x) = as-1xs-1 +...+ a0 et q(x) = bt-1 xt-1 +...+ b0 On veut calculer r(x) = p(x)q(x) de degr d = s + t. Soient n la plus petite puissance de 2 d et w une n-ime racine principale de l'unit. Soient a et b tels que a = (a0,a1,..., as-1,0,...,0) et b = (b0,b1,..., bt-1,0,0,...,0). Soient A = Fw(a) et B = Fw(b) Ai = p(wi) et Bi = q(wi) , i = 0,1,...,n-1. Soit C tel que Ci = AiBi = p(wi)q(wi) = r(wi). C = Fw(c) correspond aux coefficients de r Do La multiplication symbolique des polynmes O(d log d)
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 111

Trace de lexemple
p(x) = 3x3 - 5x2 - x + 1 et q(x) = x3 - 4x2 + 6x 2 On choisit n=8 et on sait que w=4 est une racine principale de l'unit dans larithmtique modulo 257. Soit a = (1,-1,-5,3,0,0,0,0), b = (-2,6,-4,1,0,0,0,0). Fw(a) = (255,109,199,29,251,247,70,133) et Fw(b) = (1,22,82,193,244,103,179,188). Le produit point par point modulo 257 donne C = (255,85,127,200,78,255,194,75) Comme F-1w(C) = (-2, 8, 0, -31, 37, -17, 3, 0). alors : r(x) = 3x6 - 17x5 + 37x4 - 31x3 + 8x - 2
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 112

Chapitre 7 : Algorithmes probabilistes

Caractristiques Hasard peut prendre certaines dcisions Diffrentes excutions sur le mme exemplaire peuvent produire des rsultats diffrents Conflit avec la dfinition dun algorithme Contenu Ali Baba et les 40 voleurs Calcul de Intgration numrique Test de primalit Algorithmes gntiques
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 113

Exemple 1 : Ali Baba et les 40 voleurs

Hypothses Valeur du trsor est T Trsor? les voleurs prlvent chaque nuit un montant x Une fois sur place Ali Baba peut reconnatre le trsor 4 jours de calcul pour dterminer le lieu exact 5 jours Indication de Jouha moyennant 3x
5 jours

Trsor ?

5 jours

Solutions S1 = T (4 + 5)x = T 9 x Ali Baba S2 = T (3 + 5)x = T 8 x S3 = T - 5x =T - 10 x esprance = (T - 5 x)/2 + (T 10 x)/2 = T 7,5 x

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 114

Exemple 2 : Calcul de
k : nombre des points lintrieur du cercle n : nombre total de points
x

2r
x x x x x x x x x x x x x

S1 = r2 : surface du cercle S2 = (2r)2 = 4 r2 : sUrface du carr S1/S2 = r2/4r2 = /4 = 4 S1/S2 4 k/n fonction (n) k0 pour i = 1 n faire x uniforme(0,1) y uniforme(0,1) si (x2 + y2 <1) alors k k + 1 retourner 4k/n
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

115

Exemple 3 : Intgration numrique

Soit f : [0,1] [0,1] continue Calculons lintgrale f(x) entre 0 et 1 fonction intgration1(f,n) k 0 pour i = 1 n faire x uniforme(O,1) y uniforme(0,1) si y f(x) alors k k + 1 retourner k/n

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

116

Exemple 3 : Intgration numrique

fonction intgration2(f,n) somme 0 pour i = 1 n faire x uniforme(O,1) somme somme + f(x) retourner somme/n Remarque Algorithme1 et 2 sont intressants car les algorithmes systmatiques ne donnent que des valeurs approximatives

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

117

Exemple 4 : Test de primalit

fonction premier(n) d uniforme(2, n) retourner d Remarques Cas favorable : n =1 x 2 x 3 x x (n-1) = n! Pire cas : n non premier mais est le produit de deux nombres premiers n = 2623 = 43x61 fiabilit = 2% Plusieurs tests permettent daugmenter la fiabilit Il existe dautres moyens qui donnent des tests plus prcis

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

118

Exemple 5 : Algorithmes gntiques

analogies avec les phnomnes biologiques (slection naturelle de Charles Darwin) vocabulaire : individus (solutions potentielles), population, gnes (variables), chromosomes, parents, descendants, de reproduction, de croisement, de mutations, etc.

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

119

Chapitre 8 : Pr-conditionnement
I : ensemble des exemplaires J, K I tel que i I, i=<j,k> i est la solution de i
k

Algorithme A

Algorithme Bj

Exemples Ralisation dune application = Compilation + excution Recherche dans un ensemble = Construction du tas + recherche binaire en O(log n) Evaluation rpte dun polynme = forme pr-conditionne + valuation
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 120

Evaluation rpte dun polynme

J : ensemble des polynmes une variable de degr n K : ensemble des valeurs que la variable peut prendre Hypothses Coefficient entiers valuation pour des valeurs entires Polynme unitaires n = 2k 1 Comptage du nombre de multiplications P(x) = x7 5x6 + 4x5 +- 13x4 + 3x3 10 x2 + 5 x 17 = (x4 + 2)[(x2 + 3)(x 5) + (x + 2)] + [(x2 2 4)x + (x + 9)] 5 multiplications et 9 additions
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008 121

Mthode de pr-conditionnement
Soit p(x) un polynme unitaire de degr 2k 1 k-1 p(x) = (x2 + a)(q(x) + r(x)) avec a une constante et q et r deux polynmes unitaires de degr 2k-1 -1 la mme procdure est applique rcursivement q et r p appele est la forme pr-conditionne de p Exercice : trouver p pour x7 + 2x6 5x4 + 2x3 6x2 + 6x 32 et x7 Soit M(k) : nombre de multiplications pour valuer p(x) k-1 M(k) = M(k) k + 1 Si on ne compte pas les multiplications pour x2, x4, , x2 M(k) = 0 si k = 0 = 2 M(k 1) + 1 si k 2 M(k) = 2k 1 1 M(k) = 2k 1 + k 2
Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

Do il suffit de faire :

(n-3)/2 + log(n + 1) multiplications

122

Mthodes dvaluation dun polynme

Mthode Directe Dynamique Nombre de multiplications pour p 27 12 En gnral n(n + 1)/2 - 1 2n 2

Horner Pr-conditionnement

6 5

n1 (n 3)/2 + log(n + 1)

Algorithmique et complexit de calcul, M. Eleuldj, EMI, Avril 2008

123