vecchio56
Messages postés6535Date d'inscriptionlundi 16 décembre 2002StatutMembreDernière intervention22 août 2010
-
9 juin 2004 à 12:07
MetalDwarf
Messages postés241Date d'inscriptionmardi 29 octobre 2002StatutMembreDernière intervention23 janvier 2006
-
10 juin 2004 à 17:53
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
MetalDwarf
Messages postés241Date d'inscriptionmardi 29 octobre 2002StatutMembreDernière intervention23 janvier 2006 10 juin 2004 à 17:53
vecchio56 > Oui c est vrai qu audebut c est tres bizarre, et meme tres chaint, mais comme je suis oblige d en faire, j ai du m interesser un minimum, meme si je prefere le C et le C++. Je trouve que c est un langage tres propre, mais je n ai jamais fait un programme complet avec (l objectif du programme de prepa est d apprendre l algorithmique et un peu d informatique theorique, pas de faire des programmes entiers)
Kirua > En fait, pour Caml 1997 ca fait vieux. C est un langage developpe a l INRIA et de nombreuses versions sont apparues depuis. Caml-light est une sorte de brouillon en fait, car il ne compile pas en code natif par exemple, et c est un systeme assez minimal. OCaml est apparu depuis, est oriente objet, compile en code natif sur Unix et Windows (et MacOS je crois), et possede aussi une machine virtuelle un peu a la java. De plus d apres les concepteurs de Caml, OCaml est au moins 2x plus rapide que Caml-light.
BruNews > Il est vrai qu un algorithme recursif est tres souvent plus rapide qu alogorithme iteratif. Cependant il ne faut pas oublier que la fiabilite d un code compte aussi. Passer des heures a debugger a cause d effets de bord subtiles est penible et peut etre un inconvenient plus grand que la difference de performances a l execution. Un autre point particulierement important est l aspect fiable des programmes ecris dans des langages fonctionnels comme OCaml. Il est en effet possible de prouver mathematiquement le bon fonctionnement d un algorithme en Caml (surtout si l algorithme est recursif et n utilise pas de variables au sens du C), ce qui est indispensable dans certains domaines. C est pour cela que certaines compagnies tres importantes utilisent des langages de ce type (par exemple je crois qu Airbus travaille avec des chercheurs en info pour prouver leurs programmes. Je ne sais pas si ils sont ecrit en Caml, mais c est important a noter).
Je tiens quand meme a signaler que je ne suis pas du tout un extremiste de la recursivite. Je n ecris presque jamais de fonctions recursives en C...
Juste un petit exemple d algo recursif qu on le veuille ou non : l algo Mini-Max ou alpha-beta utilise dans les jeux d echecs entre autres (il est peut etre possible de le faire iterativement, mais je ne l ai jamais vu).
BruNews
Messages postés21040Date d'inscriptionjeudi 23 janvier 2003StatutModérateurDernière intervention21 août 2019 9 juin 2004 à 21:50
MetalDwarf > tu as jete un oeil sur l'implementation de qsort() de la CRT ? Tu peux le voir sinon dans ma source sur Villes <=> CP, je l'ai detourne pour enlever les pointeurs sur callback de tri. Y a pas un iota de recursivite la dedans et je n'ai pas encore pu trouver un autre algo qui fasse mieux, pourtant j'en ai fai des tests.
cs_Kirua
Messages postés3006Date d'inscriptiondimanche 14 avril 2002StatutMembreDernière intervention31 décembre 2008 9 juin 2004 à 21:38
1997 ça fait pas encore vieux, le C est qd même de loin son ainé, et sa syntaxe est tjs aussi agréable :)
vecchio56
Messages postés6535Date d'inscriptionlundi 16 décembre 2002StatutMembreDernière intervention22 août 201014 9 juin 2004 à 21:36
j'ai fait ca en premiere année de deug mias, mais il faut dire qu'on est pa allé très loin, et comme je connaissais déja le c++, j'ai eu du mal à m'interesser...
MetalDwarf
Messages postés241Date d'inscriptionmardi 29 octobre 2002StatutMembreDernière intervention23 janvier 2006 9 juin 2004 à 21:31
T es en prepa?
C est vrai que sur le plan de la syntaxe c est un peu chiant (surtout Caml-Light, qui date quand meme de 1997!!), et qu a mon avis ce n est quand meme pas aussi bien que le C, mais c est assez puissant.
On a fait recemment des TPO sur les grands nombres. C est impressionnant la facilite avec laquelle ca se fait en Caml!! Pareil pour les operations sur les arbres.
En plus au debut j avais HORREUR de la recursivite et finalement c est tres agreable a utiliser, et tres naturel (meme si parfois mes instincts iteratifs du C reviennent...)
vecchio56
Messages postés6535Date d'inscriptionlundi 16 décembre 2002StatutMembreDernière intervention22 août 201014 9 juin 2004 à 21:24
moi en ce qui concerne caml j'en suis encore au début, c'est a dire que je déteste
cs_Kirua
Messages postés3006Date d'inscriptiondimanche 14 avril 2002StatutMembreDernière intervention31 décembre 2008 9 juin 2004 à 21:17
intéressant comme page, merci!
MetalDwarf
Messages postés241Date d'inscriptionmardi 29 octobre 2002StatutMembreDernière intervention23 janvier 2006 9 juin 2004 à 21:08
Je ne crois pas que le compilateur de OCaml retranscrive les fonctions recursives en fonctions iteratives, car bien qu un theoreme existe en informatique theorique la dessus, il est TRES difficile (voir parfois presque impossible) de faire la traduction.
Ce benchmark a ete fait en 2001, mais permet de donner une idee...
Et je rappelle que les structures de donnees ont leur importance. Travailler sur un arbre recursivement est elegant et rapide, de meme que sur une liste. Et puis pour les tris et plein d autre choses, la recursivite est quasi-indispensable.
Voila. En tout cas jetez un oeil au Caml, j ai deteste au debut et maintenant je trouve ca tres fort.
BruNews
Messages postés21040Date d'inscriptionjeudi 23 janvier 2003StatutModérateurDernière intervention21 août 2019 9 juin 2004 à 19:10
Le truc serait de savoir si on fait des comparaisons sur une func recursive C et CAML, il faudrait comparer a une fonction C bien ecrite j'entends par la ou on a supprime la recursivite.
Si CAML a un compilo qui traduit la recursivite en iteratif ok c'est performant sinon recursif sera toujours moins bon qu'iteratif, qu'on le regrette ou non.
MetalDwarf
Messages postés241Date d'inscriptionmardi 29 octobre 2002StatutMembreDernière intervention23 janvier 2006 9 juin 2004 à 18:54
> La recursivite c est pas efficace...
... Oui et non. En fait ca peut le devenir si le langage est concu pour. Je ne sais pas si tu connais le langage Caml (ou plutot le OCaml, qui est oriente objet), il a ete entierement concu autour de la recursivite et de l informatique theorique. Il se trouve que ce langage est elegant (recursivite a tous les etages) ET performant. D apres des tests, il est pas loin du tout du C, ce qui est quand meme fort. Je ne connais pas l implementation interne de la chose, mais faire des fonctions relativement sophistiquees en 2 lignes ca me plais. Si tu veux essayer de voir ca va sur le site de l INRIA (je connais ce langage car il est au programme en prepa MPSI option info). Il est en d ailleurs de meme avec tous les langages fonctionnels comme le LISP.
> L interet de la fonction de McCarthy c est de faire calculer a des eleves la correction de l algorithme et de resoudre le probleme de sa terminaison ( ce que j ai effectivement fait cette annee...)
Voila sur ce @+
BruNews
Messages postés21040Date d'inscriptionjeudi 23 janvier 2003StatutModérateurDernière intervention21 août 2019 9 juin 2004 à 15:51
non ceci est un des nombreux bugs apprarus depuis le dernier crash chez l'hebergeur il y a a peu pres 2 mois. Ce n'est pas sur toutes les sources, certaines je n'ai pas non plus de retour.
Elegance et performance, c'est bon pour Cabrel, a part rimer ça va rarement ensemble.
Recurrent va PUSHer nbr params + 1 (EIP) a chaque tour et ensuite recuperer valeurs pendant depilage, a savoir qu'un PUSH est couteux et la relecture sur la stack pas moins. Imagine un tableur ecrit de cette façon...
cs_Kirua
Messages postés3006Date d'inscriptiondimanche 14 avril 2002StatutMembreDernière intervention31 décembre 2008 9 juin 2004 à 15:45
ah ben non j'ai rêvé, dommage :(
cs_Kirua
Messages postés3006Date d'inscriptiondimanche 14 avril 2002StatutMembreDernière intervention31 décembre 2008 9 juin 2004 à 15:43
itératif c'est avec des boucles, c'est ça? j'y connais pas grand chose en compilation, mais il me semble que qd c récursif, ça grossit la place oqp dans le tas. Si c'est itératif comme tu dis, je suppose que ce phénomène n'a plus court. Dommage, parce que la récursivité c'est élégant ^^
Dis BruNews, je rêve ou je ne reçois plus de mail quand c'est moi qui poste un commentaire? C'était ça la surprise que t'avais annoncée? :) Parce que j'aimerais que ce ne soit pas une erreur ponctuelle, c'état (c'est?) tellement emmerdant :p
BruNews
Messages postés21040Date d'inscriptionjeudi 23 janvier 2003StatutModérateurDernière intervention21 août 2019 9 juin 2004 à 15:37
les suites de Fibonacci tout comme cet exemple feraient un tres bon exemple en tant que modele dont on supprimerait la recursivite. Le passage du recursif a l'iteratif me semble plus interessant car nettement plus performant, il y a une nombreuse litterature sur le sujet.
cs_Kirua
Messages postés3006Date d'inscriptiondimanche 14 avril 2002StatutMembreDernière intervention31 décembre 2008 9 juin 2004 à 15:29
mouarf brunews, ts les étudiants arrivent pas à l'unif en sachant programmer :) et puis ça ns fait une lgueur d'avance qd on y est :p (enfin, toi ça fait un bail que t'y es plus il me semble).
c'est marrant qd même comme propriété. puis c une jolie illustration de la récurrence (quoique, les suites de fibonacci sont assez élégantes à programmer aussi ^^)
BruNews
Messages postés21040Date d'inscriptionjeudi 23 janvier 2003StatutModérateurDernière intervention21 août 2019 9 juin 2004 à 13:40
1 MILLION d'excuses, je n'avais pas vu la double imbrication d'appel recurrent.
Ben si c'est ce que les etudiants apprennent.... Faut bien amuser les processeurs, ils sont si puissants maintenant.
if(x < 91) return 91;
softwareds
Messages postés11Date d'inscriptionvendredi 28 mai 2004StatutMembreDernière intervention 7 mai 2008 9 juin 2004 à 13:34
"A vue de nez et en mangeant, me semble que
func91McCarthy(63) donnera 97 et non 101."
Copiez coller de l'execution du programme :
> Si vous entrez une valeur <101, vous obtiendrez 91.
> x= 63
> Resultats: 91
"et si on entre une valeur >= 91?"
tant que l avaleur est inferieure à 101 tu obtiendras 91, sinon tu obtiendras ta valeur-10
"ET LE BUT ???"
c'est un exo classqiue que beaucoup d'étudiants d'université doivent connaitre.
BruNews
Messages postés21040Date d'inscriptionjeudi 23 janvier 2003StatutModérateurDernière intervention21 août 2019 9 juin 2004 à 13:16
A vue de nez et en mangeant, me semble que
func91McCarthy(63) donnera 97 et non 101.
ET LE BUT ???
vecchio56
Messages postés6535Date d'inscriptionlundi 16 décembre 2002StatutMembreDernière intervention22 août 201014 9 juin 2004 à 12:07
10 juin 2004 à 17:53
Kirua > En fait, pour Caml 1997 ca fait vieux. C est un langage developpe a l INRIA et de nombreuses versions sont apparues depuis. Caml-light est une sorte de brouillon en fait, car il ne compile pas en code natif par exemple, et c est un systeme assez minimal. OCaml est apparu depuis, est oriente objet, compile en code natif sur Unix et Windows (et MacOS je crois), et possede aussi une machine virtuelle un peu a la java. De plus d apres les concepteurs de Caml, OCaml est au moins 2x plus rapide que Caml-light.
BruNews > Il est vrai qu un algorithme recursif est tres souvent plus rapide qu alogorithme iteratif. Cependant il ne faut pas oublier que la fiabilite d un code compte aussi. Passer des heures a debugger a cause d effets de bord subtiles est penible et peut etre un inconvenient plus grand que la difference de performances a l execution. Un autre point particulierement important est l aspect fiable des programmes ecris dans des langages fonctionnels comme OCaml. Il est en effet possible de prouver mathematiquement le bon fonctionnement d un algorithme en Caml (surtout si l algorithme est recursif et n utilise pas de variables au sens du C), ce qui est indispensable dans certains domaines. C est pour cela que certaines compagnies tres importantes utilisent des langages de ce type (par exemple je crois qu Airbus travaille avec des chercheurs en info pour prouver leurs programmes. Je ne sais pas si ils sont ecrit en Caml, mais c est important a noter).
Je tiens quand meme a signaler que je ne suis pas du tout un extremiste de la recursivite. Je n ecris presque jamais de fonctions recursives en C...
Juste un petit exemple d algo recursif qu on le veuille ou non : l algo Mini-Max ou alpha-beta utilise dans les jeux d echecs entre autres (il est peut etre possible de le faire iterativement, mais je ne l ai jamais vu).
9 juin 2004 à 21:50
9 juin 2004 à 21:38
9 juin 2004 à 21:36
9 juin 2004 à 21:31
C est vrai que sur le plan de la syntaxe c est un peu chiant (surtout Caml-Light, qui date quand meme de 1997!!), et qu a mon avis ce n est quand meme pas aussi bien que le C, mais c est assez puissant.
On a fait recemment des TPO sur les grands nombres. C est impressionnant la facilite avec laquelle ca se fait en Caml!! Pareil pour les operations sur les arbres.
En plus au debut j avais HORREUR de la recursivite et finalement c est tres agreable a utiliser, et tres naturel (meme si parfois mes instincts iteratifs du C reviennent...)
9 juin 2004 à 21:24
9 juin 2004 à 21:17
9 juin 2004 à 21:08
A titre indicatif :
http://www.bagley.org/~doug/shootout/craps.shtml
Ce benchmark a ete fait en 2001, mais permet de donner une idee...
Et je rappelle que les structures de donnees ont leur importance. Travailler sur un arbre recursivement est elegant et rapide, de meme que sur une liste. Et puis pour les tris et plein d autre choses, la recursivite est quasi-indispensable.
Voila. En tout cas jetez un oeil au Caml, j ai deteste au debut et maintenant je trouve ca tres fort.
9 juin 2004 à 19:10
Si CAML a un compilo qui traduit la recursivite en iteratif ok c'est performant sinon recursif sera toujours moins bon qu'iteratif, qu'on le regrette ou non.
9 juin 2004 à 18:54
... Oui et non. En fait ca peut le devenir si le langage est concu pour. Je ne sais pas si tu connais le langage Caml (ou plutot le OCaml, qui est oriente objet), il a ete entierement concu autour de la recursivite et de l informatique theorique. Il se trouve que ce langage est elegant (recursivite a tous les etages) ET performant. D apres des tests, il est pas loin du tout du C, ce qui est quand meme fort. Je ne connais pas l implementation interne de la chose, mais faire des fonctions relativement sophistiquees en 2 lignes ca me plais. Si tu veux essayer de voir ca va sur le site de l INRIA (je connais ce langage car il est au programme en prepa MPSI option info). Il est en d ailleurs de meme avec tous les langages fonctionnels comme le LISP.
> L interet de la fonction de McCarthy c est de faire calculer a des eleves la correction de l algorithme et de resoudre le probleme de sa terminaison ( ce que j ai effectivement fait cette annee...)
Voila sur ce @+
9 juin 2004 à 15:51
Elegance et performance, c'est bon pour Cabrel, a part rimer ça va rarement ensemble.
Recurrent va PUSHer nbr params + 1 (EIP) a chaque tour et ensuite recuperer valeurs pendant depilage, a savoir qu'un PUSH est couteux et la relecture sur la stack pas moins. Imagine un tableur ecrit de cette façon...
9 juin 2004 à 15:45
9 juin 2004 à 15:43
Dis BruNews, je rêve ou je ne reçois plus de mail quand c'est moi qui poste un commentaire? C'était ça la surprise que t'avais annoncée? :) Parce que j'aimerais que ce ne soit pas une erreur ponctuelle, c'état (c'est?) tellement emmerdant :p
9 juin 2004 à 15:37
9 juin 2004 à 15:29
c'est marrant qd même comme propriété. puis c une jolie illustration de la récurrence (quoique, les suites de fibonacci sont assez élégantes à programmer aussi ^^)
9 juin 2004 à 13:40
Ben si c'est ce que les etudiants apprennent.... Faut bien amuser les processeurs, ils sont si puissants maintenant.
if(x < 91) return 91;
9 juin 2004 à 13:34
func91McCarthy(63) donnera 97 et non 101."
Copiez coller de l'execution du programme :
> Si vous entrez une valeur <101, vous obtiendrez 91.
> x= 63
> Resultats: 91
"et si on entre une valeur >= 91?"
tant que l avaleur est inferieure à 101 tu obtiendras 91, sinon tu obtiendras ta valeur-10
"ET LE BUT ???"
c'est un exo classqiue que beaucoup d'étudiants d'université doivent connaitre.
9 juin 2004 à 13:16
func91McCarthy(63) donnera 97 et non 101.
ET LE BUT ???
9 juin 2004 à 12:07