Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Autre AlgèbreTopics traitant de algèbre [tout]Lister tous les topics de mathématiques
Niveau autre
Partager :

Algorithme - Suite

Posté par
Nightmare 19-07-05 à 20:29

Bonjour à tous

Une fois n'est pas coutume, je vous soumet une question que je me suis posé hier soir avant de m'endormir (non je ne suis pas fou ) et à laquelle je n'ai pu apporté de réponse.

Je vais essayer d'être clair bien que cela est un peu dur à énoncer:

_______________________________________

Vous connaissez tous je suppose le jeux de la suite logique.Ce jeux consiste à donner au joueur une suite de nombres qu'il doit compléter sachant qu'ils sont reliés de façon uniforme par la même relation que l'on nomme algorithme.
Le joueur, pour pouvoir compléter cette suite doit trouver cet algorithme.

Les algorithmes des suites logiques sont souvent bidons et non mathématiques et peuvent alors appeller à plusieurs réponses à conditions qu'elles soient justifier de maniére logique ou loufoque.

Pour ma part je vais refaçoner ce jeux.
Ici, un algorithme est une succession de calculs élémentaires dans \rm \mathbb{N} c'est à dire l'addition, la soustraction (dans le cas où le resultat reste dans \rm \mathbb{N}) , la multiplication et la division (dans le cas où le résultat de la division est toujours entier).
***Edit Moi-Même : Rajouter l'exponentiation (mettre au carré, au cube etc...)***

Par exemple, un algorithme reliant 1 à 2 est ajouter 1, un autre est multiplier par 2, ou encore multiplier par 4 et soustraire 2 etc...
On peut ainsi créer une infinité d'algorithme.

Ma question est alors la suivante :
Quelque soient les entiers naturels a, b et c. Existe-t-il toujours un algorithme qui permet de trouver b en fonction de a et c en fonction de b.

Par exemple, si on prend l'algorithme : multiplier par 2 et soustraire 1
On voit bien que par cet algorithme en obtient 7 en fonction de 4 et 13 en fonction de 7.
Donc il existe bien un algorithme qui relie 4 - 7 - 13

Est-ce alors vrai pour tout entiers naturels ?

Quelque soit la réponse , \rm comment la demontre-t-on ?

_____________________________________
Si la réponse est oui alors voici une nouvelle question :
Au bout de combien d'entier naturel ne pourra-t-on plus trouver d'algorithme reliant le 2é au 1e, le 3e au 2e , .... , le n-éme au (n-1)-éme

Pareillement, quelque soit la réponse , \rm comment la demontre-t-on ?

J'espere avoir été clair, c'est assez dur à expliquer comme je l'ai dit, si vous n'avez pas compris quelque chose dites le moi


jord

Posté par philoux (invité)re : Algorithme - Suite "logique" 19-07-05 à 20:44

>NM


La question du 1) est-ce bien :

soient a, b et c
existe-t-il f telle que :
b=f(a)
c=f(b)=f²(a)
avec f composée de +,-,x,: à valeurs entières ?

Pour le 2) (voire le 1) ), je sens que les nombres premiers devront intervenir dans le raisonnement de la résolution de ton PB; peut-être chercher par là...

Philoux

Posté par
enzore : Algorithme - Suite "logique" 19-07-05 à 20:51

Salut Nightmare,

c'est une question très intéressante....

Dans le cas où la suite logique ne contient qu'une seule division ou soustraction ou multiplication ou addition, je pense qu'il existe un moyen très simple pour, trouver la "suite logique" : régression linéaire.

En revanche, en combinant plusieurs opérations différentes telle que tu l'as décrit.....je vois pas trop.

Posté par
Nightmarere : Algorithme - Suite "logique" 19-07-05 à 20:53

En quelque sorte philoux c'est ça.
C'est plutot :
\rm Existe-t-il une relation R telle que aRb et bRc

Sachant que R relie deux éléments par un nombre fini d'opérations élémentaires.
Cette relation n'est pas forcément une fonction.

Merci pour le conseil pour la 2) je vais essayer de creuser par là


Jord

Posté par
Nightmarere : Algorithme - Suite "logique" 19-07-05 à 20:54

Merci de ta réponse enzo , mais qu'appelles-tu régression linéaire ?


Jord

Posté par
enzore : Algorithme - Suite 19-07-05 à 20:54

