Eléments d'algorithmique résolution d’équations de récurrence

Récursivité

Les définitions récursives sont courantes en mathématiques. Nous avons vu au chapitre précédent l’exemple de la suite de Fibonacci, définie par une relation de récurrence. En informatique, la notion de récursivité joue un rôle fondamental. Nous voyons dans ce chapitre la puissance de la récursivité au travers essentiellement de deux algorithmes de tri ayant les meilleures performances asymptotiques pour des algorithmes génériques. Nous terminons par une étude des solutions d’équations de récurrence entrant en jeu lors de l’analyse de complexité de tels algorithmes.

Conception des algorithmes

Il existe de nombreuses facons de concevoir un algorithme. On peut par exemple adopter une approche incrémentale ; c’est le cas du tri par insertion : après avoir trié le sous-tableau tab[0]…tab[j-1], on ins`ere l’élément tab[j] au bon emplacement pour produire le sous-tableau trié tab[0]…tab[j].
Une approche souvent tr`es eﬃcace et élégante est l’approche récursive : un algorithme récursif est un algorithme défini en référence `a lui-mˆeme (c’est la cas par exemple de l’algorithme fibo1 vu au chapitre précédent). Pour éviter de boucler indéfiniment lors de sa mise en oeuvre, il est nécessaire de rajouter `a cette définition une condition de terminaison, qui autorise l’algorithme `a ne plus ˆetre défini `a partir de lui-mˆeme pour certaines valeurs de l’entrée (pour fibo1, nous avons par exemple défini fibo1(0)=0 et fibo1(1)=1).
Un tel algorithme suit généralement le paradigme ≪ diviser pour régner ≫ : il sépare le probl`eme en plusieurs sous-probl`emes semblables au probl`eme initial mais de taille moindre, résout les sous-probl`emes de fa¸con récursive, puis combine toutes les solutions pour produire la solution du probl`eme initial. La méthode diviser pour régner implique trois étapes `a chaque niveau de la récursivité :
– Diviser le problème en un certain nombre de sous-problèmes. On notera D(n) la complexité de cette étape.
– Régner sur les sous-problèmes en les résolvant de manière récursive (ou directe si le sous-problème est suﬃsamment réduit, i.e. une condition de terminaison est atteinte).
On notera R(n) la complexité de cette étape.
– Combiner les solutions des sous-problèmes pour trouver la solution du problème initial. On notera C(n) la complexité de cette étape.
Lien avec la récursivité en mathématiques. On rencontre en général la notion de récursivité en mathématiques essentiellement dans deux domaines : les preuves par récurrence et les suites récurrentes. La conception d’algorithmes récursifs se rapproche plus des preuves par récurrence, mais comme nous allons le voir, le calcul de la complexité d’un algorithme récursif se rapproche beaucoup des suites récurrentes.
Lors d’une preuve par récurrence, on prouve qu’une propriété est juste pour des conditions initiales, et on étend cette propriété `a l’ensemble du domaine en prouvant que la propriété est juste au rang n si elle est vrai au rang n − 1. Dans un algorithme récursif la condition de terminaison correspond exactement au conditions initiales de la preuve par récurrence, et l’algorithme va ramener le calcul sur une entrée `a des calculs sur des entrées plus petites.
Attention !
Lors de la conception d’un algorithme récursif il faut bien faire attention `a ce que tous les appels récursifs eﬀectués terminent bien sur une condition de terminaison. Dans le cas contraire l’algorithme peut partir dans une pile d’appels récursifs infinie (limitée uniquement par le nombre maximum d’appels récursifs autorisés). De mˆeme, en mathématique, lors d’une preuve par récurrence, si la condition récurrente ne se ramène pas toujours `a une condition initiale, la preuve peut être fausse.

Problème des tours de Hanoï

