Répondre à la discussion
Affichage des résultats 1 à 17 sur 17

fonction primitive-récursive



  1. #1
    Brumaire

    fonction primitive-récursive


    ------

    Bonjour,

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

    -----

  2. Publicité
  3. #2
    Quinto

    Re : fonction primitive-récursive

    C'est quoi une fonction primitive recursive?

  4. #3
    Brumaire

    Re : fonction primitive-récursive

    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

  5. #4
    Evil.Saien

    Re : fonction primitive-récursive

    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

  6. A voir en vidéo sur Futura
  7. #5
    olle

    Re : fonction primitive-récursive

    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 ?
    Dernière modification par olle ; 24/11/2004 à 15h52.

  8. #6
    Evil.Saien

    Re : fonction primitive-récursive

    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

  9. Publicité
  10. #7
    Brumaire

    Re : fonction primitive-récursive

    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

  11. #8
    Quinto

    Re : fonction primitive-récursive

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

  12. #9
    Brumaire

    Re : fonction primitive-récursive

    sauf la fonction d'Ackerman

  13. #10
    Evil.Saien

    Re : fonction primitive-récursive

    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

  14. #11
    martini_bird

    Re : fonction primitive-récursive

    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!

  15. #12
    Evil.Saien

    Re : fonction primitive-récursive

    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 ?

  16. Publicité
  17. #13
    martini_bird

    Re : fonction primitive-récursive

    Citation Envoyé par 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 ?
    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?

  18. #14
    Evil.Saien

    Re : fonction primitive-récursive

    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
    Dernière modification par Evil.Saien ; 25/11/2004 à 16h27.

  19. #15
    martini_bird

    Re : fonction primitive-récursive

    Citation Envoyé par martini_bird
    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...

  20. #16
    Brumaire

    Re : fonction primitive-récursive

    Citation Envoyé par 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
    Ce est aussi la première fonction pour laquelle on a démontré qu'elle n'était pas récursive

  21. #17
    taglud

    Re : recurrence

    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

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

Discussions similaires

  1. Primitive d'une fonction
    Par lakrids dans le forum Mathématiques du supérieur
    Réponses: 8
    Dernier message: 02/11/2007, 16h37
  2. Fonction primitive
    Par sverige dans le forum Mathématiques du collège et du lycée
    Réponses: 3
    Dernier message: 05/06/2007, 22h32
  3. fonction recursive
    Par hterrolle dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 23/05/2006, 17h24
  4. Primitive de la fonction ln
    Par merabti.nabila@neuf.fr dans le forum Mathématiques du collège et du lycée
    Réponses: 8
    Dernier message: 08/04/2006, 20h52
  5. Fonction rationnelle et primitive
    Par Bleyblue dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 19/03/2006, 09h52