Complexité pour programme simple

[Archytas]

Salut,
J'aurais besoin de votre aide, je vais devoir faire tourner beaucoup de programme avec une certaine complexité et du coup pour gagner du temps je voudrais minimiser la complexité. J'ai deux programmes qui sortent le même résultat un récursif et l'autre itératif habituellement pour savoir quel programme utiliser j'utilise l'option "time" de maple qui retourne le temps entre la demande du résultat et le résultat lui même. Sauf que pour mes programmes pour une une valeur de n faible time me dit que c'est le récursif le mieux et pour n très grand c'est l'itératif qui l'emporte or à vue de nez je dirais qu'ils ont exactement la même complexité alors y en a-t-il un mieux que l'autre ou c'est un bug de la fonction time qui est approximative ?

Les programmes c'est l'équation logistique avec f:x->rx(1-x) et x le paramètre ! Pour la suite à calculer qui m'interesse elle est définie par u0 et u_(n+1)=f(u_n).
Pour l'itératif j'ai "pour k = 1 à n faire u := f(u)"
Pour le récursif j'ai (le programme s'appelle un) "si n = 0 alors u0 sinon f(un(n-1))"
Si vous voulez plus de précision hesitez pas !

Edit: Je pense que c'est la fonction "time" qu'est un peu pourrave d'une fois sur l'autre elle me renvoit des résultats complétement différents quand je lui demande la même chose !
Par contre pour le récursif j'ai un petit problème...
Pour chaque programme je dois rentrer comme valeur n,u0,r et du coup pour diminuer la complexité j'ai fait un programme qui prend en fonction n,u0,r et à l'interieur j'ai fait un programme récursif qui prend en argument que "n" ce qui devrait être moins complexe comme il y a moins de paramètres sauf que le logiciel me sort en erreur "Error, (in run) too many levels of recursion
" :hum: !!

[Dlzlogic]

Bonjour,
La récursivité est une bonne technique, mais doit être utilisée avec modération.
Autrefois, c'est à dire avec des langages anciens, le nombre de niveaux étaient limité (à 7 de mémoire).
Dans tous les bouquins de programmation on cite l'exemple avec le calcul de n! (factorielle), et le temps d'exécution est beaucoup plus long.
Donc, dans votre cas, c'est surement l'itération qui est préférable.
Concernant le dépassement de mémoire, la raison est très simple, la fonction utilisée en récursivité est gardée dans la pile, donc autant de fois que celle-ci est appelée. Il suffit de dessiner un petit algorithme pour s'en persuader.

Concernant le timer, cette fonction marche forcément parfaitement. Il faut savoir que le timer n'est appelé que de temps en temps, en tout cas beaucoup moins souvent que les étapes de la boucle. Donc, il est tout à fait normal que deux exécutions identiques ne donnent pas le même résultat.

Ais-je été clair ?

[Edit] Si vous voulez faire du développement informatique, c'est à dire de la programmation, je vous conseille vivement d'apprendre un langage de bas niveau, par exemple C/C++.

[Archytas]

D'accord pour la récursivité mais pour le dépassement de mémoire je comprends pas vraiment, qu'entendez vous par "gardé dans la pile" ? Je me rappelle qu'en cours d'informatique on a utilisé cette méthode assez souvent : faire un programme et faire un sous programme dans le programme et l'appeler à la fin :/ !
Pour le timer j'ai pas trop compris non plus son fonctionnement est étrange, je rentre :
time(un(100000, .1, 3));
1.170
time(un(100000, .1, 3));
0.858

sans avoir modifié quoi que ce soit...
Edit:
J'aimerais beaucoup m'interesser aux langages C++ et Python mais je préfère attendre encore un an pour ne pas me mélanger avec le langage officiel de classe MP d'informatique qui est Caml et celui de mathématique qui est Maple. Cependant il me semble qu'avec la réforme c'est Python qui sera au programme (donc pour les sup de l'année qui vient).

[Dlzlogic]

Bon, je vais écrire l'algorithme utilisé par la machine pour faire la récursivité.
J'appelle R la fonction de récursivité

