Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Importer

Bienvenue sur Scribd !

  • 42 vues

    FeuilleRecursivite 2020

    Transféré par

    kukis14

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    FeuilleRecursivite 2020

    Transféré par

    kukis14
    42 vues3 pages

    Titre original

    FeuilleRecursivite_2020

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    42 vues3 pages

    FeuilleRecursivite 2020

    Transféré par

    kukis14

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    sur 3

    TP : Récursivité

    Exercices à préparer impérativement : 1, 2.


    Exercices faciles à préparer éventuellement : 6.
    Exercices que nous travaillerons en TP : 3, 4.

    I) Une version récursive d’un algorithme classique


    Exercice 1 (Dichotomie dans une liste)
    Écrire une fonction récursive dichoListeRec(L, x) qui recherche par dichotomie la présence d’un élé-
    ment x dans une liste triée L.

    II) Tout sur Fibonacci


    On définit la suite (un ) par

    u0 = 0 u1 = 1 ∀n ∈ N\{0, 1} un = un−1 + un−2

    C’est la « suite de Fibonacci », une suite d’entiers qui a été utilisée au XIIIe siècle pour décrire la croissance
    d’une population de lapins (on compte les couples à chaque génération, sans décès).
    Vous remarquerez que c’est une suite récurrente linéaire : vous connaissez des techniques pour calculer
    directement le n-ième terme. Mais ces techniques, appliquées à l’informatique, font utiliser des float et donc
    potentiellement perdre en précision (en fait, avec le théorème des accroissements finis on réussit à maîtriser
    l’erreur... mais ce n’est pas le sujet ici).
    Vous aurez éventuellement besoin d’augmenter le niveau de récursion autorisé par Python :

    1 import sys
    2 sys.setrecursionlimit(10000)

    A) Version récursive naïve


    Exercice 2
    1) Écrire une fonction récursive qui calcule le n-ième terme de la suite de Fibonacci.
    2) Tester la rapidité (un n raisonnable pourra être obtenu par dichotomie – à la main). Que constate-t-on ?
    3) Tracer le nombre d’appels récursifs en fonction de n, à l’aide d’un compteur. On pourra s’inspirer de
    l’exercice 4 du TP complexité. Que peut-on conjecturer pour la complexité ?
    4) (bonus) Déterminer, par une preuve rigoureuse, la complexité de l’algorithme.

    B) En partant du bas
    Exercice 3
    Écrire un algorithme itératif (c’est-à-dire une boucle) qui calcule un « du bas vers le haut », donc en partant
    de u0 et u1 . Donner la complexité de cet algorithme.

    C) Versions avec mémoïsation


    On revient à des algorithmes récursifs, en essayant d’améliorer la complexité.

    Exercice 4 (Formule de récurrence usuelle)


    Améliorer l’algorithme récursif naïf en stockant les uk déjà calculés (et donc en vérifiant, à chaque étape,
    si on a ou non déjà calculé le un que l’on cherche). Donner la complexité du nouvel algorithme (on pourra
    commencer par tracer la courbe du compteur en fonction de n).

    1
    TP Récursivité

    Dictionnaire. Pour l’exercice suivant, vous aurez besoin d’une structure de donnée appelée dictionnaire.
    Une liste L est un ensemble ordonné d’éléments auxquels on accède via leur indice : L[i].
    Un dictionnaire suit le même principe, mais au lieu d’un indice, on utilise une clef que l’on définit soi-même :
    c’est un semble de paires clef : valeur. Un exemple en forme d’annuaire :
    mesNum = {’Ariane’: 0620, ’Pierre’: 0720} Analogue de L = [2, 4, 1].
    mesNum[’Ariane’] Analogue de L[i] pour une liste.
    mesNum[’Thesee’] = 0454 Rentre une nouvelle clef.
    ’Egee’in mesNum Teste la présence d’une clef.

    Exercice 5 (Autre formule de récurrence)


    (
    u2n+1 = u2n+1 + u2n
    On admet les formules : ∀n ∈ N∗
    u2n = 2un un−1 + u2n
    Écrire un algorithme récursif avec mémoïsation qui utilise ces formules. Quelle est sa complexité ? (sans
    preuve : on pourra se contenter de faire un calcul dans le cas où n est d’une forme sympathique).

    III) Images
    Exercice 6 (Fractales : tapis de Sierpiński)
    Le but de cet exercice est de tracer un Tapis de Sierpiński, dans une image carrée de côté 3n .
    Le procédé est le suivant : on part d’une image noire, et on « enlève » le carré central de côté 3n−1 . Et ainsi
    de suite :

    Vous utiliserez une fonction récursive, des boucles, du découpage en tranches (« slicing »).
    Pour éviter que Python lisse l’affichage on fixe le paramètre interpolation à ’none’ :
    plt.imshow(a, interpolation=’none’)

    Exercice 7 (Fractales : Mandelbrot)


    On pose M = 20 et m = 10. À un nombre x quelconque, on associe la suite (un ) définie par

    u0 = 0 et un+1 = u2n + x pour n > 0

    S’il existe, on note k le plus petit entier tel que l’on ait 0 6 k 6 m et |uk | > M .
    On définit alors la fonction f par (
    k si k existe
    f : x 7→
    m + 1 sinon
    1) Coder f .
    2) Tracer l’allure de la courbe représentative de la fonction f sur [−2, 2], en créant une liste LX de 401
    valeurs équiréparties entre −2 et 2 inclus.
    3) Construire le tableau des valeurs f (x + iy) où x prend 101 valeurs comprises entre −2 et 0.5 et y prend
    101 valeurs entre −1.1 et 1.1.
    On rappelle que le nombre complexe i est représenté par 1j. Par exemple, le complexe 1 + 2i est
    représenté par 1+2j, le complexe 1 + i par 1+1j.
    4) Tracer l’image que code ce tableau. Quels paramètres peut-on modifier pour obtenir une meilleure
    résolution ?

    Exercice 8 (Remplissage d’un contour)


    Il est nécessaire de sauver sur votre disque l’image

    http://www.normalesup.org/~dconduche/informatique/PC/TP/motif.png

    2
    TP Récursivité

    Le but de cet exercice est de remplir une zone blanche de l’image, sans dépasser la ligne noir : remplir soit
    l’intérieur soit l’extérieur du contour.
    1) Écrire une fonction chargeImage qui charge l’image dans un tableau NumPy.
    2) Bien que l’image soit petite, il faut augmenter le niveau de récursion autorisé par Python (cf le début
    du TP Fibonacci).
    Écrire une fonction récursive remplissage qui prend en argument les coordonnées d’un pixel. (sup-
    posé blanc) et qui rempli la zone blanche qui contient le pixel, de proche en proche : la fonction colorie
    le pixel de départ, puis regarde si les pixels adjacents sont blanc ou noir, colorie les pixels blancs, et
    ainsi de suite.

    Vous aimerez peut-être aussi