Bonjour

La prochaine fois que vous allez devoir rediger un document scientifique dans l'informatique, voici une URL
interessante

[pdos.csail.mit.edu]

Meri du lien; il me semble qu'il y a une dizaine d'années il y a eu des choses similaires mais j'ai oublié les détails.


----

Basile STARYNKEVITCH _{où on trouve mon mél}

Membre de l'APRIL « promouvoir et défendre le logiciel libre » - adhérez vous aussi à l'APRIL!

_{N.B. N'hesitez pas à consulter aussi mes contributions antérieures.}

Le pipotron est aussi efficace, et il y en a des tonnes sur charabia.net.

--
On ne prête qu’aux riches, et on a bien raison, parce que les autres remboursent difficilement.
-+- Tristan Bernard (1866-1947) -+-

Cela me rappelle un délicieux bouquin dont le titre était, si je me souviens bien, "anatomie et physiologie des rhinopodes", paru il y a une trentaine d'année. Le bouquin décrivait toute un ordre d'animaux dont la particularité étaient de se déplacer grâce à des organes qui étaient également des narines. Tout y était: classification en familles, genres, espèces; figures; "photos"; bibliographie; etc. Un vrai délice !
Je recherche vainement ce bouquin depuis plusieurs années, alors si quelqu'un à de lumières à ce sujet ...

Tu veux parler des rhinogrades ? Le bouquin est en vente environ 30 neuros chez Dunod, c’est vraiment cher.

--
On ne prête qu’aux riches, et on a bien raison, parce que les autres remboursent difficilement.
-+- Tristan Bernard (1866-1947) -+-

nicola a écrit :

Évidemment, en cherchant rhinopode, j'avais peu de chance de trouver

Amusant.
Ca me rappelle quand je faisait mes études. Les systèmes experts étaient des
sujets très à la mode et mon prof disait que l'on pouvait faire de la démonstration automatique (en math) grace à ceux-ci.
Historiquement une conjecture célèbre a été démontré en ayant recours à des calculs sur informatique, il s'agit de la conjecture des 4 couleurs : l'indice
de coloriage d'un graphe planaire est au plus 4. Traduction en français courant : il est possible de colorier les pays sur un Atlas de manière à ce que deux pays frontaliers aient deux couleurs différentes, et cela en utilisant en tout au maximum 4 couleurs.

Et pour les pays, comme la France, qui ont plus de trois pays frontaliers, on fait comment ? :D

hachures bicolores ?

Greg L. a écrit :

Il n'y a jamais, plus de 4 pays qui se touchent simultanément.
Si tu veux éviter la démonstration mathématique, tu peux passer des heures à essayer de dessiner le cas contraire ...

Ah, expliqué comme ça, c'est beaucoup plus clair ...

Greg L. a écrit :

Prends un Atlas de l'Europe et tu verra que c'est possible. D'ailleurs si l'Atlas est en couleurs c'est surement déjà fait.
Pour la petite histoire : Les cartographes et les imprimeurs se sont rendu-compte de la conjecture parceque de façon empirique ils constataient que
4 couleurs suffisaient toujours. Ce qui était pratique pour des raisons d'économie de moyens. Les mathématiciens se sont emparés du problème et ont facilement démontré la conjecture des 5 couleurs (au plus 5 couleurs suffisent), pour montrer que 4 couleurs suffisaient un mathématicien à réussi
à montrer qu'il fallait prouver le théorème pour un nombre fini mais grand de
cas types. Il a alors écrit un programme pour traiter exhaustivement tous ces cas types. A l'époque cela a pris 5000 heures de calculs. De nos jour avec l'augmentation de la puissance des machines, cela prendrait beaucoup moins de temps.
A l'époque certains scientifiques n'admettaient pas le résultat car produit d'une machine faillible. Mon opinion est que puisque l'expérience est reproductible et qu'on peut faire une preuve de programme alors on peut admettre (après avoir vérifié et validé) le résultat et que l'attitude de refus était plutôt signe de scientisme ou d'intégrisme.

Ce théorème est vrai dans la sphère ou dans le plan, mais il faut plus de couleurs sur un tore (chambre à air).
Vous pouvez trouver un paquet de jeux dont un (map) dont le but est de colorier une carte avec quatre couleurs. Ils sont compilés pour Windows mais leur code source est disponible, et il y a un paquet pour Debian Etch (sgt-puzzles). Ils font un malheur dans mon bahut.

--
On ne prête qu’aux riches, et on a bien raison, parce que les autres remboursent difficilement.
-+- Tristan Bernard (1866-1947) -+-

Dans la série interaction de l'informatique et des mathématiques. Il y a plusieurs application de théorème de Godel (grosso-modo toute théorie axiomatique est contradictoire - c.a.d elle amène à des résultats du type l'affirmation TRUC est en même temps vraie et fausse- ou incomplète -Il existe dans les théorie des affirmations indémontrables et on peut sans contradiction les supposer vraies ou les supposer fausses : c'est un principe d'incertitude) on montre qu'il ne peut pas exister de programme prouvant tous
les programmes (En gros s'il existait un tel programme ne pourrait pas s'arrêter parce qu'il devrait se prouver lui-même), des chercheurs ont exhibé par calcul informatique des équations diophantiennes (c.a.d que les inconnues sont des entiers, qu'elles n'utilisent que des additions soustractions divisions multiplications et élévation à une puissance entière) qui sont indécidables : c.a.d qu'étant donnés des entiers on peut vérifier s'ils sont solutions (un simple calcul), mais étant donné un nombre fini de solutions ( calculées exhaustivement en épuisant un ensemble nécessairement fini d'entiers) il n'existe pas de preuve (ou d'algorithme) montrant qu'il y en a d'autres.

