Diviser pour Régner (quelques clés pour la lecon 902)

Loïc Hélouët

Loic.helouet@irisa.fr

Plan

Principe Exemples classiques Recherche d’index dichotomique Calcul d’enveloppe convexe Transformée de Fourrier

Complexité

Diviser pour régner

Principes en 3 étapes Prenons un problème P de taille n: Diviser le problème en un certain nombre de sous-problèmes de taille <n Régner sur les sous-problèmes en les résolvant récursivement (si la taille est réduite, on a souvent une solution immédiate) Combiner les solutions des sous-problèmes

Diviser pour régner

Implicitement : il existe k, petit, pour lequel la résolution de P[k] est triviale (ex :trier un tableau de taille 1,….) Plusieurs cas : la résolution d’un seul sous-problème suffit

Pas besoin de fusionner les résultats exemple : recherche dichotomique

On résout c problèmes de taille n/c une étape de fusion des résultat est nécessaire Exemples : le tri fusion, le calcul d’enveloppe convexe

Recherche d’Index Exemple 1 : Recherche d’index dans une liste triée

Donnée du problème : un tableau trié de taille n, un nombre x (existant) Résultat : l’index de x dans le tableau

1 2 3 n

5 12 23 78

ChercherSimple(T,v) = Pour i dans 1..n faire si ( T[i] = x) alors resultat = i; break; fsi fpour

ChercherDicho (T,x,i,j) = k=i + (j-i)/2 si T[k] == x alors resutat = k; si T[k] > x alors chercherDicho(x,i,k-1) sinon chercherDicho(x,k+1,j) fsi

Pire cas : O(n) Pire cas : O( log(n) )

Enveloppe convexe Exemple 2 : tri fusion Exemple 3 : Calcul d’enveloppe convexe

Donnée : liste d’au moins 3 points P, ordonnés selon leur abscisse Sortie : liste des points formant l’enveloppe convexe de P

Principe de l’algo:

Couper l’ensemble des pts en 2

Calculer 2 enveloppes séparées

Utiliser les 2 resultats pour

calculer une plus grande

enveloppe.

Enveloppe convexe Exemple 3 : Calcul d’enveloppe convexe

Donnée : un ensemble d’au moins 3 points P, ordonnés selon leur abscisse Sortie : liste des points formant l’enveloppe convexe de P

Cas triviaux : 1,2, 3 points

Enveloppe convexe

Convexe (P)

P: liste de points de taille n

Si ( |P| 3) alors

renvoyer P

Sinon

P1 = Convexe(P[1..n/2])

P2 = Convexe(P[n/2..n])

renvoyer FusionConvexe(P1,P2)

finsi

x

z

y t

t ne « voit » pas x si [x,t] [y,z]

se croisent

Enveloppe convexe Fusion Convexe

Donnée: P1, liste avec chainage double de points, ordonnés dans le sens trigo et inverse P2, liste avec chainage double de points, ordonnés dans le sens trigo et inverse. Sortie : liste des points formant l’enveloppe convexe de P (ord.trigo.)

Enveloppe convexe Fusion Convexe: Etape 1

Choisir x1, point d’abscisse maximale de P1 Choisir x2, point d’abscisse maximale de P2

x1

x2

Enveloppe convexe Fusion Convexe: Etape 2

Calculer Un « pont supérieur » : plus haut segment dont les points « se voient »

x1

x2

Enveloppe convexe Fusion Convexe: Etape 2

Calculer Un « pont inférieur » : plus bas segment dont les points « se voient »

x1

x2

Enveloppe convexe Fusion Convexe: Etape 3

Eliminer les points entre les 2 ponts (parcours de P1 & P2 dans le sens trigo. En passant par les ponts)

x2

