Forum de mathématiques - Bibm@th.net

totomm

Invité

Démonstration mathématique et Algorithme

Bonjour,

Un algorithme est écrit pour résoudre un problème : 3 notions essentielles lui sont liées.
"Correction, Terminaison et Complétude."

L'ordinateur a été utilisé pour traiter des algorithmes répondants à des problèmes posés dans des sous-forums de Bibmath, alors que des démonstrations "formalisées" (relativement ...) étaient aussi exposées.

Considérez-vous alors qu'algorithme ou démonstration valident tout autant un résultat ?

Peut-être ce débat a-t-il déjà été engagé sur ce forum ?
cordialement.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Démonstration mathématique et Algorithme

Salut,

oui, ce débat a été ouvert un jour par mes soins au sujet d'un résultat obtenu par un calcul informatique et je me désespérais de prouver que la solution trouvée était bien unique.

C'était, si je me souviens bien, un problème d'arithmétique.

J'en avais conclu que la seule manière de prouver qu'il n'y avait qu'une seule solution était bien le raisonnement, pas le calcul. Et j'ai donc poussé la réflexion jusqu'à trouver le raisonnement démontrant l'unicité de la solution.

As tu essayer de travailler sur la conjecture dite de Syracuse ? Toute la communauté pense qu'elle est vraie, mais personne ne la tient pour telle tant qu'elle n'aura pas été formellement démontrée. Il en était de même pour celle de Fermat, il en est aussi de même pour celle de Goldbach.

Cela tient au fait qu'un ordinateur ne pourra pas balayer un nombre infini d'entier, ce que seul le raisonnement abstrait peut faire. En revanche, on peut prouver que la conjecture est fausse en détectant un contre exemple. Et ça peut être fait grâce au soutien de l'informatique.

PS : j'aimerai bien avoir l'avis du camarade Barbichu et celui de Fred sur cette question. Je sais ce que yoshi pense, et je plussoie.

totomm

Invité

Re : Démonstration mathématique et Algorithme

re,

@ freddy : Il me semble que vous déviez le débat qui concerne les algorithmes respectant les notions de : "Correction, Terminaison et Complétude."
On n'en connait pas pour les conjectures que vous citez....

Le débat qui m'intéresse est bien, dans le cas des algorithmes dont on a montré qu'ils respectent ces trois notions essentielles :
"Considérez-vous alors qu'algorithme ou démonstration valident tout autant un résultat ?"

L'avis sur ce questionnement des personnes que vous citez serait effectivement bienvenu, comme celui de toute autre...

cordialement

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Démonstration mathématique et Algorithme

RE,

"Considérez-vous alors qu'algorithme ou démonstration valident tout autant un résultat ?"