en fait, j'avais mal compris ta question. je pensais que tu évoquais le cas où:
instant t on ajoute x,
instant t+1 on multiplie par y,
instant t+2 on ajoute x
....

Mais comme je l'ai dit précedemment, s'il existe une relation linéaire parfaite entre deux variables, il est sûr que la régression trouvera les coeffs...mais quant à le prouver.

Posté par
enzore : Algorithme - Suite 19-07-05 à 20:57

régression linéaire: il s'agit d'expliquer une variable Y par une ou plusieurs variables X1,....Xp.


L'équation est de la forme Y = a1X1 + a2X2 + .....+ apXp + constante + erreur.

L'erreur n'existe pas dans le cas que tu as évoqué car la relation entre Y et les Xi est parfaite.

l'objectif de la régression est de trouver a1, a2,...., ap de tel manière à ce que l'erreur soit la plus faible possible

Posté par
Nightmarere : Algorithme - Suite 19-07-05 à 21:05

Je ne te suis pas trés bien enzo.

Je vois ce qu'est une régression linéaire mais je ne vois pas en quoi cela nous aide à montrer l'existence (ou non) d'un tel algorithme ?


Jord

Posté par
enzore : Algorithme - Suite 19-07-05 à 21:08

bon un petit exemple:

je construit une suite telle que:

un+1 = 2*un + 1

ce qui donne pour les premières valeurs:
1
3
7
15
31
63
127
255
511
1023

je fais une régression entre un et un+1 et le résultat:

y = 2x + 1 soit un+1 = 2un + 1

Posté par
Nightmarere : Algorithme - Suite 19-07-05 à 21:13

Oui daccord mais ici ça marche car la régression est parfaite mais elle ne l'est pas toujours et n'est parfois qu'approximative (c'est là qu'intervient l'erreur).
Ce qu'il faut trouver dans mon probléme est une relation parfaite quelque soit les 3 entiers.


Jord

Posté par
enzore : Algorithme - Suite 19-07-05 à 21:14

c'est exactement ça....si tu veux donne moi une suite de ce type et je peux trouver les coeffs, histoire que tu vois que ça marche...

Posté par
Nightmarere : Algorithme - Suite 19-07-05 à 21:21