Enveloppe convexe Pont Supérieur (P1, P2 : listes, x1,x2 : points) Trouvé = faux ; g=x1; d=x2 ; Tant que (trouvé == faux) faire Trouvé = vrai Tant que ( g « voit » [d,prec(d)] faire d=prec(d) trouve := faux Finfaire Tant que ( d « voit » [g,succ(g)] faire d=prec(d) trouve := faux Finfaire Finfaire Renvoyer (g,d)

Transformée de Fourrier

Traitement du signal

passage d’un signal donné dans un domaine des temps

… à un domaine de fréquences

somme pondérée de sinusoïdes à décalage de phase

Intérêt : opérations sur les polynômes plus rapides ( (n) )

Le passage par la transformée permet des opération en (n log n )

au lieu de (n2) (ex produits de polynômes)

[Cormen, chap30]

Transformée de Fourrier

Passage d’une représentation par un polynome A(x)

Representable par un vecteur

À une représentation par n paires point-valeur, d’abscisses distinctes

Theorème :

Il n’existe qu’un polynome de degré <n tel que

[Cormen, chap30]

),..,( 10 naaA

),(),...,,( 1100 nn yxyx

)( kk xAy

nj

j

i xaxA..1

.)(

Transformée de Fourrier

Passage d’une representation par un polynome A(x)

Representable par un vecteur

À une transformée de Fourrier :

[Cormen, chap30]

),..,( 10 naaA

nj

j

i xaxA..1

.)(

1

0

.)(n

j

kj

nj

k

nk aAy ),..,( 10 nyyy

k

n keme racine complexe de l’unité

12/

220

]0[ ....)(

n

n xaxaaxA

12/

131

]1[ ....)(

n

n xaxaaxA

)()()( 2]1[2]0[ xxAxAxA

FFT-Recursive( A)

A : tableau

Var

y, a[0] , a[1] , y[0] , y[1] :tableaux

n= longueur(A)

Si (n==1) alors

renvoyer(A)

Sinon

n= e2i/n

= 1 a[0]=(a0,…an-2)

a[1]=(a1,…an-1)

y[0]=FFT-Recursive(a[0])

y[1]=FFT-Recursive(a[1])

pour k dans 0..n/2-1 faire

yk=yk[0] + yk

[1]

yk+n/2=yk[0] - yk

[1]

= n fait

renvoyer y

Le calcul de la FFT se fait

En (n log n)

Complexité

Cout C(n) d’un algorithme : C(n) = D(n) + R(n) + F(n) Diviser D(n) le problème Régner R(n) (résoudre les pbs de taille inférieure) Combiner F(n) les solutions Si l’algorithme contient des appels récursifs, le coût est décrit par une équation de récurrence.

Complexité

Diviser le problème : cout D(n) Partition simple : cout constant K exemple : recherche dichotomique = 2 comparaisons Partition plus complexe exemple : partition selon la médiane : O(n)

Rappel : notation de Landau

Notation Intuition sémantique

f(n) O ( g(n) ) f bornée par g asymptotiquement à un facteur près

f(n) ( g(n) ) f minorée par g asymptotiquement à un facteur près

f(n) ( g(n) ) f dominée et soumise

à g asymptotiquement

f(n) g(n) f est égal à g asymptotiquement

kngnf

nnnk

).()(

,,,0 00

)().(

,,,0 00

nfkng

nnnk

21

0021

).()().(

,,,0,

kngnfkng

nnnkk

)()()(

,,,0 00

ngnfng

nnn

Complexité

Régner : resoudre les pbs de taille inférieure R(n) Cas simple 1 : Un seul des sous problèmes à résoudre

R(n) = C(m), m<n exemple : recherche dichotomique R(n) = C(n/2)

Cas simple 2: résoudre k problèmes de même taille R(n) = k.C(n/k) exemple tri fusion, enveloppe convexe ( R(n)= 2.C(n/2) )

Cas plus complexe: le problème se partitionne en plusieurs sous-problèmes de tailles différentes R(n) = C(m1) + … + C(mk)

Cas encore difficile: Le problème se partitionne en plusieurs sous problèmes, dont le nombre et la taille dépend de n et de l’entrée du pb. R(n) =??? Récurrence difficile à trouver, difficile à calculer

Complexité

Combiner les solutions : cout F(n) Cas simple : une seule des solutions explorée F(n)=0 exemple : recherche dichotomique Sinon, F(n) dépend :

• de la taille des résultats, • de l’algorithme de fusion, • …

Complexité

Théorème :

Soit P un problème de taille n, divisible en k sous-problèmes de même taille,

et pour lequel la résolution d’un seul problème suffit.

Si

Alors

)()/()( ngknCnC

)(log

1

)()1()(n

ik

kgCnC

Diviser pour Régner

Cout C(n) de l’algorithme : C(n) = D(n) + R(n) + F(n) Exemple : recherche dichotomique Pour n>1,

D(n) = 2 (il faut tester T[k] == x et T[k] < x) R(n) = C(n/2) si n>1 F(n)= 0

))(log(22)2/(2)()2/log(

1

n

nOnCnC

1)1( C

Complexité: Théorème général

Soit P un problème de taille n, divisible en a sous-problèmes de même taille n/b,

Soient a 1, b 1, f(n) une fonction et C(n) tels que

)()/(.)( nfbnCanC

)()(log abnnC

[Cormen, chap4]

• Si

•Si

•Si

)()(log

abnOnf pour e >0 alors

)log()(log

nnnCab)()(

log abnnf alors

)log()(log

nnnCab)()(

log

abnnf pour e >0 alors

)()/( ncfbnaf pour c<1

Complexité: Théorème général

)()/(.)( nfbnCanC

[Cormen, chap4]

)()(log abnOnf

)log()(log

nnnCab

Complexité de la transformée de Fourier:

)log.()()2/(.2)( nnnnCnC fourrierfourrier

avec

Bibliographie

[1] Christine Froidevaux, Marie-Claude Gaudel, Michèle Soria,

Types de Données et Algorithmes, McGraw-Hill, 1990.

[2] Thomas Cormen, Charles Leiserson, Ronald Rivest,

Introduction à l’algorithmique, Dunod, 1994.

Mais aussi:

[3] Robert Sedgewick, Philippe Flajolet, Introduction à l’analyse des

algorithmes, Addison Wesley, 1996.