optimisation d'un algorithme récursif
Répondre à la discussion
Affichage des résultats 1 à 9 sur 9

optimisation d'un algorithme récursif



  1. #1
    kizakoo

    optimisation d'un algorithme récursif


    ------

    Bonsoir, on nous demande dans un exo de donner la fonction permettant de calculer f (voir la photo ci-dessous) de complexité en temps minimale :

    Nom : recu.jpg
Affichages : 105
Taille : 38,9 Ko

    L'algorithme de calcul direct est un copier-coller de la formule mathématique mais sa complexité est conséquente
    merci de votre aide

    -----
    Dernière modification par kizakoo ; 03/01/2020 à 02h54.

  2. #2
    CM63

    Re : optimisation d'un algorithme récursif

    Et quelle est ta question ? (à part j'aimerais qu'on fasse le travail à ma place).

  3. #3
    Jack
    Modérateur

    Re : optimisation d'un algorithme récursif

    Je ne vois pas l'intérêt de résoudre cet algorithme de manière récursive.

    Il faudra gentiment signaler à ton prof qu'arithmétique ne prend pas de 'y'

  4. #4
    pm42

    Re : optimisation d'un algorithme récursif

    Citation Envoyé par Jack Voir le message
    Je ne vois pas l'intérêt de résoudre cet algorithme de manière récursive.
    Je suis perplexe aussi. L'énoncé semble bien compliqué et sauf à avoir la suite, je dirais que la réponse serait d'utiliser la mémoïsation (https://fr.wikipedia.org/wiki/Mémoïsation) et donc d'échanger de la CPU contre de la mémoire.

    Mais si c'est le cas, une grande partie de l'énoncé ne sert pas à grand chose.

  5. A voir en vidéo sur Futura
  6. #5
    kizakoo

    Re : optimisation d'un algorithme récursif

    Bonjour, merci de vos retours.
    Je pense qu'il y'a une optimisation de l'algorithme parce que pour le calcul de f(n-3) on a besoin de f(n-5) et pour le calcul de f(n-2) on a besoin de f(n-5), f(n-5) sera alors calculée deux fois ...
    Une optimisation consistera alors à calculer une valeur qu'une seule fois.

  7. #6
    pm42

    Re : optimisation d'un algorithme récursif

    Citation Envoyé par kizakoo Voir le message
    Une optimisation consistera alors à calculer une valeur qu'une seule fois.
    Tu lis les réponses ?

  8. #7
    kizakoo

    Re : optimisation d'un algorithme récursif

    Bonsoir, oui pm42 j'ai lu ta réponse et voici mes réponses à toutes les consignes.
    Ci-dessous l'énoncé complet :

    enoncé.jpg

    Voici mes réponses :

    rep1.jpg

    rep2.jpg

    pour le calcul de la complexité dans la question 3, on ne peut pas appliquer le master theorem et je n'ai pas eu d'idées de comment pouvons-nous calculer la complexité (la hauteur de l'arbre d'appels ? le nombre de nœuds de l'arbre d'appels ?)

    Merci de vos retours sur ma rédaction et bonne soirée !

  9. #8
    kizakoo

    Re : optimisation d'un algorithme récursif

    Pouvez-vous m'aider s'il vous plait ?
    Mes réponses sont-elles correctes ?
    Merci infiniment

  10. #9
    jacknicklaus

    Re : optimisation d'un algorithme récursif

    réponse 1 : ok
    réponse 2 : pourquoi ne développes tu pas f(4), f(5) etc..., bref tous les f(n) tels que n >= 4 ? Seuls les n < 4 sont évalués directement à 1. En faisant ca, tu comprendras bien mieux comment évolue le nombre de calculs f(x) à faire pour évaluer f(n) si n >= 4.
    réponse 3 : voir dessus
    réponse 4 : c'est faux. le 1er cas "si n= 0 ou n = 1 table[n] = n" est fantaisiste et n'a aucun rapport avec l'énoncé.
    There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.

Discussions similaires

  1. algorithme par insertion récursif
    Par candelaria dans le forum Programmation et langages, Algorithmique
    Réponses: 1
    Dernier message: 13/12/2018, 21h18
  2. complexité d'un algorithme recursif
    Par bmce dans le forum Programmation et langages, Algorithmique
    Réponses: 5
    Dernier message: 08/12/2016, 07h25
  3. algorithme d'optimisation
    Par obo_ouma dans le forum Programmation et langages, Algorithmique
    Réponses: 4
    Dernier message: 10/12/2014, 15h31
  4. Algorithme d'optimisation
    Par Glouboz dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 02/05/2010, 23h56
  5. [UNIX] Path recursif
    Par invite6ed3677d dans le forum Logiciel - Software - Open Source
    Réponses: 2
    Dernier message: 23/10/2007, 10h31