Code: Tout sélectionner

Début
Appel de R
  si fini reour
  sinon
    appel de R
      si fini retour
      sinon
        appel de R
          si fini retour
........
                          appel de R
                          si fini retour 
                          là, on suppose qu'on a fini
                          donc on repasse par toutes les fonctions, et celles-ci seront supprimées de la pile.
Fin



Chaque fonction est gardée tant que on n'a pas fini.


Dans le cas de l'itération

Code: Tout sélectionner

Début
  Tant que pas fini
    calcul
  fin tant que
fin


Là la fonction "calcul" s'exécute n fois, elle est chargée à chaque fois, mais comme elle s'est terminée elle est supprimée de la pile.
Les langes évolué prévoient la possibilité de dire à une fonction "elle est courte, tu la garde en mémoire, c'est la même qui sert souvent".
Ce n'est pas possible avec une fonction récursive, puisque c'est elle-même qui s'appelle pour une nouvelle exécution.

Pour le timer, supposons que le timer soit appelé toutes les secondes.
En deux appels, le calcul a pu se faire 1000 fois.
Donc, il faudrait un sacré coup de chance pour que à chaque exécution, la lecture du timer se fasse exactement au même nombre de calculs.

L'argument "ne pas se mélanger entre les langages" ne tient pas. (autre sujet de discussion).

[Skullkid]

Bonjour, si on compte la complexité en nombre de multiplications, ton algo itératif a une complexité égale à 2n (on dira plutôt O(n), on ne soucie pas des facteurs constants) mais ton algo récursif a peut-être une complexité supérieure. Je dis "peut-être" car cela dépend de ce que fait Maple lorsqu'on lui demande de calculer "f(g(x))". Dans ton cas f(x) = r*x*(1-x) et g est ta fonction récursive. Deux possibilités :

- Soit Maple calcule d'abord g(x) pour ensuite calculer f du résultat, ce qui donne une complexité finale en O(n) identique à celle de l'algorithme itératif.
- Soit Maple appelle d'abord f, c'est-à-dire cherche à calculer r*g(x)*(1-g(x)), auquel cas il va appeler 2 fois g au lieu d'une seule, ce qui débouche sur une complexité finale en O(2^n).

Dans le doute, tu peux essayer de remplacer "si n>0 évaluer f(g(n-1))" par "si n>0 poser x = g(n-1) et évaluer f(x)", ce qui force une complexité en O(n).

