Cours: génie algorithmique · le paradigme ‘’diviser pour régner’’ Dr....

1

Cours: génie algorithmiquecours 3:La récursivité et

le paradigme ‘’diviser pour régner’’

Dr. Dhouha Maatar Razgallah2019/2020

2

Outline

Algorithmes récursifs

Application: factorielle

Application: tours de Hanoi

Paradigme ‘’diviser pour régner’’

Application: recherche dichotomique

Application: recherche maximum

2

3

Algorithmes récursifs Définition

La récursivité est le fait pour une méthode de s'appeler elle même.On parle alors de méthode récursive.

Exemple : Le calcul de la factorielle de N.N != N*(N-1)*(N-2)*…*2*1 , on peut écrire ainsi N != N*(N-1)!

La factorielle de N est définie en fonction de la factorielle de N-1La fonction a besoin d’elle-même pour donner un résultat Pour calculer N! il faut savoir calculer (N-1) ! et pour calculer (N-1) ! Il fautsavoir calculer (N-2) ! et ainsi jusqu’à 1! qui est égal à 1 et qui permet à larécursivité de s’arrêter après une série d’auto appels.-> Il est impératif donc de prévoir une condition d’arrêt à la récursion sinon leprogramme ne s’arrête jamais! A l’opposé de la récursion, l’itération utilise les structures de contrôlerépétitives comme POUR, TANT QUE, REPETER JUSQU'À

4

Algorithmes récursifs Itératif vers récursif

3

5

Algorithmes récursifs Evolution d’un appel récursif

L’exécution d’un appel récursif passe par deux phases, la phase dedescente et la phase de remontée.

Dans la phase de descente, chaque appel récursif fait à son tour un appelrécursif.

En arrivant à la condition terminale, on commence la phase de remontéequi se poursuit jusqu’à ce que l’appel initial soit terminé, ce qui termine leprocessus récursif.

Exemple:

6

Algorithmes récursifs types de récursivité

Récursivité simple

C’est une fonction qui contient dans son corps un seul appel récursif.

Exemple: Fonction Factorielle

4

7

Algorithmes récursifs types de récursivité

Récursivité multiple

La fonction contient plus qu’un appel récursif dans son corps.

Exemple: Calcul du nombre de combinaisons en se servant de la relation de Pascal:

8

Algorithmes récursifs types de récursivité

Récursivité mutuelle

Des fonctions sont dites mutuelles récursives si elles dépendent les unes des autres.

Exemple: La définition de la parité.

5

9

Algorithmes récursifs types de récursivité

Récursivité imbriquée

ça consiste à faire un appel récursif à l’intérieur d’un autre appel récursif.

Exemple: La fonction d’Ackermann.

10

Algorithmes récursifs terminale vers non terminale

Récursivité terminale vers non terminale

Un module récursif est dit terminal si aucun traitement n’est effectué après la remontée d’un appel récursif (sauf le retour du module).

Un module récursif est dit non terminal si le résultat de l’appel récursif est utilisé pour réaliser un traitement (en plus du retour du module).

Exemple: fonction factorielle

6

11

Algorithmes récursifs terminale vers non terminale

Récursivité terminale vers non terminale

12

Algorithmes récursifs Calcul de complexité

La complexité d’un algorithme récursif se fait par la résolution d’uneéquation de récurrence en éliminant la récurrence par substitution deproche en proche.

Exemple 1 : La fonction factorielle

(avec T(n) le temps d’exécution nécessaire pour un appel à Facto(n)).

7

13

Algorithmes récursifs Calcul de complexité

Exemple 1 : La fonction factorielle

Pour calculer la solution générale de cette équation, on peut procéder parsubstitution:

14

Algorithmes récursifs Calcul de complexité

Exemple 2 : Tours de Hanoi

Déplacer n disques (empilés les unes sur les autres) d un piquet (A) vers unautre (B) en utilisant un troisième (c) comme intermédiaire.

Ce sont des piles donc on ne peut accéder qu’au disque du sommet.

Un disque ne peut jamais être placé au dessus d’un autre plus petit.

8

15

Algorithmes récursifs Calcul de complexité

Exemple 2 : Tours de Hanoi

