Forum de mathématiques - Bibm@th.net

Yop,
"Oh mon dieu que c'est moche" serait la remarque (absolument non constructive) que je m'autoriserais à faire si j'étais ton prof d'info (dans le supérieur, parce que dans le secondaire ça semblerait décourageant). Malheureusement, tu n'es pas mon élève, tu n'as sûrement pas de cours d'info digne de ce nom, tu n'es pas dans le supérieur et je ne suis pas prof (enfin, ça dépend de la définition de prof). Je me contenterai donc de justifier ma remarque par un argument primitif : j'évacue pour passer à la suite de façon plus constructive.

Tout d'abord, j'admire l'entrain et le bon sens dont tu fais preuve pour écrire un code permettant de résoudre des problèmes que l'on aborde normalement bien plus tard (les problèmes aussi bien que leur code).

Par contre, et pour que tu puisses progresser, voici les reproches que je fais à ton code :
1/ Il utilise des effets de bords : typiquement, l'utilisation de variables globales modifiées par un appel à une fonction (qui en plus retourne une valeur) est une chose déconseillée dans le cas général. (En fait, c'est une façon de programmer tout à fait acceptable quand on a une bonne raison de le faire, ce qui n'est à mon humble avis pas le cas ici).

2/ Le langage python te fourni un modulo : l'opérateur est %, utilise le ! Il est bon de savoir comment le reprogrammer à partir de rien, mais par exemple tu n'as jamais envisagé de reprogrammer l'addition ? De plus, le modulo de python a beaucoup de chance d'être plus efficace que ton implémentation.
2bis/ La division entière ne nécessite pas de typecast vers les entiers : a/b est le quotient dans la division euclidienne de a par b.

3/ Pour programmer de façon propre, on distingue (au moins) deux types de fonctionnalités : le calcul d'une part, l'interaction homme-machine d'autre part. Il convient alors d'encapsuler :
   * d'un côté les fonctions de calcul, comme pgcd ou modulo (ça tu l'as fait), mais aussi ta boucle while et tes calculs compliqués que tu as mis au milieu des print ! Ça constitue en quelque sorte ce qu'on appelle généralement "librairie" (sauf que là c'est une librairie locale)
   * de l'autre coté, une fonction qui fait appel aux input et aux print. Cette fonction étant appelée lors de l'exécution du fichier.

NB :
J'avais donné une version compacte de la fonction qui résout ton problème, que j'ai nommée bezout, ici : http://www.bibmath.net/forums/viewtopic.php?id=2479 (Il s'agit là d'une version fonctionnelle, de surcroît récursive)
Il y également une version impérative donnée par yoshi, ici : http://www.bibmath.net/forums/viewtopic.php?id=2701 sous le nom xeuklid qui doit être légèrement modifié pour te sortir les coefs de bezout, mais si tu me demandes, je te la donne.

N'hésite pas à poser des questions si je ne suis pas clair dans mon commentaire, si tu veux que je donne des exemples plus précis, où si tu veux que je développe quelque chose.

++

Salut,
oui, ça s'appelle "in".
Par ex "3 in [3,4]" te répond "True".
++

Lut,
http://fr.wikipedia.org/wiki/Rubicon
La première section de l'article devrait te permettre de tout comprendre.
++

Re, allons-y

La formalisation fait paraitre le problème plus compliqué qu'il ne l'est vraiment. On en comprend très bien l'intuition en faisant de jolis dessins sur tableau noir. Malheureusement je n'ai pas de tableau noir sur bibmath ...

L'intuition est que lorsqu'on passe par une racine de multiplicté n de P, on décroit de n.
Et lorsqu'on passe des racines de dérivées de P qui proviennent de racines complexes dans P, alors on décroit également de la multiplicité de ces racines (sachant que les racines complexes viennent toujours par 2 !!!)
Là où ça devient délicat c'est qu'en un point x on peut trouver simultanément des racines de P et des racines complexes de P, mais également des parasites dans les dérivées qui proviennent des autres racines de P.
Heureusement, on ne cherche jamais à savoir si on a rencontré des racines complexes, ou des parasites.