Le problème des tours de Hanoï peut se décrire sous la forme d’un jeu (cf. Figure 2.1) : on dispose de trois piquets numérotés 1,2,3, et de n rondelles, toutes de diamètre diﬀérent. Initialement, toutes les rondelles se trouvent sur le piquet 1, dans l’ordre décroissant des diamètres (elle forment donc une pyramide). Le but du jeu est de déplacer toutes les rondelles sur un piquet de destination choisi parmi les deux piquets vides, en respectant les règles suivantes :
– on ne peut déplacer qu’une seule rondelle `a la fois d’un sommet de pile vers un autre piquet ;
– on ne peut pas placer une rondelle au-dessus d’une rondelle de plus petit diamètre. Ce problème admet une résolution récursive élégante qui comporte trois étapes :
déplacement des n − 1 rondelles supérieures du piquet origine vers le piquet intermédiaire par un appel récursif `a l’algorithme.
déplacement de la plus grande rondelle du piquet origine vers le piquet destination.
déplacement des n − 1 rondelles du piquet intermédiaire vers le piquet destination par un appel récursif `a l’algorithme.
Cet algorithme, que l’on appelle Hanoï , suit l’approche diviser pour régner : la phase de division consiste toujours `a diviser le problème de taille n en deux sous-problèmes de taille n − 1 et 1 respectivement. La phase de règne consiste `a appeler récursivement l’algorithme Hanoï sur le sous-problème de taille n − 1. Ici, il y a deux ≪ séries ≫ d’appels récursifs par sous-problème de taille n − 1 (étapes 1. et 3.). La phase de combinaison des solutions des sous-problèmes est inexistante ici. On donne ci-après le programme C implémentant l’algorithme Hanoï :
1 void Hanoi(int n, int i, int j) {
int intermediate = 6-(i+j);
3if (n > 0) {
Hanoi(n-1,i,intermediate);
printf(« Mouvement du piquet %d vers le piquet %d.\n »,i,j);
Hanoi(n-1,intermediate,j);
}
}
9 int main(int argc, char* argv[]) {
Hanoi(atoi(argv[1]),1,3);
}
On constate qu’ici la condition de terminaison est n = 0 (l’algorithme ne fait des appels récursifs que si n > 0) et pour cette valeur l’algorithme ne fait rien. Le lecteur est invité `a vérifier que l’exécution de Hanoï(3,1,3) donne :
Complexité de l’algorithme. Calculer la complexité d’un algorithme récursif peut parfois sembler compliqué, mais il suﬃt en général de se ramener `a une relation définissant une suite récurrente. C’est ce que l’on fait ici. Soit T (n) la complexité (ici, le nombre de déplacements de disques) nécessaire `a la résolution du problème sur une entrée de taille n par l’algorithme Hanoï . En décomposant la complexité de chaque étape on trouve : l’étape de division ne coûte rien, l’étape de règne coûte le prix de deux mouvements de taille n − 1 et l’étape de combinaison coûte le mouvement du grand disque, soit 1. On a T (0) = 0, T (1) = 1, et, pour n ≥ 2,
T (n) = D(n) + R(n) + C(n) = 0 + 2 × T (n − 1) + 1.
En développant cette expression, on trouve
T (n) = 2nT (0) + 2n−1 + . . . + 2 + 1,
soit T (n) = 2n−1 + . . . + 2 + 1 = 2n − 1.
Ainsi, la complexit´ de cet algorithme est exponentielle en la taille de l’entrée. En fait, ce caract`ere exponentiel ne dépend pas de l’algorithme en lui-mˆeme, mais est intrins`eque au probl`eme des tours de Hano¨ı : montrons en eﬀet que le nombre minimal minn de mouvements de disques `a eﬀectuer pour résoudre le probl`eme sur une entrée de taille n est exponentiel en n. Pour cela, nous observons que le plus grand des disques doit nécessairement ˆetre déplac´ au moins une fois. Au moment du premier mouvement de ce grand disque, il doit ˆetre seul sur un piquet, son piquet de destination doit ˆetre vide, donc tous les autres disques doivent ˆetre rangés, dans l’ordre, sur le piquet restant. Donc, avant le premier mouvement du grand disque, on aura dˆu déplacer une pile de taille n − 1. De mˆeme, apr`es le dernier mouvement du grand disque, on devra déplacer les n − 1 autres disques ; ainsi, minn ≥ 2minn−1 +1. Or, dans l’algorithme Hano , le nombre de mouvements de disques vérifie exactement cette egalit´ (on a T (n) = minn). Ainsi, cet algorithme est optimal, et la complexit´ exponentielle est intrins`eque au probl`eme.

