23
Principe et exemples Le paradigme « divide & conquer » III. Récursivité 1

1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

  • Upload
    others

  • View
    0

  • Download
    0

Embed Size (px)

Citation preview

Page 1: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Principe et exemples

Le paradigme « divide & conquer »

III. Récursivité 1

Page 2: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Récursivité 2

Algorithme récursif vs. itératif

Qui s’appelle lui-même vs. non

Lien filial avec les maths

Définition du terme d’une suite par une récurrence

Avantage

Une conception plus simple

moins de risque d’effets de bord

Inconvénient

Une complexité plus importante (pile d’appels)

plus lent

Récursivité Principe

Page 3: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Exemples 3

la factorielle

La puissance (exponentiation)

Le pgcd cf. Euclide

Récursivité Exemples

Page 4: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

La factorielle 4

1 si 0!

1 ! si 0

nn

n n n

Récursivité Exemples Factorielle Récursif

Page 5: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

La factorielle 5

1 si 0!

1 si 0

nn

n n

Récursivité Exemples Factorielle Itératif

Page 6: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

La puissance 6

1

1 si 0

si 0

n

n

na

na a

Récursivité Exemples Puissance Récursif

Page 7: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

La puissance 7

1 si 0

si 0

n

n

na a a n

Récursivité Exemples Puissance Itératif

Page 8: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Euclide 8

si 0

si 0ab

a ba b

b b

Récursivité Exemples Euclide Récursif

Page 9: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Euclide 9

Récursivité Exemples Euclide Itératif

Page 10: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Mais… 10

Cf. Euclide, il n’est pas toujours simple de transposer

Exemple : donner une version itérative de :

Récursivité Naturelle

Page 11: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Mais… 11

Récursivité Naturelle

Page 12: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Diviser pour régner 12

Principe

Scinder un problème en sous-problèmes

De tailles équivalentes

De même nature que le problème principal

Sous-traiter puis agréger les résultats

Paradigme de conception

Récursif + équilibrage

A la base de nombreux algorithmes puissants

En général O(…n) O(…lnn)

S’adapte très bien à un traitement distribué (//)

Récursivité Div & Conq Principe

Page 13: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Exemples notables 13

Tris en O(nlnn)

Tri rapide, tri fusion, …

Multiplication O(nvous le savez déjà)

Karatsuba et ses successeurs

Compilation

Analyse descendante

FFT, O(nlnn)

L’algorithme qui en accélère un tas d’autres

Imaginé par Gauss (1805)

Redécouvert par Cooley-Tukey (1965)

Récursivité Div & Conq Exemples

Page 14: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Exo: dichotomie 14

EN : Binary search algorithm

But : identifier une solution dans un espace de recherche

Stratégie

Diviser l’espace en deux

Décider dans quelle moitié d’espace chercher

Appliquer récursivement

Arrêter quand l’espace se réduit à un seul élément

Complexité : O(lnn)

Application

Recherche de racines de fonctions (théorème des valeurs intermédiaires)

Exercice

Concevoir un algorithme pour rechercher l’index, dans un tableau trié d’éléments 2 à 2 distincts, d’un élément donné

(et pour retourner 0 si cet élément n’est pas trouvé)

Récursivité Div & Conq Applications Dichotomie

Page 15: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Exo: dichotomie 15

Récursivité Div & Conq Applications Dichotomie

Page 16: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Exo: exponentiation rapide 16

Récursivité Div & Conq Applications Puissance

1

1 si 0

si 0

n

n

na

na a

2

1

2

1 si 0

si 0 et 1 2

si 0 et 0 2n

n n

n

a a a n n

a n n

Page 17: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Exo: exponentiation rapide 17

Récursivité Div & Conq Applications Puissance

O(n) O(lnn)

1 000 000 000 21

Sauriez-vous le démontrer ?

Page 18: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Multiplication de deux nombres en numération de position

Nombres de 2n chiffres

Décomposition en deux moitiés

Représentation algébrique de la multiplication naïve

Les multiplications sont plus coûteuses que les additions

Version naïve : 4 multiplications intermédiaires

Forme équivalente de Karatsuba

Complexification

Mémorisation et réutilisation de résultats intermédiaires

Ajout de 3 opérations additives supplémentaires

On tombe à 3 multiplications !

Application récursive du procédé : O(n2) O(n1,58)

Exo: multiplication de Karatsuba

n

M m

n

M m

A A b A

B B b B

2n n n n

M m M m M M M m m M m mAB A b A B b B A B b A B A B b A B

2n n

M M M m M m M M m m m mAB A B b A A B B A B A B b A B

18

Récursivité Div & Conq Applications Multiplication

Page 19: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Nous disposons d’utilitaires

longueur(N) : retourne le nombre de chiffres de N

droite(N, k) : supprime k chiffres sur la droite de N

gauche(N, k) : ajoute k de zéros sur la droite d’un Nombre

produit_scalaire(N, s) : simplement N + … + N, s fois

Principe

Si A < B, interchanger les opérandes

Mesurer les longueur lA et lB

Si B est un scalaire, terminaison : retourner le produit_scalaire

Sinon scinder A et B et produire les termes dérivés

Effectuer les 3 produits par délégation (appels récursifs)

Assembler et retourner le résultat

Exo: multiplication de Karatsuba 19

Récursivité Div & Conq Applications Multiplication

Page 20: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Exo: multiplication de Karatsuba 20

Récursivité Div & Conq Applications Multiplication

Page 21: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Exo: multiplication de Karatsuba 21

Récursivité Div & Conq Applications Multiplication

Page 22: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

Application : changement de base

Conception

Cela revient à évaluer un polynôme

Concevez la version naïve

Concevez une version qui réunit

Algorithme de Horner

Exponentiation rapide

Multiplication de Karatsuba

Comparez !

Pour conclure 22

Récursivité Conclusion

Page 23: 1 III. Récursivitéefreidoc.fr/L2 - PL2/SDD/Cours/2013-14.cours... · Si A < B, interchanger les opérandes Mesurer les longueur l A et l B Si B est un scalaire, terminaison : retourner

La version itérative est un peu plus performante que

la version récursive d’un même algorithme

Concevoir suivant le paradigme récursif du diviser

pour régner produira généralement un algorithme

radicalement plus performant que celui pensé

suivant un paradigme itératif

A retenir 23

Récursivité Conclusion