Le théorème de Gödel dirait plutôt, si mon souvenir est bon : dans toute construction logique 'valable' (ie: ayant un ensemble de postulats non-contradictoires, il existe une proposition non décidable.

C'est à dire qui n'est pas ET vraie ET fausse, mais plutôt, dont on ne peut décider si elle est vraie ou fausse. C'est à dire : si on l'ajoute à la théorie, celle-ci reste non contradictoire et si on ajoute la négation de la proposition à la théorie, elle reste aussi non contradictoire.

Pour la théorie logique ZF (dite de Zermelo et Fraenkel) , une proposition indécidable est l'hypothèse du continue (en gros, R est le plus petit ensemble plus grand que N à une bijection près)

_{Fred --
jeune padawan}

Attention à ne pas confondre indécidabilité (ou indémontrabilité) et indifférence. Une proposition indécidable (comme celle qui est exhibée par Gödel) est vraie mais non démontrable dans le système formel où elle a été formulée. Mais si on ajoute de quoi démonter cette proposition, on trouvera d’autres propositions indécidables et ainsi de suite. En revanche l’hypothèse du continu est indifférente parce qu’on peut construire des mathématiques à partir de son affirmation comme de sa négation, de la même manière que la géométrie euclidienne ou les géométries non-euclidiennes sont construites à partir de l’affirmation ou de la négation du cinquième postulat d’Euclide.

--
On ne prête qu’aux riches, et on a bien raison, parce que les autres remboursent difficilement.
-+- Tristan Bernard (1866-1947) -+-

Je me sens geek atterri dans un (autre) monde de geeks d'un autre registre...

___________________________________________________________________
_{.:! L'être humain est au sommet de la chaîne alimentaire. Certes. Mais il est surtout au sommet de la connerie et de la bêtise... !:.
-- Pour les nouveaux linuxiens : Ce n'est pas en continuant de faire ce que l'on connaît que l'on pourra faire ce que l'on ne connaît pas --}

euh... moi aussi ! Merlin8282, je te rejoins dans le même monde... j'arrive...

Léa (Fred) a écrit :

Une construction logique est donc contradictoire ou incomplète. J'ai sans doute mal ponctué mon post, mais nous disons bien la même chose. On peut trouver des applications au théorème de Gôdel dans des domaines inattendus
par exemple : une idéologie totalitaire (sans indécidable) est nécessairement contradictoire, un code de lois (à priori non contradictoire, quoique par les temps qui courrent...) contient nécessairement des vides juridiques.

Pour la théorie ZF c'est un peu plus compliqué voici une citation extraite de www.les-mathematiques.net "Notez bien aussi que si ZF est consistante, alors il est impossible de le prouver; mais que par contre si elle ne l'est pas, on dispose d'un algorithme théorique permettant en temps fini de le prouver..."
Je pense que le résultat doit plutot être : Si la théorie de Zermelo et Fraenkel est consistante (ce qui est indécidable) alors l'hypothèse du continue est elle- même indécidable. Cela dit il semble bien que ce soit le cas (consistance de ZF).

Hélène a écrit :

Cela dit, ça m'a l'air vachement intéressant ! (je pense à moi-même, quand je parle des idées de K. Dick, ou encore de Autonomy Project (d'ailleurs à ce propos, l'auteur a l'intention d'en faire une trilogie, cool )... )

___________________________________________________________________
_{.:! L'être humain est au sommet de la chaîne alimentaire. Certes. Mais il est surtout au sommet de la connerie et de la bêtise... !:.
-- Pour les nouveaux linuxiens : Ce n'est pas en continuant de faire ce que l'on connaît que l'on pourra faire ce que l'on ne connaît pas --}