Une chose qu'il faut bien comprendre aussi, c'est que la complexité d'un algorithme ne se traduit pas facilement en temps d'exécution. Le temps d'exécution dépend de ton ordi, de ce qu'il est en train de faire en même temps (tu as des processus qui tournent en tâche de fond, d'autres programmes qui tournent pendant que tu calcules, ...) et du langage que tu utilises. Ce n'est pas étonnant que le timer te renvoie des temps d'exécution différents pour le même appel à deux moment différents : ta machine n'est pas dans le même état à ces deux moments.

Ton "too many levels of recursion" peut être dû à la complexité en O(2^n) ou à un oubli de ta part quant à la condition de fin de descente récursive.

[Archytas]

D'accord mais ce que je ne comprends pas c'est pourquoi ça marche quand je fais le programme récursif à l'exterieur et qu'il prend tous les arguments et quand je le met dans le gros il ne marche plus (message d'erreur).
Quant aux différents langages je sais que si je fais trop de Caml j'ai tendance à mélanger dans Maple du style "let un m n p = ... " au lieu de "un := proc(m,n,p)" et inversement dans Caml. Si je me mélange entre deux langages je préfère ne pas prendre de risque en en rajoutant un troisième et un quatrième. Je ne pense pas qu'on puisse prétendre qu'on ne se mélange pas, j'ai toujours été assez vigilant en DS pour que ces mélanges ne me coutent que le temps de la relecture mais d'autre ne peuvent pas en dire autant et les points comtent autant que le temps pour un concours alors attendre un an de plus ne me fera je pense pas trop de mal.

[Dlzlogic]

D'accord mais ce que je ne comprends pas c'est pourquoi ça marche quand je fais le programme récursif à l'exterieur et qu'il prend tous les arguments et quand je le met dans le gros il ne marche plus (message d'erreur).

Ca veut dire quoi "à l'extérieur" ?
Maple est un langage interprété. Vous n'imaginez pas tout ce qui se passe. Avec un langage qui compile et exécute le binaire, ce serait peut être plus clair pour vous.
En tout cas, il est indispensable de comprendre ce qu'est une fonction récursive, parce que dans certains cas, c'est pratiquement la seule solution. Mais c'est pas pour ça que c'est la panacée universelle.
Je ne peux que conclure que mon explication n'a pas été claire.
Disons que pour l'instant, essayez de me croire.

[Archytas]

Ca veut dire quoi "à l'extérieur" ?

J'en ai fait un qui ne prend en argument que "n" mais qui est à l'intérieur d'un autre programme qui contient les information u0 et r et un autre qui est tout seul (à l'extérieur : oui après reflexion ça ne veut rien dire) qui contient toutes les informations et qu'on doit donc répéter dans les appels récursifs ! Nos profs nous avez conseillé pour résoudre le problème de la complexité exponentielle de la récursivité d'utiliser la fonction maple "option remember" mais je suis bien incapable de vous dire comment et pourquoi elle marche.

Je ne peux que conclure que mon explication n'a pas été claire.

Ne prenez pas la mouche, je suis très lent à comprendre !

Décidément c'est pas ma tasse de thé ce programme, j'arrive à afficher le diagramme de bifurcation jusqu'à une valeur du paramètre r=3.5 avec une temps assez merdique il faut le dire (10s à 1min suivant la précision que je demande) mais impossible d'aller juqu'à 3.6 quelque soit la précision et pour cause quand je lui demande le 1000ème terme de la suite pour le paramètre 4.1 il me répond gentillement -Float().
Edit : ok pour l'infini c'est que la suite diverge !

[Dlzlogic]

Ne prenez pas la mouche, je suis très lent à comprendre !

Oh, non, je ne prends surement pas la mouche, mais l'informatique, c'est tellement compliqué que dans bien des cas, il faut "croire", et on comprendra ensuite, voire au bout de plusieurs années.
Alors, croyez moi, n'utilisez la récursivité que si c'est nécessaire.

[Archytas]

Oh, non, je ne prends surement pas la mouche, mais l'informatique, c'est tellement compliqué que dans bien des cas, il faut "croire", et on comprendra ensuite, voire au bout de plusieurs années.
Alors, croyez moi, n'utilisez la récursivité que si c'est nécessaire.

Notre professeur nous avait dis la même chose : on apprends à programmer, pas ce qu'il y a derrière. Mais j'arrive pas à croire aveuglément, j'y peux rien ça rentre pas. J'arrive pas à retenir un théorème si je n'ai pas été convaincu de la démonstration (ou si je ne l'ai pas compris) :ptdr: ! Bref c'est pas le sujet mais ça explique ma lenteur !
Et c'est bien compris j'utiliserai un maximum d'itératif pour ma programmation personnelle ! En tout cas merci à tous : le programme tourne depuis une dixaine de minute pour m'afficher le graphe jusqu'à r=3.9 je pense qu'il en a encore pour entre 30min et 2h à tourner si le pc lache pas avant :mur: ! J'essairai de vous envoyer l'image quand elle sortira. Pour la petite info je fais ça pour mon TIPE avec un pote on veut le faire sur la théorie du chaos donc voilà, je risque dans l'année de vus redemander de l'aide sur le sujet (: !

[Archytas]

Voici le rendu, c'est pas génial, mon pc n'est pas une bête de calcul mais bon :

[img][IMG]http://img11.hostingpics.net/pics/858310DiagrammedeBifurcation.png[/img][/IMG]

merci encore !

[Dlzlogic]

Bonsoir,
Oui, c'est vraiment très joli.

[Dlzlogic]

Bonjour,
Je voudrais ajouter un petit complément à propos des fonctions utilisant la récursivité, c'est à dire une fonction qui s'appelle elle-même.
Le Fortran ne permettait pas la récursivité (Fortran IV et Fortran 77). On utilisait alors un astuce : on créait 2 fonctions A et B qui s'appelaient mutuellement. On trompait ainsi de compilateur. Mais on avait une possibilité : on pouvait créer un point d'entrée dans une fonction. Cela rendait donc la chose possible.
Je crois que cette méthode ne peut plus être employée, à cause de l'organisation différente de la mémoire. Il en résulte que la récursivité est devenue nécessaire, mais doit être utilisée avec modération.
A mon avis, pour bien la comprendre, imaginons qu'on cherche un article dans un bouquin. Cet article renvoie à un autre article du même ouvrage. On va naturellement laisser le premier bouquin ouvert et prendre dans la bibliothèque un bouquin identique, et ainsi de suite.
On aura donc sur la table autant de livres identiques ouverts à des pages différentes ou identiques. On peut même empiler les livres ouverts à la page concernée, d'où le nom de pile (LastInFirstOut) Quand on aura trouvé la réponse sur le énième bouquin, on pourra le fermer et le ranger, puis continuer la lecture de l'article sur le précédent, puis le refermer, etc. jusqu'à revenir sur le premier, terminer l'article et enfin le refermer.

Avec une méthode itérative, c'est toujours le même bouquin qui est consulté, mais l'article lu ne renvoie pas à un autre article. On n'a besoin que d'une toute petite table.

[Archytas]

Bonjour,
Je voudrais ajouter un petit complément à propos des fonctions utilisant la récursivité, c'est à dire une fonction qui s'appelle elle-même.
Le Fortran ne permettait pas la récursivité (Fortran IV et Fortran 77). On utilisait alors un astuce : on créait 2 fonctions A et B qui s'appelaient mutuellement. On trompait ainsi de compilateur. Mais on avait une possibilité : on pouvait créer un point d'entrée dans une fonction. Cela rendait donc la chose possible.
Je crois que cette méthode ne peut plus être employée, à cause de l'organisation différente de la mémoire. Il en résulte que la récursivité est devenue nécessaire, mais doit être utilisée avec modération.
A mon avis, pour bien la comprendre, imaginons qu'on cherche un article dans un bouquin. Cet article renvoie à un autre article du même ouvrage. On va naturellement laisser le premier bouquin ouvert et prendre dans la bibliothèque un bouquin identique, et ainsi de suite.
On aura donc sur la table autant de livres identiques ouverts à des pages différentes ou identiques. On peut même empiler les livres ouverts à la page concernée, d'où le nom de pile (LastInFirstOut) Quand on aura trouvé la réponse sur le énième bouquin, on pourra le fermer et le ranger, puis continuer la lecture de l'article sur le précédent, puis le refermer, etc. jusqu'à revenir sur le premier, terminer l'article et enfin le refermer.

Avec une méthode itérative, c'est toujours le même bouquin qui est consulté, mais l'article lu ne renvoie pas à un autre article. On n'a besoin que d'une toute petite table.

Donc la table c'est la mémoire et moins elle est encombrée plus on s'y retrouve !? Mais si on imagine un programme du type :
exemple(n) = si n = 1 alors 1 sinon exemple(n-1)+n. On aura pas besoin de repasser par ce que vous appeliez tous les articles ? En fait d'après ce que vous me dite le programme fait ça :
exemple(n-1)+n. Il connait pas exemple(n-1) donc il le calcul de la même manière jusqu'a arriver à 1, là est-ce qu'il conclu que exemple(n)=1+2+...+n ou alors ça lui permet de déduire exemple(2) puis 3 puis finalement exemple(n) ?

[Skullkid]

L'analogie de Dlzlogic avec les livres correspond à de la récursivité dite "non terminale", qui en effet requiert par défaut beaucoup plus d'espace mémoire qu'une méthode itérative. Mais il y a aussi la récursivité terminale, qui ne prend pas plus de mémoire qu'une méthode itérative. L'idée est de faire en sorte que les appels récursifs soient exécutés en dernier à chaque niveau de récursion, de sorte qu'il n'y a pas à remonter la descente récursive. En gros, si l'article 2 du journal A renvoie à l'article 15 du journal B, on n'a pas besoin de garder le journal A sur la table puisqu'on sait qu'on n'en aura plus besoin.

Tout algorithme peut s'écrire itérativement ou récursivement, les deux ont leurs avantages et les compilateurs d'aujourd'hui sont très doués pour optimiser les empreintes mémoire des algorithmes récursifs. Certaines structures de données (les octrees, par exemple) et méthodes de programmation (divide and conquer, par exemple) très efficaces sont intimement liées à la récursivité.

Au final c'est surtout une question de goût. À une époque il y avait de vraies raisons de préférer l'itératif (les compilateurs n'étaient pas adaptés, l'espace mémoire était une denrée rare, ...) mais la plupart sont devenues obsolètes et les points forts du récursif (algorithmes de présentation claire, structures de données adaptées) font qu'il est souvent préféré dans beaucoup de problèmes. Bien sûr il faut l'utiliser intelligemment (tout comme l'itératif d'ailleurs), mais je ne vois pas pourquoi Dlzlogic conseille de limiter son usage au maximum.

[Archytas]

L'analogie de Dlzlogic avec les livres correspond à de la récursivité dite "non terminale", qui en effet requiert par défaut beaucoup plus d'espace mémoire qu'une méthode itérative. Mais il y a aussi la récursivité terminale, qui ne prend pas plus de mémoire qu'une méthode itérative. L'idée est de faire en sorte que les appels récursifs soient exécutés en dernier à chaque niveau de récursion, de sorte qu'il n'y a pas à remonter la descente récursive. En gros, si l'article 2 du journal A renvoie à l'article 15 du journal B, on n'a pas besoin de garder le journal A sur la table puisqu'on sait qu'on n'en aura plus besoin.

Tout algorithme peut s'écrire itérativement ou récursivement, les deux ont leurs avantages et les compilateurs d'aujourd'hui sont très doués pour optimiser les empreintes mémoire des algorithmes récursifs. Certaines structures de données (les octrees, par exemple) et méthodes de programmation (divide and conquer, par exemple) très efficaces sont intimement liées à la récursivité.

Au final c'est surtout une question de goût. À une époque il y avait de vraies raisons de préférer l'itératif (les compilateurs n'étaient pas adaptés, l'espace mémoire était une denrée rare, ...) mais la plupart sont devenues obsolètes et les points forts du récursif (algorithmes de présentation claire, structures de données adaptées) font qu'il est souvent préféré dans beaucoup de problèmes. Bien sûr il faut l'utiliser intelligemment (tout comme l'itératif d'ailleurs), mais je ne vois pas pourquoi Dlzlogic conseille de limiter son usage au maximum.

D'accord tout est clair. Merci à vous deux c'est plus clair et j'utiliserai le récursif avec le plus de discernement possible !
Concernant mon graphe j'ai un soucis que j'espère vous pourrez m'aider à contourner. La complexité et le temps de calcul sont assez désastreux (mon pc à tourné toute la nuit pour afficher un graphe qui lui a couté entre 1.900.000 et 1.900.000.000 opérations) parce que je dois stocker des valeurs. Je cherche un mode "point par point" qu'aurait maple. Parce que je dois accumuler des listes pour les afficher "au final" alors qu'avec un mode point par point je n'aurais pas besoin de concerver quoique ce soit et j'aurais un temps de calcul moins élevé. Mon pote de TIPE l'a fait sur Caml avec ce mode et sur le même pc le graphe à mis environ 1 minute à s'afficher avec une meilleure précision... Des idées ? Des fonctions ? Des astuces ?

[Dlzlogic]

@ Skullkid,
Concernant la méthode récursive, mon compilateur a plus de 10 ans.
Quoi qu'il en soit, j'avoue que je ne connaissais pas la récursivité à "mode terminal". De quelle façon précise-t-on le point de retour ? Si tu pouvais me préciser grossièrement l'algorithme, ça m'intéresserait d'essayer. Est-ce valable aussi pour les langages interprétés, type Maple ?
En fait, ma question est simple, s'agit-il d'une particularité de certains langages (type Camel), ou est-ce un méthodee applicable à tous les langages, par exemple C ?

@ Archytas,
Si vous m'envoyez votre code, je pourrai vous donner mon avis.
Si, comme je le suppose, Caml est un langage compilé, alors il n'y a pas vraiment à aller chercher plus loin.

[Archytas]

D'accord le voici :

Code: Tout sélectionner

bifur := proc (rmin, rmax, n, u0, e, p, m)
 local un, etapun, f, k, L, r;
L := [];
un := proc (r, n)
local u, i, f;
f :=x-> x*r*(1-x);
u := u0;
for i to n do u := f(u) end do;
 u ;
end proc;
for r from rmin by p to rmax do
k := 2;
if abs(un(r, n)-un(r, n+1)) < e then L := [op(L), [r, un(r, n)]]
 else
 L := [op(L), [r, un(r, n)], [r, un(r, n+1)]];
 while e < abs(un(r, n)-un(r, n+k)) and k < m do
 k := k+1;
L := [op(L), [r, un(r, n+k)]] end do
end if
 end do;
 plots:-pointplot(L, style = point, symbol = point, trickness = 0)
end proc

Avec rmin et rmax les valeurs minimale et maximale du paramètre n la valeur vers laquelle on teste un, u0 la valeur initiale de la suite qui importe très peu, e la précision du teste de convergence p le pas avec lequel on fait évoluer le paramètre et m le nombre de point maximum pour lesquels on teste si un converge (pour les bandes chaotiques ça représente le nombre de point sur la bande). ça c'est la version "améliorée" celle d'hier était moins bien ordonnée et tous les programmes prenaient toutes les valeurs en arguments presque et certains paramètre comme la fonction f était redéfini systèmatiquement etc... bref je verrais bien ce que ça donne !

[Skullkid]

En fait, ma question est simple, s'agit-il d'une particularité de certains langages (type Camel), ou est-ce un méthodee applicable à tous les langages, par exemple C ?

A priori je dirais que ce n'est pas forcément applicable à tous les algorithmes récursifs (un algorithme récursif terminal peut très facilement être transformé en itératif, alors qu'il faut vraiment galérer pour trouver la version itérative de certains algorithmes récursifs...) mais tous les langages admettant la récursivité devraient pouvoir tirer parti de la récursivité terminale, pourvu que le compilateur ne soit pas trop primitif.

On peut prendre l'exemple classique de la factorielle en pseudo-code. La fonction de base

Code: Tout sélectionner

factorielle(n)
 si n = 0
  alors 1
  sinon n*factorielle(n-1)
 fin si
fin


n'est pas récursive terminale, puisqu'on doit garder en mémoire n pour pouvoir le multiplier par factorielle(n-1) quand le calcul de celui-ci sera terminé. Autrement dit on doit garder en mémoire tous les entiers de 1 à n pendant la descente récursive. Une version récursive terminale est

Code: Tout sélectionner

factorielle_aux(n,acc)
 si n = 0
  alors acc
  sinon factorielle_aux(n-1,n*acc)
 fin si
fin

factorielle(n)
 factorielle_aux(n,1)
fin


Ici il n'y a pas d'encombrement mémoire, puisqu'on ne stocke que acc, dont la valeur change pendant l'éxecution. Il n'y a pas à "remonter" les niveaux récursifs puisque toutes les informations sont directement là une fois la descente finie.

[Dlzlogic]

Bonsoir Skullkid,
Saur erreur, avec mon compilateur, ce code boucle.
La raison : la fonction "factorielle_aux" ne renvoie pas de valeur, donc, avec mon compilateur, elle ne peut pas de terminer.
Sauf erreur de ma part, avec mon compilateur, une fonction doit se terminer et retourne à la ligne suivante.
Autrement dit, une fonction récursive doit forcément avoir une valeur de retour.
Mais ceci doit naturellement être testé.
On va probablement arriver à -MAXINT, puis recommencer. A tester.