Complexité pour programme simple

[leon1789]

Chez moi, le code tourne parfaitement.

[Dlzlogic]

Bon, je complète lma réponse, parce que le problème me parait intéressant.
Le cas typique d'utilisation de la récurrence consiste à vouloir adresser tous les éléments élémentaires d'une organisation en objets.
Un objet contient plusieurs objet, lesquels, éventuellement, objets. Au bout de la liste il y a un ou plusieurs élément(s) élémentaire(s) ou d'autres sous-objets.

La fonction pourrait se présenter ainsi :

Code: Tout sélectionner

bool Function(objet)
{
  pour chaque élément de l'objet
    si   element == "élémentaire"
      alors Traitement(...)
      return TRUE
    sinon
      Fonction(element)
      return FALSE
    fin si
  fin pour
  return TRUE
}


Je n'imagine pas comment une fonction récursive pourrait être en "mode terminal"

[leon1789]

Pourquoi écrire "return FALSE" ? Pour éviter un appel récursif terminal ?

[/CODE]Je n'imagine pas comment une fonction récursive pourrait être en "mode terminal"

ah... bon, alors tu peux lire les dernières pages de ce petit diaporama par exemple https://www.lri.fr/~hivert/COURS/M2-CCI/03-Recursivite.pdf

On dit qu’un fonction est récursive terminale, si tout appel récursif
est de la forme return f(...)

[Dlzlogic]

Pourquoi écrire "return FALSE" ? Pour éviter un appel récursif terminal ?

Parce qu'à 23H38 je n'avais plus tout à fait les yeux en face des trous.

[Dlzlogic]

Bonjour Skullkid,
J'ai pas trop bien compris ton explication (cad les 2 codes)
1- que signifie "alors 1" ou "alors acc" ? est-ce une valeur de retour, alors après "alors" il devrait y avoir une instruction. Donc, je suppose que ça doit être compris comme "return FINI"
2- je ne crois pas que la difficulté de la récursivité réside dans le fait de garder en mémoire des valeurs numériques successives, mais de garder en mémoire les adresses de retour.

Il est vrai que il est difficile de programmer une récursivité sans récursivité. La seule méthode que je connaisse est de créer un tableau qui mémorise la succession des appels et donc remplacer ce qu'on utilise maintenant : la pile (stack).

[Dlzlogic]

Bonjour Archytas,
Comme promis, j'ai regardé votre code.
Comme je ne connais pas Maple, j'ai commencé par indenter et numéroter les lignes.

Code: Tout sélectionner

( 1)bifur := proc (rmin, rmax, n, u0, e, p, m)
( 2)  local un, etapun, f, k, L, r;
( 3)  L := [];
( 4)
( 5)  un := proc (r, n)
( 6)    local u, i, f;
( 7)    f :=x-> x*r*(1-x);
( 8)    u := u0;
( 9)    for i to n
(10)      do
(11)        u := f(u)
(13)      end do;
(14)    u ;
(15)  end proc;
(16)
(17)  for r from rmin by p to rmax
(18)    do
(19)      k := 2;
(20)      if abs(un(r, n)-un(r, n+1)) < e
(21)        then
(22)          L := [op(L), [r, un(r, n)]]
(23)        else
(24)          L := [op(L), [r, un(r, n)], [r, un(r, n+1)]];
(25)
(26)        while e < abs(un(r, n)-un(r, n+k)) and k < m
(27)          do
(28)            k := k+1;
(29)            L := [op(L), [r, un(r, n+k)]]
(30)          end do
(31)      end if
(32)    end do;
(33)  plots:-pointplot(L, style = point, symbol = point, trickness = 0)
(34)end proc

D'abord, je voudrais être sûr que les niveaux correspondent bien.
En particulier que la procédure un(...) est bien intérieure à la procédure bifur.
J'aimerais bien que vous m'expliquiez en 2 mots la syntaxe des tableaux, on les déclare sans dimension puis on les renseigne avec un rang "op(L)", puis avec 2 ou 3 paramètres. J'ai un peu de mal à comprendre.
Pourquoi créer ce tableau, que contient-il?
En fait je ne connais pas les hypothèses de départ.

[leon1789]

D'accord le voici :
[CODE]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)) et je préfère "unapply". A mon avis,

f :=x-> x*r*(1-x);

serait avantageusement changé en

