algorithme en seconde

Bonjour,

Le document d'accompagnement ( http://eduscol.education.fr/D0015/Doc_ress_algo_v25.pdf ) ne donne aucun exemple d'algorithme récursif (et n'en parle pas du tout). Est-ce que ça signifie que c'est hors programme ?

J'ai trouvé cet article donnant des comparaison entre itératif et récursif : http://revue.sesamath.net/spip.php?article216

Dido

[Activation du lien. AD]
«1

Réponses

  • Prends l’exemple rebattu de la factorielle : l’algorithme récursif s’appelle, l’algorithme itératif utilise une boucle répétée.

    Factorielle_récursive(n)
      Si n>1
        Retourner Factorielle_récursive(n−1)
      Sinon
        Retourner 1
    
    Factorielle_itérative(n)
      f=1
      Pour i de 1 à n, faire
        f*=i
      Retourner f
    

    Je code les fins de boucle comme en Python, en utilisant les tabulations.

    Je pense que ça risque de passer au-dessus de la tête des élèves, même si le calcul du PGCD par l’algorithme d’Euclide peut se comprendre comme un algorithme récursif. À moins qu’un élève ne pose la question, je te conseille de cacher ça sous le tapis.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Nicolas,

    Merci de ta réponse. En fait, je ne cherchais pas un exemple d'algorithme récursif.
    Ma question était : est-ce que le fait que le doc d'accompagnement n'y fait pas allusion signifie que c'est hors programme ?

    Merci
  • Bonjour.

    Attention ! Je vais surement dire une énormité.

    Est-ce qu'il ne faut pas distinguer l'algorithme et l'écriture de l'algorithme qui elle peut-être récursive ou pas récursive ? Sachant que de toutes façons le compilo va dérécursifier tout ça. Mmh ?

    amicalement,

    e.v.
    Personne n'a raison contre un enfant qui pleure.


  • EV,

    L'article cité plus haut de la revue sésamath donne des exemples d'algorithme qui sont différents selon qu'ils soient itératif ou récursif, sans aucun rapport avec leurs programmations.

    Par exemple, pour la somme des entiers de 1 à n, on considère que somme(n)=n+somme(n-1) et on descend jusqu'à 1, alors que pour l'itératif, on part de S=1 et en faisant une boucle sur k jusqu'à n, on ajoute k à S. Le résultat est alors le S obtenu en sortie de boucle.

    L'algorithme n'est pas le même et surtout, la logique est très différente.
  • Tu crois qu’un élève de seconde moyen va se demander ce que fait le compilateur ?
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Non, et surtout nous ne sommes pas des profs d'info.
    Donc si on sort de la partie programmation pour ne rester que sur l'algorithme, je trouve que la récursivité peut être plus intéressante.
    Maintenant, d'un point de vue pédagogique, je ne sais pas ce qui est le moins perturbant pour des élèves de seconde, une variable itérative qui change tout le temps de valeur et qui est supposée représenter le résultat attendu au bout d'un moment, ou une fonction qui s'appelle elle-même, alors qu'ils ne savent pas encore bien ce qu'est une fonction ? La récursivité est plus proche de la définition mathématiques il me semble, l'itératif est plus un processus qui permet d'arriver au résultat voulu.
  • Je pense au contraire que l’itératif est plus facile à contrôler par un élève : cela lui évite de se poser la question du domaine de définition d’une fonction qu’on compose plusieurs fois. Cela dit, si cela peut expliquer par un autre moyen ce qu’est une composition…
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Dido,

    Je ne vois strictement aucune différence entre les algorithmes :

    récursif : somme(n)=n+somme(n-1) et somme(0) = 0

    et itératif : S=1 et en faisant une boucle sur k jusqu'à n, on ajoute k à S.

    Ce sont deux écritures différentes du même algorithme.
    Après traduction en langage machine, il est probable (mais qui sait ?) que le premier prendra (beaucoup ?) plus de temps que le deuxième.

    Nicolas: Si tu te sers d'un langage de programmation il n'est pas indispensable de savoir ce que fait un compilateur, mais si tu enseignes ce langage de programmation, là je ne vois pas comment tu peux t'en passer. J'ai le souvenir d'un élève qui a voulu me tester en me demandant ce que faisait un petit programme. C'était piègeux si tu ne savais pas comment le compilateur traitait les passages d'arguments par adresse. Lui le savait, il valait mieux que je le sache aussi...
    Il y a des élèves qui programment. Peu, mais il vaut mieux savoir quoi répondre à leurs questions. ça me paraît un minimum.

    Par ailleurs, comme tous les TZR, je ne vois pas comment je peux me dispenser d'apprendre TOUS les langages proposés (je n'en connais aucun...) sachant que je peux intervenir dans n'importe quelle classe de n'importe quel lycée. De toutes façons, que va-t-il se passer en première ? Y aura-t-il encore de la programmation ? Si non autant laisser tomber tout de suite, ça ne sera pas au bac. Si oui, au gré du prof, faudra-t-il que l'élève change de langage ou bien le prof devra-t-il se faire a à TOUS les langages possibles.
    Le LSE des années 80 n'a peut-être pas fait carrière, mais au moins était-il unique. Je ne vois pas pourquoi, alors qu'il était très bien à l'époque, il ne vaut plus un pet de lapin de nos jours.

    e.v.
    Personne n'a raison contre un enfant qui pleure.


  • Ça m’énerve au plus haut point, cette manie de tester les professeurs. Ils feraient mieux de tester leurs connaissances. :X
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Ev,

    Pour moi ce n'est pas le même algorithme, dans le sens où ce ne sont pas les mêmes processus, même s'ils arrivent au même résultat. Non ?
    L'itératif peut être plus naturel dans certaine situation, mais il me semble dommage de se priver du récursif pour l'algorithme d'Euclide par exemple, alors que les élèves l'ont déjà appris comme ça.
    Encore une fois, les docs d'accompagnement ne montre que de l'itératif, d'où mon étonnement et ma question.

    Je pense personnellement travailler le plus souvent possible avec les calculatrices. D'abord parce que ça évite de devoir multiplier les langages alors qu'il n'y a même pas d'accord entre profs d'un même lycée. Et surtout, je veux éviter de devoir consacrer des modules entiers en salle info, la programmation n'est pas supposé être le but ultime de ce qu'on va faire en agorithmie. Je vais plutôt favoriser la recherche de quelques algorithmes dans chacun des chapitres, sauf au début pour l'initialisation. Cependant, je vais peut-être utiliser un peu Xcas qui a l'avantage de pouvoir être utiliser en ligne alors que beaucoup d'élèves n'ont pas de possibilité d'installer quelque chose sur l'ordi familiale. Je vais en tout cas fuir scratch qui me semble horrible (j'ai lu que ça avait été créer pour initier les petits américains à la programmation à partir de 7 ans, d'où les couleurs......)
  • Essaie peut-être Python, mais ça risque de leur faire peur.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Bonsoir,

    Qu'il y ait une différence sur la forme, le fond ne change pas et certaines situations sont en effet plus adaptées au récursif qu'à l'itératif (algorithme d'Euclide compris en effet). Cependant, il faut se rappeler que les documents pédagogiques fournis en marge du programme de maths de seconde, ne reste là QUE à titre indicatif pour que les professeurs complètement largués puissent avoir quelques bases justement. Mais en aucun cas ces documents servent de base pédagogique ou encore pire de fil conducteur de tel chapitre ou telle partie du programme (heureusement pour nous je pense car il manquerait un paquet de doc si on devait réellement enseigner leur programme avec leur état d'esprit et non le notre et nous perdrions notre utilité étant formaté).

    Par conséquent, et heureusement pour toi, tu restes tout à fait libre d'enseigner ceci comme il te plaît avec ou sans récursif du moment que le cadre du programme est respecté et que le minimum syndicale donné par le programme est vu durant ton cours. Après tu es libre de voir les choses comme tu le sens surtout si tu as l'avantage d'en savoir plus que les documents d'accompagnement et que tu considères que ta connaissance serait plus adaptée que le fil donné par le document en question, vas-y fonce j'ai envie de dire (tes élèves te remercieront plus tard).

    Sinon, attention à une chose tout de même c'est que lorsque je te lis, tu parles surtout de calculatrice et de programmation mais ceci n'est pas de l'algorithmique. Enfin, je chipote sans doute mais pour moi, l'algorithmique a une énorme part sans programmation justement pour comprendre tout le langage et les procédés (savoir lire un algorithme, écrire un algorithme, la logique qu'il y a derrière, ...). Après la programmation c'est le côté ludique en quelque sorte (sexy comme dirait notre ancien ministre) et qui permet de savoir si les algorithmes écrits sur le papier (d'abord !!!) marchent ou pas. Mais, je pense qu'en second il y avait déjà les tableurs, géoplan (et compagnie du même style) ainsi que quelque programme à la calculatrice, je pense qu'ils "savent faire" quelques programmes (de type clique-clique mais bon l'intuition est là tout de même) par contre niveau algorithmique justement, il y a un fossé qui n'était pas abordé et qui est maintenant mis à l'honneur presque.

    Donc je trouve que le titre n'est pas du tout piégieux en soi et que le terme algorithmique est très bien choisi pour justement éviter de tomber dans le "faire que de la programmation sans réflexion papier ni recule sur la programmation". La logique et l'algorithmique vont bien ensemble et il n'y a pas forcément besoin d'ordinateur pour en faire.

    Après, c'est sûr que dès que les notion seront sues, il faudra bien passer sur le côté pratique (voire "jeu", je vois pas d'autre mot) du test des programmes sur un logiciel de programmation (ou un éditeur texte vu les programmes qu'on a, je ne vois toujours pas pourquoi, ne pas revenir à la base après tout mais bon après, j'ai pu voir de très bon logiciel libre et gratuit voir le jour ces derniers temps, donc pourquoi pas).

    En tout cas, je trouve cela plutôt prometteur que des enseignants commencent à travailler sur le programme de seconde et si tout les profs faisaient cela et se mettait d'accord pour les logiciels pris au sein de leur équipe pédagogique, cela ferait réellement avancer les choses (déjà au sein même d'une équipe pédagogique d'une même matière mais aussi pour les élèves eux-même) ne pas arriver en septembre avec l'état d'esprit: "on verra bien ce qu'on fera" (car j'en connais hélas qui sont ainsi). D'ailleurs, ce qui est assez bizarre c'est que les gens qui ont passer le capes et qui seront en stage à la rentrée en seconde peut-être ne se renseignent pas des programmes et pour la plupart ne sont même pas au courant qu'il y a un nouveau programme pour la seconde pour la rentrée 2009 (bizarre mais il paraît que c'est normal qu'ils ne se renseignent de rien et qu'ils verront bien ce que leur dira leur référent de stage, moi ça à tendance à me faire peur et à m'énerver surtout ce genre de réaction mais bon, c'est comme, ça il paraît).

    Bonne continuation!
  • Rémi,

    Je suis entièrement d'accord avec toi sur la place à donner à la programmation. Pour moi, elle permettra surtout au élève de tester leurs algorithmes et de leur donner envie d'être rigoureux dans l'écriture de l'algorithme, ce qui ne sera surement pas naturel pour beaucoup d'entre eux, et qui constitue pour moi un intérêt majeur de ce sujet. C'est la raison pour laquelle je ne veux pas investir trop de temps en classe à apprendre à programmer (les TICE peuvent être très chronophages) et que la calculatrice permettra de faire des séances courtes et de leur faire programmer chez eux un algorithme qu'on aura étudier en classe par exemple.

    J'ai bien peur que dans la plupart des établissements, beaucoup de profs de maths n'auront pas réfléchi à la question. D'abord parce que les programmes et les docs d'accompagnement sont arrivés très tard, et surtout parce que lorsqu'on a aucune notion de programmation, et même si l'algorithmique n'est pas à confondre avec la programmation, ce n'est pas facile de s'y mettre tout seul. J'imagine bien que la plupart de ceux qui ne sont qu'à quelques années de la retraite, n'auront pas facilement envie et ne verront peut-être pas l'intérêt. Alors quant à se mettre tous d'accord !

    A la décharge des nouveau capesiens, ils ne savent pas encore quelles classes ils vont avoir (ils ne le sauront que quelques jours avant la rentrée), alors ce n'est pas évident d'étudier de près tous les programmes en vigueurs. Je ne l'avais pas fait moi même, et ma conseillère pédagogique qui était aussi formatrice à l'iufm n'avait pas regarder les nouveaux programmes avant la rentrèe........... Le fait de connaître ses classes au dernier moment, empêche de préparer ses cours à l'avance et oblige à avoir le nez dans le guidon toute l'année......
  • nicolas.patrois écrivait:

    > Je pense que ça risque de passer au-dessus de la
    > tête des élèves, même si le calcul du PGCD par
    > l’algorithme d’Euclide peut se comprendre comme un
    > algorithme récursif. À moins qu’un élève ne pose
    > la question, je te conseille de cacher ça sous le
    > tapis.


    Je reviens sur ce que disait Nicolas. C'est justement une question que je me pose. Doit-on leur faire comprendre et étudier la différence entre itératif et récursif ? Ca me semble aller plus loin que le programme, mais je me vois mal "cacher ça sous le tapis"; si par exemple on commence que par des algorithme itératifs, ils vont bien voir qu'on fait quelque chose de différent, qu'on utilise une fonction lorsqu'on va passer au récursif. Et si on demande de créer un algorithme, il faudra bien étudier les deux solutions proposées par les élèves.
  • Bonjour Dido.

    Je ne suis plus prof de seconde, donc mets mes conseils à la poubelle si tu veux. Mais pour avoir fait un peu d'algorithmes avec des étudiants à bac+2 qui ont eu des cours d'algorithmique-programmation, j'imagine qu'avec une partie de tes classes, tu auras du mal à mettre en place la notion d'itération. Donc soit tu travaille pour les 2 (classe faible) à 10 (très bonne classe) meilleurs (et tant pis pour les autres), soit tu laisse ce sujet pour une discussion avec les 2 ou 3 passionnés, à qui tu apporteras beaucoup.
    Je pense que la vraie difficulté est d'obtenir un algorithme qui ne soit pas déjà un programme écrit dans un langage connu de l'élève. Un petit truc : Il faut demander aux élèves de présenter le "calcul" de façon à pouvoir retraduire aussi bien avec un tableur (programmation en tableau) qu'avec un langage type C (langage discursif).

    Cordialement
  • Gerard,

    Je suis justement à la recherche de prof qui ont de l'expérience dans cet enseignement. Merci de ta réponse.
    Veux-tu dire que les algorithmes itératifs sont difficiles pour les élèves ou que formaliser la différence entre l'itératif et récursif est compliqué (même s'ils peuvent utiliser les deux ?).

    La difficulté d'obtenir un algorithme universel est en fait aussi une difficulté pour le prof je crois, je sens bien que je vais aussi devoir lutter au début contre la tentation d'écrire quelque chose qui ressemble trop à un programme, n'ayant jamais étudié l'algorithmique et ayant fait de la programmation il y a très longtemps.

    Ta remarque sur le tableur est très intéressante, ça me donne des idées de modules où on pourrait travailler sur un algorithme puis l'implémenter sur différents supports......
  • Traduis le programme en français, comme ça tu seras sûre qu’il ne sera pas écrit dans un langage existant.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Nous ne sommes pas supposés utiliser les organigrammes (dixit le doc d'accompagnement). Y-a-t-il toutefois une convention ou une norme sur l'écriture formel d'un algorithme ?
  • Somme,Produit=0,1		# On initialise.
    Pour i de 1 à 10, faire:
    	Somme=Somme+i		# On additionne i à la somme.
    	Produit=Produit×i		# Et on multiplie le produit par i.
    					# La boucle est terminée.
    Afficher Somme, Produit	# On affiche.
    

    J’ai utilisé une syntaxe à la Python, mais tu peux terminer explicitement tes boucles.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • haskell c'est vachement plus classe pour faire ce genre de trucs :
    foldl ((\f g (cs,cp) x->(f cs x,g cp x)) (+) (*)) (0,1) [1..10]
    
    Sans utiliser ce raccourci un peu barbare, la syntaxe
    foldl (+) 0 u
    
    c'est exactement $\sum_i u_i$.

    Pour faire des maths, je ne suis pas sur que l'impératif soit obligatoire. Les élèves passent leur temps à se tromper dès qu'il faut faire des boucles imbriqués, or, ce n'est pas là qu'on a envie de mettre l'accent. Les problèmes qu'ils ont sont très souvent liés au fait que la séquentialité imposée par un langage impératif, où les boucles se déroulent naturellement en une suite d'instructions, n'est pas naturelle du tout pour un non-programmeur. Alors qu'une vision avec des sommes à doubles indices par exemple est peut-être plus simple conceptuellement. En tout cas, la bonne compréhension de ce concept apportera un plus en mathématiques.
  • dIDO a écrit:
    Veux-tu dire que les algorithmes itératifs sont difficiles pour les élèves ou que formaliser la différence entre l'itératif et récursif est compliqué (même s'ils peuvent utiliser les deux ?).
    Effectivement, les algorithmes itératifs sont assez peu naturel pour les élèves : Faire calculer la somme des 1000 premier impairs par programme est déjà, pour la plupart difficile. En fait, la principale difficulté est d'accepter de décomposer suffisamment le travail pour qu'il soit parfaitement défini. Si tu dis à un élève "comment ferais-tu à la main ?" (C'est la bonne question pour programmer : comment doit-on faire précisément), il répondra "j'ajoute 1 + 3 puis je continue". C'est effectivement une explication pour humains, il faut les faire passer à une explication pour machine.

    Pour le récursif, la grande difficulté est que les conditions de fin sont délicates à manier, encore plus que pour les boucles. Et qu'il est rapidement impossible de simuler "à la main" : Les appels s'empilent, les calculs commencés aussi. D'ailleurs, on apprend aux informaticiens à "dérécursiver" les programmes (accélération d'exécution et gain de place en mémoire). Essaie par exemple le calcul du 3000ième nombre de fibonnacci (même en valeur approchée) par récurrence à partir de la formule. Il y a 23000 calculs, au lieu de 3000 en itératif. A la main, tu peux remplacer 3000 par 10.

    Il me semble donc que la récursion doit être réservée à une étape ultérieure.

    Pour l'écriture des programmes, l'écriture "recette de cuisine", en bon français, avec autant d'alinéas qu'il y a d'étapes est assez efficace pour apprendre (rajouter des contraintes d'écriture peut venir dans un deuxième temps, si des structures (séquence, test, boucles, ...) ont été assimilées.

    Cordialement
  • Une idée :

    Certains élèves ont probablement des programmes tout faits sur leur calculette programmable (copiés, ou faits par le précédent possesseur de la calculatrice). Décoder les instructions et retrouver "comment on a fait faire à la machine" peut être instructif.
  • Gerard : fibonacci c'est une récurrence linéaire sur des vecteurs de dimension 2. Si on veut implémenter la récurrence c'est la seule observation à faire.
    Voila, par exemple en caml :
    let fib n = let rec fibx n (u,v) = if n = 0 then u else fibx (n-1) (v,u+v) in fibx n (1,1)
    
    tu pourras observer que la récursivité y est terminale, et on n'a même pas besoin d'empiler un seul calcul. En fait, ce code une fois traduit en assembleur c'est exactement le code impératif auquel tu fait référence.
  • Effectivement, Deufeufeu.

    On peut évidemment choisir des méthodes récursives efficaces. Je ne connais pas Caml, mais j'ai quand même l'impression qu'on simule la boucle simple habituelle par une récursion, ce qui fait empiler pour rien les appels de récursion.
    Mais je sais que c'est devenu la mode.

    Cordialement.

    NB : Tu te vois expliquer ce programme en seconde ?
  • Le gros problème est que chaque machine a son langage, même au sein d’une même marque.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • moi si j'ai des secondes, ils auront le privilège de se shooter au camL!!! (en fait on se rend pas compte mais les élèves adorent (enfin 40%)

    (2 jeux de mots en 1... Je dis ça au cas où vous auriez pas remarqué)
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Salut

    Merci à cc qui vient de me convertir au(x!) camL mais ne serait-ce pas pour les filtres que tu aimes tant camL?

    (tant qu'à être lourdingue, rajoutons-en !!!)

    F.D.

    [Blague de fumeur ? :D AD]
  • HHHooooooo puréééééééée t'es trop fort, je n'y avais même pas pensé!
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • J'arrive après la bataille, mais quand même : ev, pourquoi souhaites-tu identifier récursivité envellopée et itération (ie récursivité terminale), alors que tu conviens toi-même que les temps d'exécution de deux programmes qui calculent la même chose en utilisant l'une ou l'autre méthode pourront être très différents ?


    Si tu écris :
    ev a écrit:
    somme(n)=n+somme(n-1) et somme(0) = 0
    à l'exécution ton programme va remplir une pile qui accumule n,n-1,n-2,...,0 avant d'ensuite calculer les sommes, c'est quand même un procédé très différent que celui-ci
    ev a écrit:
    S=1 et en faisant une boucle sur k jusqu'à n, on ajoute k à S.
    qui calcule les sommes directement sans passer par l'empilement préalable de ce qu'on va sommer, qu'on pourrait par contre éventuellement identifier à
    somme(n,accu)=somme(n-1,accu+n) et somme(0,accu) = accu


    Si tu veux identifier ton premier programme à ton deuxième programme, c'est que tu identifies les programmes extensionellement égaux. Tu dois alors aussi identifier le tri par fusion et le tri par insertion (et tous les autres algorithmes de tri). Tu ne peux plus évoquer la notion de complexité. Bref tu vides l'algorithmique de sa substance.
  • Pour AD : ancien fumeur depuis le 4 Octobre 2004!

    Pour ceux qui se demandent comment faire : l'envie de cigarette dure 1 minute, j'ai bien dit 1 minute. C'est pas si long, non?

    F.D.
  • Bonsoir Barbu.

    Je n'identifie pas les programmes. J'identifie (sûrement à tort) les algorithmes. Je prétends naïvement qu'un algorithme n'est ni récursif ni itératif. Il est.
    Un programme, dans son écriture, lui est récursif ou itératif. Sachant qu'après le passage dans le compilo-broyeur, il ne sera ni l'un ni l'autre, il sera empilé.
    J'ai tort ?
    A ma courte honte je ne connais rien aux algorithmes de tri. D'où ma naïveté dans le domaine sûrement. Est-il bien raisonnable de me confier des élèves ?

    amicalement,

    e.v.

    PS J'ai parlé de temps d'exécution, j'aurais aussi bien pu parler de taille mémoire. Un problème qui était beaucoup plus pertinent du temps où je programmais. Le temps d'exécution, on faisait avec pendant que le programme tournait : un peu de cuisine, un peu de ménage, aller au cinéma, aller au boulot ou une semaine aux sports d'hiver.
    Personne n'a raison contre un enfant qui pleure.


  • @DFF:

    haskell c'est vachement plus classe pour faire ce genre de trucs :


    foldl ((g (cs,cp) x->(f cs x,g cp x)) (+) (*)) (0,1) [1..10]


    Sans utiliser ce raccourci un peu barbare, la syntaxe


    foldl (+) 0 u


    c'est exactement $ \sum_i u_i$.
    Je me demande si élèves de Seconde qui vont aller en STG ou être ré-orientés en BacPro vont adhérer à haskell...

    @tous:

    Dans l'absolu, il y a un truc qui m'échappe : les IPR nous ont dit "il suffit d'écrire en langage naturel (paradoxe de Richard, etc. cc sait que nos IPR peuvent être très drôles) et le doc dit "complexification des langages de programmation"... où va-t-on avec ça???

    Pour ma part, je programme TurboPascal, VBasic, Scilab, Matlab, Maple et ça s'arrêtera là. Je veux bien que je vais pouvoir m'y mettre plus vite que le mômes si je dois faire CmaL etc. mais bon, c'est un peu limite, non?
    Est-ce que le "on découvre le langage ensemble et on merde ensemble" peut être un objectif pédagogique? lol

    Amicalement,

    F.D.
  • FrançoisD a écrit:
    Est-ce que le "on découvre le langage ensemble et on merde ensemble" peut être un objectif pédagogique? lol

    Rigole : c’est le genre de chose que certains vantaient à l’IUFM, un professeur aussi ignorant que ses élèves.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Salut,

    Tu me diras, quand j'ai débuté j'ai fait ça avec Dijkstraa et ça a marché... lol

    Le fond du truc c'est savoir reconnaître que l'on a merdé et l'avouer sinon là on passe pour un sale con.

    F.D.
  • Salut ev !

    Rapidement, parce que je suis malheureusement un peu in a rush.
    ev a écrit:
    Je n'identifie pas les programmes. J'identifie (sûrement à tort) les algorithmes. Je prétends naïvement qu'un algorithme n'est ni récursif ni itératif. Il est.
    Un programme, dans son écriture, lui est récursif ou itératif. Sachant qu'après le passage dans le compilo-broyeur, il ne sera ni l'un ni l'autre, il sera empilé.
    J'ai tort ?

    Oui.

    D'abord je ne comprends pas ton obsession des compilateurs. Tu as un algorithme qui, comme tu dis, est, et toi, tu l'as écrit dans un langage donné. Basiquement, ton compilateur va traduire ton algorithme dans un langage de plus bas niveau. Mais il s'git réellement d'une opération de traduction bête : comme tu le dis si bien, le programme change (parce que la langue change) mais l'algorithme (le contenu du programme) ne change pas. Bien sûr, on s'efforce de faire des compilateurs qui font de l'optimisation de code, de sorte que si tu as écrit un algorithme très bête, le compilo se dise "bon, là, c'est vraiment trop con ce qu'il a écrit, je vais un peu changer ça", mais c'est parfaitement irréaliste de supposer qu'un compilateur va transformer un programme récursif enveloppé en programme itératif (peut-être que les compilos de Caml ou de Python peuvent le faire dans certains exemples très très pathologique,s mais ça n'est vraiment pas dit, et ce sera surtout très très rare) ne serait-ce que pour la simple et bonne raison qu'il y a certains algorithmes récursifs enveloppés qui n'ont pas de variante itérative.

    Regarde mon dernier message : les deux derniers programmes font effectivement la même chose (en fait presque, parce que l'ordre de sommation est inversé, mais faisons comme si tu avais écrit la somme dans l'ordre inverse pour celui qui utilise la boucle for), je te suis pour dire qu'il s'agit de deux implémentations du même algorithme. Cet algorithme consiste à prendre n, à sommer avec n-1, puis à somme les résultat avec n-2, puis etc jusqu'à ajouter 1, là on a fini et on lit le résultat.

    Prends maintenant le premier programme de mon précédent message, celui que tu tiens à identifier aux autres. Celui-là est une implémentation d'un autre algorithme, d'une autre méthode pour calculer cette somme, qui elle est (en gros) : prends n, mets le sur le tas d'une pile initialement vide. Ensuite prends n-1, mets-le sur le tas de ta pile. Ensuite prends n-2, mets-le sur le tas de ta pile. Etc. Quand tu as mis 1 sur le tas de ta pile, somme les deux premier éléments de de ta pile. Ensuite somme les deux premiers éléments de ta pile. Ensuite somme les deux premeiers éléments de ta pile. Etc. Quand ta pile n'a plus qu'un élément, c'est ton résultat, tu le lis.

    ev a écrit:
    A ma courte honte je ne connais rien aux algorithmes de tri. D'où ma naïveté dans le domaine sûrement.

    Laisse tomber les algorithmes de tri et regarde ces deux programmes qui calculent Fibonacci :
    Fibo1(n) =
    si n<=1 alors n
    sinon Fibo1(n-1)+Fibo1(n-2)
    
    Fibo2(n) = Aux(n,0,1)
    Aux(n,a,b) =
    si n=0 alors a
    sinon Aux(n-1,a+b,a)
    

    L'algorithme correspondant au premier est récursif enveloppé, le second itératif : tu remarqueras que ça n'a pas de lien avec l'implémentation. Dans le premier cas, tu vas calculer 2^n fois fib(1), dans le second cas, tu va le calculer 1 fois. La méthode utilisée pour calculer le ne nombre de Fibonacci est donc différente ! Identifier ces deux algorithmes n'est pas pertinent.


    ... désolé, je dois vraiment filer.
  • Bonjour Barbu.

    1- C'est quoi du récursif enveloppé ?

    2- Je croyais naïvement que le langage machine n'était pas un langage récursif et donc que tout compilateur d'un langage récursif devait dérécursifier ses procédures récursives. Et dérécursifier les tours de Hanoï c'est pas du mille-feuilles. (et je ne parle pas des récursivités croisées pour masochistes avancés)

    3- Si je m'intéresse aux compilateurs jusqu'à l'obsession (il vaut mieux écrire ça au passé) c'est que mes rares tentatives d'écrire en assembleur ont été des succès mitigés...

    4- Dans mon rude patois et avec les mauvaises manières contractées à programmer en pascal, je dis que ton deuxième programme est récursif, ton sous-programme s'appelant lui-même.
    Et là il vaut mieux savoir ce que fait ton compilateur (pascal pfli). S'il est bien écrit ton deuxième programme va être kif-kif itératif, sinon, si son ramasse-miette (le talon d'achille de bien des compilo pascal) a été écrit avec mes pieds, il devient vraiment récursif en prenant une place mémoire proportionnelle à n.

    Le vrai itératif pour moi s'écrit avec un indice de boucle un accumulateur et deux variables temporaires, ce qui donne le programme jansséniste suivant :

    k=0,T=1,S=1,Temp=0.
    Tant que k<=n faire
    Temp = S+T
    T=S
    S=Temp
    k=k+1
    fin faire
    Fibo3 = S

    Celui-là est itératif quel que soit le compilateur (quoique depuis que j'ai vu des compilateurs générer du code plus rapide lorsque je rajoutais des parenthèses superflues je ne m'étonne plus de rien).

    Fibo1 est naze et élégant. Il fait déborder la baignoire pour n = 1024.
    Fibo2 est lisible mais demande d'avoir foi en son compilateur (tu vas avoir du mal à me guérir...)
    Fibo3 fait son job (si j'ose dire) mais est écrit comme un cochon et contient probablement des fautes.

    Je te remercie de tes efforts pour me soigner. Le mal est profond et pernicieux, il va falloir amputer large.

    e.v.
    Personne n'a raison contre un enfant qui pleure.


  • Salut,

    serait-il possible d'isoler les algorithmes de ce fil sur un doc pdf ( = les auteurs sont-ils d'accord?) d'algo "pour les nuls" ou plutôt orienté "je sais le faire mais comment l'expliquer (ou les exemples qui vont bien)"...

    J'avoue que pour des raisons indépendantes de ma volonté (vacances = pas mon pc = pas LaTeX) je ne pourrais le faire que difficilement.

    Amicalement,

    F.D.

    PS: merci à ceux qui alimentent "constructivement" cette discussion
  • Sinon,

    "récursif enveloppé" =

    Fibo1(n) =
    si n<=1 alors n
    sinon Fibo1(n-1)+Fibo1(n-2)

    car Fibo1 s'appelle 2 FOIS

    c'est plus général que "récursif terminal" =

    Fac(n)=n*Fac(n-1) / Fac(0)=1 (écrit comme on le sent sur les conditions) qui ne s'appelle en fait qu'une seule fois ici

    merci wiki et LBR si j'ai pigé qque chose.

    Amicalement vôtre,

    Brett Sinclair.

    (j'en peux plus moi)

    F.D.
  • Le barbu rasé écrivait:

    > Prends maintenant le premier programme de mon
    > précédent message, celui que tu tiens à identifier
    > aux autres. Celui-là est une implémentation d'un
    > autre algorithme, d'une autre méthode pour
    > calculer cette somme, qui elle est (en gros) :
    > prends n, mets le sur le tas d'une pile
    > initialement vide.
    > (...)

    Tu dis que c'est un autre algorithme. Ça se discute. Le problème est le terme extensible d'"algorithme". En première approximation, je considère qu'il s'agit du même algorithme. Quel est cette algorithme ? Rép. : parcourir la liste (virtuelle ou pas, en première approximation ce n'est pas le problème) des termes de la suite et additionner. C'est l'algorithme qui colle à la définition de la suite de Fibonacci, ce que j'appelle l'algorithme naïf. Un autre algorithme serait par exemple la méthode de Dijkstra. Idem, quand on parle de l'algorithme d'Euclide, on s'en moque complètement que le calcul soit fait récursivement ou itérativement : tu calcules les restes successifs et le dernier non nul est le pgcd. Par contre, calculer le pgcd en faisant une décomposition en facteurs premiers est un autre algorithme.

    Ce que tu as dit est plutôt de l'ordre de l'implémentation (cf. la "pile"). Ça ne veut pas dire pour autant que je pense qu'il faille négliger ces questions. Au demeurant je pense qu'au niveau Seconde, il ne faut pas être tatillon sur ces questions, le plus important restant malgré tout qu'ils sachent implémenter sur machine le calcul du nième terme de la suite de Fibonacci.
  • Salut, ev, François, candide.

    ev a écrit:
    1- C'est quoi du récursif enveloppé ?

    Alors déjà, ça n'est pas du tout ce qu'a écrit François.
    Si j'écris f(n)=g(f(n-1)), l'appel récursif (à f(n-1)) est enveloppé (par la fonction g).
    Si j'écris f(n,accu)=f(n-1,g(accu)), l'appel récursif (à f(n-1,g(accu))) est direct.

    Plus généralement, quand on écrit : f(truc)=g(f(bidule)) avec bidule structurellement plus petit que truc, on fait de la récursivité enveloppée. Quand on écrit f(truc)=f(machin) avec machin structurellement plus petit que truc, on fait de la récursivité terminale, mieux connue sous le nom d'itération.

    Il existe une notion syntaxique de récursivité, qui est "la fonction s'appelle elle-même" : cette notion n'a pas d'intérêt, car rien ne distingue conceptuellement la récrusivité terminale de l'itération par boucles.
    En revanche, il existe aussi une notion sémantique de récursivité (la bonne) : celle qui distingue un algorithme récursif enveloppé d'un algorithme itératif.
    On devrait dire "récursif" tout simplement pour parler de la récursivité enveloppée. J'emploie l'expression "récursif enveloppé" pour clairement signifier que c'est à la bonne notion (la notion sémantique) que je fais référence.

    NB : je trouve la page wikipedia dont parle François (s'il s'agit bien de celle-ci) très bien écrite.

    ev a écrit:
    2- Je croyais naïvement que le langage machine n'était pas un langage récursif et donc que tout compilateur d'un langage récursif devait dérécursifier ses procédures récursives.

    Au sens syntaxique, oui. Mais pas au sens sémantique : la question n'est pas de savoir si tu vas avoir une procédure qui s'appelle elle-même, la question est de savoir si tu vas devoir empiler tous tes résultats intermédiaires avant de pouvoir enfin t'en servir pour calculer ton résultat final, ou si cet empilement n'est pas nécessaire parce que tu calcules dynamiquement ton résultat tout au long de ta procédure.

    Je le répète, ça n'est pas la même chose : il s'agit de deux façons de procéder différentes.

    ev a écrit:
    4- Dans mon rude patois et avec les mauvaises manières contractées à programmer en pascal, je dis que ton deuxième programme est récursif, ton sous-programme s'appelant lui-même.

    Est-ce que ça va mieux avec les sous-titres ?

    c.candide a écrit:
    Tu dis que c'est un autre algorithme. Ça se discute. Le problème est le terme extensible d'"algorithme". [...] Ce que tu as dit est plutôt de l'ordre de l'implémentation (cf. la "pile"). Ça ne veut pas dire pour autant que je pense qu'il faille négliger ces questions. Au demeurant je pense qu'au niveau Seconde, il ne faut pas être tatillon sur ces questions, le plus important restant malgré tout qu'ils sachent implémenter sur machine le calcul du nième terme de la suite de Fibonacci.

    Je suis d'accord sur le fait que ça se discute (on peut toujours identifier ce qu'on veut, du moment qu'on dit clairement pourquoi et où on s'arrête), mais pas sur le fait que c'est une question d'implémentation. La pile dont je parle ne résulte ni d'un défaut de compilation, ni d'une maladresse d'écriture : elle résulte d'un choix méthodologique.
  • Merci barbu pour tes sous-titres. Je comprends mieux ce que tu voulais dire.

    Pour François un 4ème algorithme, "direct" avec les guillemets qui s'imposent.

    Calculer $\dfrac{1+\sqrt 5}2$.
    Elever à la puissance $n$
    Diviser par $\sqrt 5$.
    Arrondir.

    e.v.
    Personne n'a raison contre un enfant qui pleure.


  • > ev :

    très discutable ta proposition d'algorithme. A priori, on cherche la valeur exacte du terme de la suite, question à laquelle ne répond pas l'algorithme. Ensuite, l'algorithme est entaché d'approximation : en deux étapes de ton algorithme, il y a le problème de la précision de $\sqrt 5$, il y a ensuite la précision du calcul d'exponentiation et de division et enfin le vague de la formulation de "arrondir". Et pour en revenir au niveau Seconde, il y a le "parachutage" de l'approximation. Et par ailleurs, d'une façon générale, il ne faut pas entretenir la confusion chez le débutant en programmation de la possibilité de calcul en précision presque illimitée avec les flottants sous prétexte que l'amplititude d'utilisation est très grande (pour la Norme IEEE, ça va de $10^{-37}$ à $10^{+37}$). Par contre, il peut y avoir des questions motivantes pour certains élèves de calcul d'approximation (par exemple, calcul de $\pi$ par différentes méthodes). Mais les questions de multiprécision pour les flottants sont délicates, au point que non fournies en standard dans de nombreux langage (C, Python, etc).
  • Salut,

    donc, si je comprends bien : f(n-1)+f(n-2) c'est enveloppé dans la fonction "+"?

    Oui je suis bouché. (Pas "boucher", ça c'est mon cousin ;-p)

    Bref, c'est pas encore si évident le contenu et les capacités attendues pour ces notions d'algo. Miam, ça va débattre dur!

    F.D.
  • En effet, je trouve bizarre la distinction entre récursion enveloppée et non enveloppée. À partir du moment où tu appliques une bête fonction affine à ta fonction récursive, voire l’identité, tu as une récursion enveloppée.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • c.candide a écrit:
    on cherche la valeur exacte du terme de la suite, question à laquelle ne répond pas l'algorithme.
    Ah bon ?
    c.candide a écrit:
    le vague de la formulation de "arrondir".
    D'accord, arrondir à l'unité.

    Les guillemets que je signalaient sont en partie liés au problème que tu soulèves~:
    Comment calculer la puissance n-ième.
    1- Soit par une boucle et ce n'est pas très direct.
    2- Soit par $\exp\left( n\log \left(\dfrac{1+\sqrt 5}2 \right) \right)$.
    Pas très niveau seconde, mais les suites ne sont pas du niveau seconde.
    Le problème de la multiprécision se pose aussi avec les nombres entiers.

    e.v.
    Personne n'a raison contre un enfant qui pleure.


  • ev écrivait:

    > Ah bon ?
    >

    En théorie ta formule est valide, en pratique non. Je viens d'écrire le code, et la relation de récurrence n'est plus vraie à partir du rang n=71 :
    from math import sqrt
    
    r=sqrt(5)
    def f(n) : return int(round(pow((1.0+r)/2.0,n)/r))
    
    n=0
    while (f(n+2)==f(n+1)+f(n)): n+=1
    
    print (n, f(n),f(n+1),f(n+2))
    

    ce qui affiche :
    (69, 117669030460994L, 190392490709135L, 308061521170130L)
    

    Sans compter qu'assez rapidement, tu vas obtenir un dépassement de capacité qui te donnera une approximation :
    1.6050064381636755e+17
    


    > Le problème de la multiprécision se pose aussi
    > avec les nombres entiers.

    Certes mais c'est beaucoup moins difficile que pour les flottants. D'ailleurs par exemple Python vient par défaut avec de la multiprécision entière mais pas flottante. Et pour en revenir au problème initial si tu dois coder toi-même (à la main ie sans bibliothèque) toute l'arithmétique flottante en multiprécision nécessaire pour obtenir de façon exacte un terme arbitraire de la suite de Fibonacci, avec contrôle de l'erreur, ce sera un code beaucoup plus difficile à écrire et un code beaucoup plus volumineux que de la gestion de grands entiers tout simplement parce que la suite de Fibonacci ne nécessite que d'implémenter l'addition de deux grands entiers ce qui est presque trivial (l'addition de l'école primaire est linéaire en le nombre de chiffres et il suffit de gérer a retenue).

    En fait, il se peut parfois que l'on souhaite seulement une approximation au lieu d'une valeur exacte auquel cas ta méthode convient mais bon, de même que je peux utiliser la fonction gamma pour calculer une factorielle ;)
  • Une variante de l'algorithme d'ev, sans approximation (calcul exact sur les entiers, par exemple en Maple) :

    Posons $\alpha= \dfrac{1+\sqrt{5}}{2} \in \Q[\sqrt{5}]$.

    Calculer $\dfrac{1}{\sqrt{5}}\,\alpha^n$ sous la forme $u_n + v_n \sqrt{5}$ avec $u_n$ et $v_n$ rationnels (par exponentiation rapide, bien sûr, ce qui fait $O(\log n)$ multiplications, mais avec des entiers dont la taille croit).

    Servir $2u_n$.

    Cordialement.
  • re moi,

    La méthode utilisée par Maple est de calculer $A^n$ où $A= \begin{pmatrix} 1&1\\ 1&0\end{pmatrix}$ (toujours par exponentiation rapide, bien entendu).

    Sur la feuille ci-dessous, Fib est le calcul proposé dans mon message précédent, fibonacci la commande toute faite de Maple.
    12823
  • donc, si je comprends bien : f(n-1)+f(n-2) c'est enveloppé dans la fonction "+"?

    Exactly.
  • Ga? écrivait:

    > La méthode utilisée par Maple (...)
    > Sur la feuille ci-dessous, Fib est le calcul
    > proposé dans mon message précédent, fibonacci la
    > commande toute faite de Maple.


    Que ce soit une méthode ou l'autre, c'est un autre problème que le problème initial puisqu'il s'agit d'accélérer le calcul de $F_n$ pour de grandes valeurs de $n$. Les outils sont accessibles mais pas totalement immédiats à récrire (exponentiation rapide de matrice, produit accéléré de grands entiers par Karatsuba probablement avec Maple). Sur ma machine avec Maple 10, pour n=10^8, ta méthode ne passe pas et la méthode builtin met 40s.

    L'avantage de la méthode de Dijkstra est qu'elle ne nécessite presque aucun prérequis, en principe c'est à la portée d'un élève du lycée peut-être même de Seconde. Le code est assez facile à écrire :
    import time
    
    t0 = time.clock()
    
    def f(n):
        if n==0: return 0
        elif n==1: return 1
        elif n%2: # n est impair
                return f(n//2)**2+f(n//2+1)**2
        else :# n est pair
            a=f(n//2)
            return a*(a+2*f(n//2-1))
    
    x=f(10**6)
    
    t1 = time.clock()
    print "%.3f" % (t1-t0), "secondes CPU"
    

    qui affiche :
    4.100 secondes CPU
    

    Par contre, c'est assez lent , pour 10**7 ça me fait 50 secondes mais il me semble qu'on peut un certain nombre d'optimisations efficaces.

    La bibliothèque GMP (utilisé entre autres par Maple pour diverses tâches) implémente un calcul des $F_n$ et elle utilise aussi la méthode de Dijkstra (cf. la doc de GMP). Je l'ai testé chez moi et au lieu des 40s sous Maple j'obtiens 12s. Bien sûr, ce n'est pas tout à fait comparable, Maple est interprété et GMP, c'est du compilé mais je pense que les modules de Maple sont souvent écrit en C (ou C++). Mais je pense que les deux méthodes sont comparables.
Connectez-vous ou Inscrivez-vous pour répondre.