Dans le cadre de mon article sur les théories pré-Univers, j'ai essayé de me documenter et de recueillir les avis de différentes personnes sur ce sujet et plus précisément sur les travaux des frères Bogdanov.
J'ai donc participé à un forum "anti"-Bogdanov pour tenter de savoir en quoi leur théorie n'avait "aucun sens" : http://ybmessager.free.fr/epiphysique/forums/phpBB2/
J'ai tenté dans mes interventions de présenter les points qui me semblaient intéressants et j'ai demandé aux intervenants de m'expliquer point par point les incohérences.
J'ai pu recueillir quelques arguments intéressants, comme par exemple l'impossibilité de donner une interprétation physique aux modèles pré-Univers.
Cependant, la plupart de mes questions sont restées sans réponses.
Les intervenants, dont je ne citerai pas le nom, m'ont littéralement descendu et ont refusé de répondre à mes questions et de clarifier les problèmes de fond, pour rendre les objections à cette théorie intelligibles.
J'ai été ce matin banni de ce forum avec un sous-entendu déplorable (mon dernier post m'a renvoyé sur le site des Bogdanov...)
Alors puisque YBM (oups) ne souhaite pas que "n'importe qui" puisse s'exprimer dans son forum, qu'il aille donc se faire foutre, il y a plus de 10 milliards de pages sur le net, alors une de plus ou de moins...
Je ne supporte plus cet élitisme sur certains forums, où les intervenants pensent savoir tout sur tout et se moquent dès qu'une personne commet une erreur ou ne commprend pas quelque chose.
Pire que çà, ces gens là veulent supprimer l'imagination et le libre arbitre de la science, sous couvert de rigueur.
Alors pour tous ceux qui sont frustrés et qui en ont marre de ces connards, je les invite volontiers à participer sur mon blog.
A bientôt !
mercredi 19 mars 2008
lundi 3 mars 2008
Les théories pré-espace temps (partie 2)
Dans la première partie, nous avons vu les deux théories les plus en vogue concernant la création de l'Univers : A1 (scénario ekpyrotique) et A2 (scénario du multivers). Ces deux théories correspondent à la définition A (scientifique) de l'Univers.
Avant de présenter une théorie du pré-Univers alternative, j'aimerai pointer les problèmes posés par les théories A1, A2 et plus généralement par toutes les théories pré-Univers basées sur la définition A.
Les problèmes des théories Ax
Le point commun entre toutes ces théories est que l'Univers (sphère causale) ne représente justement pas "l'ensemble de toute chose" : on admet qu'il puisse exister en dehors de la sphère causale un méta-système qui l'a engendré.
Cette hypothèse est - à mon avis - motivée par deux raisons que l'on a déjà évoqué dans la première partie :
Problème 1 : Le principe de conservation de l'entropie
Au début du XXème siècle, Emmy Noether, une mathématicienne Allemande a démontré un des plus beaux théorèmes qui s'applique à la physique théorique.
Vous pourrez trouver un site très pédagogique sur le théorème de Noether ici : http://semsci.u-strasbg.fr/noether.htm
Le théorème de Noether nous dit que chaque loi de conservation correspond à une symétrie sur le système considéré : Le principe de conservation de l'énergie correspondrait à la symétrie de translation temporelle.
Citons un passage du site ci-dessus, qui définit cette symétrie : "L'invariance par translation dans le temps rend l'origine du temps inobservable, assurant par la même la conservation de l'énergie".
On en déduit que la conservation de l'énergie est valable en tout point de l'espace-temps, sauf - justement - à l'origine du temps. (c'est du moins ce que j'en ai déduit...).
Problème 2 : Le principe anthropique
Le principe anthropique est valable en supposant l'existence d'un grand nombre d'Univers possibles et du fait qu'on ne dispose d'aucun critère, autre que notre existence, pour expliquer l'Univers dans lequel nous vivons.
Ce principe est en ce moment très à la mode dans un autre domaine de la physique : la théorie des cordes. En effet, la théorie des cordes possède un très grand nombre de paramètres que l'on peut ajuster pour obtenir des théories très différentes. Les cordistes appelent cet ensemble le "paysage" et justifient le choix du "bon" paysage par le principe anthropique.
Ici, nous sommes dans un cas légèrement différent : pourquoi supposer que la création de l'Univers (sphère causale) est un événement "multiple" ?
En fait, ce choix est justifié uniquement par la définition A : l'Univers est la sphère causale, mais pas "l'ensemble de toute chose", on peut donc supposer qu'il existe "autre" chose (donc de multiples sphères causale) en dehors de la nôtre.
On se retrouve alors dans un raisonnement cyclique : les théories Ax sont basées sur le principe anthropique, car le principe anthropique est basé sur la définition A !
Mais avant de remettre en cause la définition A, il me reste un problème important à examiner. Un problème plus fondamental, qui s'appliquera de toute façon, à toutes les théories - quelle que soit la définition de l'Univers.
Problème 3 : La preuve expérimentale
Bernard Weber - dont je suis fan - disait à juste titre "Pour comprendre un système, il faut s'en extraire" (je ne suis d'ailleurs pas sûr que cette citation soit de lui, bref...).
Toutes les théories pré-Univers sont
et resteront vraissemblablement spéculatives, pour quelle raison ? Eh bien, que l'on prenne la définition A ou B, nous nous trouvons dans une sphère causale dont nous ne pouvons sortir. Si nous supposons qu'il existe des membranes ou d'autres sphères causales en dehors de la nôtre, nous ne pourrons malheureusement jamais le savoir, du moins directement.
Il pourrait effectivement exister des "indices" en faveur d'une ou l'autre théorie, mais en réalité, ces indices nous montreraient simplement que la création de notre sphère causale n'est pas incompatible avec telle ou telle théorie.
En fait, tout ce que nous imaginons au delà de notre sphère causale n'a aucune justification, si ce n'est par exemple, que le taux d'expansion de notre sphère causale pourrait correspondre à un cycle expansion/contraction de l'Univers (il se trouve que c'est un mauvais exemple car il semble que notre sphère causale soit en fait en expansion accélérée, mais ceci est un autre débat...).
Alors si tout ce que l'on imagine au delà de la sphère causale n'est pas justifié, pourquoi l'imaginer ?
On peut supposer que l'Univers est la sphère causale, tout en étant "l'ensemble de toute chose". (Je suis enfin d'accord avec les scientifiques et les religieux sur la définition du mot Univers !)
Unification des définition A et B
Posons donc notre nouvelle définition de l'Univers, que l'on pourrait appeler A+B, ou AB pour les puristes...
Définition AB : L'Univers est l'ensemble de toute chose, c'est à dire la sphère causale
Cette définition de l'Univers bénéficie d'un principe supplémentaire, qui est souvent essentiel dans la nature (même s'il est parfois trompeur) : le principe d'économie : Il n'existe rien en dehors de la sphère causale.
Maintenant que nous possédons une nouvelle définition, quelles théories pré-Univers peut-on formuler ?
Et bien, il me semble qu'il n'y a que deux possibilités :
Si vous avez lu ma "démonstration" dans la première partie, vous "savez" déjà que Dieu = Univers. Je trouve amusant que l'expression "L'Univers s'est créé lui même" est alors équivalente à "Dieu à créé l'Univers". Mais revenons à notre théorie AB2...
Théorie AB2 : l'Univers s'est créé lui-même à partir de rien
Cette phrase peut sembler absurde (et je sais que pour beaucoup elle l'est certainement...). Cependant, je voudrai insister sur deux points qui la justifient, en suivant la définition AB :
Cependant, peut-être serez-vous surpris de savoir que d'autres ont déjà tenté de développer une telle théorie ? Je veux parler bien-sûr de la théorie de la singularité initiale de Igor et Grishka Bogdanov.
Mon point de vue :
Cette théorie est bien sûr très controversée et j'ai longtemps hésité avant de prendre parti pour cette théorie de peur d'être considéré comme un imbécile par mes (quelques) lecteurs (potentiels).
J'ai eu connaissance de cette théorie en juin 2004, lors de la sortie du livre - lui aussi très discuté - "Avant le Big Bang". J'ai lu 2 ou 3 fois ce livre, en alternance avec d'autres livres, considérés comme "plus sérieux".
Malgré toutes les oppositions et tous les arguments - en apparence bien fondés - à l'encontre de cette théorie et des frères Bogdanov, je ne pouvais m'empêcher d'admirer cette théorie.
Je dois bien l'avouer aujourd'hui, je suis un "pro-Bogda", ou plutôt un "pro-théorie de la singularité initiale", pour ne pas être assimilé à un fan inconditionnel des frêres Bogdanov (bien que j'apprécie leurs émissions).
Dans la prochaine partie, je tenterai donc de présenter la théorie AB2 : Théorie de la singularité initiale, des frêres Bogdanov.
Je tiens à donner une dernière précision aux "anti-Bogda" : comme je l'ai dit précédemment - et comme les Bogdanov le reconnaissent eux-mêmes - toute théorie pré-Univers est spéculative. Il n'y a donc à priori aucune raison de ne pas considérer la théorie AB2 avec la même crédibilité que les théories Ax.
Avant de présenter une théorie du pré-Univers alternative, j'aimerai pointer les problèmes posés par les théories A1, A2 et plus généralement par toutes les théories pré-Univers basées sur la définition A.
Les problèmes des théories Ax
Le point commun entre toutes ces théories est que l'Univers (sphère causale) ne représente justement pas "l'ensemble de toute chose" : on admet qu'il puisse exister en dehors de la sphère causale un méta-système qui l'a engendré.
Cette hypothèse est - à mon avis - motivée par deux raisons que l'on a déjà évoqué dans la première partie :
- Le principe de conservation de l'entropie (énergie/matière)
- Le principe anthropique
Problème 1 : Le principe de conservation de l'entropie
Au début du XXème siècle, Emmy Noether, une mathématicienne Allemande a démontré un des plus beaux théorèmes qui s'applique à la physique théorique.
Vous pourrez trouver un site très pédagogique sur le théorème de Noether ici : http://semsci.u-strasbg.fr/noether.htm
Le théorème de Noether nous dit que chaque loi de conservation correspond à une symétrie sur le système considéré : Le principe de conservation de l'énergie correspondrait à la symétrie de translation temporelle.
Citons un passage du site ci-dessus, qui définit cette symétrie : "L'invariance par translation dans le temps rend l'origine du temps inobservable, assurant par la même la conservation de l'énergie".
On en déduit que la conservation de l'énergie est valable en tout point de l'espace-temps, sauf - justement - à l'origine du temps. (c'est du moins ce que j'en ai déduit...).
Problème 2 : Le principe anthropique
Le principe anthropique est valable en supposant l'existence d'un grand nombre d'Univers possibles et du fait qu'on ne dispose d'aucun critère, autre que notre existence, pour expliquer l'Univers dans lequel nous vivons.
Ce principe est en ce moment très à la mode dans un autre domaine de la physique : la théorie des cordes. En effet, la théorie des cordes possède un très grand nombre de paramètres que l'on peut ajuster pour obtenir des théories très différentes. Les cordistes appelent cet ensemble le "paysage" et justifient le choix du "bon" paysage par le principe anthropique.
Ici, nous sommes dans un cas légèrement différent : pourquoi supposer que la création de l'Univers (sphère causale) est un événement "multiple" ?
En fait, ce choix est justifié uniquement par la définition A : l'Univers est la sphère causale, mais pas "l'ensemble de toute chose", on peut donc supposer qu'il existe "autre" chose (donc de multiples sphères causale) en dehors de la nôtre.
On se retrouve alors dans un raisonnement cyclique : les théories Ax sont basées sur le principe anthropique, car le principe anthropique est basé sur la définition A !
Mais avant de remettre en cause la définition A, il me reste un problème important à examiner. Un problème plus fondamental, qui s'appliquera de toute façon, à toutes les théories - quelle que soit la définition de l'Univers.
Problème 3 : La preuve expérimentale
Bernard Weber - dont je suis fan - disait à juste titre "Pour comprendre un système, il faut s'en extraire" (je ne suis d'ailleurs pas sûr que cette citation soit de lui, bref...).
Toutes les théories pré-Univers sont
et resteront vraissemblablement spéculatives, pour quelle raison ? Eh bien, que l'on prenne la définition A ou B, nous nous trouvons dans une sphère causale dont nous ne pouvons sortir. Si nous supposons qu'il existe des membranes ou d'autres sphères causales en dehors de la nôtre, nous ne pourrons malheureusement jamais le savoir, du moins directement.
Il pourrait effectivement exister des "indices" en faveur d'une ou l'autre théorie, mais en réalité, ces indices nous montreraient simplement que la création de notre sphère causale n'est pas incompatible avec telle ou telle théorie.
En fait, tout ce que nous imaginons au delà de notre sphère causale n'a aucune justification, si ce n'est par exemple, que le taux d'expansion de notre sphère causale pourrait correspondre à un cycle expansion/contraction de l'Univers (il se trouve que c'est un mauvais exemple car il semble que notre sphère causale soit en fait en expansion accélérée, mais ceci est un autre débat...).
Alors si tout ce que l'on imagine au delà de la sphère causale n'est pas justifié, pourquoi l'imaginer ?
On peut supposer que l'Univers est la sphère causale, tout en étant "l'ensemble de toute chose". (Je suis enfin d'accord avec les scientifiques et les religieux sur la définition du mot Univers !)
Unification des définition A et B
Posons donc notre nouvelle définition de l'Univers, que l'on pourrait appeler A+B, ou AB pour les puristes...
Définition AB : L'Univers est l'ensemble de toute chose, c'est à dire la sphère causale
Cette définition de l'Univers bénéficie d'un principe supplémentaire, qui est souvent essentiel dans la nature (même s'il est parfois trompeur) : le principe d'économie : Il n'existe rien en dehors de la sphère causale.
Maintenant que nous possédons une nouvelle définition, quelles théories pré-Univers peut-on formuler ?
Et bien, il me semble qu'il n'y a que deux possibilités :
- Théorie AB1 : l'Univers n'a pas eu de création et donc a toujours existé. Cette théorie semble peu probable si on considère la théorie du Big Bang.
- Théorie AB2 : "l'Univers s'est créé lui-même" à partir... de rien. Je développerai cette théorie un peu plus bas.
Si vous avez lu ma "démonstration" dans la première partie, vous "savez" déjà que Dieu = Univers. Je trouve amusant que l'expression "L'Univers s'est créé lui même" est alors équivalente à "Dieu à créé l'Univers". Mais revenons à notre théorie AB2...
Théorie AB2 : l'Univers s'est créé lui-même à partir de rien
Cette phrase peut sembler absurde (et je sais que pour beaucoup elle l'est certainement...). Cependant, je voudrai insister sur deux points qui la justifient, en suivant la définition AB :
- Il n'existe rien en dehors de l'Univers lui-même, donc rien n'est susceptible de l'avoir créé
- La théorie de la relativité générale montre clairement que l'Univers est dynamique, l'Univers ne peut donc pas "toujours avoir existé"
- Le principe de conservation de l'énergie n'est pas respecté
- Le principe anthropique n'est pas valable
Cependant, peut-être serez-vous surpris de savoir que d'autres ont déjà tenté de développer une telle théorie ? Je veux parler bien-sûr de la théorie de la singularité initiale de Igor et Grishka Bogdanov.
Mon point de vue :
Cette théorie est bien sûr très controversée et j'ai longtemps hésité avant de prendre parti pour cette théorie de peur d'être considéré comme un imbécile par mes (quelques) lecteurs (potentiels).
J'ai eu connaissance de cette théorie en juin 2004, lors de la sortie du livre - lui aussi très discuté - "Avant le Big Bang". J'ai lu 2 ou 3 fois ce livre, en alternance avec d'autres livres, considérés comme "plus sérieux".
Malgré toutes les oppositions et tous les arguments - en apparence bien fondés - à l'encontre de cette théorie et des frères Bogdanov, je ne pouvais m'empêcher d'admirer cette théorie.
Je dois bien l'avouer aujourd'hui, je suis un "pro-Bogda", ou plutôt un "pro-théorie de la singularité initiale", pour ne pas être assimilé à un fan inconditionnel des frêres Bogdanov (bien que j'apprécie leurs émissions).
Dans la prochaine partie, je tenterai donc de présenter la théorie AB2 : Théorie de la singularité initiale, des frêres Bogdanov.
Je tiens à donner une dernière précision aux "anti-Bogda" : comme je l'ai dit précédemment - et comme les Bogdanov le reconnaissent eux-mêmes - toute théorie pré-Univers est spéculative. Il n'y a donc à priori aucune raison de ne pas considérer la théorie AB2 avec la même crédibilité que les théories Ax.
A suivre...
vendredi 29 février 2008
Les théories pré-espace temps
J'ai souhaité écrire cet article pour tenter de faire un petit état des lieux, à mon niveau, des théories qui décrivent la création de l'univers - ou plus précisément ce qui a engendré l'Univers - et discuter les hypothèses qui sous-tendent ces théories.
Vous trouverez aussi dans cet article quelques réflexions subjectives un peu "métaphysiques", j'ai annoté ces passages "Mon point de vue".
Avant toute chose, pour se mettre d'accord sur le vocabulaire, je tenterai de donner une, ou plutôt deux définitions de l'univers.
Définition A (scientifique) : L'Univers est la sphère causale qui englobe toute les ondes, particules et forces physiques
Définition B (sémantique) : L'Univers est l'ensemble de toute chose.
La définition A que j'ai surnommée "scientifique" est celle - me semble t'il - qui est admise par la communauté scientifique.
La définition B est plutôt "sémantique", elle s'intéresse à ce que signifie le mot Univers, indépendamment des connaissances scientifiques actuelles.
Comme je l'ai précisé, les théories pré-Univers proposées au sein de la communauté scientifique portent toutes (à ma connaissance), sur la définition A. La définition B quant à elle paraît plus métaphysique et il semble donc difficile d'élaborer un modèle concret à partir d'une définition aussi vague. Examinons donc les théories pré-Univers compatibles avec la définition A. J'appelerai ces théories Ax, x étant l'ordre dans lequel j'en parle (ayant une très faible connaissance de ces théories, je n'ai aucune préférence particulière)
Une dernière précision : je ne prétend pas donner une explication complète ni même correcte de chaque théorie évoquée ci-dessous, j'essayerai simplement d'en résumer l'idée principale. Toutes les précisions ou corrections seront les bienvenues.
Théorie A1 : Le scénario ekpyrotique
L'Univers ("sphère causale") serait issu du "choc" entre deux membranes à plusieurs dimensions (au sens de la théories des cordes). Ces membranes seraient en mouvement périodique, qui engendrerait un cycle création/destruction de l'Univers, à priori infini.
Théorie A2 : Le scénario du Multivers
L'Univers serait une "bulle" causale, engendré par une autre bulle-Univers causale. Il existerait une infinité (?) d'Univers connectés les uns aux autres dans une sorte d'arbre, que l'on pourrait appeler le Multivers.
Ces deux théories - j'imagine, comme d'autres théories Ax - ont un avantage indéniable : elles permettent de respecter le principe de conservation de l'entropie (énergie/matière). En effet, la sphère causale est vue comme le résultat d'une interaction entre d'autres éléments, dans un système plus grand (les membranes ou le multivers) : rien ne se crée, rien ne se perd, etc.
Cependant en faisant cela, ne retombe t'on pas finalement sur la même question, légèrement transformée : Au lieu de se demander "d'où vient l'Univers ?" on se demande maintenant "d'où viennent les membranes ?" ou "d'où vient le Multivers ?" ...
Je ne connais pas l'explication pour la théorie ekpyrotique, je peux cependant citer l'argument de la théorie du Multivers : Le Multivers représente l'ensemble de tous les Univers possibles, il n'y a donc pas d'explication - ou de choix - à l'origine de son existence. Donc pour revenir à nous, nous existons dans notre Univers car c'est celui dans lequel on existe : il s'agit de l'argument anthropique. J'imagine que la théorie ekpyrotique avance un argument un peu similaire, du style : chaque cycle engendre un Univers différent qui au final créé tous les Univers possibles, on peu alors avancer l'argument anthropique.
Un dernier point commun qui me semble essentiel entre ces 2 théories est l'aspect "infini" du méta-système (membranes ou multivers), par opposition à la taille "finie" de l'Univers (sphère causale).
En outre, ce que j'ai appelé le méta-système (membranes ou multivers) semble correspondre maintenant à la définition B : L'ensemble de toute chose.
Mon point de vue :
Depuis que je suis tout petit, j'adhère à la définition B. Pour moi, l'Univers ne peut-être que l'ensemble de toute chose : si l'on trouve quelque chose qui englobe l'Univers connu, alors on devrait appeler ce nouvel ensemble l'Univers.
J'aimerai au passage donner ma "démonstration" (un peu tirée par les cheveux, il est vrai...) de la non existence de Dieu avec cet argument :
Supposons que Dieu existe et a créé l'Univers. L'Univers étant l'ensemble de toutes chose (B), on en déduit que Dieu est inclus dans l'Univers. Supposons enfin, comme c'est le cas - à ma connaissance - dans les 3 grandes religions monothéistes, que Dieu "est partout", autrement dit que l'Univers est inclus dans Dieu. Ces deux concepts étant inclus l'un dans l'autre, on en déduit qu'il sont égaux : le mot Dieu, désigne la même chose que le mot Univers. On peut penser soit que Dieu n'existe pas, que ce n'est qu'un autre terme pour définir l'Univers, soit que l'Univers est Dieu (pour les plus croyants).
Je tiens à préciser que le point - à mon avis - sur lequel les religieux ne sont pas d'accord avec ce raisonnement est la définition B de l'Univers : L'Univers n'est pas l'ensemble de toute chose, car Dieu n'est pas DANS l'Univers, Dieu l'a créé.
Pour conclure ce point de vue, il semble que "ma" définition de l'Univers ne soit ni acceptée par les scientifiques, ni par les religieux (je suis tout seul ...snif) . Plus étonnant encore, il semble même, d'après la remarque que j'ai faite dans le paragraphe précédent, que la définition A de l'Univers soit la même pour les scientifiques ET pour les religieux (aurions nous trouvé un point d'entente ?)
Je reviendrai dans la prochaine partie sur les théories A1 et A2 et j'essayerai de défendre "ma" définition B en présentant une théorie que j'appellerai - à priori - B1.
Vous trouverez aussi dans cet article quelques réflexions subjectives un peu "métaphysiques", j'ai annoté ces passages "Mon point de vue".
Avant toute chose, pour se mettre d'accord sur le vocabulaire, je tenterai de donner une, ou plutôt deux définitions de l'univers.
Définition A (scientifique) : L'Univers est la sphère causale qui englobe toute les ondes, particules et forces physiques
Définition B (sémantique) : L'Univers est l'ensemble de toute chose.
La définition A que j'ai surnommée "scientifique" est celle - me semble t'il - qui est admise par la communauté scientifique.
La définition B est plutôt "sémantique", elle s'intéresse à ce que signifie le mot Univers, indépendamment des connaissances scientifiques actuelles.
Comme je l'ai précisé, les théories pré-Univers proposées au sein de la communauté scientifique portent toutes (à ma connaissance), sur la définition A. La définition B quant à elle paraît plus métaphysique et il semble donc difficile d'élaborer un modèle concret à partir d'une définition aussi vague. Examinons donc les théories pré-Univers compatibles avec la définition A. J'appelerai ces théories Ax, x étant l'ordre dans lequel j'en parle (ayant une très faible connaissance de ces théories, je n'ai aucune préférence particulière)
Une dernière précision : je ne prétend pas donner une explication complète ni même correcte de chaque théorie évoquée ci-dessous, j'essayerai simplement d'en résumer l'idée principale. Toutes les précisions ou corrections seront les bienvenues.
Théorie A1 : Le scénario ekpyrotique
L'Univers ("sphère causale") serait issu du "choc" entre deux membranes à plusieurs dimensions (au sens de la théories des cordes). Ces membranes seraient en mouvement périodique, qui engendrerait un cycle création/destruction de l'Univers, à priori infini.
Théorie A2 : Le scénario du Multivers
L'Univers serait une "bulle" causale, engendré par une autre bulle-Univers causale. Il existerait une infinité (?) d'Univers connectés les uns aux autres dans une sorte d'arbre, que l'on pourrait appeler le Multivers.
Ces deux théories - j'imagine, comme d'autres théories Ax - ont un avantage indéniable : elles permettent de respecter le principe de conservation de l'entropie (énergie/matière). En effet, la sphère causale est vue comme le résultat d'une interaction entre d'autres éléments, dans un système plus grand (les membranes ou le multivers) : rien ne se crée, rien ne se perd, etc.
Cependant en faisant cela, ne retombe t'on pas finalement sur la même question, légèrement transformée : Au lieu de se demander "d'où vient l'Univers ?" on se demande maintenant "d'où viennent les membranes ?" ou "d'où vient le Multivers ?" ...
Je ne connais pas l'explication pour la théorie ekpyrotique, je peux cependant citer l'argument de la théorie du Multivers : Le Multivers représente l'ensemble de tous les Univers possibles, il n'y a donc pas d'explication - ou de choix - à l'origine de son existence. Donc pour revenir à nous, nous existons dans notre Univers car c'est celui dans lequel on existe : il s'agit de l'argument anthropique. J'imagine que la théorie ekpyrotique avance un argument un peu similaire, du style : chaque cycle engendre un Univers différent qui au final créé tous les Univers possibles, on peu alors avancer l'argument anthropique.
Un dernier point commun qui me semble essentiel entre ces 2 théories est l'aspect "infini" du méta-système (membranes ou multivers), par opposition à la taille "finie" de l'Univers (sphère causale).
En outre, ce que j'ai appelé le méta-système (membranes ou multivers) semble correspondre maintenant à la définition B : L'ensemble de toute chose.
Mon point de vue :
Depuis que je suis tout petit, j'adhère à la définition B. Pour moi, l'Univers ne peut-être que l'ensemble de toute chose : si l'on trouve quelque chose qui englobe l'Univers connu, alors on devrait appeler ce nouvel ensemble l'Univers.
J'aimerai au passage donner ma "démonstration" (un peu tirée par les cheveux, il est vrai...) de la non existence de Dieu avec cet argument :
Supposons que Dieu existe et a créé l'Univers. L'Univers étant l'ensemble de toutes chose (B), on en déduit que Dieu est inclus dans l'Univers. Supposons enfin, comme c'est le cas - à ma connaissance - dans les 3 grandes religions monothéistes, que Dieu "est partout", autrement dit que l'Univers est inclus dans Dieu. Ces deux concepts étant inclus l'un dans l'autre, on en déduit qu'il sont égaux : le mot Dieu, désigne la même chose que le mot Univers. On peut penser soit que Dieu n'existe pas, que ce n'est qu'un autre terme pour définir l'Univers, soit que l'Univers est Dieu (pour les plus croyants).
Je tiens à préciser que le point - à mon avis - sur lequel les religieux ne sont pas d'accord avec ce raisonnement est la définition B de l'Univers : L'Univers n'est pas l'ensemble de toute chose, car Dieu n'est pas DANS l'Univers, Dieu l'a créé.
Pour conclure ce point de vue, il semble que "ma" définition de l'Univers ne soit ni acceptée par les scientifiques, ni par les religieux (je suis tout seul ...snif) . Plus étonnant encore, il semble même, d'après la remarque que j'ai faite dans le paragraphe précédent, que la définition A de l'Univers soit la même pour les scientifiques ET pour les religieux (aurions nous trouvé un point d'entente ?)
Je reviendrai dans la prochaine partie sur les théories A1 et A2 et j'essayerai de défendre "ma" définition B en présentant une théorie que j'appellerai - à priori - B1.
A suivre...
lundi 11 février 2008
P = NP : problème ou illusion ? (partie 3)
Dans la deuxième partie , nous avons calculé la complexité de la multiplication scolaire à N chiffres : il s'agit d'un calcul à temps quadratique, nous avions vu que l'addition scolaire est un calcul à temps linéaire dans la première partie
Nous avions conclut que ces deux opérations appartiennent à l'ensemble P, qui représente l'ensemble des calculs déterministes à temps polynomial.
Dans la conjecture P = NP, l'ensemble NP représente les calculs non déterministes à temps polynomial. Mais avant de revenir sur cet ensemble plus en détail, il nous faut voir une dernière notion.
Avant, je dois préciser que certains passages peuvent contenir des erreurs pour deux raisons : d'une part, je ne suis pas un spécialiste de la théorie de la complexité et encore moins du problème P = NP. D'autre part, je présenterai à certains endroits mon point de vue, qui là encore peut contenir des erreurs ou même sembler simpliste aux spécialistes, vous voilà prévenus...
Les calculs à temps exponentiel
Imaginons que l'on souhaite connaître le nombre d'ancêtres A que nous avons, pour une génération N, par exemple :
A(1) = 2 (parents)
A(2) = 4 (grands parents)
A(3) = 8 (arrière grands parents)
...
A(N) = 2^N
Pour calculer A(N), il nous faut multiplier le résultat précédent A(N-1) par deux. En prenant comme opération unitaire la multiplication, on a donc un calcul à temps exponentiel, c'est à dire du type :
T(calcul exponentiel) = K^N
Où K est un nombre fixé (2 dans le cas du calcul des ancêtres) et N le nombre de données (dans notre exemple, le nombre de générations)
Un point fréquent dans les calculs à temps exponentiels est qu'ils sont récursifs : pour calculer A(N), on doit calculer A(N-1). Le résultat final n'est possible qu'en faisant tous les calculs
Mon point de vue : On peut se représenter le calcul à temps polynomial ou exponentiel comme une série de calculs à effectuer dans l'ordre : les calculs sont "branchés" en série, un peu comme des composants d'un circuit électrique. Tous les "circuits sont nécéssaires pour alimenter" le résultat. Les problèmes P ou E (voir plus bas) sont des "calculs en ET".
Nous pouvons maintenant définir l'ensemble E, comme étant l'ensemble des calculs à temps exponentiel. Mais quel rapport avec P = NP ? En quoi cela peut-il nous aider à définir l'ensemble NP ?
Calculs non déterministes à temps polynomial
Que signifie un calcul "non déterministe" ? En gros, que l'algorithme doit effectuer un certain nombre de calculs indépendants les uns des autres et qu'en fonction du "choix" qu'il fera, il pourra mettre moins de temps que nécéssaire, s'il avait dû tous les calculer, ou s'il les avait calculé dans un "ordre déterministe".
Pour cette raison, on dit souvent que les problèmes de la classe NP sont des problèmes de "décision".
On observe plusieurs propriétés importantes des problèmes de la classe NP :
- On peut calculer un problème NP avec un algorithme à temps exponentiel
- On peut vérifier le calcul d'un problème NP avec un algorithme à temps polynomial
On voit qu'en terme d'efficacité, les problèmes NP semblent se situer "entre" les problèmes P et E.
Autre point important : un problème P fait également partie de la classe NP. En termes ensembliste, on dira que l'ensemble P est inclus dans l'ensemble NP.
En mathématique, pour que deux ensembles (P et NP) soient égaux, il faut (et il suffit) qu'ils soient inclus l'un dans l'autre. Nous savons déjà que P est inclus dans NP. Toute la question de l'hypothèse P = NP est en fait de savoir si la réciproque est vraie : En fait la question n'est pas "P est-il égal à NP ?", mais plus précisément "NP est-il inclus dans P ?", autrement dit :
Pour chaque problème NP, existe-il un algorithme déterministe à temps polynomial capable de le résoudre ?
Généralement, les problèmes mathématiques commençant par "Pour chaque...existe t'il..." sont les plus difficiles à résoudre , car il faut démontrer l'existence d'un tel algorithme pour chaque problème, mais comment peut-on étudier en même temps TOUS les problèmes de type NP ? (Une blague de mathématicien serait de dire qu'on se trouve en face d'un problème à temps exponentiel...)
En fait, dans les années 60, un mathématicien américain du nom de Stephen Cook a découvert qu'on pouvait étudier tous les problèmes d'une classe, en étudiant uniquement "les plus difficiles" de cette classe : En résumé, "qui peut le plus, peut le moins". On appelle ces problèmes des problèmes complets.
Un problème NP-Complet : le problème du voyageur
Imaginons qu'un touriste veuille visiter N villes. Il souhaite effectuer le trajet le plus court possible, ou plus précisément, plus court qu'une certaine distance autorisée, qu'on appelera D, tout en passant par toutes les villes.
Pour résoudre ce calcul il faudrait à priori calculer toutes les combinaisons possibles de trajets, soit (N-1)! et sélectionner uniquement celles inférieures à D, par exemple :
Pour deux villes (N=2), il y a 1 seul trajet possible (T=1), donc une seule distance à calculer.
N = 3, T = 2
N = 4, T = 6
N = 5, T = 24
...
N = k, T = (k-1)! = (k-1) * (k-2) * ... * 1
On retrouve un peu le même schéma que pour le calcul des ancêtres (à temps exponentiel) : une série de multiplications, on peut donc à priori classer cet algorithme dans l'ensemble E.
Cependant, on peut vérifier si notre solution est correcte en beaucoup moins de temps : en faisant la somme des distances des trajets parcourus, on obtient une distance qui doit nécéssairement être inférieure à D. L'algorithme de vérification appartient à la classe P, car le temps de calcul est proportionnel au nombre de villes.
Ces deux éléments (calcul dans E et vérification dans P) suffisent à classer notre problème dans la catégorie NP.
En plus de cela (la démonstration m'est inconnue) ce problème est un problème "NP difficile", un problème NP-Complet. On peut reformuler la conjecture P = NP comme cela :
Si on parvient à trouver un algorithme déterministe à temps polynomial pour résoudre le problème du voyageur, alors on pourra le faire pour n'importe quel problème NP. La classe NP sera alors réduite à la classe P.
Le problème, c'est que personne n'a encore trouvé d'algorithme déterministe à temps polynomial pour aucun problème NP-Complet, donc pour l'instant, force est de constater que P n'est pas égal à NP !
Mon point de vue : P n'est pas égal à NP
Comme je l'ai dit dans la première partie de cet article, je ne suis pas un spécialiste, pourtant, en lisant divers articles sur le problème P = NP, dont l'excellent livre "les énigmes mathématiques du 3ème millénaire", je me suis mis à rêver d'une légitimité pour donner ma conception de ce problème... Voici mon idée, peut-être naïve ou stupide, mais c'est une idée...
Les problèmes NP consistent à effectuer plusieurs calculs, qui sont à priori pas tous nécéssaires, pour les résoudre : Dans le problème du voyageur, "si on a de la chance", on peut tomber sur le plus court trajet du premier coup, pas besoin de tous les calculer.
On peut se représenter les problèmes NP comme des calculs "en parallèle" (comme dans un circuit électrique), nous n'avons pas besoin "d'alimenter tous les circuits" pour arriver au résultat. Les problème NP sont des "calculs en OU".
J'ai dit plus haut que les problèmes P ou E sont des "calculs en ET". D'où la nécéssité d'effectuer TOUS les calculs pour arriver au résultat.
Les mathématiciens, car il existe de nombreuses méthodes (appelées heuristiques) pour trouver les meilleurs chemins, ont conjecturé qu'un problème NP ("calcul en OU") n'est pas aussi complexe qu'un problème E ("calcul en ET"). ET que donc, on pouvait réduire les problèmes NP à des problèmes P ("calculs en ET") beaucoup plus simples que le problème E ("calcul en ET") équivalent.
Mon idée est que pour un algorithme donné, il existe un seul "calcul en ET" et que celui-ci est nécéssairement le problème E d'origine. Je dirais donc que NP n'est pas inclus dans P mais qu'au contraire, NP est inclus dans E.
Je pense que le meilleur moyen de résoudre un problème NP est donc d'utiliser ces heuristiques ou des algorithmes non déterministes comme par exemple les algorithmes génétiques.
Car il est vrai qu'un problème NP se distingue d'un problème E, par la possibilité de "sauter" des étapes du calcul, mais je suis convaincu qu'il n'existe pas de "formule magique" pour effectuer ce choix, on peut simplement éviter de faire de "mauvais choix" (heuristiques), ou expérimenter des échantillons prometteurs de choix (algo génétique).
J'ai bien conscience qu'il s'agit d'un avis tranché, sans aucun vrai argument scientifique ou mathématique. J'essayerai d'étayer cette idée plus tard avec, si je peux, des arguments plus rigoureux ou à défaut, par d'autres images peut-être plus convaincantes.
Une dernière précision sur P = NP : on peut se poser la question de savoir si cette conjecture est démontrable (ou réfutable). Autrement dit, il y a trois réponses possibles à la question P = NP ?
1- Vrai
2- Faux
3- Indémontrable
J'ai dis que je pensais que la réponse était Faux, mais je dois avouer que la troisième solution est tentante : Cela pourrait signifier soit une limite dans les outils mathématiques à notre portée (3A), soit que la question n'a pas de sens dans l'absolu (3B).
En résumé, je pencherais pour la solution 2 ou - dans une moindre mesure - la solution 3B.
Et vous, qu'en pensez-vous ? Quelle solution vous semble la plus plausible ?
PS : Si j'ai commis des erreurs dans cet article, je vous prie de m'en excuser, je n'aime pas trop me documenter pour écrire, mon but n'était pas de faire une "leçon" sur la théorie de la complexité. N'hésitez pas à apporter des corrections si nécéssaire.
Nous avions conclut que ces deux opérations appartiennent à l'ensemble P, qui représente l'ensemble des calculs déterministes à temps polynomial.
Dans la conjecture P = NP, l'ensemble NP représente les calculs non déterministes à temps polynomial. Mais avant de revenir sur cet ensemble plus en détail, il nous faut voir une dernière notion.
Avant, je dois préciser que certains passages peuvent contenir des erreurs pour deux raisons : d'une part, je ne suis pas un spécialiste de la théorie de la complexité et encore moins du problème P = NP. D'autre part, je présenterai à certains endroits mon point de vue, qui là encore peut contenir des erreurs ou même sembler simpliste aux spécialistes, vous voilà prévenus...
Les calculs à temps exponentiel
Imaginons que l'on souhaite connaître le nombre d'ancêtres A que nous avons, pour une génération N, par exemple :
A(1) = 2 (parents)
A(2) = 4 (grands parents)
A(3) = 8 (arrière grands parents)
...
A(N) = 2^N
Pour calculer A(N), il nous faut multiplier le résultat précédent A(N-1) par deux. En prenant comme opération unitaire la multiplication, on a donc un calcul à temps exponentiel, c'est à dire du type :
T(calcul exponentiel) = K^N
Où K est un nombre fixé (2 dans le cas du calcul des ancêtres) et N le nombre de données (dans notre exemple, le nombre de générations)
Un point fréquent dans les calculs à temps exponentiels est qu'ils sont récursifs : pour calculer A(N), on doit calculer A(N-1). Le résultat final n'est possible qu'en faisant tous les calculs
Mon point de vue : On peut se représenter le calcul à temps polynomial ou exponentiel comme une série de calculs à effectuer dans l'ordre : les calculs sont "branchés" en série, un peu comme des composants d'un circuit électrique. Tous les "circuits sont nécéssaires pour alimenter" le résultat. Les problèmes P ou E (voir plus bas) sont des "calculs en ET".
Nous pouvons maintenant définir l'ensemble E, comme étant l'ensemble des calculs à temps exponentiel. Mais quel rapport avec P = NP ? En quoi cela peut-il nous aider à définir l'ensemble NP ?
Calculs non déterministes à temps polynomial
Que signifie un calcul "non déterministe" ? En gros, que l'algorithme doit effectuer un certain nombre de calculs indépendants les uns des autres et qu'en fonction du "choix" qu'il fera, il pourra mettre moins de temps que nécéssaire, s'il avait dû tous les calculer, ou s'il les avait calculé dans un "ordre déterministe".
Pour cette raison, on dit souvent que les problèmes de la classe NP sont des problèmes de "décision".
On observe plusieurs propriétés importantes des problèmes de la classe NP :
- On peut calculer un problème NP avec un algorithme à temps exponentiel
- On peut vérifier le calcul d'un problème NP avec un algorithme à temps polynomial
On voit qu'en terme d'efficacité, les problèmes NP semblent se situer "entre" les problèmes P et E.
Autre point important : un problème P fait également partie de la classe NP. En termes ensembliste, on dira que l'ensemble P est inclus dans l'ensemble NP.
En mathématique, pour que deux ensembles (P et NP) soient égaux, il faut (et il suffit) qu'ils soient inclus l'un dans l'autre. Nous savons déjà que P est inclus dans NP. Toute la question de l'hypothèse P = NP est en fait de savoir si la réciproque est vraie : En fait la question n'est pas "P est-il égal à NP ?", mais plus précisément "NP est-il inclus dans P ?", autrement dit :
Pour chaque problème NP, existe-il un algorithme déterministe à temps polynomial capable de le résoudre ?
Généralement, les problèmes mathématiques commençant par "Pour chaque...existe t'il..." sont les plus difficiles à résoudre , car il faut démontrer l'existence d'un tel algorithme pour chaque problème, mais comment peut-on étudier en même temps TOUS les problèmes de type NP ? (Une blague de mathématicien serait de dire qu'on se trouve en face d'un problème à temps exponentiel...)
En fait, dans les années 60, un mathématicien américain du nom de Stephen Cook a découvert qu'on pouvait étudier tous les problèmes d'une classe, en étudiant uniquement "les plus difficiles" de cette classe : En résumé, "qui peut le plus, peut le moins". On appelle ces problèmes des problèmes complets.
Un problème NP-Complet : le problème du voyageur
Imaginons qu'un touriste veuille visiter N villes. Il souhaite effectuer le trajet le plus court possible, ou plus précisément, plus court qu'une certaine distance autorisée, qu'on appelera D, tout en passant par toutes les villes.
Pour résoudre ce calcul il faudrait à priori calculer toutes les combinaisons possibles de trajets, soit (N-1)! et sélectionner uniquement celles inférieures à D, par exemple :
Pour deux villes (N=2), il y a 1 seul trajet possible (T=1), donc une seule distance à calculer.
N = 3, T = 2
N = 4, T = 6
N = 5, T = 24
...
N = k, T = (k-1)! = (k-1) * (k-2) * ... * 1
On retrouve un peu le même schéma que pour le calcul des ancêtres (à temps exponentiel) : une série de multiplications, on peut donc à priori classer cet algorithme dans l'ensemble E.
Cependant, on peut vérifier si notre solution est correcte en beaucoup moins de temps : en faisant la somme des distances des trajets parcourus, on obtient une distance qui doit nécéssairement être inférieure à D. L'algorithme de vérification appartient à la classe P, car le temps de calcul est proportionnel au nombre de villes.
Ces deux éléments (calcul dans E et vérification dans P) suffisent à classer notre problème dans la catégorie NP.
En plus de cela (la démonstration m'est inconnue) ce problème est un problème "NP difficile", un problème NP-Complet. On peut reformuler la conjecture P = NP comme cela :
Si on parvient à trouver un algorithme déterministe à temps polynomial pour résoudre le problème du voyageur, alors on pourra le faire pour n'importe quel problème NP. La classe NP sera alors réduite à la classe P.
Le problème, c'est que personne n'a encore trouvé d'algorithme déterministe à temps polynomial pour aucun problème NP-Complet, donc pour l'instant, force est de constater que P n'est pas égal à NP !
Mon point de vue : P n'est pas égal à NP
Comme je l'ai dit dans la première partie de cet article, je ne suis pas un spécialiste, pourtant, en lisant divers articles sur le problème P = NP, dont l'excellent livre "les énigmes mathématiques du 3ème millénaire", je me suis mis à rêver d'une légitimité pour donner ma conception de ce problème... Voici mon idée, peut-être naïve ou stupide, mais c'est une idée...
Les problèmes NP consistent à effectuer plusieurs calculs, qui sont à priori pas tous nécéssaires, pour les résoudre : Dans le problème du voyageur, "si on a de la chance", on peut tomber sur le plus court trajet du premier coup, pas besoin de tous les calculer.
On peut se représenter les problèmes NP comme des calculs "en parallèle" (comme dans un circuit électrique), nous n'avons pas besoin "d'alimenter tous les circuits" pour arriver au résultat. Les problème NP sont des "calculs en OU".
J'ai dit plus haut que les problèmes P ou E sont des "calculs en ET". D'où la nécéssité d'effectuer TOUS les calculs pour arriver au résultat.
Les mathématiciens, car il existe de nombreuses méthodes (appelées heuristiques) pour trouver les meilleurs chemins, ont conjecturé qu'un problème NP ("calcul en OU") n'est pas aussi complexe qu'un problème E ("calcul en ET"). ET que donc, on pouvait réduire les problèmes NP à des problèmes P ("calculs en ET") beaucoup plus simples que le problème E ("calcul en ET") équivalent.
Mon idée est que pour un algorithme donné, il existe un seul "calcul en ET" et que celui-ci est nécéssairement le problème E d'origine. Je dirais donc que NP n'est pas inclus dans P mais qu'au contraire, NP est inclus dans E.
Je pense que le meilleur moyen de résoudre un problème NP est donc d'utiliser ces heuristiques ou des algorithmes non déterministes comme par exemple les algorithmes génétiques.
Car il est vrai qu'un problème NP se distingue d'un problème E, par la possibilité de "sauter" des étapes du calcul, mais je suis convaincu qu'il n'existe pas de "formule magique" pour effectuer ce choix, on peut simplement éviter de faire de "mauvais choix" (heuristiques), ou expérimenter des échantillons prometteurs de choix (algo génétique).
J'ai bien conscience qu'il s'agit d'un avis tranché, sans aucun vrai argument scientifique ou mathématique. J'essayerai d'étayer cette idée plus tard avec, si je peux, des arguments plus rigoureux ou à défaut, par d'autres images peut-être plus convaincantes.
Une dernière précision sur P = NP : on peut se poser la question de savoir si cette conjecture est démontrable (ou réfutable). Autrement dit, il y a trois réponses possibles à la question P = NP ?
1- Vrai
2- Faux
3- Indémontrable
J'ai dis que je pensais que la réponse était Faux, mais je dois avouer que la troisième solution est tentante : Cela pourrait signifier soit une limite dans les outils mathématiques à notre portée (3A), soit que la question n'a pas de sens dans l'absolu (3B).
En résumé, je pencherais pour la solution 2 ou - dans une moindre mesure - la solution 3B.
Et vous, qu'en pensez-vous ? Quelle solution vous semble la plus plausible ?
PS : Si j'ai commis des erreurs dans cet article, je vous prie de m'en excuser, je n'aime pas trop me documenter pour écrire, mon but n'était pas de faire une "leçon" sur la théorie de la complexité. N'hésitez pas à apporter des corrections si nécéssaire.
vendredi 25 janvier 2008
P = NP : problème ou illusion ? (partie 2)
Dans la première partie nous avons calculé la complexité de l'addition scolaire, dans le cas d'une addition à N chiffres, on a vu que l'addition scolaire était un calcul à temps linéaire, c'est à dire que le temps de calcul est proportionnel à N.
Calculons maintenant la complexité de la multiplication scolaire à N chiffres. Pour cela, nous allons prendre comme unité de temps, l'opération AxB, où A et B sont des nombres à un seul chiffre, donc :
T(AxB) = 1
Si on note A(N) et B(N) des nombres à N chiffres, calculer T(A(N)xB(N)) revient à calculer combien de multiplications "unitaires" (chiffre à chiffre) il faut réaliser pour calculer A(N)xB(N) avec la méthode scolaire.
Pour N = 2, par exemple, avec A(2) = 12 et B(2) = 34
12 * 34 = 2*4 + 10*(4*1) + 10*( 3*2 + 10*(3*1) )
Comme nous sommes en base 10, l'opération X + 10*Y revient à accoler les chiffres X et Y, en écrivant le nombre "YX", cette opération ne sera pas comptabilisé dans le calcul de la ocmplexité, on a donc :
T(A(2)xB(2)) = 4
De manière générale, pour multiplier deux nombres à N chiffres, il faudra multiplier deux à deux chaque chiffre de l'un avec ceux de l'autre, on obtient donc :
T(A(N)xB(N)) = N²
On en déduit que la multiplication scolaire est un calcul à temps quadratique : Le temps de calcul nécéssaire dépend du carré du nombre de chiffres.
De la même manière, on peut calculer le temps de calcul de n'importe quelle opération ou algorithme.
Les calculs comme l'addition ou la multiplication sont dits à temps "polynomial", car le temps dépend d'une fonction polynomiale de N (le nombre de données), c'est à dire :
T(calcul polynomial) = somme (a(k)*N^k) pour k entier
On peut donc classer l'addition et la multiplication (et un grand nombre d'autres calculs) dans l'ensemble des calculs à temps polynomiaux, on appelle cet ensemble P. (le fameux P de P = NP)
Plus précisément, l'ensemble P est appellé "Ensemble des calculs déterministes à temps polynomial", c'est à dire l'ensemble des calculs qui ne font pas appel à des fonctions aléatoires (comme l'addition ou la multiplication)
On devine donc que l'ensemble NP est tout simplement "L'Ensemble des calculs non déterministes à temps polynomial" (et non comme on le croit parfois, "L'ensemble des calculs à temps non polynomial)
Voilà pour la base... Dans la prochaine partie, nous verrons un troisième ensemble et je tenterai de donner une explication concrète du problème P = NP.
Calculons maintenant la complexité de la multiplication scolaire à N chiffres. Pour cela, nous allons prendre comme unité de temps, l'opération AxB, où A et B sont des nombres à un seul chiffre, donc :
T(AxB) = 1
Si on note A(N) et B(N) des nombres à N chiffres, calculer T(A(N)xB(N)) revient à calculer combien de multiplications "unitaires" (chiffre à chiffre) il faut réaliser pour calculer A(N)xB(N) avec la méthode scolaire.
Pour N = 2, par exemple, avec A(2) = 12 et B(2) = 34
12 * 34 = 2*4 + 10*(4*1) + 10*( 3*2 + 10*(3*1) )
Comme nous sommes en base 10, l'opération X + 10*Y revient à accoler les chiffres X et Y, en écrivant le nombre "YX", cette opération ne sera pas comptabilisé dans le calcul de la ocmplexité, on a donc :
T(A(2)xB(2)) = 4
De manière générale, pour multiplier deux nombres à N chiffres, il faudra multiplier deux à deux chaque chiffre de l'un avec ceux de l'autre, on obtient donc :
T(A(N)xB(N)) = N²
On en déduit que la multiplication scolaire est un calcul à temps quadratique : Le temps de calcul nécéssaire dépend du carré du nombre de chiffres.
De la même manière, on peut calculer le temps de calcul de n'importe quelle opération ou algorithme.
Les calculs comme l'addition ou la multiplication sont dits à temps "polynomial", car le temps dépend d'une fonction polynomiale de N (le nombre de données), c'est à dire :
T(calcul polynomial) = somme (a(k)*N^k) pour k entier
On peut donc classer l'addition et la multiplication (et un grand nombre d'autres calculs) dans l'ensemble des calculs à temps polynomiaux, on appelle cet ensemble P. (le fameux P de P = NP)
Plus précisément, l'ensemble P est appellé "Ensemble des calculs déterministes à temps polynomial", c'est à dire l'ensemble des calculs qui ne font pas appel à des fonctions aléatoires (comme l'addition ou la multiplication)
On devine donc que l'ensemble NP est tout simplement "L'Ensemble des calculs non déterministes à temps polynomial" (et non comme on le croit parfois, "L'ensemble des calculs à temps non polynomial)
Voilà pour la base... Dans la prochaine partie, nous verrons un troisième ensemble et je tenterai de donner une explication concrète du problème P = NP.
A suivre...
dimanche 13 janvier 2008
Comment faire rire un ordinateur ?
QUand je n'ai rien à faire, j'aime me ballader sur le site de l'université de Cornell www.arxiv.org qui publie une nombre incroyable d'articles scientifiques dans tous les domaines.
L'autre jour, je suis tombé sur un vieil article (1994) écrit par un chercheur russe I.M. Suslov,, l'article était intitulé "Can a computer laugh ?" suivi d'une deuxième article "How to realize a sense of humour in computers ?"
J'ai d'abord pensé à un gros canular, mais après avoir lu quelques paragraphes, je me suis très vite rendu compte du sérieux de cet article et surtout de sa pertinence : il semble bien que l'humour ait une explication tout à fait rationnelle, l'humour serait de plus indispensable au développement de l'intelligence, y compris chez les ordinateurs !
Pour ceux qui sont intéressés, voici le lien vers ces différents articles : http://arxiv.org/find/all/1/all:+humour/0/1/0/all/0/1
Pour les plus fainéants - ou les moins anglophiles - je vais tenter de résumer l'idée de départ de Monsieur Suslov. (J'avoue que je n'ai pas eu le courage de lire l'article en entier, car la suite devient plus technique...)
Soit une phrase, composée de n mots que l'on notera A(1),A(2),...,A(n).
Chaque mot est associé à un tableau de m images (ou sens) que l'on notera B(n,1), ...,B(n,m).
On dira que le mot n de la phrase possède m(n) sens possibles, B(i,j) représente le j-ème sens du i-ème mot.
Comprendre une phrase "correctement" reviens à trouver la bonne "trajectoire", c'est à dire la suite k(n) telle que la suite B(n,k(n)) représente la suite d'images qui a le "plus de sens".
Lorsque nous essayons de comprendre une phrase, notre inconscient analyse différentes trajectoires possibles et détermine la trajectoire qui semble avoir le plus de sens.
Pour cela, notre cerveau procède par étape, Suslov nous suggère l'algorithme suivant :
Suslov interprète l'humour comme le dysfonctionnement qui arrive, lorsque l'esprit arrive dans une impasse au niveau du choix des images (le sens de la phrase nous apparaît alors comme absurde)
Plus précisément, on peut avoir sélectionné au i-ème mot l'image qui nous a semble la plus "sensée" et se rendre compte au i+1-ème mot qu'on ne peut pas choisir une image sensée en rapport avec les images précédemment choisies.
Dans ce cas, le rire permettrait de remettre à zéro le processus de compréhension et permettrait à l'esprit de revenir en arrière pour choisir une autre image du ou des mots précédents.
Je pense qu'il s'agit là d'une très bonne interprétation du rire. Cette approche a en plus le mérite de fournir un modèle simple de compréhension du langage.
Pour terminer, voici une petite blague pour illustrer ce principe :
Au restaurant, le garçon demande au client:
- Comment avez-vous trouvé le beefsteak?
- Tout à fait par hasard, en soulevant une frite!
Je vous laisse le soin d'analyser cette blague pour y déceler le mécanisme suggéré par Suslov.
Une dernière chose : j'ai écrit cet article car j'ai été très intéressé par l'idée de Monsieur Suslov, j'ai tenté ici de résumer une partie de son article telle que je l'ai compris, mais le raisonnement de ce chercheur est bien sûr plus profond et plus détaillé. Il identifie par exemple plusieurs types d'humours. J'ai décrit ici uniquement l'humour basé sur un double sens mais il y a bien d'autres variantes qui permettent de couvrir l'ensemble du "sens de l'humour".
Il semble également que Suslov étende son raisonnement à d'autres sentiments humains, mais je n'ai pas trouvé d'articles sur le sujet.
En attendant, riez bien, c'est important pour la santé !
L'autre jour, je suis tombé sur un vieil article (1994) écrit par un chercheur russe I.M. Suslov,, l'article était intitulé "Can a computer laugh ?" suivi d'une deuxième article "How to realize a sense of humour in computers ?"
J'ai d'abord pensé à un gros canular, mais après avoir lu quelques paragraphes, je me suis très vite rendu compte du sérieux de cet article et surtout de sa pertinence : il semble bien que l'humour ait une explication tout à fait rationnelle, l'humour serait de plus indispensable au développement de l'intelligence, y compris chez les ordinateurs !
Pour ceux qui sont intéressés, voici le lien vers ces différents articles : http://arxiv.org/find/all/1/all:+humour/0/1/0/all/0/1
Pour les plus fainéants - ou les moins anglophiles - je vais tenter de résumer l'idée de départ de Monsieur Suslov. (J'avoue que je n'ai pas eu le courage de lire l'article en entier, car la suite devient plus technique...)
Soit une phrase, composée de n mots que l'on notera A(1),A(2),...,A(n).
Chaque mot est associé à un tableau de m images (ou sens) que l'on notera B(n,1), ...,B(n,m).
On dira que le mot n de la phrase possède m(n) sens possibles, B(i,j) représente le j-ème sens du i-ème mot.
Comprendre une phrase "correctement" reviens à trouver la bonne "trajectoire", c'est à dire la suite k(n) telle que la suite B(n,k(n)) représente la suite d'images qui a le "plus de sens".
Lorsque nous essayons de comprendre une phrase, notre inconscient analyse différentes trajectoires possibles et détermine la trajectoire qui semble avoir le plus de sens.
Pour cela, notre cerveau procède par étape, Suslov nous suggère l'algorithme suivant :
- Notre conscience lit le premier mot A(1)
- Notre inconscient fait la liste des images B(1)
- Notre conscience lit le mot suivant A(i)
- Notre inconscient fait la liste des B(i) images de ce mot
- Notre inconscient met en mémoire les combinaisons d'images entre B(i-1) et B(i) les plus probables (en réalité ce choix est fait en observant toutes les combinaisons précédentes)
- La combinaison la plus probable est renvoyée à notre conscience
- Retour à l'étape 3
Suslov interprète l'humour comme le dysfonctionnement qui arrive, lorsque l'esprit arrive dans une impasse au niveau du choix des images (le sens de la phrase nous apparaît alors comme absurde)
Plus précisément, on peut avoir sélectionné au i-ème mot l'image qui nous a semble la plus "sensée" et se rendre compte au i+1-ème mot qu'on ne peut pas choisir une image sensée en rapport avec les images précédemment choisies.
Dans ce cas, le rire permettrait de remettre à zéro le processus de compréhension et permettrait à l'esprit de revenir en arrière pour choisir une autre image du ou des mots précédents.
Je pense qu'il s'agit là d'une très bonne interprétation du rire. Cette approche a en plus le mérite de fournir un modèle simple de compréhension du langage.
Pour terminer, voici une petite blague pour illustrer ce principe :
Au restaurant, le garçon demande au client:
- Comment avez-vous trouvé le beefsteak?
- Tout à fait par hasard, en soulevant une frite!
Je vous laisse le soin d'analyser cette blague pour y déceler le mécanisme suggéré par Suslov.
Une dernière chose : j'ai écrit cet article car j'ai été très intéressé par l'idée de Monsieur Suslov, j'ai tenté ici de résumer une partie de son article telle que je l'ai compris, mais le raisonnement de ce chercheur est bien sûr plus profond et plus détaillé. Il identifie par exemple plusieurs types d'humours. J'ai décrit ici uniquement l'humour basé sur un double sens mais il y a bien d'autres variantes qui permettent de couvrir l'ensemble du "sens de l'humour".
Il semble également que Suslov étende son raisonnement à d'autres sentiments humains, mais je n'ai pas trouvé d'articles sur le sujet.
En attendant, riez bien, c'est important pour la santé !
Inscription à :
Articles (Atom)