Discussion: Preuve de programme

  1. #1
    Futur Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    octobre 2016
    Messages
    11
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 20
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : octobre 2016
    Messages : 11
    Points : 9
    Points
    9

    Par défaut Preuve de programme

    Bonjour à tous,

    En cours on nous a donné un algorithme dont on doit faire la preuve (une preuve par induction), or je ne sais pas par où commencer car dans les différents exemples que l'on a eu en cours, ça n'a toujours été que sur une seule variable, or dans ce programme (qui développe le nombre a dans la base b, a et b étant des entiers supérieur ou égal à 0). Voici le programme :

    Dev(a, b) :

    si (a < b)

    renvoie a

    sinon

    afficher (a modulo b)

    renvoie Dev(a/b, b)

    Fin Dev

    Je ne demande pas la solution mais qu'on m'aide, c'est-à-dire comment trouver la base de la récurrence pour pouvoir commencer s'il vous plaît, je pense que la base doit commencer par a = 0 si c'est le cas quelle est la valeur de b s'il vous plaît ?

    je vous remercie d'avance et vous souhaite une bonne journée !

  2. #2
    Membre expert
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 488
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 488
    Points : 3 944
    Points
    3 944

    Par défaut

    il manque quelque définition
    "a" c'est quoi un entier naturel positif ou autre chose
    "b" c'est quoi ? (Idem A)
    DEBUT Dev(a, b) :
    SI b <> 0 ALORS // évite les division par zero
    SI (a < b) ALORS // ici tu as a < b
    renvoie a
    SINON
    afficher (a modulo b)
    renvoie Dev(a/b, b) // Ici tu vois la récurrence "a" devient "a/b" si b=1 que fait ton programme ?
    FIN SI
    FIN SI
    FIN Dev
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  3. #3
    Futur Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    octobre 2016
    Messages
    11
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 20
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : octobre 2016
    Messages : 11
    Points : 9
    Points
    9

    Par défaut

    Bonsoir Anapurna,
    A est supérieur à 0
    B strictement supérieur à 1
    Je pense en tout cas que c'est cela car vous avez marqué que se passe t'il si b=1, eh bien ça ne s'arrêterait pas donc comme base on à A = 0 et B = 2 ? Est ce bien cela (car je ne suis vraiment pas sûr )?
    Bonne soirée

  4. #4
    Membre expert
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 488
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 488
    Points : 3 944
    Points
    3 944

    Par défaut

    salut,

    regarde bien la première condition il faut absolument que a soit supérieur a b pour que la boucle continu
    si a < b on arrête la boucle et on affiche a donc la condition de rupture est .... a < b
    si b est inférieur a 1 on multiplie
    exemple a=3 b = 0.5 la prochaine boucle seras 3/1/2 = 3*2 = 6
    donc effectivement b doit être strictement supérieur a 1 sinon on se retrouve avec des boucle infini
    et faut que a > b donc a > 1 aussi
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  5. #5
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    496
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 496
    Points : 964
    Points
    964
    Billets dans le blog
    5

    Par défaut Preuve de programme

    Bonjour,

    Il s'agit apparemment d'un programme récursif visant le développement d'un entier en base (b): ce terme ne peut donc être inférieur à 2.

    Pour décrire correctement ce qui se passe, il faut absolument discerner les valeurs successives de la variable (a), qui n'est en soi qu'une mémoire dont le contenu change à chaque étape.

    Regardons par exemple le développement d'un entier en base (10), soit a = 1843 . On aura schématiquement:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    a0 = 1843 ---- a1 = a0 DIV b = 0184 ---- a2 = a1 DIV b = 0018 ---- a3 = a2 DIV b = 0001 ---- a4 = a3 DIV b = 0000
     |              |                         |                         |                         |
     |              |                         |                         |                         |
    a0 MOD b = 3   a1 MOD b = 4              a2 MOD b = 8              a3 MOD b = 1              a4 MOD b = 0
    La fonction récursive Dev(a, b) réitère la division entière de (a) par (b) jusqu'à ce que l'on obtienne la condition d'arrêt (a<b) - cas précédent l'apparition définitive de termes nuls, donc la fin du développement du nombre initial (a0) dans la base considérée.
    On récupère donc successivement: 3 , 4 , 8 , 1 par l'instruction afficher (a modulo b).

    Je ne vois pas très bien en quoi consiste la preuve d'un programme, si ce n'est vérifier dans le détail la tâche accomplie; les remarques précédentes devraient te permettre de mettre en forme la réponse demandée.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  6. #6
    Membre habitué

    Homme Profil pro
    Étudiant
    Inscrit en
    août 2017
    Messages
    68
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val d'Oise (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : août 2017
    Messages : 68
    Points : 189
    Points
    189
    Billets dans le blog
    1

    Par défaut

    Bonjour,
    Pour prouver la correction d'un algorithme récursif, le plus simple est de faire une preuve par induction.
    En gros:
    • Tu testes d'abord la condition de fin de boucle, c'est-à-dire, si a < b alors tu affiches simplement a qui est la représentation de a dans la base b, évidemment
    • Maintenant, soit a > b. On suppose le résultat vrai pour tout k tel que 0 <= k <= a-1, c'est-à-dire que dev(k,b) renvoie l'écriture de k dans la base b.
      Dans ce cas, comme a > b, alors on affiche a % b puis comme a / b < a on affiche a / b dans la base b.
      Voilà la structure, il te reste à rédiger la fin, et bien rédiger le début que j'ai écrit vraiment à l'arrache

  7. #7
    Futur Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    octobre 2016
    Messages
    11
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 20
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : octobre 2016
    Messages : 11
    Points : 9
    Points
    9

    Par défaut

    Bonjour à tous et désolé de ne répondre que maintenant mais j'ai eu des soucis qui ont fait qu je ne pouvais étudier ... Enfin bref, d'abord merci à tous pour vos réponses, Lulzec oui c'est d'ailleurs ce que l'on fait en cours, donc ici ma condition d'arrêt c'est effectivement a < b, cependant je ne comprends pas pourquoi tu écris "puisque a/b < a alors on affiche a/b dans la base b" sinon je pense avoir pigé le truc manque plus que de m'entraîner un peu je pense
    Bonne journée et merci d'avance

  8. #8
    Membre habitué

    Homme Profil pro
    Étudiant
    Inscrit en
    août 2017
    Messages
    68
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val d'Oise (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : août 2017
    Messages : 68
    Points : 189
    Points
    189
    Billets dans le blog
    1

    Par défaut

    En fait, quand tu es dans le cas a > b, alors tu passes par le "else" de la condition. Tu affiches donc d'abord a mod b.
    Une fois ça fait, tu fait un appel à Dev(a/b, b). Comme b > 1, alors a/b < a. Tu peux donc appliquer ton hypothèse de récurrence, qui ici est: "Dev(a/b,b) affiche la décomposition du nombre a/b dans la base b."
    Avec un peu de maths, si on écrit a dans la base b on a:
    Formule mathématique
    Ainsi
    Formule mathématique
    et
    Formule mathématique
    En gros tu affiches d'abord a_0, et ensuite grace à ton hypothèse de récurrence tu dis que tu affiches a_1, a_2, ..., a_n.
    Tu affiches donc bien tous les chiffres de a dans la base b (à l'envers néanmoins)

  9. #9
    Futur Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    octobre 2016
    Messages
    11
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 20
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : octobre 2016
    Messages : 11
    Points : 9
    Points
    9

    Par défaut

    D'accord j'ai compris merci beaucoup !
    Je vais faire des exos sur ça (je suppose que y a pas de miracle)
    Bonne journée à toi Lulzec et aux autres qui m'ont aidé

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [gasche] Mémoire de maîtrise et preuve de programme
    Par SpiceGuid dans le forum Langages fonctionnels
    Réponses: 1
    Dernier message: 28/11/2016, 01h28
  2. Preuve de programme en C
    Par boozook dans le forum C
    Réponses: 10
    Dernier message: 06/06/2012, 10h31
  3. Algorithme polynomial et preuve de programme
    Par yaya125 dans le forum Général Algorithmique
    Réponses: 1
    Dernier message: 28/02/2011, 19h12
  4. [Fondements] Preuve de programme: utopie ou réalité ?
    Par DrTopos dans le forum Débats sur le développement - Le Best Of
    Réponses: 115
    Dernier message: 05/10/2007, 17h12
  5. [Kylix] icone associée à un programme
    Par Anonymous dans le forum EDI
    Réponses: 1
    Dernier message: 22/03/2002, 10h43

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