J'en reviens à ce que j'ai déjà dit ailleurs (avec ici peut-être clarification de ma pensée)...
Oui, bien sûr, parce que dans ce cas le programme ne fait que reproduire un cheminement que, techniquement, le mathématicien aurait été capable de reproduire (humainement, c'est une autre paire de manches : fatigue, erreur(s) de calcul, perte(s) de mémoire...) la démonstration.

Dans ce cas l'algorithme ne fait "que" de la Démonstration Assistée par Ordinateur, ce que j'ai baptisé ailleurs DemAO.
C'est de le démonstration traduite dans un langage adapté à une machine...

Ainsi encore que je l'ai déjà dit, supposons un exercice qui serait résolu résoudre par l'être humain par un raisonnement par récurrence.
Y a-t-il une autre voie, via l'algorithmique, que celle qui consiste à faire exécuter via un logiciel de calcul formel ledit raisonnement ?
Là, grosse supériorité de la machine : infatigable, sans faute, et des millions de fois plus rapides...
Je dis non, pas d'autre voie possible : mais résultat valable...

Regardez  les programmes d'échecs qui tournent sur les supercalculateurs : l'ancien champion du monde Vladimir Kramnik a été battu par l'un d'entre eux dans le cadre de "test matches" comme on dit en sport...
Pourquoi ? Humain, il a commis des erreurs de jugement et de calculs des positions.
Et alors, la machine était-elle infaillible ?
Oui, dans la limite de son "champ de vision" (mais au delà ?), sur des calculs de combinaisons s'achevant sur un gain matériel (ou le mat) sur 10 coups par exemple, aucune "chance d'erreur".
J'ai tout un petit logiciel d'échecs, GnuChess, libre et gratuit, à l'horizon 5 coups (10 demi-coups), il est infaillible à 99,9 %.
Après, ce n'est pas parce qu'on "perd" du matériel, que le jugement de la position doit être systématiquement défavorable à celui qui a perdu du matériel...
Par contre, lorsque la combinaison se termine par un mat (quel que soit son "horizon"), la machine a bien fait la preuve que la position était perdante !
Mais l'être humain, techniquement, en théorie, était aussi capable de trouver ladite combinaison ; en pratique, il faut tenir compte des imperfections humaines...

@+

lefeu

Invité

Re : Démonstration mathématique et Algorithme

Bonjour
cette question est intéressante, si on prend Syracuse, il ne s'agit pas de lui faire exécuter les itérations sur n'importe quel entier cela n'apporterait rien.

mais serait-il possible de faire calculer la structure arithmétique dont Syracuse dépend, en supposant:

a) un vol infini dans les entiers relatifs,

b) ou un autre cycle de boucle que les trois existant dans ces entiers relatifs.{-4, -2,-2} ; {-20 , -10, -14} et le troisième je ne met que la fin {-68 -34 -50}

chaque vol est lié à deux autres c'est à dire par leurs itération en modifiant la formule qui donne le même résultat mais on ne prend en compte que les itération N pair, soit N₁,N₂....N_n
de la transformation de l'entier i impair :
(2i *3 +2)/2 = N₁ on réitère  (N₁*3 +2)/2 = N₂ ; ou N₁/2 = N₂ si N est multiple de 4.

il existe deux autres vol i tel que
2*N₂ - N'_2' = N''_2''

plus simplement il existe continuellement 3 vol x,y, z
tel que 2x - y = Z  prenons l'itération N₂ pour ces trois vols, N₂ = X , y, Z différent bien entendu, sinon la formule serait fausse.

avec y entier positif > 0 , x et z dans les négatifs,

ce qui donne :
pour le vol y ,  (3*N_n-1* 3 +2)/ 2 = N_y = 2* -N_x - (-N_z)

où les trois itérations de ces trois vols sont bien trois itération N_n+1 une positive et deux négatives.

[pour info , l'écart entre est trois vols est de 2ⁿ si on passe à l'itération Nⁿ⁺¹ l'écart serra bien entendu de 2ⁿ⁺¹ entre les vols.
on connait aussi à partir de quel itération du vol y les Nn son en relation avec les deux autres vol -i = -x et-z
le tout est parfaitement ordonné par une structure arithmétique simple, mais masquée par la formule 3k+1.]

la question qui se pose :
pour qu'elle raison une structure arithmétique aussi bien ordonnée, ferait-elle apparaître un vol infini dans les positifs ou les relatifs, ou encore donnerait un autre cycle de boucle que les trois déjà existant dans ces relatifs ou ne serait ce qu'un autre dans les positifs...

un algorithme pourrait-il apporté la réponse en supposant un changement dans la structure de Syracuse. qui jusqu'à preuve du contraire, est très bien ordonnée par des suites en progression arithmétique d'où cette formule.

merci

leg

Invité

Re : Démonstration mathématique et Algorithme

Attention,

Au lieu de :

de ce qui donne :
pour le vol y ,  (3*N_n* 3 +2)/ 2 = N_y = 2* -N_x - (-N_z)

lire

ce qui donne :
pour le vol y ,  (N_n* 3 +2)/ 2 = N_y = (2* -N_x) - (-N_z) avec bien entendu :(N_n non multiple de 4 car sinon il faudrait simplement divisé par 2 pour obtenir N_n+1= N_y