⋆ Complexite Spatiale des Appels Recursifs

Notons que l’implémentation que nous donnons de l’algorithme Hano n’est pas stan-dard : l’algorithme est en général programmé `a l’aide de trois piles (cf. section 3.3.1), mais comme nous n’avons pas encore etudié cette structure de donnée, notre algorithme se contente d’aﬃcher les opérations qu’il eﬀectuerait normalement. En utilisant des piles, la complexit´ spatiale serait Θ(n) (correspondant `a l’espace nécessaire pour sto-cker les n disques). Ici il n’y a pas d’allocation mémoire, mais la complexit´ spatiale est quand mˆeme Θ(n) : en eﬀet, chaque appel récursif nécessite d’allouer de la mémoire (ne serait-ce que pour conserver l’adresse de retour de la fonction) qui n’est libérée que lorsque la fonction appelée récursivement se termine. Ici le programme utilise jusqu’`a n appels récursifs imbriqués donc sa complexit´ spatiale est Θ(n). Il n’est pas courant de prendre en compte la complexit´ spatiale d’appels récursifs imbriqués, car en général ce nombre d’appels est toujours relativement faible.

Algorithmes de tri

Nous continuons ici l’étude de méthodes permettant de trier des données indexées par des clefs (ces clefs sont munies d’une relation d’ordre et permettent de conduire le tri). Il s’agit de réorganiser les données de telle sorte que les clefs apparaissent dans un ordre bien détermin´ (alphabétique ou numérique le plus souvent).
Les algorithmes simples (comme le tri par insertion, mais aussi le tri par sélection ou le tri `a bulle) sont `a utiliser pour des petites quantités de données (de l’ordre de moins de 100 clefs), ou des données présentant une structure particuli`ere (données compl`etement ou presque triées, ou comportant beaucoup de clefs identiques).
Pour de grandes quantités de données aléatoires, ou si l’algorithme doit ˆetre utilisé un grand nombre de fois, on a plutˆot recours `a des méthodes plus sophistiquées. Nous en présentons deux ici : le tri fusion et le tri rapide. Tous deux sont de nature récursive et suivent l’approche diviser pour régner.

Le tri fusion

Cet algorithme repose sur le fait que fusionner deux tableaux triés est plus rapide que de trier un grand tableau directement. Supposons que l’algorithme prenne en entrée un tableau de n eléments dans un ordre quelconque. L’algorithme commence par diviser le tableau des n eléments en deux sous-tableaux de n2 eléments chacun (étape diviser). Les deux sous-tableaux sont triés de mani`ere récursive 1 en utilisant toujours le tri fusion (régner) ; ils sont ensuite fusionnés pour produire le tableau trié (combiner).
L’algorithme de tri fusion (merge sort en anglais) du tableau d’entiers tab entre les indices p et r est le suivant :
1 void merge_sort(int* tab, int p, int r) {
int q;
if (r-p > 1) {
4q = (p+r)/2;
merge_sort(tab,p,q);
merge_sort(tab,q,r);
merge(tab,p,q,r);
}
}
La procédure fusion (la fonction merge décrite ci-dessous) commence par recopier les deux sous-tableaux triés tab[p]…tab[q-1] et tab[q]…tab[r-1] ≪ dos-`a-dos 2 ≫ dans un tableau auxiliaire tmp. L’intérˆet de cette fa¸con de recopier est que l’on n’a alors pas besoin de rajouter de tests de fin de sous-tableaux, ni de case supplémentaire contenant le symbole par exemple `a chacun des sous-tableaux. Ensuite, merge remet dans tab les eléments du tableau tmp trié, mais ici le tri a une complexit´ linéaire (Θ(n)) puisque tmp provient
La récursion s’arrˆete lorsque les sous-tableaux sont de taille 1, donc trivialement triés.
Ainsi, tmp est le tableau [tab[p],…,tab[q-1],tab[r-1],…,tab[q]]. de deux sous-tableaux déj`a triés ; le procéd´ est alors le suivant : on part de k = p, i = p et j = r − 1, et on compare tmp[i-p] avec tmp[j-p]. On met le plus petit des deux dans tab[k] ; si c’est tmp[i-p], on incrémente i, sinon, on décrémente j ; dans tous les cas, on incrémente k. On continue jusqu’`a ce que k vaille r.
1 void merge(int* tab, int p, int q, int r) {
int* tmp = (int* ) malloc((r-p)*sizeof(int ));
3int i,j,k;
4for (i=p; i<q; i++) {
5tmp[i-p] = tab[i];
}
for (i=q; i<r; i++) {
tmp[r-p-1-(i-q)] = tab[i];
}
i=p;
j=r-1;
for (k=p; k<r; k++) {
if (tmp[i-p] < tmp[j-p]) {
tab[k] = tmp[i-p];
i++;
} else {
tab[k] = tmp[j-p];
j–;
}
}
free(tmp);
}
Ainsi, au début de chaque itération de la boucle pour k, les k − p eléments du sous-tableau tab[p]…tab[k-1] sont triés. Pour trier le tableau tab de taille n, on appelle merge sort(tab,0,n).

Note sur la Reallocation de Memoire

L’algorithme merge sort tel qu’il est écrit ne g`ere pas bien sa mémoire. En eﬀet, chaque appel `a la fonction merge commence par allouer un tableau tmp de taille r − p, et les opérations d’allocation mémoire sont des opération relativement coˆuteuses (longues `a exécuter en pratique). Allouer une mémoire de taille n a une complexit´ Θ(n), et réallouer de la mémoire `a chaque appel de merge ne change donc pas la complexit´ de l’algorithme. En revanche, en pratique cela ralentit beaucoup l’exécution du programme. Il serait donc plus eﬃcace d’allouer une fois pour toutes un tableau de taille n au premier appel de la fonction de tri et de passer ce tableau en argument `a toutes les fonctions afin qu’elles puissent l’utiliser. Cela demande cependant d’ajouter une fonction supplémentaire (celle que l’utilisateur va appeler en pratique), qui alloue de la mémoire avant d’appeler la fonction récursive merge sort.
Complexit´ du tri fusion. Evaluons `a présent la complexit´ en temps de l’algorithme merge sort, en termes de nombre de comparaisons de clefs. On note T (n), cette complexit´ pour une entrée de taille n.
La phase de division ne nécessite aucune comparaison. La phase de r`egne requiert deux fois le temps de l’algorithme merge sort sur un tableau de taille deux fois moindre, i.e. 2 × T (n2 ). La phase de recombinaison est la procédure merge. Lorsqu’appelée avec les param`etres (p, q, r), elle nécessite r − p comparaisons. On a donc :
T (n) = D(n) + R(n) + C(n) = 0 + 2 × T (n2) + n.
Supposons d’abord que n est une puissance de 2, soit n = 2k. Pour trouver la solution de cette récurrence, on construit un arbre de récursivit´ : c’est un arbre binaire dont chaque nœud représente le coˆut d’un sous-probl`eme individuel, invoqué `a un moment de la récursion. Le noeud racine contient le coˆut de la phase de division+recombinaison au niveau n de la récursivit´ (ici n), et ses deux sous-arbres représentent les coˆuts des sous-probl`emes au niveau n2 . En développant ces coˆuts pour n2 , on obtient deux sous-arbres, et ainsi de suite jusqu’`a arriver au coˆut pour les sous-probl`emes de taille 1. Partant de n = 2k, le nombre de niveaux de cet arbre est exactement log(n) + 1 = k + 1 (la hauteur de l’arbre est k). Pour trouver la complexit´ T (n), il suﬃt `a présent d’additionner les coˆuts de chaque noeud. On proc`ede en calculant le coˆut total par niveau : le niveau de profondeur 0 (racine) a un coˆut total égal `a n, le niveau de profondeur 1 a un coˆut total égal `a n2 + n2 ,…
le niveau de profondeur i pour 0 ≤ i ≤ k − 1 a un coˆut total de 2i × 2ni = n (ce niveau comporte 2i nœuds). Le dernier niveau correspond aux 2k sous-probl`emes de taille 1 ; aucun ne contribue `a la complexit´ en termes de nombre de comparaisons, donc le coˆut au niveau k est nul. Ainsi, chaque niveau, sauf le dernier, contribue pour n `a la complexit´ totale. Il en résulte que T (n) = k × n = n log(n).
Lorsque n n’est pas nécessairement une puissance de 2, on encadre n entre deux puissances de 2 consécutives : 2k ≤ n < 2k+1. La fonction T (n) étant croissante, on a T (2k) ≤ T (n) ≤ T (2k+1), soit k2k ≤ T (n) ≤ (k + 1)2k+1. Comme ⌊log(n)⌋ = k, on obtient une complexit´ en Θ(n log(n)).
Remarques :
– Le tri fusion ne se fait pas ≪ en place 3 ≫ : en eﬀet, la procédure merge sort nécessite un espace mémoire supplémentaire sous la forme d’un tableau (tmp) de taille n.
– Le calcul de complexit´ précédent est indépendant de la distribution des entiers `a trier : le tri fusion s’exécute en Θ(n log(n)) pour toutes les distributions d’entiers. La complexit´ en moyenne est donc égale `a la complexit´ dans le pire cas.

Le tri rapide

Le deuxi`eme algorithme de tri que nous étudions suit également la méthode diviser pour régner. Par rapport au tri fusion, il présente l’avantage de trier ≪ en place ≫. En
Un tri se fait ≪ en place ≫ lorsque la quantité de mémoire supplémentaire – la cas echéant – est une petit constante (indépendante de la taille de l’entrée).
revanche, son comportement dépend de la distribution de son entrée : dans le pire cas, il poss`ede une complexit´ quadratique, cependant, ses performances en moyenne sont en Θ(n log(n)), et il constitue souvent le meilleur choix en pratique 4. Le fonctionnement de l’algorithme sur un tableau tab `a trier entre les indices p et r est le suivant :
1 void quick_sort(int* tab, int p, int r) {
int q;
if (r-p > 1) {
q = partition(tab,p,r);
quick_sort(tab,p,q);
quick_sort(tab,q+1,r);
}
}
La procédure partition détermine un indice q tel que, `a l’issue de la procédure, pour p ≤ i ≤ q − 1, tab[i] ≤ tab[q], et pour q + 1 ≤ i ≤ r − 1, tab[i] > tab[q] (les sous-tableaux tab[i]…tab[q-1] et tab[q+1]…tab[r-1] n’étant pas eux-mˆemes triés). Elle utilise un elément x = tab[p] appel´ pivot autour duquel se fera le partitionnement.
1 int partition(int* tab, int p, int r) {
int x = tab[p];
3int q = p;
4int i,tmp;
5for (i=p+1; i<r; i++) {
6if (tab[i] <= x) {
q++;
tmp = tab[q];
tab[q] = tab[i];
10tab[i] = tmp;
}
}
tmp = tab[q];
tab[q] = tab[p];
tab[p] = tmp;
return q;
}
`
A la fin de chacune des itérations de la boucle for, le tableau est divisé en trois parties :
∀i, p ≤ i ≤ q, tab[i] ≤ x
∀i, q + 1 ≤ i ≤ j − 1, tab[i] > x
L’ordre de grandeur de complexit´ en termes de nombre de comparaisons, mais aussi de nombre d’opérations elémentaires (aﬀectations, incrémentations) est le mˆeme que pour le tri fusion, mais les constantes cachées dans la notation Θ sont plus petites.
Pour j ≤ i ≤ r, les clefs tab[i] n’ont pas de lien fixé avec le pivot x (éléments non encore traités).
Si le test en ligne 6 est vrai, alors l’élément en position j est inférieur ou égal `a x, donc on le décale le plus `a gauche possible (lignes 8 `a 10) ; mais on incrémente d’abord q (ligne 7) de fa¸con `a pouvoir insérer cet elément entre tab[p] et tab[q] strictement. A l’issue de la boucle for sur j, tous les eléments de tab[p]…tab[r-1] inférieurs ou égaux `a x ont et´ placés `a gauche de tab[q] (et `a droite de tab[p]) ; il ne reste donc plus qu’`a mettre x `a la place de tab[q] (lignes 13 `a 15).
Complexit´ du tri rapide. La complexit´ de l’algorithme quick sort dépend du ca-ract`ere equilibré ou non du partitionnement, qui lui-mˆeme dépend de la valeur du pivot choisi au départ. En eﬀet, si x = tab[p] est inférieur `a tous les autres eléments du tableau, la procédure partition découpera le tableau initial en deux sous-tableaux extrˆemement déséquilibrés : l’un de taille 0 et l’autre de taille n − 1. En particulier si le tableau est déj`a trié (ou inversement trié), cette configuration surviendra `a chaque appel récursif. Dans ce cas, le temps d’exécution T (n) de l’algorithme satisfait la récurrence

1 Complexite
1.1 Definitions
1.1.1 Comparaison asymptotique de fonctions
1.1.2 Complexit´e d’un algorithme
1.1.3 Complexit´e spatiale, complexit´e variable
1.2 Un seul probl`eme, quatre algorithmes
1.3 Un premier algorithme pour le tri
2 Recursivite
2.1 Conception des algorithmes
2.2 Probleme des tours de Hanoı
2.3 Algorithmes de tri
2.3.1 Le tri fusion
2.3.2 Le tri rapide
2.3.3 Complexite minimale d’un algorithme de tri
2.4 Resolution d’equations de recurrence
2.4.1 R´ecurrences lineaires
2.4.2 ⋆ R´ecurrences de partitions
2.5 ⋆ Complements
2.5.1 ⋆ Recursivit´e terminale
2.5.2 ⋆ Derecursification d’un programme
2.5.3 ⋆ Ind´ecidabilit´e de la terminaison
3 Structures de Donnees
3.1 Tableaux
3.1.1 Allocation m´emoire d’un tableau
3.1.2 ⋆ Compl´ement : allocation dynamique de tableau
3.2 Listes chaˆın´ees
3.2.1 Op´erations de base sur une liste
3.2.2 Les variantes : doublement chaˆın´ees, circulaires..
3.2.3 Conclusion sur les listes
3.3 Piles & Files
3.3.1 Les piles
4 Recherche en table
4.1 Introduction
4.2 Table `a adressage direct
4.3 Recherche s´equentielle
4.4 Recherche dichotomique
4.5 Tables de hachage
4.6 Tableau r´ecapitulatif des complexit´es
5 Arbres
5.1 Pr´eliminaires
5.1.1 D´efinitions et terminologie
5.1.2 Premi`eres propri´et´es
5.1.3 Repr´esentation des arbres
5.2 Utilisation des arbres
5.2.1 ´Evaluation d’expressions & parcours d’arbres
5.2.2 Arbres Binaires de Recherche
5.2.3 Tas pour l’impl´ementation de files de priorit´e
5.2.4 Tri par tas
5.3 Arbres ´equilibr´es
5.3.1 R´e´equilibrage d’arbres
5.3.2 Arbres AVL
6 Graphes
6.1 D´efinitions et terminologie
6.2 Representation des graphes
6.2.1 Matrice d’adjacence
6.2.2 Liste de successeurs
6.3 Existence de chemins & fermeture transitive
6.4 Parcours de graphes
6.4.1 Arborescences
6.4.2 Parcours en largeur
6.4.3 Parcours en profondeur
6.5 Applications des parcours de graphes
6.5.1 Tri topologique
6.5.2 ⋆ Calcul des composantes fortement connexes
6.5.3 Calcul de chemins optimaux
7 Recherche de motifs
7.1 Definitions
7.2 L’algorithme de Rabin-Karp
7.3 Automates pour la recherche de motifs . .
7.3.1 Automates finis
7.3.2 Construction d’un automate pour la recherche de motifs
7.3.3 ⋆ Reconnaissance d’expression regulieres