f := unapply(x*r*(1-x), x);

Par ailleurs, tu utilises une liste L pour collecter des objets. Or c'est nettement plus joli de le faire avec une suite : cela évite des opérations op() pour libérer les [], puis remettre des crochets [] pour revenir à une liste, en permanence !

(...)
L := [];
(...)
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)]];
(...)
L := [op(L), [r, un(r, n+k)]] end do
plots:-pointplot(L, style = point, symbol = point, trickness = 0)
end proc

serait amélioré en

(...)
L := NULL; # L = suite vide
(...)
if abs(un(r, n)-un(r, n+1)) < e then L := L, [r, un(r, n)]
else
L := L, [r, un(r, n)], [r, un(r, n+1)];
(...)
L := L, [r, un(r, n+k)] end do

plots:-pointplot( [ L ] , style = point, symbol = point, trickness = 0)
end proc

en mettant des [] seulement au dernier moment (plots).

[leon1789]

Et tout ce passage peut être simplifié !

Code: Tout sélectionner

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


Perso, j'écrirais (avec une suite L) :

Code: Tout sélectionner

L := L, [r, un(r, n)] ;
for k to ceil(m)-1 while e < abs(un(r, n)-un(r, n+k)) do
  L :=  L, [r, un(r, n+k)]
end do


[leon1789]

Et tout ce passage peut être simplifié !

Code: Tout sélectionner

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


Perso, j'écrirais (avec une suite L) :

Code: Tout sélectionner

L := L, [r, un(r, n)] ;
for k to ceil(m)-1 while e < abs(un(r, n)-un(r, n+k)) do
  L :=  L, [r, un(r, n+k)]
end do


Remarque : si m est un entier, alors ceil(m) se simplifie en m.

[Archytas]

D'accord léon merci, je connais pas l'opérateur @@ ! Et l'affectation -> marche très bien je n'ai jamais eu de soucis avec. Ce qui me gène que ce soit liste ou séquence c'est de garder les valeur calculer et les afficher à la fin, c'est extrèmement long !!!! Point par point ça se ferais en quelques minutes tout au plus.

Si je peux me permettre une petite explication de mon code pour qu'éventuellement vous me disiez s'il y a des erreurs de logique ou des maladresse chronophages :id: !
un(r,n) calcul la n ème valeur de la suite (f@@n)(u0). Ensuite je compare deux termes consécutifs pour n "grand" s'ils sont très proches (la valeur absolue de leur différence est inférieur à "e" petit) j'en conclu qu'il sera de même pour ceux qui suivent. Donc une seule valeur de convergence si ça n'est pas le cas on compare ce même terme avec le successeur du successeur jusqu'à ce que le différence soit

[leon1789]

En conclusion, avec tous les changements proposés (contenu et présentation), ton code deviendrait celui-ci

Code: Tout sélectionner

bifur := proc (rmin, rmax, n, u0, e, p, m)
  local un, etapun, f, k, L, r;
  L := NULL ;

  un := proc (r, n)
    local u, i, f;
    f := unapply(x*r*(1-x), x);
    return  (f@@n)(u0) ;
  end proc;

  for r from rmin by p to rmax do
    L := L, [r, un(r, n)] ;
    for k to ceil(m)-1 while e < abs(un(r, n)-un(r, n+k)) do
       L :=  L, [r, un(r, n+k)]
    end do
  end do

  plots:-pointplot([L], style = point, symbol = point, trickness = 0)
end proc


[leon1789]

Ce qui me gène que ce soit liste ou séquence c'est de garder les valeur calculer et les afficher à la fin, c'est extrèmement long !!!! Point par point ça se ferais en quelques minutes tout au plus.

je comprends. Pour l'instant, je ne vois comment faire plaisir à pointplot sans lui donner une liste énorme.

Si je peux me permettre une petite explication de mon code pour qu'éventuellement vous me disiez s'il y a des erreurs de logique ou des maladresse chronophages :id: !
un(r,n) calcul la n ème valeur de la suite (f@@n)(u0). Ensuite je compare deux termes consécutifs pour n "grand" s'ils sont très proches (la valeur absolue de leur différence est inférieur à "e" petit) j'en conclu qu'il sera de même pour ceux qui suivent.

On peut optimiser le code en ce qui concerne le calcul des un(r,n) , un(r,n+1), un(r,n+2), ... sans repartir de u0 à chaque fois. A suivre.

