fonction primitive-récursive

[invite56460777]

Bonjour,

Comment fait-on pour prouver que la fonction (n,m) -> n + m est primitive-récursive?? Comment fait-on pour la formuler autrement?
-----

[inviteab2b41c6]

C'est quoi une fonction primitive recursive?

[invite56460777]

apparemment beaucoup de fonctions peuvent être aussi définies par récurences.
Par exemple n! est primitive-récursive.
Factoriel se définit aussi comme
0! = 1 et (n+1)! = n! (n+1)
Je n'ai pas de définition dans mon cours juste cet exemple

[Evil.Saien]

ben dans ce cas,
(n, m) -> n+m peut etre definie comme
Uk+1 = Uk + 1
avec k allant de 0 à n+m-1 et U0 = 0

[A voir en vidéo sur Futura]

[invite00411460]

si f(m,n) = m+n

pour être complet :

f(m,n) = f(m-1,n)+1 , m != 0 et n != 0
f(0,n) = f(0,n-1)+1, n != 0
f(0,0) = 0

mais ça sert à quoi dans ce cas présent ?

[Evil.Saien]

bonne question, et surtout je comprend pas le terme "prouver" qu'on peut l'ecrire sous cette forme... Ca devrait plutot etre "exprimer" la fonction sous cette forme...
Bon je chipotte

[invite56460777]

Ecrire f(m, n) = m + n ou n! sous une forme récurrente permet de pouvoir les calculer. Maintenant, comme je n'ai pas de définition d'une fonction primitive-récursive, je ne comprends pas pourquoi nous devons le prouver.
La plupart des fonctions doivent être primitive-récursives. Une exception notable est la fonction d'Ackermann

[inviteab2b41c6]

Mais toute suite peut etre vue recursivement:
Un=u(n-1)=u(n)-u(n-1)
non?

[invite56460777]

sauf la fonction d'Ackerman

[Evil.Saien]

