Récurrence forte et récurrence double
Salut
Soit $P$ un prédicat portant sur les entiers naturels.
Est-ce qu'on ne peut pas utiliser le principe de récurrence forte au lieu de celui de récurrence double et on utilise seulement le rang $n-2$ et $n-1$ pour déduire le rang $n$ et éviter pendant l'initialisation de voir si $P(0)$ et $P(1)$ sont vérifiées ?
Soit $P$ un prédicat portant sur les entiers naturels.
Est-ce qu'on ne peut pas utiliser le principe de récurrence forte au lieu de celui de récurrence double et on utilise seulement le rang $n-2$ et $n-1$ pour déduire le rang $n$ et éviter pendant l'initialisation de voir si $P(0)$ et $P(1)$ sont vérifiées ?
Réponses
-
C'est le genre de question qu'il vaut mieux poser à propos d'un exemple bien précis. Là, ça risque de partir dans tous les sens.
-
GaBuZoMeu je pense que ne dois donner des exemples car la majorité de mes messages dans le forum partent dans tous les sens
-
???
-
Je pense que t'as raison je dois penser à ajouter des exemples bien précis à mes postes car souvent ils partent dans tous les sens
-
Ah d'accord, le "ne dois" du message précédent était une coquille.
-
La grosse différence entre une récurrence dite "forte" et une récurrence dite "double" est que dans la première, le nombre d'hypothèses effectuées pour démontrer P(n) varie en fonction de n... et en particulier lorsque n=1, on ne peut pas utiliser P(n-2)... puisque cela ne fait pas partie des hypothèses !
-
Il y a 1001 énoncés EQUIVALENTS FORTEMENT pour exprimer l'axiome de récurrence. Chaque fois que tu demandes "peut on utiliser l'un plutôt que l'autre ?" la réponse est oui les yeux fermés.
La seule façon de faire des distinctions serait d'ajouter des adverbes ou adjectifs comme "rapidement" ; "élégant"; etc. "Est-il plus élégant d'utiliser...?"
Mais on sort alors des maths sauf à rebifursuer vers la complexité des preuves et textes (qui est une notion mathématique académique, mais je doute que tu jouirais de lire des échanges techniques dans ce sens.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
À noter d'ailleurs qu'inconsciemment ou non bisam à déjà mis un pied dedans :-DAide les autres comme toi-même car ils sont toi, ils sont vraiment toi
-
Salut Nemya, j'ai l'impression que tu proposes une sorte de mixte entre les méthodes de récurrence forte et double, qui emprunterait à la fois la "rapidité" de la seconde et une "dispense" de vérifier l'une des conditions initiales dans la première ? J'ai peut-être mal compris...
-
Ltav oui effectivement je me suis dit qu'on peut utiliser la récurrence forte au lieu de la récurrence double et vérifier seulement le premier rang et pas les deux premiers rang car parfois le premier rang est vérifié or le 2 ème non
-
Si la propriété est fausse ("non vérifiée au deuxième rang") pour un entier naturel, il ne sert à rien d'essayer de faire une démonstration qu'elle est vraie pour tout entier naturel.Nemya a écrit:et vérifier seulement le premier rang et pas les deux premiers rang car parfois le premier rang est vérifié or le 2 ème non -
@bisam: je ne suis pas sûr que tu aies bien pris ce que j'ai dit. Je voulais juste dire que ton message contenait implicitement une préoccupation de complexité informatique, rien de plus.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
-
Merci Nemya, je comprends mieux, donc tu recherches s'il est possible d'optimiser (vitesse, nombres d'étapes) une résolution de problème par récurrence. Tu voulais plutôt te demander que faire si deux rangs vérifient une propriété alors que l'une des méthodes te dispense de vérifier un rang. Il est clair que l'optimisation est l'un des intérêts du mathématicien et surtout de l'ingénieur lorsqu'il est confronté à plusieurs techniques équivalentes (du point de vue logique). En général, il procède au cas par cas. Fais attention toutefois à l'usage de "il suffit de vérifier seulement que" : un petit nombre d'étapes dans une méthode peut te prendre beaucoup plus de temps qu'un grand nombre dans une autre équivalente. Il pourrait a priori y avoir des cas où l'une des récurrences est plus "rapide" que l'autre, et des cas où c'est l'inverse.
Regarde cette ancienne conversation, je la trouve intéressante :
http://www.les-mathematiques.net/phorum/read.php?2,244032,244032#msg-244032 -
Merci pour votre réponse
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 30
+24 Invités