Re: Temps polynomial

par AntiSubjectiviste Dim 17 Mar 2024 - 16:14

Bergame a écrit: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).

Bergame a écrit: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.

Bergame a écrit:... 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).

Bergame a écrit: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.

par Bergame Dim 17 Mar 2024 - 16:51

AS a écrit: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 Temps polynomial - Page 2 2101236583

) en quoi c'est extraordinaire ?

AS a écrit: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 ?

par AntiSubjectiviste Dim 17 Mar 2024 - 19:38

Bergame a écrit: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.

Bergame a écrit: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 ?

Bergame a écrit: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.

par maraud Lun 18 Mar 2024 - 10:20

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

par Kercos Lun 18 Mar 2024 - 12:10

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

par Kercos Ven 22 Mar 2024 - 8:21

maraud a écrit:.... 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.

par maraud Ven 22 Mar 2024 - 10:15

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...)

par Bergame Sam 23 Mar 2024 - 10:21

maraud a écrit: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. Temps polynomial - Page 2 2101236583

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

par maraud Sam 23 Mar 2024 - 11:05

Bergame a écrit: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...?)

par alain Sam 23 Mar 2024 - 12:30

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 ).

par maraud Sam 23 Mar 2024 - 14:09

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)

par alain Sam 23 Mar 2024 - 22:39

maraud a écrit: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.

par Kercos Dim 24 Mar 2024 - 8:39

maraud a écrit:
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 ?

par maraud Dim 24 Mar 2024 - 10:26

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"...

par Kercos Dim 24 Mar 2024 - 11:40

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.

par alain Dim 24 Mar 2024 - 12:29

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é.

par maraud Dim 24 Mar 2024 - 12:52

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.

par Contenu sponsorisé