On va donc décomposer le V en trois types de blocs :
* les racines réelles (cf C/a/) :
une racine nieme se détecte par l'annulation des n-1 premieres dérivées et la non annulation de la nieme.
On va voir que c'est sur les changements de signes de cette zone que s'effectue la décroissance en n (cf B/).

* les parasites+les racines complexes (cf C/b/)
on les trouves forcement plus bas, et le fait que la paraité de V y soit conservé est un petit miracle (cf A/ + B/ => C/b/)

* les zones sans problème (cf C/c/)

Exemples
Première lignes = valeurs de x
Deuxième ligne = séparateurs
Lignes suivantes = signes de P et de ses dérivées successives au point x

Ex1 : X^3 (Réel pur, sans parasites)

Ex2 : X^3-1, (une racine rélle, deux racines complexes conjuguées, pas d'interference)

Ex3 : X^3+X (une racine réelle, deux racines complexes conjugués, qui interferent avec cette derniere)

Ex4 : X^3-X (3 racines réelles, -1 0 et 1. et la combinaison de -1 et 1 parasite 0, sans compter)

================================
===         FORMALISATION              ===
================================
/!\ Attention, danger pour les neurones /!\

Considérons [tex]P[/tex] un polynôme de degré [tex]n[/tex]. 
Étant donné un étant donné un élément [tex]x \in \mathbb{R}[/tex] on défini les notations suivantes :
* [tex]\mathcal{O}(x) = \{i | P^{(i)}(x) = 0\}[/tex]
* [tex]\mathcal{V}(x)_{[[i,j]]} = \left\{ (i',j')\ /\ \begin{Bmatrix} i \le i'<j' \le j,\ P^{(i')}P^{(j')} < 0 \\ \wedge\; \forall k \textrm{ tq } i'<k<j',  P^{(k')}=0 \end{matrix} \right\}[/tex]
* [tex]V_{[[i,j]]}(x) = \textrm{Card}(\mathcal{V}_{[[i,j]]}(x))[/tex]
* [tex]\mathcal{V}(x) = \mathcal{V}_{[[0,n]]}(x)[/tex]
  * Alors [tex]V(x) = \textrm{Card}(\mathcal{V}(x))[/tex]
On remarque que si [tex]k\not\in\mathcal{O}(x)[/tex], alors [tex]\mathcal{V}(x)_{[[i,j]]} = \mathcal{V}(x)_{[[i,k]]} \sqcup \mathcal{V}(x)_{[[k,j]]}[/tex] (R)

I/ Preliminaires
A/ Si [tex]x \in \matR[/tex],  [tex]i<j[/tex] et [tex]P^{(i)}(x)P^{(j)}(x) \neq 0[/tex] alors :
[tex]P^{(i)}(x)P^{(j)}(x) > 0[/tex] ssi [tex]V_{[[i,j]]}(x)[/tex] est pair
Preuve :
Trivial par recurrence forte sur [tex]j-i[/tex] :
* Si [tex]j-i[/tex] = 1,  [tex]P^{(i)}(x)P^{(j)}(x) > 0 \Leftrightarrow (i,j)\not\in\mathcal{V}_{\{i,j\}}\Leftrightarrow \mathcal{V}_{[[i,j]]} = \varnothing  \Leftrightarrow V_{[[i,j]]}=0 [/tex]
   En effet : [tex]\mathcal{V}_{[[i,j]]} \subset \{(i,i+1)\}[/tex]

* Sinon, soit [tex]k>i[/tex] le plus petit, tel que [tex]k\not\in\mathcal{O}(x)[/tex].
   * Si [tex]k=j[/tex], la démo est la même que ci-dessus (Attention, on utilise pas d'hypothèse de récurrence ici)
   * Sinon, on applique l'hypothèse de récurrence à [tex](i,k)[/tex] et [tex](k,j)[/tex] on recolle par (R)
Qed.

Considérons maintenant [tex]a,x, b \in \matR[/tex] tels que [tex]a < x < b[/tex] d'une part
et tel que pour tout [tex]y \in [a,x[\cup]x,b][/tex] aucune des dérivées de P ne s'annule.
(Notez bien que je n'impose rien sur [tex]x[/tex])

B/ Si [tex]i \in \mathcal{O}(x)[/tex] alors [tex](i,i+1) \in \mathcal{V}(a)[/tex] et  [tex](i,i+1) \not\in \mathcal{V}(b)[/tex]
Preuve :
(C'est l'argument de Fred, mais mieux localisé)
Comme [tex]i \in \mathcal{O}(x)[/tex], on a [tex]P^{(i)}(x)=0[/tex].
(i) Supposons [tex]P^{(i+1)}(a)>0[/tex] (le cas négatif s'en déduit par symmétrie et le cas nul est éliminé par hypothèse)
On sait par hypothèse que [tex]P^{(i+1)}[/tex] ne s'annule pas sur [tex][a,x[[/tex], d'où [tex]P^{(i)}[/tex] croissante sur [tex][a,x[[/tex].
Et comme [tex]P^{(i)}[/tex] s'annule seulement en [tex]x[/tex], il est négatif sur [tex][a,x[[/tex] donc en a .
Donc [tex](i,i+1) \in \mathcal{V}(a)[/tex]
(ii) Idem, mais en raisonnant sur l'intervalle [tex]]x,b][/tex]. On trouve [tex](i,i+1) \not\in \mathcal{V}(a)[/tex].
Qed.

Soit maintenant [tex]i_0, j_0, i_1, j_1 \ldots , i_p, j_p[/tex] tels que
* [tex]\forall k\in[[0,p]], i_k \leq j_k [/tex]
* [tex]\forall k\in[[0,p-1]], j_k + 1 < i_{k+1} [/tex]
* [tex]\mathcal{O}(x) = [[i_0,j_0]] \sqcup \ldots \sqcup [[i_p,j_p]][/tex]
(On pose par convention : [tex]j_{-1}=0[/tex] et [tex]i_{p+1}=n[/tex])

C/  Montrons que :
   a/ Si [tex]k\in[[0,p]][/tex] et [tex]i_k=0[/tex] (on a alors nécessairement [tex]k=0[/tex]), alors  [tex]V_{[[i_k,j_k+1]]}(a) = j_k-i_k+1[/tex] et [tex]\mathcal{V}_{[[i_k,j_k+1]]}(x) = \mathcal{V}_{[[i_k,j_k+1]]}(b)) = \varnothing[/tex]
Preuve :
On remarque que par constructions des [tex](i_k,j_k)[/tex], on a nécessairement [tex]P^{(j_k+1)}[/tex] non nul.

On a [tex][[i_k,j_k]] \subset \mathcal{O}(x)[/tex], d'où par B/ :
(i) [tex]\forall i \in [[i_k,j_k]] (i,i+1) \in \mathcal{V}[[i_k,j_k+1]](a)[/tex], et alors [tex]V_{[[i_k,j_k+1]]}(a) = j_k-i_k+1[/tex]
(ii) [tex]\forall i \in [[i_k,j_k]] (i,i+1) \not\in \mathcal{V}[[i_k,j_k+1]](b)[/tex] et alors  [tex]\mathcal{V}_{[[i_k,j_k+1]]}(b) = \varnothing[/tex]
Enfin, comme il n'existe pas dans [tex]\mathcal{V}[[i_k,j_k+1]](x)[/tex] de paire [tex](i,j)[/tex] tel que [tex]P^{(i)}[/tex] et [tex]P^{(j)}[/tex] soient simultanment non nuls, on a nécessairement  [tex]\mathcal{V}_{[[i_k,j_k+1]]}(x) = \varnothing[/tex]
Qed.

    b/ Si [tex]k\in[[0,p]][/tex] et [tex]i_k>0[/tex],  alors [tex]V_{[[i_k-1,j_k+1]]}(a) \geq V_{[[i_k-1,j_k+1]]}(x) = V_{[[i_k-1,j_k+1]]}(x)[/tex] et
[tex]V_{[[i_k-1,j_k+1]]}(a) \equiv V_{[[i_k-1,j_k+1]]}(x) \pmod 2[/tex]
Preuve :
On remarque que par constructions des [tex](i_k,j_k)[/tex], on a nécessairement [tex]P^{(i_k-1)}(x)[/tex] et [tex]P^{(j_k+1)}(x)[/tex] non nul.

* On a [tex][[i_k,j_k]] \subset \mathcal{O}(x)[/tex], d'où par B/ :
[tex]\forall i \in [[i_k,j_k]] (i,i+1) \not\in \mathcal{V}[[i_k,j_k+1]](b)[/tex] et alors  [tex]\mathcal{V}_{[[i_k-1,j_k+1]]}(b) \subset \{(i_k-1,i_k)\}[/tex]

* Comme il existe  dans [tex]\mathcal{V}[[i_k-1,j_k+1]](x)[/tex] un unique paire [tex](i,j) = (i_k-1,j_k+1)[/tex] telle que [tex]P^{(i)}[/tex] et [tex]P^{(j)}[/tex] soient simultanment non nuls, on a nécessairement  [tex]\mathcal{V}_{[[i_k,j_k+1]]}(x) \subset \{(i_k-1,j_k+1)\}[/tex]

Donc [tex]V_{[[i_k,j_k+1]]}(b)[/tex] et [tex]V_{[[i_k,j_k+1]}](x)[/tex] sont dans [tex]\{0,1\}[/tex]
Et dans les deux cas, la parité du cardinal détermine complètement le cardinal :

Enfin, comme  [tex]P^{(i_k-1)}P^{(j_k+1)}[/tex] ne s'annule ni en [tex]a[/tex], ni en [tex]b[/tex], ni en [tex]x[/tex], on en tire par A/ que les trois cardinaux
[tex]V_{[[i_k-1,j_k+1]]}(a)[/tex], [tex]V_{[[i_k-1,j_k+1]}](b)[/tex] et [tex]V_{[[i_k-1,j_k+1]}](x)[/tex] ont même parité.

On en tire trivialement l'énoncé
Qed.

    c/ Si [tex]k\in[[-1,p]][/tex], alors [tex]\mathcal{V}_{[[j_k+1,i_{k+1}-1]]}(a)) = \mathcal{V}_{[[j_k+1,i_{k+1}-1]]}(x)) = \mathcal{V}_{[[j_k+1,i_{k+1}-1]}](b))[/tex]
Preuve :
Trivial : Il n'y a pas de changements de signes hors de [tex]\mathcal{O}(x)[/tex].
Qed.

D/ Enfin, si [tex]P[/tex] admet une racine [tex]n^{\textrm{ieme}}[/tex] en [tex]x[/tex] (avec [tex]n[/tex] éventuellement égal à [tex]0[/tex]),
alors
(i) [tex]V(a) - V(b) \geq n[/tex] et [tex]V(a) - V(b) \equiv n \pmod 2[/tex]
(ii) [tex]V(x) = V(b)[/tex]

Preuve :
On rappelle que par (R) on a : [tex]\forall u \in \{a,x,b\}, \mathcal{V}(u) = \bigsqcup_{k=0}^{p}\mathcal{V}_{[[i_k-1,j_k+1]]}(u)
\sqcup \bigsqcup_{k=-1}^{p}\mathcal{V}_{[[j_k+1,i_{k+1}-1]]}(u)[/tex] (car aucun des $i_k-1$ et $j_k+1$ n'est dans $\mathcal{O}$)

(ii) Trivial par C/a/b/c/ : il y a toujours égalité des [tex]V[/tex] pour [tex]x[/tex] et [tex]b[/tex].

(i) Il y a deux cas a distinguer :
   a) [tex]n = 0[/tex], donc [tex]x[/tex] n'est pas vraiment une racine de [tex]P[/tex]. Alors le cas C/a/ disparait, le cas C/c/ permet de simplifier la comparaison et il n'y a qu'à appliquer le cas C/b/ pour trouver que [tex]V(a) - V(b) \geq 0[/tex] et  [tex]V(a) - V(b) \equiv 0 \pmod 2[/tex]
   b) [tex]n > 1[/tex], on sait alors que les [tex]n-1[/tex] premières dérivées de [tex]P[/tex] s'annulent en [tex]x[/tex] et que la dérivée nième ne s'y annule pas. D'où [tex][[i_0,j_0]] = [[0,n-1]][/tex] et alors
[tex]V_{[[i_0,j_1]]}(a) = n[/tex] et [tex]V_{[[i_0,j_1]]}(b) = 0[/tex], par C/a/. En assemblant le reste avec C/b/ et C/c/. On obtient le resultat voulu.

Qed.

Rq : de D/ on déduit également :
(iii) [tex]V(a) - V(x) \geq n[/tex] et [tex]V(a) - V(x) \equiv n \pmod 2[/tex]

II/ Cas général
Soient [tex]a,b\in\matR[/tex] avec [tex]a < b[/tex] et [tex]P(a)P(b) \neq 0[/tex]
L'ensemble des points en lesquels P ou l'une de ses dérivées s'annule sur [tex]]a,b[[/tex] est fini, notons [tex]a < x_1 < \ldots < x_N < b[/tex] ses points. Et soient [tex]\mu_1, \ldots, \mu_N[/tex] leur multiplicité respective (éventuellement nulle) en temps que racine de P.
Soient alors [tex]a_0,\ldots,a_N[/tex] tels que [tex]a < a_0 < x_1 < \ldots < a_{N-1} < x_N < a_N < b[/tex]
On a [tex]V(a) - V(b) = V(a) - V(a_0) + \sum_{k=0}^{N-1}\left(V(a_k) - V(a_{k+1})\right) + V(a_N) - V(b)[/tex]

Or, en appliquant D/ judicieusement :
* [tex]V(a) - V(a_0)= 0[/tex] par D/(ii)
(en effet, [tex]a[/tex] joue le rôle de [tex]x[/tex] et [tex]a_0[/tex] le rôle de [tex]b[/tex] dans D/).
* [tex]V(a_k) - V(a_{k+1}) \geq \mu_{k+1}[/tex] et [tex]V(a_k) - V(a_{k+1}) \equiv \mu_{k+1} \pmod 2[/tex] et par D/(i)
(en effet, [tex]a_k[/tex] joue le rôle de [tex]a[/tex] et [tex]a_{k+1}[/tex] le rôle de [tex]b[/tex] dans D/).
* [tex]V(a_N) - V(b) \geq 0[/tex] et [tex]V(a_N) - V(a_b) \equiv 0 \pmod 2[/tex] par D/(iii)
(en effet, [tex]a_N[/tex] joue le rôle de [tex]a[/tex] et [tex]b[/tex] le rôle de [tex]x[/tex] dans D/).

En sommant, on obtient [tex]V(a) - V(b) \geq \sum\mu_k[/tex] et [tex]V(a) - V(b) \equiv \sum\mu_k \pmod 2[/tex] CQFD !

III/ La question 2 : appliquer la question 1 en 0 et b avec b suffisamment grand !

Ouahou !

Salut,
Non, si on sait que le présentateur tire au hasard, on a une chance sur deux pour chaque à la fin.
En fait, j'ai l'impression (parce que ça, je ne l'ai pas vérifié) que si le choix du présentateur est indépendant de la position de la voiture, alors on a une chance sur deux pour chaque choix à la fin.

++

Edit> Je n'avais pas non plus lu jusqu'au bout, mais l'article wikipédia est d'accord avec moi : http://fr.wikipedia.org/wiki/Problème_d … 7ouverture (et pousse même plus loin http://fr.wikipedia.org/wiki/Problème_d … e_globale)

Salut,
la méthode ? Il n'y a pas de méthode pour tout, parfois il faut juste plonger les mains dans le cambouis et essayer des trucs. Souvent d'ailleurs ce n'est pas une méthode qu'on cherche mais une reformulation de la question, qui elle admet une méthode "connue".
Ici la reformulation serait "comment savoir si alpha*X est solution de l'équation ?" et la méthode est : "injecter alpha*X dans l'équation et calculer/regarder sous quelles conditions elle la vérifie".
++

Re,
le passage avec if __name__ ... ne sert que pour la ligne de commande shell (et ms-dos si c'est compatible)
(sous ligne de commande ms-dos, il doit falloir faire C:\chemin_complet_vers_python\python inv_modulo.py 2 5)

Par contre pour l'utiliser dans le shell python, il suffit de faire l'import et d'utiliser la fonction, comme une fonction python, grâce au petit bout de code de mon dernier message en exemple ; et je suis certain que ça marche chez toi, vu que "import inv_modulo" a marché dans ton shell python. (Et il n'y a rien à modifier par rapport au fichier que j'ai soumis ici)
++

Re,
Un petit benchmark, sur ma machine
./inv_modulo_yoshi.py 10000001 100000000000000 => résultat en 15 secondes
./inv_modulo.py 10000001 100000000000000 => résultat en moins d'1 seconde

./inv_modulo_yoshi.py 100000001 1000000000 => résultat en 2min 12 secondes
./inv_modulo.py 100000001 1000000000; => résultat en moins d'1 seconde

++

Re,
C'est sensé remplacer l'integralité de ton code, à condition de rajouter à la fin

et de supprimer toute la partie if __name__ ....

Et sinon
1. Oui, ma fonction bezout est récursive, je pourrais la dérécursifier, mais elle est plus agréable et mieux compréhensible ainsi
2. le "_" est une variable "puits", que je n'utiliserai donc pas. J'aurais très bien pu mettre "v" ou "toto", ce qui aurait mis un nom inutile dans l'espace de nom de ma fonction.

[edit] voila qui devrait te renseigner un peu mieux
++

Salut yoshi,
je n'avais pas vu ce programme. Je te propose cette version qui est plus courte et beaucoup plus efficace :

[Edit] J'ai ajouté à mon code de quoi le rendre autonome pour répondre à la question de yoshi
Il s'utilise maintenant de la ligne de commande en lui fournissant comme argument le nombre et le modulo. Exemple, si je l'enregistre sous le nom "inv_modulo.py" :

++

J'ai lu tes documents, et tu nous donne là un bon exemple qu'on peut faire dire au chiffres tout ce qu'on veut.
Si tu choisi à la fois les constantes et le pattern, il n'y a plus rien d'exceptionnel ! C'est comme si je te disais :
"dans le nombre 1/Phi=0,61803398874989484820458684749214, il y avait 1 chances sur  1 000 000 que les 6 premières décimales soient 618033 !", or tu m'accorderas que ça n'a rien d'exceptionnel.

J'ai écrit un petit programme python qui permet, à partir de 2 séquences de décimales de trouver un pattern divisé en au moins 4 zones. ça a 4% de chances d'arriver (résultat experimental). J'ai tenté une autre experience : je tire au hasard 100 séquences décimales, j'arrive alors à trouver un pattern de au moins 4 zones qui recouvre une 15aines de ces séquences.

Cela veut dire que si j'essaye d'attraper un maximum de "constantes fondamentale", entre pi, phi, e, leurs inverses, des racines carrés diverses, et des combinaisons qu'on retrouve dans le monde des maths, je dois bien trouver là plus d'une 100aine de séquences, et ce n'est donc pas improbable du tout d'y coller un schema comme tu l'as fait ! Cependant, tu omets de préciser que tu as considéré plein de constantes sur lesquelles tu n'as pas réussi à y coller ce pattern, ce qui n'est pourtant pas négligeable pour la crédibilité de ton étude.

Si tu veux mon programme python, n'hésite pas à me le demander.
Je veux bien me donner la peine de le mettre en forme et de décrire précisément les expériences que j'ai effectués. (Si on me laisse du temps)

++

Salut,
Tout dépend si je connais le pari de l'autre. Si je le connais, et si mon adversaire parie :
* FF, je parie PF => j'ai alors 3 chances sur 4 de gagner
* PP, je parie FP => idem
* FP, je paries PF => j'ai une chance sur deux.
* PF, je paries FP => idem
Autrement dit, je parie toujours deux cotés différents, avec comme premier choix, celui opposé au sien.

Si je ne connais pas son pari, je parie FP (resp PF). S'il parie PF ou FF (resp FP ou PP), c'est équitable. S'il parie PP (resp FF) j'ai trois chance sur quatre de gagner.

Voila, sauf erreur de calcul de ma part.
++