Conception de la solution

16

Algorithmes récursifs Calcul de complexité

Exemple 2 : Tours de Hanoi

9

Calcul de complexité

17

Rappel Sommation

18

Principe:

Spécifier la solution du problème en fonction de la (ou des) solution(s) d’un(ou de plusieurs) sous-problème(s) plus simple(s) traité(s) de façon récursive.

Le paradigme ‘’diviser pour régner’’ parcourt trois étapes à chaque appelrécursif à savoir:

Diviser: le problème en un certain nombre de sous-problèmes de taillemoindre.

Régner: sur les sous-problèmes en les résolvant d’une façon récursive oudirectement si la taille d’un sous-problème est assez réduite.

Combiner: les solutions des sous-problèmes en une solution globalepour le problème initial.

Paradigme ‘’diviser pour régner’’ Principe

10

19

Paradigme ‘’diviser pour régner’’ Principe

Principe:

20

Formule de complexité:

Le temps d’exécution d’un algorithme ‘’diviser pour régner’’ se décomposesuivant les trois étapes du paradigme de base.

Diviser: le problème en a sous-problèmes chacun de taille 1/b de la tailledu problème initial. Soit D(n) le temps nécessaire à la division du problèmesen sous-problèmes.Régner: soit a T(n/b) le temps de résolution des a sous-problèmes.Combiner: soit C(n) le temps nécessaire pour construire la solution finaleà partir des solutions aux sous-problèmes.

Finalement le temps d’exécution global de l’algorithme est :T(n) = a T(n/b) +D(n) + C(n)

Soit la fonction f(n) qui regroupe D(n) et C(n). T(n) est alors définie:

T(n) = a T(n/b) +f(n)

Paradigme ‘’diviser pour régner’’ Complexité

11

21

Théorème de résolution de la récurrence

Paradigme ‘’diviser pour régner’’ Complexité

22

Exemple: recherche dichotomique

Soit Tab un tableau trié (ordre croissant) à n éléments.

La recherche par dichotomie compare l’élément cherché x avec l’élément en position m situé en position du milieu du sous-tableau:

• Si Tab[m] =x: alors on a trouvé l’élément x en position m. • Si Tab[m] > x: il est possible que x se trouve avant la position m du tableau.Il reste à traiter uniquement la moitié inférieure du tableau.• Enfin Si Tab[m] < x: il est possible que x se trouve après la position m. Il reste à traiter uniquement la moitié supérieure du tableau.

On continue ainsi la recherche jusqu’à trouver l’élément ou bien aboutir à un tableau de taille nulle, dans ce cas x n’est pas présent et la recherche s’arrête.

Paradigme ‘’diviser pour régner’’ recherche dichotomique

12

23

Exemple: recherche dichotomiqueFonction dicho _recursif (T:tab, borneinf,bornesup: entier; x: entier):booleenDebut T(n)Si (borneinf<= bornesup) alors

mil ← (borneinf + bornesup) div 2si (T[mil] = x) alors

retourner (vrai)sinon

si (T[mil] > x) alorsretourner dicho_recursif(T, borneinf, mil-1, x)

sinon T(n/2)retourner dicho_recursif(T, mil+1, bornesup, x)

finsiFinsi

sinon

retourner (faux) T(n) = T(n/2) +C Finsi

Fin

Paradigme ‘’diviser pour régner’’ recherche dichotomique

24

Complexité de recherche dichotomiqueD’après le théorème du paradigme ’’diviser pour régner’’, on a:

Complexité de l’algorithme de recherche dichotomique

Paradigme ‘’diviser pour régner’’ recherche dichotomique

13

25

Exemple : Recherche maximumSoit Tab un tableau à n éléments, écrire une fonction récursive permettant de

rechercher l’indice du maximum dans Tab en utilisant le paradigme‘’diviser pour régner’’.

Paradigme ‘’diviser pour régner’’ Recherche maximum

26

Exemple : Recherche maximum

Paradigme ‘’diviser pour régner’’ Complexité

14

27

Exemple : Recherche maximum

Complexité de l’algorithme de recherche du maximum

Paradigme ‘’diviser pour régner’’ Complexité