Discussion :

[Tonio12]

Bonsoir,
je suis entrain de préparer une épreuve d'informatique mais je reste coincé sur des éxercices, qui sont du type qcm, les voici en pièces jointes.questions 35,36,37,38.
En fait j'ai un gros problème pour voir l'évolution du temps de calcul, j'essaye de prendre des éxemples particuliers mais bon.

De plus, concernant l'évolution de la place prise lors de l'éxécution d'un programme(n²,1/n...) auriez vous des méthodes pour la déterminer??

Par avance merci à tous ceux qui pourront m'aider dans ma préparation.

P.S: ne faites pas attention aux réponses mises

[PRomu@ld]

Pour le 35 -> c, la fonction d'ackerman est une fonction qui croit très rapidement, par conséquent il y a de forte chances que tu dépasse la capacité du type considéré.

Pour le 36 -> d, la fonction d'ackerman a une croissance exponentielle. On l'utilise pour quelques algos (notament sur les ensembles disjoints). Par exemple Ack(4,n) vaut 2^(2^2^...) et ce qui est dans la parenthèse est répété n fois. Ack(4,4) dépasse le nombre de particules élémentaires de l'univers...

Pour le 37 -> b , la fonction termine pour n > 1 ( sous réserve aussi que le résultat soit dans la capacité des entiers).

Pour le 38 -> a, il manque un cas pour traiter fibo(1), car on va avoir un appel à fibo (1 - 2) ce qui est indéfini.

Pour ce qui est de la fonction d'ackerman, tu dois avoir quelque chose dans le Knuth il me semble et également quelque chose dans le Cormen (mais il me semble que c'est seulement le Cas particulier de A(n,n) ).

[Tonio12]

Merci pour vos réponses, mais quelque chose me chagrine, la réponse c pour la 35.Vous dites qu'il y a de forte chance pour que la capacité du type considéré soit dépassée mais en même temps la réponse c correspond à:"doit théoriquement se terminer toujours, aux problèmes de tps de calcul et de place mémoire près"
Peut on dans ce cas dire que la bonne est la c?, sachez que la réponse e est possible...

[fomazou]

35 (c), la fonction d'ackerman est une fonction qui croit très rapidement
36 (d), la fonction d'ackerman a une croissance exponentielle.
37 (b) , la fonction termine pour n > 1
38 (a),

[PRomu@ld]

35 (c), la fonction d'ackerman est une fonction qui croit très rapidement
36 (d), la fonction d'ackerman a une croissance exponentielle.
37 (b) , la fonction termine pour n > 1
38 (a),

C'est pas ce que je viens de dire ?

doit théoriquement se terminer toujours, aux problèmes de tps de calcul et de place mémoire près

Mathématiquement la fonction d'ackerman termine toujours, or dans un contexte pratique la fonction crois tellement rapidement et donc pour certaines valeurs, la fonction va provoquer un débordement de type, c'est bien ce qui est précisé: "aux problèmes de place près". Ca me parait donc la réponse la plus adéquat. Si tu veux le prouver, c'est pas bien compliqué, quelque soit le cas, soit tu maintiens la valeur d'un paramètre, soit tu la fait décroire (ça mériterait une étude un peu plus approfondie mais l'idée est là).

[Tonio12]

Merci encore à toi PRomu@ld, tes réponses sont précises et plutôt claires(ce n'est pas toujours le cas)