et la suite Un = 1, celle ci aussi on peut pas l'écrire de manière recursive, enfin pas comme quinto l'a spécifié...
Je crois déceler l'utiliter de devoir écrire les suites (fonctions discrètes) de manière récursive, ca sert à accélérer les algorithmes...
Par exemple prenons une fonction de bessel:
Jm(x) = somme(l=0, inf) ((-1^l) / (2^(2l+m) * l! * (m+l)!) * x^(2l+m)
Si on devait l'évaluer en calculant betement chauqe terme de la somme, c'est très très lent et loin d'etre optimal... Par contre si on definie chaque terme de la somme en fonction du terme précédent, ca devient rapide et efficace...
Voila, ce fut juste un exemple

[invite4793db90]

Salut,

la suite constante Un=1 peut-être définie par récurrence:
U0=1, Un=U(n-1).

La fonction d'Ackerman est une suite double, mais elle est également définie par récurrence:
http://perso.wanadoo.fr/jean-paul.da...ts/suites/ack/

Pour la somme partielle Sn d'un une série sum(Un), on peut écrire que Sn=S(n-1)+Un.

Par contre, si on considère la suite dont le n-ième terme est la n-ième décimale de Pi ou d'un nombre "compliqué", trouver une relation de récurrence me paraît quand même ardu!

[Evil.Saien]

j'ai pas dit qu'elle pouvait pas etre ecrite recursivement, juste pas comme quinto l'a dit...
Mais la fonction log(n), comment tu l'ecris recursivement ?

[invite4793db90]

j'ai pas dit qu'elle pouvait pas etre ecrite recursivement, juste pas comme quinto l'a dit...
Mais la fonction log(n), comment tu l'ecris recursivement ?

On est d'accord.

A propos de Un=log(n), je pourrais écrire:
U(n+1)=Un+log(1+1/n).

Question: pourquoi ce n'est pas une écriture récursive?

[Evil.Saien]

ca a l'air bon... mais je suis quand meme scéptique quant au fait qu'il n'y aurait qu'UNE seule fonction qu'on ne puisse écrire recurssivement...
Ici ils disent que la fonction de Ackermann est la plus simple qui ne soit pas primitive recursive, mais pas que c'est la seule...
http://mathworld.wolfram.com/Primiti...eFunction.html

[invite4793db90]

On est d'accord.

A propos de Un=log(n), je pourrais écrire:
U(n+1)=Un+log(1+1/n).

Question: pourquoi ce n'est pas une écriture récursive?

Salut,

d'abord excusez-moi, je ne connaissais pas la définition précise de "primitive-récursive". En fait, si on donne une suite Un=f(n), on peut toujours écrire que
U(n+1)=U(n)+f(n+1)-f(n) (c'est ce que j'ai fait pour le log)

Par contre, ça n'a aucun intérêt. Mais du coup, si on donne une suite Un=f(n), elle est forcément primitive récursive.

Pour la suite d'Ackermann, le problème, si j'ai bien compris, c'est qu'on ne sait pas à l'avance quand le calcul s'arrête. Effectivement Evil.Saien, il ne semble pas que ce soit la seule, mais pour en construire une et démontrer qu'elle n'est pas primitive-récursive...

[invite56460777]

ca a l'air bon... mais je suis quand meme scéptique quant au fait qu'il n'y aurait qu'UNE seule fonction qu'on ne puisse écrire recurssivement...
Ici ils disent que la fonction de Ackermann est la plus simple qui ne soit pas primitive recursive, mais pas que c'est la seule...
http://mathworld.wolfram.com/Primiti...eFunction.html

Ce est aussi la première fonction pour laquelle on a démontré qu'elle n'était pas récursive

[invite48a4cde4]

slt jèmerè kon m'aide a résoudre ce type de problème
merci
Problème 1
On appelle palindrome un nombre entier qui peut–être lu de gauche à droite ou de droite à gauche en donnant le même résultat. Exemple*: 1771 et 12321 sont des palindromes. Combien y a-t-il de palindromes dans l’ensemble N= *?
On désigne par an le nombre de chaînes de n caractères de l’alphabet qui ne contiennent pas le sous ensemble DM.
b1) Démontrer la relation de récurrence*: an=26an-1 – an-2
b2) Déterminer les conditions initiales et résoudre la relation de récurrence pour trouver la formule explicite de an.

***********
***********
Problème 2

Un nombre entier positif est appelé cubique s’il est divisible par la puissance 3 d’un nombre entier strictement
plus grand que 1. Par exemple, 108 est un nombre cubique car il est divisible par 3(puissance3)= 27, tandis que 175 n’est
pas un nombre cubique. Calculer le nombre des nombres cubiques dans l’ensemble (1, 2, 3, …, 1000) par le
principe du pigeonnier.

************
**************
Problème 3

1.1 (2 points)
Soit a1, a2, …a9 une permutation de 1, 2, 3, 4, 5, 6, 7, 8, 9.
a) Combien y a-t-il de permutations satisfaisant ai<ai+1 pour i=1, 2, 3, 4, 5, 6, 7, 8 ?
b) Combien y a-t-il de permutations satisfaisant ai<ai+1 pour i=1, 2, 3, 4, 6, 7, 8 et a5>a6 ?

1.2 (2 points)
On appelle suite trinaire de longueur n une suite de n chiffres appartenant à
l’ensemble {0,1,2}. Démontrer que le nombre de suites trinaires de longueur n
contenant un nombre pair de 0 est (3n + 1)/2.


**************
**************
Problème 5
Soit an le nombre de chaînes binaires de longueur n qui ne contiennent pas 110 comme sous-chaîne.
5a) (2 points) Calculer a1, a2
5b) (3 points) Montrer que an satisfait la relation de récurrence suivante :
an = an-1 + an-2 + 1, n >= 3

***************
***************