Re: Temps polynomial

[Invité]

Oui, et d'autant plus parce que, si je comprends bien, toutes les opérations mathématiques peuvent être formalisées par un algorithme. Dire qu'un problème est théoriquement résoluble sur une machine de Turing revient donc à dire qu'il est résoluble mathématiquement (?)

En gros, oui. Plus précisément (et ce n'est pas évident du tout, donc c'est extraordinaire), il y a une correspondance entre les algorithmes informatiques et les démonstrations mathématiques : tout théorème mathématique (vu comme la conclusion d'une démonstration, donc d'une suite de propositions) peut être traduit en un algorithme sur une machine de Turing, et vice versa. C'est la correspondance de Curry-Howard. C'est pour cette raison que l'incomplétude de Gödel portant sur un système axiomatique correspond à un certain phénomène portant sur les algorithmes (l'indécidabilité du problème de l'arrêt).

Bon, je pense que je comprends pas trop mal, jusqu'à ce que tu abordes NP. Là, je suis largué.

Ce n'est quand-même pas évident si tu découvres le domaine. Il y a beaucoup de notions subtiles, impossibles à comprendre sur base des définitions seules. Il faut bosser des exemples, faire des exercices, prendre le temps de réfléchir, pour comprendre ces notions.

... est-ce que cette distinction vérifiable / résoluble est la même que celle entre la conjecture de Hilbert et sa reformulation par Turing (que je ne comprenais pas bien) ?

Non, ça n'a rien à voir à la base (même si on peut toujours faire des liens).

Mais, en somme, qu'est-ce qu'ajoute au raisonnement la machine non-déterministe ?

Pour simplifier, une machine non-déterministe peut traiter en temps polynomial des problèmes qui, sur une machine déterministe, sont traités en temps exponentiel. Ou plus simplement encore : une machine non-déterministe traite sous la forme d'un seul cas de figure un problème qui, sur une machine déterministe, doit se décomposer en plusieurs cas de figure.

Une machine non-déterministe fonctionne comme une armée de machines déterministes travaillant simultanément, chacune chargée de développer un cas de figure.

[Bergame]

En gros, oui. Plus précisément (et ce n'est pas évident du tout, donc c'est extraordinaire), il y a une correspondance entre les algorithmes informatiques et les démonstrations mathématiques : tout théorème mathématique (vu comme la conclusion d'une démonstration, donc d'une suite de propositions) peut être traduit en un algorithme sur une machine de Turing, et vice versa. C'est la correspondance de Curry-Howard. C'est pour cette raison que l'incomplétude de Gödel portant sur un système axiomatique correspond à un certain phénomène portant sur les algorithmes (l'indécidabilité du problème de l'arrêt).

Ok. Est-ce que j'ai raison de penser que cette correspondance est conséquente du fait que les "états" d'une machine de Turing (=d'un algorithme) correspondent aux opérateurs booléens à partir desquels on peut reconstituer les opérations de la logique du 1er ordre ?

Si non, voudrais-tu stp tenter d'expliquer (autant que possible ) en quoi c'est extraordinaire ?

Une machine non-déterministe fonctionne comme une armée de machines déterministes travaillant simultanément, chacune chargée de développer un cas de figure.

Ok. Bon, effectivement, je ne comprends pas bien la distinction vérifiable / résoluble, je vais continuer mes lectures.

Mais simplement, est-ce que je comprends bien en revanche si je comprends que les approximations à une machine non-déterministe sont aujourd'hui :
- L'"informatique distribuée" -càd en somme la mise en réseau ?
- Les GPU qui, si je comprends bien, sont en fait des processeurs à plusieurs centaines voire milliers de "coeurs" en parallèle (?), chacun pouvant prendre en charge des tâches assez simples ?

[Invité]

Est-ce que j'ai raison de penser que cette correspondance est conséquente du fait que les "états" d'une machine de Turing (=d'un algorithme) correspondent aux opérateurs booléens à partir desquels on peut reconstituer les opérations de la logique du 1er ordre ?

Les états d'une machine de Turing ne correspondent absolument pas à des opérateurs booléens. C'est beaucoup moins direct que ça. Par ailleurs, les opérateurs booléens ne suffisent pas pour reconstituer la logique du 1er ordre, mais c'est un autre sujet.

Si non, voudrais-tu stp tenter d'expliquer (autant que possible ) en quoi c'est extraordinaire ?

C'est extraordinaire parce que, a priori, les maths et l'informatique n'ont rien à voir. En maths, il est question de propositions à démontrer au sein d'un système axiomatique. En informatique, il est question d'algorithmes réalisant une certaine tâche ; il n'y est question nulle part de démonstration ni de vérité. Si la preuve que 1+2=3 correspond à un programme, que fait ce programme ?

Mais simplement, est-ce que je comprends bien en revanche si je comprends que les approximations à une machine non-déterministe sont aujourd'hui :
- L'"informatique distribuée" -càd en somme la mise en réseau ?
- Les GPU qui, si je comprends bien, sont en fait des processeurs à plusieurs centaines voire milliers de "coeurs" en parallèle (?), chacun pouvant prendre en charge des tâches assez simples ?

Je ne suis pas spécialiste, mais il me semble que rien de tout cela ne soit au niveau d'une machine de Turing non-déterministe. Jusqu'à présent, ce concept est surtout théoriquement utile pour réfléchir à propos des limites des machines déterministes, en fait.

[maraud]

Bergame,
je ne sais pas au juste le but que tu vises. Pour l'instant, je comprends que tu te questionnes sur le temps polynomial mis en rapport avec l'IA, ainsi que sur les algorithmes et leurs potentialités...

Le sujet de l'IA m'intéresse pour une raison d'actualité. J'essaye en effet de saisir l'ampleur du bouleversement que va provoquer l'IA dans la vie quotidienne et notamment dans le domaine militaire et sécuritaire en général.

En résumé: La Nature est Matière/Intelligence, sont "langage" est Géométrie, il est  traduit/transcrit en langage humain via une logique mathématique. Cette logique mathématique est le support de toute activité intelligente humaine: ce qui est inintelligible est soit inhumain, soit inintelligent. Dans ce registre l'être humain avance avec pour préalable que: " l'absence de la preuve n'est pas la preuve de l'absence".

A ce jour, j'en suis là: il y a dans la classe NP des problèmes qui peuvent encore être résolus en P et d'autres dont on ne sait pas très bien s'ils le sont. Pour ce faire on utilise des algorithmes plus complexes qui sont capables de vérifier les algorithmes avec lesquels on se propose de résoudre ces problèmes " mal évalués". Il en ressort, en dernier lieu, qu'il existe des cas de figure où même si les algo de contrôle et vérification nous disent que tel algo fonctionnera, il nous est impossible de le vérifier sans en faire l'expérience, or il est des tas d’expériences qui sont irréalisables parce que techniquement impossibles, dangereuses etc. Le problèmes de cet état de fait vient de ce que l'on peut exploiter ce type d'algo, mais alors en sachant que le résultat peut être expédient mais pas nécessairement optimal.
Dit autrement: il vient fatalement un moment où l'algorithme de vérification est à peine plus complexe que l'algo qu'il vérifie, jusqu'à perdre toute pertinence de contrôle.

voici un " amuse-bouche" sur la fonction " arrêt": https://pixees.fr/informatiquelycee/n_site/nsi_term_calcu.html

[Kercos]

Sur l' IA, une émission hier concernant la nouvelle start up française :
https://www.radiofrance.fr/franceculture/podcasts/soft-power/mistral-ai-la-licorne-francaise-de-l-intelligence-artificielle-5832374

[Kercos]

.... Cette logique mathématique est le support de toute activité intelligente humaine: ce qui est inintelligible est soit inhumain, soit inintelligent.

Dans le lien que j'ai mis sur ce prof de philo allemand, il dit que l' on peut comparer le concept d'inaccessibilité de l' être, "la chose en soi" etc ...à celui de la géométrie non euclidienne.
Un peu sur le même thème, certains historiens montrent une corrélation entre les systèmes monétaires et l'écriture : un transfert du sens -don- / sens-image vers l'abstraction quantité / son qui ne prennent de sens qu'apres une agglomération. Ces 2 processus ayant évolué simultanément.

[maraud]

Oui,l'activité humaine trouve ses limites dans l'homme qui se pense comme " mesure de toute chose". Toutefois, l'idée d'être et de chose en soi par exemple ne trouvent aucune correspondance dans la logique du monde humain, trop humain. Et pourtant on en parle.... C'est bien que l'homme " sent confusément quelque chose" ( comme Rantanplan). Perso, je parle de logique pure, d'une logique que nous pouvons exploiter dans une "dimension" qui nous est pas clairement donnée ( Platon parlait d'un " monde des idées" et de "simulacres" pour tout ce que l'on en tirait).

Cette " logique pure" je la trouve par exemple chez les mathématiciens de génie qui découvrent des vérités mathématiques avant d'en avoir une quelconque représentation. Je veux dire par là, qu'ils découvrent une chose avant qu'elle ne prenne corps dans une formulation mathématique. Cela suppose ( pour moi) que la formule mathématique est toujours une réduction de l'intuition première qui la fait maître en tant que " simulacre de l'idée pure".

Cela se vérifie par l'analogie qui fait qu'une pensée n'est jamais parfaitement exprimée en parole ( pensée à l'intérieur, parole à l'extérieur)

On comprend sans trop de peine que l'être n'est pas l'existent ( l'étant d'heidegger): l'être est logique pure et l'existent est un simulacre de cette idée pure ( il est ce qui est porté par autre chose: la matière, le verbe ....), comme l'information a besoin d'un support pour exister ( neurones, papier, ordi...)

[Bergame]

Le sujet de l'IA m'intéresse pour une raison d'actualité. J'essaye en effet de saisir l'ampleur du bouleversement que va provoquer l'IA dans la vie quotidienne et notamment dans le domaine militaire et sécuritaire en général.

Oui, voila, moi aussi. Enfin, pas forcément dans le domaine de la sécurité, mais évidemment, le phénomène est... intéressant, et ouvre à des questions assez vertigineuses. Pour l'instant, je lis, j'essaie de comprendre, je verrai ensuite ce que je compte/peux en faire.
Merci pour ton commentaire et le lien.

En passant : Je ne te "voyais" pas forcément intéressé par les questions militaires (?)

[maraud]

En passant : Je ne te "voyais" pas forcément intéressé par les questions militaires (?)

C'est hélas d'actualité!

Mon questionnement est le suivant: l'invention de l'arme à feu a, en son temps, bouleversé le paradigme militaire/sécuritaire.Partant, avec l'apparition de l'IA dans le domaine militaire, seront-ce les plus matheux qui détrôneront les plus riches/industrialisés ?

Les malfrats, qui ont toujours un temps d'avance sur les flics, vont-ils s'engouffrer dans la brèche? (imagine un trafic de drogues/armes opéré par des meutes de drones...?)

[alain]

Ou se trouverait donc la différence entre la notion de " idée pure " et celle de " logique pure " ?
Ma question a t' elle un sens logique ?

Je sens que l' inaccessible est sans cesse présent et impossible à conceptualiser.

( c' est juste une parenthese car je suis incapable de suivre et de comprendre ce qui est débatu sur ce fil ... c' est d'ailleurs peut être bien ce qui a suscité cette petite intervention ).

[maraud]

Inspirons-nous de Kant: imagine un triangle dans ton "espace mentale" ( comme pour un calcul mental), tu as alors un triangle générique qui se détache plus ou moins clairement sur un fond sans limites, c'est un triangle dans un plan. Ce triangle est un concept ( partiel, car aucune collection de triangles n'épuise, n'égale parfaitement le concept de triangle) et cet espace est absolu quand il n'y a rien dedans ( la page blanche...)

La logique pure est libre et sans objets: on collectionne les chiffres, avec ses chiffres on réalise une opération . Eh bien le fait de pouvoir réaliser cette opération découle de notre capacité à utiliser la logique pure mais elle est dans ce cas " logique pratique". Si je te dis que 2 et 2 égale 4 puis que 4 moins 2 égale 3, ton sens logique va protester! To entendement est donc régit par la logique pure.

Pour ce qui est de l'idée, c'est moins évident puisqu'on parle des idées avec des idées ( gros risque que par contiguïté ce que l'on décrit se confonde avec l'outil qui les décrit) : on a pu, logiquement, décomposer une idée en schèmes ( disons que ce sont les éléments constitutifs de l'idée, les briques en somme). Quand une idée nous vient ( quand elle veut...), c'est qu'elle a mûri sous une autre forme, non encore assemblée ( donc avant que la conscience ne puisse la saisir ( les schèmes pourraient être dits: inconscient...)
L'idée se construit sur de l'information, or aucune quantité ou qualité d'information n'épuise le concept d'idée, ce en quoi c'est une chose pure.

Dans ce domaine, le contraire de pur, c'est de mon point de vu, parfait : le carbone peut se durcir jusqu'à devenir diamant, et dans cette progression, le morceau de charbon devient un morceau de diamant " parfait". ( c'est un peu comme les probabilités, plus on lance les dès, moins les issues sont nombreuses)

[alain]

Inspirons-nous de Kant: imagine un triangle dans ton "espace mentale" ( comme pour un calcul mental), tu as alors un triangle générique qui se détache plus ou moins clairement sur un fond sans limites, c'est un triangle dans un plan. Ce triangle est un concept ( partiel, car aucune collection de triangles n'épuise, n'égale parfaitement le concept de triangle) et cet espace est absolu quand il n'y a rien dedans ( la page blanche...)

La logique pure est libre et sans objets: on collectionne les chiffres, avec ses chiffres on réalise une opération . Eh bien le fait de pouvoir réaliser cette opération découle de notre capacité à utiliser la logique pure mais elle est dans ce cas " logique pratique". Si je te dis que 2 et 2 égale 4 puis que 4 moins 2 égale 3, ton sens logique va protester! To entendement est donc régit par la logique pure.

Pour ce qui est de l'idée, c'est moins évident puisqu'on parle des idées avec des idées ( gros risque que par contiguïté ce que l'on décrit se confonde avec l'outil qui les décrit) : on a pu, logiquement, décomposer une idée en schèmes ( disons que ce sont les éléments constitutifs de l'idée, les briques en somme). Quand une idée nous vient ( quand elle veut...), c'est qu'elle a mûri sous une autre forme, non encore assemblée ( donc avant que la conscience ne puisse la saisir ( les schèmes pourraient être dits: inconscient...)
L'idée se construit sur de l'information, or aucune quantité ou qualité d'information n'épuise le concept d'idée, ce en quoi c'est une chose pure.

Dans ce domaine, le contraire de pur, c'est de mon point de vu, parfait : le carbone peut se durcir jusqu'à devenir diamant, et dans cette progression, le morceau de charbon devient un morceau de diamant " parfait".  ( c'est un peu comme les probabilités, plus on lance les dès, moins les issues sont nombreuses)

Merci de m' expliquer.
Je pense avoir à peu près compris.

[Kercos]

L'idée se construit sur de l'information, or aucune quantité ou qualité d'information n'épuise le concept d'idée, ce en quoi c'est une chose pure.

Si je reviens à l' idée du triangle. C'est un polygone ...et l' IA peut il "épuiser" le concept ? L'usage principal humain du triangle est lié au fait que c'est le seul polygone indéformable. L'importance de ce caractère sera t il pris en compte par l' IA ?

[maraud]

Kercos,
je n'ai aucune idée des limites de L'IA.

Les impossibilités qui paraissent évidentes sont liées aux limites physiques qu'offre la technologie: si on demande à un ordi de nous donner l'heure à la minute près, il pourra le faire sans peine, mais si on lui demande de nous dire l'heure exacte de manière exponentielle, il va bugger parce que le programme ne trouvera pas de solution avant que ces limites matérielles ne soient atteintes ( dans tout système, il y a de l'entropie). Tu me diras qu'un programme qui ne tient pas compte de ce genre de problème est "idiot", mais c'est pourtant bien ce qui nous pend au nez dans l'IA, puisque dans son ensemble, l'IA est une expérience dans laquelle tout n'est pas prévisible...

Les formes géométriques sont relativement pures, ce en quoi elles ont des potentialités très étendues.
Si on prend l'exemple du seul triangle, on sait qu'une de ses caractéristiques est " consommée" ( peut-être épuisée parce que parfaite ?) en ce que la somme de ses angles totalise 180°. Toutefois, il se posera encore la question de cette valeur sous un point de vu infinitésimal ...? Qu'est-ce qu'un degré parfait ? Qu'est-ce qu'un n-ième de degré parfait ? Etc. De manière fractale, un triangle est géométriquement " infini"...

[Kercos]

Toujours sur l' IA:
Jusqu'à présent on pouvait différencier la création par le vivant (la nature) de celle par l'homme, du fait que les "bruits" des créations humaines perturbent le signal principal et finissent par le détruire ....alors que les "bruits" induits par les créations naturelles sont réutilisées et participent à renforcer le signal et le rendent plus résilient.

[alain]

Je me souviens de l' horloge parlante de l' époque, au téléphone.
" Au quatrième top il sera exactement ... ".
En fait la seule façon de donner l' heure exacte c' est de convenir d' un point dans le temps : un signal.
Sinon c' est éternel puisqu' à chaque instant l' heure donnée à changé.

[maraud]

Kercos,
sauf erreur, je crois que nos neurones sont capables d'échanger des infos à l'électron près. Il me semble aussi que la photosynthèse met en action un processus si rapide qu'on ne peut le visionner/filmer. Apparemment, il n'y a pas de bruit...
Si on compare ça avec le facteur de bruit induit par la moindre de nos activité, c'est clair, y'a pas photo!

Dans l'ordre du bruit, il faut souligner la quantité folle d'ions positifs qu'on propulse dans notre environnement même le plus intime.

[Magni]

Effectivement, comme cela a été dit, le "temps polynomial" fait référence à l'efficacité d'un algorithme en fonction de la taille de ses données d'entrée.

Ce qui n'a pas été dit, c'est que dans ce contexte, "polynomial" signifie "efficace" et s'oppose à "exponentiel".

Pour un algorithme donné, lorsque les données d'entrée augmentent de X valeurs et que l'on doit effectuer un nombre de calculs supplémentaires pour trouver le résultat,
si le nombre de calculs supplémentaires est un polynôme de X (par exemple X^2), alors il est possible de trouver le résultat, c'est réalisable avec un ordinateur, et cela est considéré comme efficace.

Pour un algorithme donné, lorsque les données d'entrée augmentent de X valeurs et que l'on doit effectuer un nombre de calculs supplémentaires pour trouver le résultat,
si le nombre de calculs supplémentaires est un exponentiel de X (par exemple 2^X), alors il devient impossible de trouver le résultat car le nombre de calculs supplémentaires à effectuer devient rapidement insurmontable, même avec un ordinateur. Un tel algorithme est considéré comme inefficace.

[Magni]

∞^2 = ∞

2^∞ > ∞

[Bergame]

Je ne découvre que maintenant ta réponse, magni, mais elle est lumineuse. Merci.

En revanche, heu : 2^∞ > ∞ . Ca n'a pas de sens, ou bien ?

[Invité]

En revanche, heu : 2^∞ > ∞ . Ca n'a pas de sens, ou bien ?

Ça a du sens, mais ça n'a rien à voir avec le sujet de discussion...

[maraud]

Oui, ça a un sens: la confusion entre infini et indéfini!

Est infini ce qui est sans limitation, or 2 exposant l'infini est absurde car ce 2 ne serait alors pas inclus dans l'infini...
Il y a un seul infini possible car si l'on devait essayer de concevoir " deux infinis" on achopperait immédiatement sur le fait suivant: "deux infinis" supposeraient inévitablement qu'ils se limiteraient l'un l'autre, or l'infini est sans limitation aucune donc....

Il me semble que la notion d'infini n'a d'autre objet que de "contenir" la possibilité, et ce que l'on envisage logiquement, n'est alors que de l'indéfini, du pas encore défini.

[Vanleers]

En revanche, heu : 2^∞ > ∞ . Ca n'a pas de sens, ou bien ?

Cette inégalité signifie que le cardinal de l’ensemble des parties d’un ensemble infini est supérieur au cardinal de cet ensemble, comme l’a démontré Cantor.

https://fr.wikipedia.org/wiki/Cardinalit%C3%A9_(math%C3%A9matiques)

[Invité]

En revanche, heu : 2^∞ > ∞ . Ca n'a pas de sens, ou bien ?

Une illustration possible est la suivante : il y a une infinité de nombres naturels, il y a une infinité de nombres réels. Mais on peut démontrer qu'il y a plus de nombres réels que de nombres naturels. Par ailleurs, si ∞ désigne le nombre de nombres naturels, alors on peut démontrer que 2^∞ correspond au nombre de nombres réels. Il en découle que 2^∞ > ∞.

[Saint-Ex]

En revanche, heu : 2^∞ > ∞ . Ca n'a pas de sens, ou bien ?

Une illustration possible est la suivante : il y a une infinité de nombres naturels, il y a une infinité de nombres réels. Mais on peut démontrer qu'il y a plus de nombres réels que de nombres naturels. Par ailleurs, si ∞ désigne le nombre de nombres naturels, alors on peut démontrer que 2^∞ correspond au nombre de nombres réels. Il en découle que 2^∞ > ∞.

Et la signification de ∞ disparaît ...

[Invité]

Et la signification de ∞ disparaît ...

Elle se précise, plutôt. Les mathématiques ont donné aux concepts d'infini une caractérisation qui permet de les penser et de les manipuler conceptuellement. Mathématiquement, ce sont des infinis en acte.

[Contenu sponsorisé]