Suite à cette <a href=http://www.cafzone.net/modules.php?op=modload&name=News&file=article&sid=604>news, voici un petit complément d’information que je viens de recevoir à l’instant. Attention ça parle, algo sévère mais bon, ça peut intéresser quelques über geeks.
Intrigué par cette petite news, j’ai demandé à mon prof d’algorithme ce qu’il en pensait…
Voici son témoignage:
[] La primalité dans P n’est pas une révolution. Beaucoup de monde s’y attendait. Bien sûr il fallait trouver ces algorithmes polynomiaux… Voilà, c’est fait.
[] On connaît un algo déterministe dans P sous l’hypothèse de Riemman généralisée. Comme presque tout le monde accepte cette hypothèse…
[] Leur algorithme marche en O(n puissance12) et avec une modification (conjecture) on pourra le ramener en O(n puissance 6)
[] L’algo probabiliste que l’on apprend en DEUG MI2 a des beaux jours devant lui : il est efficace en pratique O(n puissance 3) et on peut minimiser l’erreur (Quand la probabilité devient une CERTITUDE ?!)
[*] Le vrai problème de tous ces machins là, c’est la factorisation. Celui qui trouve un algorithme polynomial qui se cogne ça aura droit à gloire et puissance. Au passage, il pourra casser une grande partie des systèmes de sécurités (d’où gloire et puissance).
(Pour info ce mail provient de Emmanuel Kounalis, tuteur des thèses d’algorithme à la faculté de Nice Sophia Antipolis. Il a écrit plusieurs livres et est assez réputé.)
ndCaf : j’ai quand même retouché son mail, sinon la partie sur ses capacités d’écritures n’était pas viable. :-p
“Leur algorithme marche en O(n puissance12) et avec une modification (conjecture) on pourra le ramener en O(n puissance 6)”
Dans l’article ils parlent plutôt de le ramener en O(n^3), s’ils arrivent à démontrer leur conjecture.
Sinon c’est clair que pour l’instant, cet algorithme a un intérêt purement théorique (montrer rigoureusement que OUI, primes est dans P). En pratique, l’algo probabiliste est plus simple, et ne se plante qu’avec une probabilité absurdement petite (du style 10^-100) dès que le nombre est suffisamment grand.
Euh Pi c’est Pi, y a pas de nombre en écriture décimale qui lui soit égal, puisqu’il est irrationnel (on en est à 53 milliards de décimales il me semble actuellement. j’ai la flemme de chercher).
Non la quadrature du cercle n’est pas résolvable, c’est démontré depuis longtemps :-
Huhu j’aime bien quand ca part n’importe ou comme ca Alors c’etait clairement rethorique comme questions mais je reponds quand meme (hehe).
PI c’est le nombre qui intervient dans le rapport de la circonference du cercle et de son diametre.
La quadrature du cercle n’est pas possible pour la simple raison que PI est un nombre TRANSCENDANT. C’est a dire qu’il n’est pas exprimable comme la solution d’un polynome aux coefficients rationels (ou entiers c’est pareil). Concretement les chiffres qui composent ce nombre viennent au hazard et sont en nombre infini. Il n’y a aucune representation « plus courte » de ce nombre, a part le nombre lui meme. Pi c’est Pi et non pas une fraction, ou la solution d’un polynome quelconque du type x^4+3x^3+123=0.
Ce qui est encore plus fort c’est la demonstration de Cantor qui demontre que en prenant un nombre au hazard, la probabilite qu’il soit transcendant est 1. On dit aussi que l’espace des reels est transcendant « presque partout ». Ce qui, aussi bizzare que cela puisse paraitre, est en fait une definition mathematique tres rigoureuse et precise. Sans etre tres rigoureux moi meme, cela veut dire que l’ensemble des nombres reels qui sont non transcendants, bien qu’infini est ce que l’on appelle denombrable, alors que celui des transcendants dans R ne l’est pas. En gros il y a infiniement plus de nombre transcendants que de nombres non transcendants. Intuituvement on peut toujours placer une infinite de nombre transcendants entre deux nombres non transcendants.
Donc la probabilite est nulle de tomber au hazard sur un nombre non transcendant :- C’est bien bizzare a souhait
Effectivement, tout ce qui est constructible a la regle et au compas est solution d’un polynome a coefficients entiers. Pi etant transcendant, on ne peut pas construire de carre de cote sqrt(Pi), et donc resoudre la quadrature du cercle.
“Intuituvement on peut toujours placer une infinite de nombre transcendants entre deux nombres non transcendants.”
C’est vrai, mais ce n’est pas ca qui fait la difference. L’inverse est vrai aussi, on peut placer une infinite de nombres non transcendants entre 2 transcendants donnes (les nombres non transcendants sont denses dans R).
Je vais passer pour un crétin mais je voulais savoir s’il y avait une utilité de calculer autant de décimales de Pi ou ils le calculent pour la beauté du geste?
Ca sert aussi à peaufiner les algos de multiplication de grands nombres (genre tu vois le million de milliard ? Bah c’est le nombre de chiffres qui composent les nombres à traiter)
C’est particulièrement utile aussi dans les domaines concernés par la théorie du chaos (cad où pour avoir des résultat à peu près fiable, il faut avoir beaucoup de décimales) Exemple type : la météo
Justement non, ce que la théorie du chaos te dit c’est que quelque soit le nombre de décimales dont tu dispose, les erreurs vont croître exponentiellement et tu seras dans les choux de toute façon. Un nombre avec plus de 10 ou 20 décimales n’a aucun sens physique.
En tout cas dans ces domaines connaitre Pi à des milliards de décimales ne sert à rien.
Oui, bien évidemment on sera toujours dans les choux à un moment ou à un autre. On recule simplement le moment où les erreurs seront non-négligeable, et en météo, c’est plutôt cool de pouvoir faire des prévisions à peu près sûre à 7 jours au lieu de 2, non ?
Sinon, pour les décimales de pi, en elles-mêmes, non, elles servent à rien. C’est leur recherche qui est utile.
Non c’est pour ca que j’ai dit intuitivement mathematiquement ca veut rien dire. C’est juste la difference entre un infini denombrable et un infini non denombrable. Ou la puissance du continu comme dit xentyr (merci l’ENSEEIHT).
Le fait de pouvoir faire des prévisions à 7 jours (c’te blague ;)) est plutôt dû à une amélioration des modèles physiques, qui eux demandent effectivement plus de puissance et des algorithmes efficaces. Mais pouvoir faire des calculs à 1000 décimales ne sert strictement à rien, vu qu’on ne connait les conditions initiales (température, pression, etc…) qu’avec une précision bien moindre.
D’après ce que je sais c’est plutôt l’inverse… les modèles physiques n’ont pas changés mais c’est la précision des calculs qui augmente. Même si tu as par exemple 3 chiffres après la virgule dans les données initiales, si tu multiplies deux nombres de la sorte entre eux, ça te fait 9 chiffres après la virgule. Et ainsi de suite. Si tu tronques les valeurs, alors tu perds de la précision par rapport aux malheureuses 3 décimales de départ.
Précision des cacluls oui, mais pas en terme de nombre de décimales, plutôt diminution du pas de la grille utilisée pour discrétiser le problème (par exemple dans les codes d’éléments finis).
Pour l’accumulation des erreurs, ce qui compte est la précision relative et non la précision absolue. Si tu connais tes 2 nombres avec une précision expérimentale de 10^-3, alors tu connais le produit avec une précision relative de 2.10^-3. Les décimales qui sont au-delà n’ont pas de sens physique.