[leon1789]

On peut optimiser le code en ce qui concerne le calcul des un(r,n) , un(r,n+1), un(r,n+2), ... sans repartir de u0 à chaque fois. A suivre.

A la place de cela

Code: Tout sélectionner

  for r from rmin by p to rmax do
    L := L, [r, un(r, n)] ;
    for k to ceil(m)-1 while e  abs(v-u) then break end if ;  # on sort de la boucle for k
       L :=  L, [r, u]
    end do
  end do


Ce code est un peu plus lourd à lire, mais plus efficace car il ne calcule pas plusieurs fois les mêmes un(r, ...) en laissant faire f@@(n+k) .
Tu vois ce que je veux dire ?

[adrien69]

Un algorithme sans commentaire c'est comme un pet. C'est bien seulement si c'est le tien.

[leon1789]

En conclusion, avec tous les changements proposés (contenu et présentation), ton code deviendrait celui-ci

Code: Tout sélectionner

bifur := proc (rmin, rmax, n, u0, e, p, m)
  local u,v, f, k, L, r;
  L := NULL ;

  for r from rmin by p to rmax do
    f := unapply(x*r*(1-x), x);
    v := (f@@n)(u0) ;     # ici, v = un(r, n)
    L := L, [r, v] ;
    u := v ;
    for k to ceil(m)-1 do
       u := f(u) ;       # ici, u = un(r, n+k)
       if e > abs(v-u) then break end if ;  # on sort de la boucle for k
       L :=  L, [r, u]
    end do
  end do  ;

  plots:-pointplot([L], style = point, symbol = point, trickness = 0)
end proc ;


[leon1789]

Un algorithme sans commentaire c'est comme un pet. C'est bien seulement si c'est le tien.

absolument d'accord, surtout dans les boucles : je pense qu'il faut prendre l'habitude de signaler un (ou des) invariant(s) de boucle pour montrer comment l'algo évolue et ne pas se perdre dans les indices.

[adrien69]

Je ne disais pas ça pour toi, ta présentation est très claire (même si je ne connais ni le but du truc -j'ai juste jeté un coup d'oeil- ni le "@@" donc je ne peux pas deviner) mais pour Archytas qui passe des concours l'an prochain. C'est une petite formulation que j'aime bien et qu'avait coutume d'employer mon prof d'info en prépa. Ça se décline à toutes les sauces : "un calcul sans commentaire, etc", "une ipp sans les fonctions, etc", "une copine nympho, etc", etc.

p-s. Jolie fractale linguistique n'est-il pas ?

[leon1789]

Pour être un peu plus efficace dans le stockage, on peut inverser les objets :

Code: Tout sélectionner

     
L := [r, v], L ;
(...)
L := [r, u], L ;

est peut-être meilleur que

Code: Tout sélectionner

     
L := L, [r, v] ;
(...)
 L := L, [r, u] ;

Cela inverse complètement la liste [L], mais cela n'a pas d'importance car tu ne fais que du pointplot (a priori, mais je ne connais pas la suite de ton calcul...)

[Dlzlogic]

Un algorithme sans commentaire c'est comme un pet. C'est bien seulement si c'est le tien.

A mon avis, ça vaut même pas un pet.
Au bout de plusieurs années, je défie l'auteur d'un code de se relire s'il n'y a pas de commentaire.
J'avais prévu comme seconde étape de demander à Archytas de documenter son code, mais heureusement Léon est arrivé pour tout refaire.

Je préfère utiliser le terme "algorithme" pour une suite logique d'opérations, souvent écrit en français, quelque-fois sous forme d'ordinogramme, en tout cas toujours compréhensible, indépendamment de tout langage. Pour les trucs un peu compliqués, je le fais encore en début de mes modules. Souvent une dizaine de lignes suffisent, même si le code qui suit fait plusieurs centaines de lignes. C'est la distinction entre l'étape "analyse" et l'étape programmation. Cette seconde étape pouvant être confiée à n'importe qui. et écrite dans n'importe quel langage adapté au problème traité.

[Archytas]

Ok ouais désolé j'ai donné l'expli qu'après.
J'ai plusieurs questions : pourquoi L:=[r,u],L mieux que l'inverse ? Et j'ai pas super bien compris la fonction break :/.

PS: désolé pour l'algo flatulent !