IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Mathématiques Discussion :

validité et terminaison d'un algo


Sujet :

Mathématiques

  1. #1
    Membre à l'essai
    Homme Profil pro
    Inscrit en
    Mai 2012
    Messages
    20
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Mai 2012
    Messages : 20
    Points : 18
    Points
    18
    Par défaut validité et terminaison d'un algo
    bonjour a tous,
    je dois démontrer la validité et la terminaison d'un algorithme en langage C que voici :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int FiboIt(n){
      if(n==0)return 0;
      int x=0,y=1,i=1,z;
      while(i<n){
        z=x+y;
        x=y;
        y=z;
        i++;
      }
      return y;
    }
    Démontrez la terminaison de la fonction FiboIt(n) pour tout n appartenant a N
    • Que valent les suites xi et yi en fonction de la suite de Fibonacci ?
    • Démontrez ce résultat par récurrence sur i
    • En déduire la validité de la fonction FiboIt
    • quelle est la complexité de la fonction FiboIt(n) ? justifiez votre réponse


    Pour la terminaison, il n'y a pas de problème mais je bloque pour la validité, il faut que je démontre d'abord le resultat par récurrence et je n'y arrive pas, j'ai supposé la propriété vrai au rang i et je veux montrer que ça l'est aussi au rang i+1 mais je n'aboutis pas si quelqu'un pouvait m'aider ça serait sympa
    (j'ai xi=yi-1 et yi=x(i-1)+y(i-1)
    merci d'avance

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par goldengear Voir le message
    Pour la terminaison, il n'y a pas de problème mais je bloque pour la validité, il faut que je démontre d'abord le resultat par récurrence et je n'y arrive pas, j'ai supposé la propriété vrai au rang i et je veux montrer que ça l'est aussi au rang i+1 mais je n'aboutis pas si quelqu'un pouvait m'aider ça serait sympa
    D'après le contenu de ta boucle:
    (5) Z[i+1] = X[i] + Y[i]
    (6) X[i+1] = Y[i]
    (7) Y[i+1] = Z[i+1]

    (5) et (6) --> (A) Z[i+1] = Y[i-1] + Y[i]
    (7) et (A) --> (B) Y[i+1] = Y[i-1] + Y[i]

    La formulation (B) est la définition de récurrence de la suite de Fibonacci. Reste à démontrer que Y[1]=1 et Y[2]=1, ce qui n'est pas très compliqué.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Membre à l'essai
    Homme Profil pro
    Inscrit en
    Mai 2012
    Messages
    20
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Mai 2012
    Messages : 20
    Points : 18
    Points
    18
    Par défaut
    merci de l'aide pseudocode.
    sinon pour la compéxité de l'alogo, est elle bien de O(n) car elle fait n-1 itération ? (et n-1 appartient a O(n)) ?

  4. #4
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par goldengear Voir le message
    merci de l'aide pseudocode.
    sinon pour la compéxité de l'alogo, est elle bien de O(n) car elle fait n-1 itération ? (et n-1 appartient a O(n)) ?
    Tout a fait.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Discussions similaires

  1. cherche algos Delphi pour : Huffman, R.S.A, D.E.S.
    Par X-Delphi dans le forum Débuter
    Réponses: 3
    Dernier message: 24/08/2002, 19h51
  2. Cherche l'algo crc 16 bits
    Par icepower dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 21/08/2002, 14h27
  3. Algo de calcul de FFT
    Par djlex03 dans le forum Traitement du signal
    Réponses: 15
    Dernier message: 02/08/2002, 18h45
  4. Algo de Hough et ou de Radon
    Par victorracine dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 29/07/2002, 12h09
  5. Recherche algo tree
    Par Anonymous dans le forum Algorithmes et structures de données
    Réponses: 10
    Dernier message: 24/05/2002, 14h44

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo