Complexité pour programme simple

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 17:25

par leon1789 » 22 Aoû 2013, 22:06

Archytas a écrit:J'ai plusieurs questions : pourquoi L:=[r,u],L mieux que l'inverse ? Et j'ai pas super bien compris la fonction break :/.

J'imagine que pour exécuter un chaînage de deux suites " truc, machin ", le logiciel parcours la suite truc jusqu'à son dernier terme pour y "coller" le premier terme de la suite machin. Si la suite truc est petite (exemple, un seul terme), le parcourt est de courte durée ; si la suite truc est longue, le parcourt sera de longue durée...

La fonction "break" permet de sortir de la boucle de plus haut niveau : dans ton algo, à l'endroit où j'ai placé le break, c'est la boucle "for k" qui est de plus haut niveau. Quand le break est exécuté, on sort de la boucle "for k", mais on continue à faire tourner la boucle "for r".



Dlzlogic
Membre Transcendant
Messages: 5273
Enregistré le: 14 Avr 2009, 14:39

par Dlzlogic » 22 Aoû 2013, 22:50

@ Léon,
Je m'attendais à une réponse de ce genre.
En fait, tu ne sais absolument pas ce qui se passe dans ce type d'exécution "haut niveau", et moi non plus d'ailleurs, c'est la raison pour laquelle je préfère les langages bas niveau, au moins, je sais à peu près ce qui se passe.
Donc toute hypothèse en la matière est sans objet.
A mon avis, la méthode pour pouvoir aider Archytas est d'abord de savoir ce qu'il faut faire, rédiger un algorithme clair et compréhensible, puis l'orienter pour rédiger un code efficace avec le langage qu'il a choisi, apparemment Maple.
Si on se limite à des histoires de syntaxe, d'astuces ou de cas particuliers du langage, on n'ira pas loin et autant arrêter tout de suite.

Archytas
Habitué(e)
Messages: 1223
Enregistré le: 19 Fév 2012, 15:29

par Archytas » 23 Aoû 2013, 03:17

Vous en faites pas c'est clair ! Le truc ce serait de trouver un moyen de pas stocker tous les points et je suis sur qu'il doit y avoir une fonction pour ça mais je trouve pas...
Autre chose : c'est quoi ceil ? C'est comme partie entière mais avec l'entier supérieur non ? Si m est déjà entier y a pas besoin !

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 17:25

par leon1789 » 23 Aoû 2013, 10:06

Dlzlogic a écrit:@ Léon,
Je m'attendais à une réponse de ce genre.
En fait, tu ne sais absolument pas ce qui se passe dans ce type d'exécution "haut niveau", et moi non plus d'ailleurs, c'est la raison pour laquelle je préfère les langages bas niveau, au moins, je sais à peu près ce qui se passe.
Donc toute hypothèse en la matière est sans objet.

Au contraire, à défaut de connaître l'intérieur de maple, toute hypothèse cohérente en la matière est potentiellement intéressante. En l'occurrence, tu as dû constaté que j'ai présenté rapidement la manière dont les langages "bas niveau" concatènent deux listes simplement chaînées : c'est pas un total délire.

D'autre part, tu as bien remarqué que j'ai commencé ma réponse par " J'imagine "et pris en compte des expressions comme " peut-être " que j'ai utilisées plusieurs fois, tout ça pour signifier que je ne suis pas du tout certain de l'idée que j'avance concernant le fonctionnement interne de maple.

Dlzlogic a écrit:A mon avis, la méthode pour pouvoir aider Archytas est d'abord de savoir ce qu'il faut faire, rédiger un algorithme clair et compréhensible, puis l'orienter pour rédiger un code efficace avec le langage qu'il a choisi, apparemment Maple.
Si on se limite à des histoires de syntaxe, d'astuces ou de cas particuliers du langage, on n'ira pas loin

Je sais, toi qui ne connais pas du tout maple (cf ton message ci-dessus), tu n'as que faire des différentes structures, les atouts , les faiblesses, les pièges du langage, d'améliorer la présentation du code et de le simplifier en utilisant les fonctionnalités propres à maple, etc. Quand on utilise un langage de "haut niveau" (dont tu te défends ouvertement depuis toujours, préférant réinventer toi-même l'eau chaude), qui plus est "orienté mathématique", il est bon, par expérience, d'utiliser les possibilités du langage et faire coller le code le plus possible aux maths : cela n'a rien à voir avec des astuces, c'est de la compétence.

Si on veut enseigner l'art de programmer, il faut commencer par montrer l'exemple (j'ai lu quelques uns de tes algos, et je t'ai signalé quelques erreurs algorithmiques que tu n'as surement pas pris en compte...). D'ailleurs, je t'invite à reprendre, si ce n'est déjà fait, et comprendre les deux petits bouts de codes de Skullkid sur la récursivité terminale... On parle de réellement progresser en programmation et connaissance d'un langage : il est évident qu'un forum ne peut remplacer un enseignant et un nombre suffisant d'heures de cours et de TP !

Dlzlogic a écrit:autant arrêter tout de suite.

C'est ce que je t'invite à faire !

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 17:25

par leon1789 » 23 Aoû 2013, 10:16

Archytas a écrit:Autre chose : c'est quoi ceil ? C'est comme partie entière mais avec l'entier supérieur non ? Si m est déjà entier y a pas besoin !

exactement
leon1789 a écrit:Remarque : si m est un entier, alors ceil(m) se simplifie en m.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 23 Aoû 2013, 11:53

bj,

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.

L'adresse de retour de quoi. De la fonction? Du contexte de données?
Dans tous les cas, c'est pas mal lié au compilateur, mais un exemple assembleur plus son commentaire sur une récursive simple nous éclairerait un peu plus :)
avec gcc, ca doit etre -s de mémoire
la vie est une fête :)

Dlzlogic
Membre Transcendant
Messages: 5273
Enregistré le: 14 Avr 2009, 14:39

par Dlzlogic » 23 Aoû 2013, 13:38

fatal_error a écrit:bj,


L'adresse de retour de quoi. De la fonction? Du contexte de données?
Dans tous les cas, c'est pas mal lié au compilateur, mais un exemple assembleur plus son commentaire sur une récursive simple nous éclairerait un peu plus :)
avec gcc, ca doit etre -s de mémoire

Bonjour,
Il me semble que ce diaporama cité par Léon https://www.lri.fr/~hivert/COURS/M2...Recursivite.pdf soit suffisamment détaillé pour répondre à toutes les questions.
On peut seulement regretter que l'exemple de la factorielle ait été limité à 4 ou 5 et qu'il manque la comparaison avec la méthode itérative.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 23 Aoû 2013, 15:35

soit suffisamment détaillé pour répondre à toutes les questions.


L'adresse de retour de quoi. De la fonction? Du contexte de données?

pas celle-ci.

et je t'invite à y répondre ayant toi même introduit le sujet.

edit: pour les plus feignants, utiliser http://gcc.godbolt.org/ + un guide assembleur..
la vie est une fête :)

Dlzlogic
Membre Transcendant
Messages: 5273
Enregistré le: 14 Avr 2009, 14:39

par Dlzlogic » 23 Aoû 2013, 16:25

Il s'agit de l'adresse de retour de la fonction.
Cette information est stockée dans la pile.
J'ai donné une comparaison avec des bouquins identiques que l'on ouvre siccessivement et que l'on empile. Dans la réalité (en informatique comme dans une bibliothèque) on a un seul exemplaire de chaque ouvrage. Donc, chaque fois que l'on referme un ouvrage, et avant de le refermer, on note sur une feuille de papier, le nom de l'ouvrage, le numéro de la page et le numéro de la ligne où sont indiquées les références de l'article suivant à consulter.
Ces 3 valeurs sont notés lignes après ligne, de haut en bas. Pour mémoire, les valeurs numériques éventuelles servant à l'article suivant sont notées sur un bout de papier, ou simplement gardées en tête le temps de trouver l'article suivant.
Lorsque, enfin, on aura trouvé le résultat cherché, c'est à dire l'article qui ne revoie pas à un autre article, il faut revenir en arrière. Alors on reprend la liste, du bas vers le haut, on ré-ouvre tous les ouvrages les uns après les autres, à l'article concerné, on lit la ligne suivante de l'article. Disons, pour simplifier, que ce sera un ordre "return", on peut fermer l'ouvrage et lire la ligne précédente de la pile, jusqu'à arriver en haut de la feuille, c'est à dire l'appel à la fonction récursive.

Dans le cas que j'ai pris pour simplifier : la ligne suivante est un ordre "return" (on en est sûr), par exemple dans le cas typique de factorielle, cet organisation peut être remplacée par une itération, et le nombre de ces itérations peut être énorme.
Par contre, dans le cas plus général que j'ai décrit avec des objets et des sous-objets, si on ne veut pas utiliser la récursivité, il faudra écrire un système de pile équivalent. Il est naturellement plus intéressant d'utiliser la récursivité mais dans ce cas le nombre d'étapes doit être limité et la pile suffisamment grande pour contenir la liste de toutes les adresses de retour (de fonction).

Dlzlogic
Membre Transcendant
Messages: 5273
Enregistré le: 14 Avr 2009, 14:39

par Dlzlogic » 23 Aoû 2013, 22:43

Petit UP, j'ai bon, ou j'ai faux ?
Mon explication est claire on complètement incompréhensible ?
Est-elle conforme au lien donné par Léon, ou complètement à côté de la plaque ?
Quelqu'un a-t-il des expériences concrète de la récursivité ?

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 02 Sep 2013, 22:12

c'est trop flou pour moi.
Ps: es-tu sûr qu'on garde les adresses de retour des fonctions? :-)
Tu crois que quand tu as une recursive tu as autant de code généré que d'appels?
Mon but c'est pas dire que t'as tord, mais juste de te faire remarquer que t'es quand même pas mal vague (en référence avec ton exemple de livres qui sont supposés différents alors qu'on parle d'une récursive, donc à priori du code identique)
la vie est une fête :)

Dlzlogic
Membre Transcendant
Messages: 5273
Enregistré le: 14 Avr 2009, 14:39

par Dlzlogic » 02 Sep 2013, 22:58

Bonjour fatal_error.
D'abord, il se trouve que l'exemple de la factorielle est généralement donné pour montrer que la récursivité n'est pas la bonne solution.
Oui, je suis sûr qu'on garde les adresses de retour, c'est le principe de la pile LIFO.
Quand on a une fonction récursive, le code généré n'est pas répété, mais seulement l'adresse de retour, pour pouvoir continuer, puis revenir au point de départ quand on a trouvé la fin..
Je crois qu'il faut bien distinguer la récursivité, type factorielle, qui doit naturellement être remplacée par une itération, de la récursivité que j'appelle nécessaire, qui permet d'adresser des objets à partir d'un objet maitre.
Je suit prêt à faire des simulations, c'est à dire des exécutions avec impressions intermédiaires pour montrer cela. J'ai eu l'occasion d'en faire pour faire du debug (oui, il m'arrive d'en faire).
C'est en quelque sorte une différence fondamentale entre une organisation de la mémoire type "Fortran d'époque" avec l'organisation actuelle qui est basée sur la récupération de l'espace mémoire.

Le cours dont il a été fait référence dit tout ce qu'il faut, c'est à dire explique tout, sauf le principale, c'est à dire que la récursivité ne doit être utilisée que si nécessaire et que le nombre d'étapes doit être assez petit.

Par ailleurs il est possible de remplacer la pile par une écriture de fichier, mais alors, fini les performances.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 03 Sep 2013, 01:03

Quand on a une fonction récursive, le code généré n'est pas répété, mais seulement l'adresse de retour, pour pouvoir continuer, puis revenir au point de départ quand on a trouvé la fin..
D'abord, il se trouve que l'exemple de la factorielle est généralement donné pour montrer que la récursivité n'est pas la bonne solution.

la généralité est fausse, voir la récursivité terminale. (ca a déjà été cité)

Je suit prêt à faire des simulations, c'est à dire des exécutions avec impressions intermédiaires pour montrer cela.

comme dit plus haut, il n'est point besoin d'impressions intermédiaire, mais de simplement lire le code assembleur généré.

la récursivité que j'appelle nécessaire, qui permet d'adresser des objets à partir d'un objet maitre.

Ne veut rien dire.

Comme une fois de plus on s'embourbe, voici un exemple très simple (que tu aurais pu utiliser au lieu d'insister dans le flou):
Code: Tout sélectionner
int fact(int n){
  if(n==1) return 1;
  return n*fact(n-1);
}

Code: Tout sélectionner
fact(int):                               # @fact(int)
   movl   $1, %eax
   jmp   .LBB0_2
.LBB0_1:                                # %tailrecurse
   imull   %edi, %eax
   decl   %edi
.LBB0_2:                                # %tailrecurse
   cmpl   $1, %edi
   jne   .LBB0_1
   ret

dans ce cas là, ret est clairement appelé une seule fois.

Une variante avec une récurse non terminal:
Code: Tout sélectionner
int collatz(int n){
  if(n%2==0){
    return collatz(n/2)+3;
  }
  return collatz(5*n+1);
}

Code: Tout sélectionner
collatz(int):                            # @collatz(int)
   pushq   %rbp
   movq   %rsp, %rbp
   jmp   .LBB0_2
.LBB0_1:                                # %tailrecurse
   leal   1(%rdi,%rdi,4), %edi
.LBB0_2:                                # %tailrecurse
   testb   $1, %dil
   jne   .LBB0_1
   movl   %edi, %eax
   shrl   $31, %eax
   addl   %edi, %eax
   sarl   %eax
   movl   %eax, %edi
   callq   collatz(int)
   addl   $3, %eax
   popq   %rbp
   ret

où clairement dans ce cas là, on constate qu'effectivement on store l'adresse de la fonction pour pouvoir retourner à l'appelant. (pushq, popq).

bref, ce qu'il faut en déduire, c'est qu'un mécanisme de pile des instructions (pour revenir après un call) est mis en oeuvre dans le cas où le compilateur n'arrive pas à optimiser le code.
la vie est une fête :)

Dlzlogic
Membre Transcendant
Messages: 5273
Enregistré le: 14 Avr 2009, 14:39

par Dlzlogic » 03 Sep 2013, 13:17

Naturellement, tu as raison, alors j'ai pas compris ces questions insistantes.
c'est trop flou pour moi.

C'est clair maintenant ?

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 33 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite