Représente une stratégie (approche ou désigne) pour résoudre un problème. méme probléme pour grand probléme et sous probléme.
- Diviser le problème en un certain nombre de sous-problèmes similaires au problème initial, mais de taille moindre.
- Régner les sous-problèmes en les résolvant récursivement. Par ailleurs, si la taille d'un sous-problème est assez réduite, on peut le résoudre directement.
- Combiner les solutions des sous-problèmes en une solution complète pour le problème initial.
1.1. La fonction divide and conquer
Fonction DAC (P)
Debut
Si (petit(p)) alors S(p)
Sinon
déviser p en p1, p2, p3, p4, p5 …….., pk
appliquer DAC(p1), DAC(p2)……
combiner (DAC(p1), DAC(p2)……
1.2. La complexité des problémes récursive :
Calculer le temps d’exécution d’un algorithme récursive nécesite une démonstration par récurrence de l’algorithme qui décrit le temps d'exécution global pour un problème de taille n en fonction du temps d'exécution pour des entrées de taille moindre. Au lieu quel est appelé F elle est appelé t
.
Il existent trois méthodes :
Méthode de substitution : Nous faisons une estimation de la solution, puis nous utilisons l'induction mathématique pour prouver que la supposition est correcte ou incorrecte.
Reccurence de type t(n-1)+constante :
Procédure test (n :entier)…………………T
Debut
Si (n>0) alors ……….1
Ecrire ……….1
Test (n-1) ………..t(n-1)
Fin si
T(0)=1 si n=0
T(n-1) +2 si n>0
substitution avant :
rechercher un modéle : substitué à partir de la valeur initiale
t(0)=1
t(1)=3
t(2)=t(1)+2 = 5
t(3)=t(2)+2 = 7
t(4)=t(3)+2 = 9
t(5)=t(4)+2 = 11
deviner :
- nous devinons à partir de la suite que t=2n+1
- 3,5,8,9,11……
vérification : est correct s'il satisfait la formule générale et les conditions initiales
- T
= T(n-1)+1 = [(2n-1] + 2 = 2n+1 (t(n-1)=2(n-1)+1
- T(1) = 1+2 = 3
- T(0)=1
substitution arrière :
T=t(n-1)+2
T=[t(n-2)+2]+2
T=t(n-2)+4
T=t(n-3)+6
Vas se repéter k time inconu
T=t(n-k)+2k on arrête après k steps usqu’à n=0
Donc :
Puisque T(1)=t(0)+2 alors N=1 et n-k=0 ce qui donne n=k
On remplace k par n et on obtient :
T=t(n-n)+2n
T=t(0)+2n
1+2n
Vérification :
- T
- T(1) = 1+2 = 3
Resultat de la complexité = O
Récurrence de type : t=t(n-1)+n
Sybstitution forward :
T(1)=t(0)+1=2
T(2)=t(0)+1+2=4
T(3)= t(0)+1+2+3=7
T(4)= t(0)+1+2+3+4=11
T(5)= t(0)+1+2+3+4+5=16
Deviner :
T=1+n(n+1)/2
Asymptotiquement = n2
Verification :
T(0)=1
T=t(n-1)+1=n2/2-n/2+2 asymptotiquement = n2
Substitution backward
Procedure test ……………………….T
Debut
Si (n>0) …………………..1
Pour iß0 à n-1 faire………………….. 2n+2
Ecrire ……………………..n
Fin pour
Test(n-1)………………………………………….T(n-1)
finsi
Fin procedure
T=2n+2+n+1+t(n-1) =3n+3+t(n-1)
Asymptotiquement 3n+3=n (pour grand tille de n toujours)