Je ne te suis de nouveau plus...
Dans le cas de la suite que tu as donné dans ton autre post,ça marche bien (on a l'algorithme multiplier par 2 puis rajouter 1).
Mais peux-tu garantir que ces coefficients sont entiers ? (car je rappelle que l'algorithme ne doit comporter que des entiers)

Par exemple prenons les nombres 4-18-51

Par régression linéaire , quel algorithme trouves-tu qui relies 4 à 18 et 18 à 51 ?


Jord

Posté par
enzore : Algorithme - Suite 19-07-05 à 21:26

excat...bien vu, j'avais zappé le coup des entiers. Alors dans ce cas là, ça devient autrement plus complexe....désolé d'avoir été à côté de la plaque si longtemps. De toute façon, je dois partir

Alors bon courage dans tes recherches!!

Posté par
Nightmarere : Algorithme - Suite 19-07-05 à 21:27

Merci j'en aurais besoin

En tout cas merci à toi d'avoir essayé

Si quelqu'un à une idée qu'il n'hésite pas


Jord

Posté par
enzore : Algorithme - Suite 19-07-05 à 21:27

Mais dès que je reviens je vais jeter un coup d'oeil sur mes cours d'info....

Posté par
Nightmarere : Algorithme - Suite 19-07-05 à 21:30

Je ne suis pas sur que tu y trouves grand chose. J'ai demandé à mon frére qui est ingénieur en informatique et il n'a rien trouvé, il a dit qu'il n'était pas mathématicien


Jord

Posté par majid52 (invité)re : Algorithme - Suite 20-07-05 à 01:33

Bonjour Nightmare (Modérateur),
assez intéressante comme question mais elle manque de précisions:
les exemples que tu as donné pour expliquer le mot "algorithme"laissent croire que c'est une transformation affine  x\in \mathbb{N}\to px+q  avec (p,q)\in \mathbb{Q}\times\mathbb{Z} mais avec aussi px entier aumoins pour les deux valeurs entières distinctes x=a et x=b et bien entendu \{{pa+q=b\atop\ pb+q=c}\ est-ce bien cela?
si c'est cela tu vois bien que c'est un systéme linéaire à 2 équatios et 2 inconnues son détérminant est \Delta=a-b\neq0 d'où \{{p=\frac{c-b}{b-a}\atop\ q=\frac{b^2-ac}{b-a}}\ on aboutit alors avec la condition (pa,pb,q)\in \mathbb{Z}^{3} au fait que l'entier b-a doit etre un diviseur commun des 3 entiers a(c-b), b^2-ac et b(c-b)
prenons l'exemple de a=4 , b=7 et c=13 on a
b-a=3 , a(c-b)=4\times6=24 , b^2-ac=49-4\times13=-3 et b(c-b)=7\times9=63 tous multiples de 3 d'où p=2 et q=-1 et l'algorithme est x\to 2x-1
pour a=4 , b=18et c=51on a b-a=14n'est pas diviseur de a(c-b)=4\times33 donc pas d'algorithme dans ce cas.
Voilà en tout cas c'est ce que j'ai compris du mot "algorithme"d'aprés les explications de Nightmare (Modérateur)
si ce n'est pas cela priére de bien vouloir donner d'autres exemples pour bien mettre au clair la signification mathématique de ce mot
amicalement majid52

Posté par
Nightmarere : Algorithme - Suite 20-07-05 à 01:39

Bonsour majid52

Non ce n'est pas forcément une fonction affine, c'est une succession finie de calculs élémentaires.
D'ailleur dans ces calculs élémentaires j'aimerais ajouter l'exponentiation.

Donc par exemple un algorithme serait :

\rm mettre au carre, multiplier par 3 puis ajouter 5


Jord

Posté par
Nightmarere : Algorithme - Suite 20-07-05 à 01:43

Oui en fait je viens de me rendre compte que sans l'exponentiation c'est tout bonnement comme vous me le faites remarquer une fonction affine...

Posté par
enzore : Algorithme - Suite 20-07-05 à 12:31

Re Nigthmare

> La régression fonctionne alors dans le cas de fonction affine. En suivant le raisonnement de majid52, si les coeffs de la régression appartiennent à alors il n'y a pas d'algo, s'ils appartiennent à alors il y en a une.

> j'avais oublié ça hier mais il existe un algo (réseaux de neurones) qui est capable d'approximer n'importe quelle fonction. L'ennui avec cette méthode, c'est qu'elle nécessite un nombre d'exemples "suffisant" (=avoir un bon paquet de valeurs en entrée) pour fonctionner correctement.

Posté par
Nightmarere : Algorithme - Suite 20-07-05 à 13:36

Et dans le cas où l'on rajoute l'exponentiation ça se complique non ?


Jord

Posté par
enzore : Algorithme - Suite 20-07-05 à 13:41

pour la régression:
- si tu as qqch ds cet ordre: opération élémentaires puis exponentiation, je ne pense pas que ça marche.

- pour le cas où l'ordre est différent, autrement dit, exponentiation puis opérations +,-,*,/ ça devrait marcher à condition de rajouter les explicatives correspondantes: X², X3, ....ça devient vite très lourd.

pour les réseaux de neurones: ça marche ds tous les cas

Posté par
Nightmarere : Algorithme - Suite 20-07-05 à 13:43



Merci à toi en tout cas je vais essayer de résumer un petit peu tout ce qu'on m'a dit et essayer de l'appliquer.


Jord

Posté par
enzore : Algorithme - Suite 23-07-05 à 13:36

Nightmare,

j'ai vérifié, la régression marche également ds tous les cas.....

Posté par
enzore : Algorithme - Suite 23-07-05 à 13:58

une preuve:

L'algorithme recherché est une fonction du terme précédent. Ainsi,

un+1 = f(un) + c  où c est une constante.
Quelque soit la nature de f on peut écrire (car dans notre cas on ne s'intéresse qu'à l'exponentiation et aux quatre opérations élémentaires) :

un+1 = c + a1 unp + a2 unp-1 + .... + ap un0.

Autrement dit, il existe toujours une forme linéaire pour décrire un+1

D'après le théorème de Gauss-Markov, l'estimateur de la régression linéaire est le meilleur estimateur possible (pour simplifier).

Voilà, je te passe le détail de Gauss-Markov....tu peux toujours essayer de regarder si tu veux, mais il faut quand même un bon bagage stat pour percuter.

Posté par
Nightmarere : Algorithme - Suite 23-07-05 à 16:37

Merci beaucoup enzo je vais regarder ça


Jord

Posté par
elhor_abdelali Correcteurre : Algorithme - Suite 23-07-05 à 18:03

Bonjour tout le monde;à mon avis un algorithme qui permet de créer une suite logique d'entiers à partir d'un entier a est une fonction f:\mathbb{N}\to\mathbb{R} dont tous les itérés en a sont des entiers.
Comme Nightmare (Modérateur) veut en plus qu'elle soit une succession d'opérations élémentaires +,\times,-,/ elle est polynomiale à coefficients rationnels (comme l'a bien vu enzo).On peut donc voir le problème comme suit:
étant donné 3 entiers a<b<c existe-t-il f\in\mathbb{Z}[X] telle que f(a)=b et f(b)=c (la condition f\in\mathbb{Z}[X] assurant que tous les itérés de f en a soient des entiers)


Posté par
Nicolas_75 Correcteurre : Algorithme - Suite 24-07-05 à 08:31


Bonjour,

Je suis peut-être à côté de la plaque, mais j'ai l'impression que l'"algorithme" existe toujours, et que c'est un polynôme à coefficients dans \mathbb{N}, suivi d'une division par un entier, et que tous les paramètres se calculent facilement.

Je comprends l'énoncé ainsi :
Soit a_0, ..., a_p des nombres entiers. On suppose que si a_i=a_k, alors a_{i+1}=a_{k+1} (*) (sinon, souci !). Existe-il une suite finie d'opérations élémentaires + - * / ^ exp à paramètres dans \mathbb{N} permettant de passer d'un a_i à son successeur ?

Prenons trois exemples.
Exemple 1 : 4, 18, 51.
Exemple 2 : 4, 18, 51, 4, 18, 51, 4, 18, 51 (une sorte de boucle).
Exemple 3 : 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023.

Dans les "suites" (a_n), supprimons les couples (a_i, a_{i+1}) qui sont les mêmes.
On obtient les "suites" (u_n) suivantes, avec les u_i différents deux à deux, sauf éventuellement avec le dernier d'entre eux (**) :
Exemple 1 : 4, 18, 51.
Exemple 2 : 4, 18, 51, 4.
Exemple 3 : 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023.

Soit p le nombre d'entiers dans la "suite" (u_n)_{1\le n\le p}
Exemple 1 : p=3
Exemple 2 : p=4
Exemple 3 : p=10

Sauf erreur (à démontrer rigoureusement, en travaillant dans \mathbb{Q}[X], et en s'appuyant sur les hypothèses (*) et (**)), il existe un unique polynôme P à coefficients rationnels et de degré inférieur ou égal à p-2 tel que :
\forall{i}, u_{i+1} = P(u_i)
Notons P(X) = c_0 + ... + c_{p-2}.X^{p-2}

En écrivant toutes les relations u_{n+1} = P(u_n), il vient :
\[\array{1&u_1&u_1^2&...&u_1^{p-2} \\ ...&...&...&...&... \\ 1&u_{p-1}&u_{p-1}^2&...&u_{p-1}^{p-2}}\].\[\array{c_0 \\ ... \\ c_{p-2}}\] = \[\array{u_2 \\ ... \\ u_p}\]

Donc :
\[\array{c_0 \\ ... \\ c_{p-2}}\] = \[\array{1&u_1&u_1^2&...&u_1^{p-2} \\ ...&...&...&...&... \\ 1&u_{p-1}&u_{p-1}^2&...&u_{p-1}^{p-2}}\]^{-1}.\[\array{u_2 \\ ... \\ u_p}\]

Exemple 1 :
\[\array{1&4\\1&18}\].\[\array{c_0\\c_1}\] = \[\array{18\\51}\]
donc \[\array{c_0\\c_1}\] = \[\array{120\\33}\]/14
u_{n+1}=\frac{120+33.u_n}{14}

Exemple 2 :
\[\array{1&4&4^2\\1&18&18^2\\1&51&51^2}\].\[\array{c_0\\c_1\\c_2}\] = \[\array{18\\51\\4}\]
donc \[\array{c_0\\c_1\\c_2}\] = \[\array{60336\\89617\\-1747}\]/21714
u_{n+1}=\frac{60336+89617.u_n-1747.u_n^2}{21714}

Exemple 3 :
\[\array{1&1&1&1&1&1&1&1&1\\1&3&3^2&3^3&3^4&3^5&3^6&3^7&3^8\\1&7&7^2&7^3&7^4&7^5&7^6&7^7&7^8\\1&15&15^2&15^3&15^4&15^5&15^6&15^7&15^8\\1&31&31^2&31^3&31^4&31^5&31^6&31^7&31^8\\1&63&63^2&63^3&63^4&63^5&63^6&63^7&63^8\\1&127&127^2&127^3&127^4&127^5&127^6&127^7&127^8\\1&255&255^2&255^3&255^4&255^5&255^6&255^7&255^8\\1&511&511^2&511^3&511^4&511^5&511^6&511^7&511^8}\].\[\array{c_0\\c_1\\c_2\\c_3\\c_4\\c_5\\c_6\\c_7\\c_8}\] = \[\array{3\\7\\15\\31\\63\\127\\255\\511\\1023}\]
donc \[\array{c_0\\c_1\\c_2\\c_3\\c_4\\c_5\\c_6\\c_7\\c_8}\] = \[\array{1\\2\\0\\0\\0\\0\\0\\0\\0}\]
u_{n+1}=1+2.u_n
(c'est bien ainsi que l'exemple avait été construit plus haut)

Nicolas

Posté par
elhor_abdelali Correcteurre : Algorithme - Suite 24-07-05 à 12:51

Re-bonjour tout le monde;
Nicolas_75,je reprends l'exemple de la suite 4,18,51..et l'algorithme que tu as trouvé u_{n+1}=\frac{120+33u_n}{14} pour u_0=4pas de problème tu as u_1=18 et u_2=51 mais u_3=\frac{1803}{14} n'est plus entier et ton algorithme ne génére donc pas une suite logique d'entiers.Comme je l'ai expliqué plus haut il faut trouver Q\in\mathbb{Z[X]} tel que Q(4)=18 et Q(18)=51 (s'il existe bien entendu)

Posté par
Nicolas_75 Correcteurre : Algorithme - Suite 24-07-05 à 13:02

elhor_abdelali, nous ne répondons pas à la même question.

Je comprends ta problématique (plus intéressante que la mienne) : non seulement, trouver l'"algorithme", mais faire en plus en sorte que les nombres générés ensuite soient tous entiers.

Quant à moi, j'essayais juste de répondre à la question initiale de Nightmare, qui demandait de relier des nombres existants. Cf messages ci-dessus et message initial :

"Ma question est alors la suivante :
Quelque soient les entiers naturels a, b et c. Existe-t-il toujours un algorithme qui permet de trouver b en fonction de a et c en fonction de b.
Par exemple, si on prend l'algorithme : multiplier par 2 et soustraire 1
On voit bien que par cet algorithme en obtient 7 en fonction de 4 et 13 en fonction de 7.
Donc il existe bien un algorithme qui relie 4 - 7 - 13
Est-ce alors vrai pour tout entiers naturels ?
[etc...]"

C'est du moins ma compréhension.

Cordialement,

Nicolas

Posté par
elhor_abdelali Correcteurre : Algorithme - Suite 24-07-05 à 17:22

Une condition nécéssaire:
supposons qu'il existe P\in\mathbb{Z}[X] tel que:
P(a)=b et P(b)=c en écrivant P(X)=\Bigsum_{k=0}^{k=n}p_{k}X^k (n\ge1,p_n\neq0 )on voit que:
c-b=\Bigsum_{k=1}^{k=n}p_{k}(b^k-a^k) et donc que l'on doit avoir:3$\red\ b-a/c-b

Posté par
elhor_abdelali Correcteurre : Algorithme - Suite 24-07-05 à 18:41

Une condition suffisante:
Supposons que 2$\red\ b-a/c-b et posons alors;
p_{1}=\frac{c-b}{b-a} (c'est un entier naturel non nul) et p_{0}=b-ap_{1}=c-bp_{1}(c'est un entier) il est alors facile de voir que l'algorithme \{{u_{0}=a\atop\ u_{n+1}=p_{1}u_{n}+p_{0}génére une suite logique d'entiers a,b,c..
remarque: on voit que le mot "algorithme" se réduit à une transformation affine à coefficients entiers et qu'une condition nécéssaire et suffisante d'existence d'un algorithme générant la suite d'entiers a,b,c.. est que 3$\red\ (b-a) divise (c-b)
Voilà,j'éspére que j'ai répondu à ta question Nightmare

Posté par
elhor_abdelali Correcteurre : Algorithme - Suite 01-08-05 à 06:17

Ainsi,il n'existe pas d'algorithme générant la suite 4,18,51.. puisque 18-4=14 n'est pas diviseur de 33=51-18


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1717 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !