Le Deal du moment :
Cartes Pokémon 151 : où trouver le ...
Voir le deal

Temps polynomial

+3
AntiSubjectiviste
Saint-Ex
Bergame
7 participants

Page 1 sur 2 1, 2  Suivant

Aller en bas

Temps polynomial Empty Temps polynomial

Message par Bergame Jeu 22 Fév 2024 - 14:27

Il y a quelques matheux parmi nous. Est-ce que quelqu'un pourrait avoir la patience et la bonté de m'expliquer en termes simples ce qu'est le temps polynomial ?

_________________
...que vont charmant masques et bergamasques...
Bergame
Bergame
Persona
Persona

Nombre de messages : 5033
Date d'inscription : 03/09/2007

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par Saint-Ex Dim 25 Fév 2024 - 8:18

Bergame a écrit:Il y a quelques matheux parmi nous. Est-ce que quelqu'un pourrait avoir la patience et la bonté de m'expliquer en termes simples ce qu'est le temps polynomial ?

Je ne savais pas ce qu'était le temps polynomial. Alors ma curiosité a pris le dessus.

Je me suis d'abord penché sur la première leçon de mathématiques qui m'a semblé sérieuse sur la seule expression «polynomial».

Voilà ce qu'en dit un mathématicien qui a l'air de connaître son métier :



Mais si on manque d'exercice pour comprendre ce que nous dit ce mathématicien, alors on sera intéressé par la vulgarisation extrême mais exacte de ce qu'est en réalité une expression polynomiale.

Temps polynomial Captu223

Inutile de résoudre le problème posé par cette illustration. Il suffit de comprendre que les objets à emporter sont d'un nombre à découvrir et surtout de poids différents.

Chaque objet à emporter est un monôme mathématique, s'il y a plusieurs objet à emporter, l'ensemble de ses objets est un polynomial mathématique.

Le temps de calcul nécessaire pour résoudre le problème posé, c'est ça, le temps polynomial.

.

Ah, j'allais oublier, le temps polynomial est un élément d'importance en informatique ...

.
Saint-Ex
Saint-Ex
Digressi(f/ve)
Digressi(f/ve)

Nombre de messages : 1654
Date d'inscription : 01/07/2023

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par Bergame Lun 26 Fév 2024 - 11:00

Merci, Saint-Ex !
Oui, figure-toi que je cherche à comprendre comment fonctionnent les IA.... Temps polynomial 843891157

_________________
...que vont charmant masques et bergamasques...
Bergame
Bergame
Persona
Persona

Nombre de messages : 5033
Date d'inscription : 03/09/2007

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par AntiSubjectiviste Mar 5 Mar 2024 - 22:25

Bergame a écrit:Il y a quelques matheux parmi nous. Est-ce que quelqu'un pourrait avoir la patience et la bonté de m'expliquer en termes simples ce qu'est le temps polynomial ?
L'expression "temps polynomial" provient de la théorie de la complexité, qui est une branche de l'informatique théorique. Dans ce contexte, le mot "temps" désigne le nombre d'instructions qu'un algorithme doit exécuter pour produire son résultat.

Dans le cas d'un algorithme qui requiert un input de l'utilisateur, son temps d'exécution est une fonction f(n) de la taille n de cet input, et ce temps est dit polynomial si cette fonction est un polynôme en la variable n. (Un polynôme en la variable n est un calcul constitué de sommes ou de produits de constantes et de la variable n.) Quand c'est le cas, on dit que cet algorithme est de complexité polynomiale.

L'idée, c'est qu'un algorithme de complexité polynomiale est un algorithme dont le temps d'exécution n'augmente pas trop lorsque la taille de son input augmente; c'est donc un algorithme considéré comme "efficace" ou "performant", théoriquement parlant.

AntiSubjectiviste
Digressi(f/ve)
Digressi(f/ve)

Nombre de messages : 170
Date d'inscription : 16/07/2022

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par Bergame Mer 6 Mar 2024 - 9:49

Merci, AS. Temps polynomial 2101236583
Si je comprends un peu : Un algorithme se définissant entre autres choses par sa finitude et sa consommation en capacité de mémorisation, le but est de réaliser des algorithmes qui garantissent soit l'aboutissement à une solution correcte d'un problème défini, soit l'aboutissement à un état de non-solution, et ce dans le temps le plus court possible avec la consommation de capacité et d'énergie la plus économe possible (?)
Dans cette perspective, les problèmes de classe NP (non-déterministes en temps polynomial) sont des problèmes auxquels on ne peut parvenir à ce double aboutissement en temps polynomial.
Mais alors, cela signifie qu'il existe une mesure du temps polynomial ? Je veux dire : Il existe une durée maximale du temps polynomial au-delà de laquelle on estime : Ce problème X n'est pas déterministe en temps polynomial ?

_________________
...que vont charmant masques et bergamasques...
Bergame
Bergame
Persona
Persona

Nombre de messages : 5033
Date d'inscription : 03/09/2007

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par Kercos Mer 6 Mar 2024 - 11:54

AntiSubjectiviste a écrit:
L'idée, c'est qu'un algorithme de complexité polynomiale est un algorithme dont le temps d'exécution n'augmente pas trop lorsque la taille de son input augmente; .

Je dois me planter mais ça ressemble à la notion d'attracteur: le nombre suffisant d'entrées (variables et constantes) pour définir (cerner) correctement l'attracteur.

Kercos
Digressi(f/ve)
Digressi(f/ve)

Nombre de messages : 955
Date d'inscription : 25/04/2022

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par Saint-Ex Jeu 7 Mar 2024 - 2:49

.

À propos d'intelligence artificielle, Peggy Sastre m'informe d'une petite pensée (du jour bonjour) de la part d'un des ses collègues de travail, Yascha Mounk :

«Les nouveaux outils de génération d’images et de textes par IA sont bourrés de biais woke qui déforment la réalité.»

Qui est Yascha Mounk ? Voir ici :

https://www.yaschamounk.com

.
Saint-Ex
Saint-Ex
Digressi(f/ve)
Digressi(f/ve)

Nombre de messages : 1654
Date d'inscription : 01/07/2023

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par maraud Dim 10 Mar 2024 - 22:46

En électronique, le temps se mesure, se matérialise par une quantité de courant: lorsqu'un courant électrique remplit un réservoir, on compte une unité au moment précis où ce courant cesse de circuler parce que le réservoir en question est plein. C'est une "base-temps" ex: un condensateur talonné par une résistance , on a alors deux inconnues à ajouter aux polynômes 1 la valeur ohmique de la résistance 2) la capacité en micro/nano/pico farad du condensateur. Pour obtenir un temps donné, on consomme la quantité de courant nécessaire. En informatique, Il en va de même pour toute information exploitée, elle se matérialise par la consommation ou non de courant  ( grosso modo 1 correspond à une conso de courant sous 5 volts, 0 correspond à une absence de conso.) . On comprend aisément que les polynômes qu'il faut envisager pour l'IA ne sont pas du second degré... Temps polynomial 177519025

Il faut considérer que le temps dont il est question se présentera dans sa plus simple expression sous forme d'une équation à deux inconnues , donc déjà polynomial. ( on comprends aisément de quel niveau de complexité seront les algorithmes qui intégreront tous les sous-ensembles de comptages de temps dans les super-ordinateurs de l'IA. Au reste on a beau, sans cesse miniaturiser les composants, il y a hélas des seuils " physiologiques" indépassables pour nombre de composants qui requièrent toujours des tensions et intensités de courants importantes. D'où certaines astuces de délestages pour économiser l'énergie c'est pourquoi, enfin e l'imagine, on parle de "temps polynomial"...

_________________
La vie est belle!
maraud
maraud
Digressi(f/ve)
Digressi(f/ve)

Nombre de messages : 2334
Date d'inscription : 04/11/2012

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par Bergame Lun 11 Mar 2024 - 21:18

Salut maraud ! Merci. Temps polynomial 2101236583

une équation à deux inconnues , donc déjà polynomial.
C'est-à-dire qu'un polynôme, c'est une équation à plus d'une inconnue ?

_________________
...que vont charmant masques et bergamasques...
Bergame
Bergame
Persona
Persona

Nombre de messages : 5033
Date d'inscription : 03/09/2007

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par AntiSubjectiviste Lun 11 Mar 2024 - 23:23

Bergame a écrit:Merci, AS.  Temps polynomial 2101236583
Si je comprends un peu : Un algorithme se définissant entre autres choses par sa finitude et sa consommation en capacité de mémorisation, le but est de réaliser des algorithmes qui garantissent soit l'aboutissement à une solution correcte d'un problème défini, soit l'aboutissement à un état de non-solution, et ce dans le temps le plus court possible avec la consommation de capacité et d'énergie la plus économe possible (?)
Ce n'est pas ça du tout.
Pour comprendre les enjeux de la notion de "temps polynomial", il faut d'abord acquérir des notions préliminaires :
  • ce qu'est une machine de Turing déterministe (ainsi qu'une machine de Turing non déterministe),
  • ce qu'est un problème de décision,
  • ce qu'est un algorithme,
  • ce qu'est la complexité d'un algorithme (et la notion de "temps" associée).

Sur cette base, étant donné un problème, le but n'est pas d'en trouver un algorithme de résolution "rapide", mais plutôt d'en trouver un qui soit "peu complexe".

Bergame a écrit:Dans cette perspective, les problèmes de classe NP (non-déterministes en temps polynomial) sont des problèmes auxquels on ne peut parvenir à ce double aboutissement en temps polynomial.
Mais alors, cela signifie qu'il existe une mesure du temps polynomial ? Je veux dire : Il existe une durée maximale du temps polynomial au-delà de laquelle on estime : Ce problème X n'est pas déterministe en temps polynomial ?
Ces questions n'ont aucun sens, parce que tu n'es pas familier avec les notions préliminaires ci-dessus. Un problème de classe NP est résoluble en temps polynomial, mais sur une machine de Turing non déterministe. Cela équivaut (mais ce n'est pas évident) à dire qu'un problème est de classe NP si la validité d'une proposition de solution est vérifiable en temps polynomial sur une machine de Turing déterministe.

J'écris ces phrases pour te donner des éléments de recherche d'information, mais je ne les expliquerai pas (trop long).

Exemple basique : le sudoku. Étant donné une grille de sudoku lacunaire, il est facile de vérifier qu'une proposition de solution (c.-à-d. un remplissage particulier des cases vides par des chiffres) est valide ou pas. Mais il est beaucoup plus difficile de trouver la bonne solution. Pourtant, il y a un algorithme pour cela : celui qui passe en revue tous les remplissages possibles jusqu'à tomber sur le bon. C'est juste que cet algorithme, bien que simple dans son principe, est extrêmement laborieux : il y a énormément de remplissages possibles et tous les passer en revue s'avère peu efficace (ça pourrait prendre bien plus que des milliards d'années...). Eh bien le problème du sudoku est un exemple de problème NP (je passe des détails).


Bergame a écrit:Salut maraud ! Merci. Temps polynomial 2101236583

une équation à deux inconnues , donc déjà polynomial.
C'est-à-dire qu'un polynôme, c'est une équation à plus d'une inconnue ?
Non, ça n'a rien à voir, maraud raconte n'importe quoi. Voir Wikipédia.

AntiSubjectiviste
Digressi(f/ve)
Digressi(f/ve)

Nombre de messages : 170
Date d'inscription : 16/07/2022

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par maraud Mar 12 Mar 2024 - 13:22

Bergame a écrit:Salut maraud ! Merci. Temps polynomial 2101236583

une équation à deux inconnues , donc déjà polynomial.
C'est-à-dire qu'un polynôme, c'est une équation à plus d'une inconnue ?

Salut Bergame,

S'cuse, je suis allé trop vite!





Dernière édition par maraud le Mar 12 Mar 2024 - 18:22, édité 1 fois

_________________
La vie est belle!
maraud
maraud
Digressi(f/ve)
Digressi(f/ve)

Nombre de messages : 2334
Date d'inscription : 04/11/2012

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par maraud Mar 12 Mar 2024 - 14:26

AntiSubjectiviste,

mea culpa! Temps polynomial 1f60c


Dernière édition par maraud le Mar 12 Mar 2024 - 18:32, édité 1 fois

_________________
La vie est belle!
maraud
maraud
Digressi(f/ve)
Digressi(f/ve)

Nombre de messages : 2334
Date d'inscription : 04/11/2012

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par neopilina Mar 12 Mar 2024 - 14:32

Salut Maraud !

AntiSubjectiviste a écrit:Non, ça n'a rien à voir, maraud raconte n'importe quoi. Voir Wikipédia.

Toujours un peu " abrupt " le camarade A.S. : un matheux !

_________________
" Tout Étant produit par moi m'est donné (c'est son statut philosophique), a priori, et il est Mien (cogito, conscience de Soi, libéré du Poêle) ". " Savoir guérit, forge. Et détruit tout ce qui doit l'être ", ou, équivalents, " Tout l'Inadvertancier constitutif doit disparaître ", " Le progrès, c'est la liquidation du Sujet empirique, notoirement névrotique, par la connaissance ". " Il faut régresser et recommencer, en conscience ". Moi.
C'est à pas de colombes que les Déesses s'avancent.
neopilina
neopilina
Digressi(f/ve)
Digressi(f/ve)

Nombre de messages : 8364
Date d'inscription : 31/10/2009

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par maraud Mar 12 Mar 2024 - 18:13

Salut Neo,

oui, AS a été expéditif!

je comprends néanmoins sa réaction ( il a raison!)

Le fait est que s'agissant de programmation informatique, la forme polynomiale n'est pas un simple polynômes, mais la "forme" polynomiale appliquée à des algorithmes... autant dire que c'est nettement plus complexe.

_________________
La vie est belle!
maraud
maraud
Digressi(f/ve)
Digressi(f/ve)

Nombre de messages : 2334
Date d'inscription : 04/11/2012

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par Bergame Mar 12 Mar 2024 - 19:24

Je finis par me demander s'il n'y a pas un lien entre l'égotisme et l'ignorance. Ce qui serait assez logique, du reste : Quand on est persuadé d'être plus intelligent que les autres, on n'a pas besoin d'apprendre.
Souviens-toi les mots de Socrate, neopilina : Tout ce que je sais, c'est que je ne sais pas.

Ok, merci AS. Je vais bosser un peu les pistes que tu proposes, et je reviens.

_________________
...que vont charmant masques et bergamasques...
Bergame
Bergame
Persona
Persona

Nombre de messages : 5033
Date d'inscription : 03/09/2007

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par neopilina Mar 12 Mar 2024 - 19:58

Bergame a écrit:Souviens-toi les mots de Socrate, neopilina : Tout ce que je sais, c'est que je ne sais pas.

Ce qui, comme chacun sait, est une paraphrase de Métrodore de Chio placée dans la bouche de Socrate par Platon.

P.S. Il y a sur ce forum la meilleure édition française des fragments de Métrodore de Chio, du nectar, on aurait tort de se priver !

_________________
" Tout Étant produit par moi m'est donné (c'est son statut philosophique), a priori, et il est Mien (cogito, conscience de Soi, libéré du Poêle) ". " Savoir guérit, forge. Et détruit tout ce qui doit l'être ", ou, équivalents, " Tout l'Inadvertancier constitutif doit disparaître ", " Le progrès, c'est la liquidation du Sujet empirique, notoirement névrotique, par la connaissance ". " Il faut régresser et recommencer, en conscience ". Moi.
C'est à pas de colombes que les Déesses s'avancent.
neopilina
neopilina
Digressi(f/ve)
Digressi(f/ve)

Nombre de messages : 8364
Date d'inscription : 31/10/2009

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par AntiSubjectiviste Mar 12 Mar 2024 - 20:53

maraud a écrit:Le fait est que s'agissant de programmation informatique, la forme polynomiale n'est pas un simple polynômes
Si, c'est un simple polynôme.

AntiSubjectiviste
Digressi(f/ve)
Digressi(f/ve)

Nombre de messages : 170
Date d'inscription : 16/07/2022

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par Bergame Mer 13 Mar 2024 - 9:21

neopilina a écrit:Ce qui, comme chacun sait, est une paraphrase de Métrodore de Chio placée dans la bouche de Socrate par Platon.
Pas du tout ! Rolling Eyes Je t'ai d'ailleurs déjà expliqué la différence entre les deux.
Le pire, c'est que tu ne tiens absolument aucun compte de ce qu'on te dit.

_________________
...que vont charmant masques et bergamasques...
Bergame
Bergame
Persona
Persona

Nombre de messages : 5033
Date d'inscription : 03/09/2007

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par maraud Jeu 14 Mar 2024 - 11:16

Bon,après mon malencontreux " pet verbal".... Temps polynomial 1f61f

Pour comprendre ce qu'est le temps polynomial il suffit de le comparer au temps non-polynomial, en l’occurrence le temps exponentiel: est polynomial le temps selon lequel s'exécute un algorithme dont la complexité temporelle s'élève à un seul exposant.( n exposant k) ces algorithmes sont disponibles et plutôt répandus. On parle alors de problèmes de classe" P" ( P pour "polynomial" peut-être ?)

Vient ensuite la classe des problèmes  "EXPTIME": Les algorithmes nécessaires sont une complexification des algorithmes de classe P , la complexité des algo.de classe P se voit augmentée d'un exposant à l'échelle supérieure   ( 2^n^ k) Là on attaque la zone extrêmement chronophage puisque le nombre  d'opérations nécessaires augmentent exponentiellement...

Pour un nombre d'instructions nécessaires en classe P  (polynomiales) de n ^2 ( pour n=10, on a 100 opérations)on passe en classe EXPRIM à 2^n^2 (on a alors 10^30 opérations).

Vient enfin entre la classe P et La classe EXPRIM une zone " grise" dite classe NP . ( où l'on rencontre des problèmes par toujours bien identifiables, mais que l'on peut éventuellement "vérifier" ( on vérifie les solutions plus qu'on ne les trouve)


Le temps polynomial est donc le temps économiquement/écologiquement le moins dispendieux, mais pas suffisant pour les problèmes qui requièrent un nombre d'opérations vertigineux. D'où le critère de vitesse pour évaluer un composant/module/ordi. Il faut noter que la notion de "temps" est corrélée à celle "d'espace"...


Dernière édition par maraud le Ven 15 Mar 2024 - 7:43, édité 1 fois

_________________
La vie est belle!
maraud
maraud
Digressi(f/ve)
Digressi(f/ve)

Nombre de messages : 2334
Date d'inscription : 04/11/2012

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par maraud Jeu 14 Mar 2024 - 18:51

Bergame a écrit:Dans cette perspective, les problèmes de classe NP (non-déterministes en temps polynomial) sont des problèmes auxquels on ne peut parvenir à ce double aboutissement en temps polynomial.
Mais alors, cela signifie qu'il existe une mesure du temps polynomial ? Je veux dire : Il existe une durée maximale du temps polynomial au-delà de laquelle on estime : Ce problème X n'est pas déterministe en temps polynomial ?

C'est apparemment le problème à un "million de dollars..."

Pour le temps polynomial ( en classe P) sa valeur est fixée par ^ k ( n étant le volume de données à traiter.) Pour un n=10, on a 10^2= 100 opérations et pour un n= 1000, on a 1million d'opérations.

Dans les opérations polynomiales le temps est fixé dans la formulation et ne peut aller au delà de ce que permet k.

.........................................................................................................................................
Dans le temps exponentiel, il grandit en s'accélérant  avec ce que cela peut impliquer... N'oublions pas qu'en informatique la cause et l'effet peuvent quasiment se superposer/confondre puisqu'on travaille quasiment à la vitesse de la lumière et que la finesse avec laquelle on œuvre dans les labos peut approcher l'électron lui-même , c'est-à-dire que dans ce cas " le messager devient le message" un peu comme si l'information s'émancipait de son support. Attention: là c'est une pure divagation de ma part lol

......................................................................................................................................

C'est bien dans la zone "grise" NP que les matheux travaillent à "unifier" les classes P, NP et EXPTIME pour résoudre, entre-autres choses, le problème que tu évoques et il y a bien un million de dollars de Prix à la clef. C'est dire...

Certains pensent qu'il faut s'en tenir à trouver des algorithmes suffisamment simples pour rester polynomiaux mais suffisamment performant pour faire un travail optimal d'une complexité de classe EXPTIME  ( ça fait un peu " game changer/arme magique"...), d'autres travaillent à élaborer/trouver de nouvelles classes  (esprit cartésien) d'autres encore envisagent un ordinateur quantique ( rêveur, visionnaires...?)

_________________
La vie est belle!
maraud
maraud
Digressi(f/ve)
Digressi(f/ve)

Nombre de messages : 2334
Date d'inscription : 04/11/2012

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par Bergame Sam 16 Mar 2024 - 18:54

Merci Maraud, mais je crois que tu es un peu en avance sur moi.
Dans un premier temps au moins, je vais m'efforcer de suivre le programme de recherche que me propose AS.

Qu'est-ce qu'une machine de Turing ?

En première approximation, une machine de Turing est une machine à calculer qui décide elle-même des opérations à effectuer.
Plus précisément : C'est une machine composée d'un "ruban" sur lequel est inscrite une suite de chiffes 0 ou 1 ; et d'une "table de transition", qui traduit successivement les 0 et 1 (entrées) en "états internes" qui, en sortie, déterminent une action : Soit continuer à lire le ruban, soit revenir en arrière sur le ruban, soit arrêter.
La table de transition est donc un algorithme. Et les états internes (ai-je cru comprendre) correspondent aux opérateurs booléens.
Mais Turing a démontré qu'il existe des machines de Turing dont la table de transition peut être écrite sur le ruban : Des machines de Turing "universelles". Ainsi, les machines de Turing universelles sont "programmables" -théorème qui a conduit à la distinction entre hardware et software.
(Je laisse pour l'instant la question de savoir ce qu'est une machine de Turing "déterministe" et surtout "non-déterministe", pas clair pour l'instant)

Qu'est-ce que le problème de la décision ?
Au départ, une conjecture de Hilbert : Il existe un algorithme universel capable de résoudre tout problème mathématique qu'on lui poserait, c'est-à-dire capable de déterminer, pour n'importe quelle proposition mathématique, si elle est vraie ou fausse. Et Hilbert propose un programme de recherche particulièrement dense pour parvenir à la formulation de cet algorithme.

Turing aborde la question un peu autrement : Existe-t-il un algorithme capable de calculer la décidabilité d'une proposition mathématique ? (je ne suis pas sûr de bien voir la différence, d'ailleurs)
Pour y réponde, Turing commence par formaliser la notion d'"algorithme" : Une suite d'instructions est un algorithme ssi elle peut être retranscrite sur le ruban d'une machine de Turing universelle (en somme).
Ceci fait, Turing propose : L'algorithme de Hilbert doit être un algorithme d'une machine de Turing universelle capable, quelle que soit la conjecture mathématique qu'on lui présente, de s'arrêter sur 0 ou 1, c'est-à-dire de déterminer s'il existe une preuve en faveur de cette conjecture, ou non. En effet, si on présente d'un côté une conjecture, et de l'autre les preuves simples de cette conjecture, l'algorithme pourra décider si l'une de ces preuves est juste. Si aucune ne l'est, il pourra passer aux preuves moins simples. Et ainsi de suite, jusqu'à finir par trouver une preuve juste. Ce qui signifie que s'il n'existe aucune preuve de la conjecture, l'algorithme continuerait à tourner indéfiniment.
Turing eut l'idée de se demander s'il existait un (autre) algorithme universel capable de déterminer si un algorithme "termine" ou non. C'est le problème de "l'arrêt", dont il montre qu'il est équivalent au problème de la décision, et conclut à la négative.
Par conséquent, le problème de la décision dépasse l'algorithmie, et n'a pas (à ce jour) de solution.

Du reste, le lendemain même de la présentation de Hilbert (je crois), Gödel présente son premier théorème d'incomplétude : Toute théorie mathématique contient des vérités indémontrables, qui n'admettent pas de preuve et/ou qui ne sont pas réfutables. Ces théories sont dites "indécidables". Et par la suite, Gödel démontrera, second théorème, qu'il en sera toujours ainsi.

Qu'est-ce que la complexité d'un algorithme ?
Soit, donc, un problème mathématique, la question qui se pose est : Existe-t-il un algorithme capable de solutionner ce problème, ou de décider qu'il n'y a pas de solution, et ce, dans une durée... comment dire, raisonnable ? (je ne sais même pas trop comment formuler le problème, en fait).
Par exemple, il existe un algorithme relativement simple pour solutionner le problème des échecs, càd gagner à tous les coups quelle que soit la stratégie adverse. Mais c'est un algorithme qui, à chaque coup de l'adversaire, devrait jouer toutes les parties possibles afin de déterminer la stratégie gagnante -autrement dit, un algorithme qui prendrait énormément de temps à tourner avant de jouer. Apparemment, et si je comprends bien, le calcul du nombre d'états possibles est une fonction exponentielle.
Par exemple, tu as choisi l'exemple du sudoku, AS, je comprends maintenant pourquoi : Le nombre de remplissages possibles de la grille (de 9 cases sur 9) est (9x9)^9 soit approx. 10^17.  

Donc, un problème pour lequel il est possible de réaliser un algorithme capable de solutionner ce problème ou de décider qu'il n'y a pas de solution dans un temps... raisonnable est dit de complexité "polynomiale" (ou "facile"). Un problème pour lequel ce n'est pas possible est dit "non-polynomial" (ou "difficile").

Non, il y a un truc que je ne comprends pas entre "P/NP" et "facile/difficile".
Et je bute aussi, pour l'instant, sur la notion de temps que j'ai appelé "raisonnable" : Il y a une limite claire entre P et NP ?

_________________
...que vont charmant masques et bergamasques...
Bergame
Bergame
Persona
Persona

Nombre de messages : 5033
Date d'inscription : 03/09/2007

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par AntiSubjectiviste Dim 17 Mar 2024 - 12:09

Qu'est-ce qu'une machine de Turing ?
Une machine de Turing est un modèle théorique, idéal et simplifié, d'ordinateur programmé pour exécuter une certaine tâche. Sa table de transition indique ce qu'elle doit faire à chaque étape. L'intérêt du concept de machine de Turing est que l'on considère que tout algorithme (au sens intuitif du terme) peut-être traduit sous la forme d'une machine de Turing avec une table de transition appropriée. Autrement dit, on considère que l'on peut confondre "machine de Turing" et "algorithme" : c'est ce qu'affirme la thèse de Church-Turing, qui explique pourquoi on invoque les machines de Turing dès que l'on s'intéresse aux algorithmes.

Lorsqu'un problème est théoriquement résoluble sur une machine de Turing, cela signifie donc qu'il est algorithmiquement résoluble tout court, et donc qu'il l'est sur tout autre type d'ordinateur ou de machine (ce qui est une conséquence hyper puissante).

Il est vrai qu'il existe une machine de Turing "universelle", dont la table de transition permet de simuler toutes les machines de Turing possibles. Cette machine de Turing universelle est donc une sorte de fusion de toutes les machines en une seule, un super-émulateur. Mais c'est un autre sujet, qui n'est pas nécessaire pour comprendre la conjecture P=NP.

Par contre, la notion de machine de Turing non-déterministe est importante. Une machine de Turing "normale" (ou déterministe) passe, à chaque étape, d'un état à un seul autre état, en partant d'un état initial pour aboutir à un unique état final. L'ensemble de tous ses états intermédiaires se succèdent linéairement dans le temps, comme les maillons d'une chaîne. Une machine de Turing non-déterministe, par contre, peut passer d'un état à plusieurs autres états en parallèle, et ce à chaque étape de son exécution. C'est comme si une telle machine pouvait explorer différentes pistes simultanément. L'ensemble de ses états intermédiaires ne se succèdent pas linéairement, mais sous la forme d'un arbre de décision dont les branches se démultiplient constamment.

Il faut noter que les machines de Turing déterministes sont réalistes (et correspondent à nos ordinateurs réels). Les machines non-déterministes, par contre, sont des fictions théoriques : aucun ordinateur actuel ne fonctionne de façon non-déterministe.

Qu'est-ce qu'un problème de décision ?
(Ne pas confondre la notion de problème de décision avec ce qu'on appelle LE problème de l'arrêt (the halting problem, ou le problème de déterminer algorithmiquement si un algorithme va s'arrêter ou boucler indéfiniment). Ce dernier est intéressant en soi, mais n'est pas directement lié à la question P=NP. Ce qui suit développe la notion de problème de décision.)

Un problème de décision est simplement une question dont la réponse est oui/non. Un problème de décision est (algorithmiquement) résoluble s'il existe un algorithme qui aboutit à une réponse ("oui" ou "non"). En général, on s'intéresse aux problèmes portant sur un nombre donné en input. Exemple : "le nombre X est-il pair ?" où X est fourni par l'utilisateur. Voici un algorithme basique pour le résoudre :
  1. Demander à l'utilisateur d'entrer la valeur de X.
  2. Si le dernier chiffre de X est "0", "2", "4", "6" ou "8", alors répondre "oui", sinon, répondre "non".

Cet algorithme est ici présenté intuitivement, mais il est facile de le coder concrètement dans n'importe que langage de programmation, et théoriquement sous la forme d'une machine de Turing. Le problème de décider si un nombre donné est pair ou pas est donc algorithmiquement résoluble.

Dans cet exemple, on remarque même que même si X est un nombre très grand, l'algorithme n'examine que son dernier chiffre. La réponse sera donc toujours donné en une seule étape (la 2), et le temps d'exécution ne va même pas s'allonger même si la valeur de X augmente. On dira que cet algorithme est de complexité constante : son temps d'exécution est constant, peu importe la taille de l'input.

Qu'est-ce que la complexité d'un algorithme ?
Mais en général, le temps d'exécution augmente quand la taille de l'input augmente. Voici un autre problème de décision élémentaire : "le nombre X est-il premier ?" Voici un algorithme basique pour le résoudre :
  1. Demander à l'utilisateur d'entrer la valeur de X.
  2. Pour chaque nombre D entre 2 et X-1 :
    1. Diviser X par D.
    2. Si le résultat est un nombre entier, répondre "non" et s'arrêter. Sinon, continuer.


  3. Répondre "oui" et s'arrêter.

Cet algorithme examine si X possède un diviseur autre que 1 et lui-même; si oui, alors X n'est pas premier (réponse "non"), sinon il est premier (réponse "oui"). Ici, plus X est élevé, plus l'algorithme va devoir le diviser par les nombres qui lui sont inférieurs. Le temps d'exécution va donc augmenter avec la taille de l'input X.

La question est savoir comment le temps d'exécution augmente quand la taille de l'input augmente : augmente-t-il un peu, beaucoup, à la folie ? C'est là qu'interviennent les mathématiques : si la taille de l'input est notée n, alors le temps d'exécution sur une certaine machine de Turing (déterministe ou pas) est une fonction de n. Si cette fonction est polynomiale en n (par exemple, 2n+1, n², n³, ...), alors on dira que l'algorithme est de complexité polynomiale (sur cette machine de Turing). Si, par contre, cette fonction n'est pas polynomiale en n (par exemple, 2n, qui est une exponentielle en n), alors on dira que l'algorithme n'est pas de complexité polynomiale (sur cette machine de Turing).

Le point est que si le temps d'exécution est exponentiel en n (ce qui n'est pas polynomial en n), alors il devient vite déraisonnablement long lorsque la taille n de l'input augmente. Les algorithmes de sécurité informatique reposent là-dessus : les clés de cryptage peuvent théoriquement être crackées, mais ces clés sont des codes suffisamment longs pour que le temps de crackage soit, en pratique, déraisonnablement long pour un pirate (des millions d'années, même sur un ordinateur performant).

Enfin, lorsqu'un problème de décision est résoluble par un algorithme de complexité polynomiale sur une machine de Turing déterministe, alors on dit que ce problème est de classe P.

Avant de parler de la classe NP, il faut d'abord définir ce qu'est un problème de décision "vérifiable" (ce qui est moins exigeant que "résoluble"). Un problème de décision (portant sur un input X) est (algorithmiquement) vérifiable s'il existe un algorithme (sur une machine de Turing) qui détecte les valeurs de X qui entraînent la réponse "oui".

Pour parler de la classe NP, il faut faire intervenir les machines de Turing non-déterministes. Une machine de Turing non-déterministe est plus puissante qu'une version déterministe : elle est capable d'effectuer en parallèle plusieurs chaînes d'instructions, sans limite. (Rappelons toutefois que ces machines sont des fictions théoriques irréalisables en pratique.) Il y a toutefois un lien entre les deux : un problème résoluble en temps polynomial sur une machine non-déterministe, est vérifiable en temps polynomial sur une machine déterministe (et ça, c'est accessible via nos ordinateurs). De tels problèmes sont, par définition, de classe NP. La différence entre les classes P et NP est donc celle entre les notions de "résoluble" et de "vérifiable" (tous deux en temps polynomial).

Beaucoup de problèmes importants sont de classe NP. Par exemple : le problème de cracker un mot de passe. Si l'on possède le bon mot de passe, il est facile de vérifier que c'est le bon. Par contre, il est très difficile de trouver, à partir de rien, le bon mot de passe : si le mot de passe est long et complexe, il faudrait, dans l'état de nos connaissances, un temps déraisonnablement long pour le cracker.

Une des grandes questions du siècle est de savoir si P=NP, c'est-à-dire si les problèmes NP (vérifiables en temps polynomial) sont également P (résolubles en temps polynomial). Si oui, ça serait terrible : cela signifierait qu'il existe un algorithme de complexité polynomiale (donc, relativement "rapide") pour cracker n'importe quel mot de passe ou clé de cryptage ! Mais la communauté scientifique estime en majorité que P et NP sont différents, heureusement... même si on ne l'a pas encore prouvé.

AntiSubjectiviste
Digressi(f/ve)
Digressi(f/ve)

Nombre de messages : 170
Date d'inscription : 16/07/2022

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par Bergame Dim 17 Mar 2024 - 14:30

Merci AS ! Temps polynomial 4017359721

AntiSubjectiviste a écrit:Lorsqu'un problème est théoriquement résoluble sur une machine de Turing, cela signifie donc qu'il est algorithmiquement résoluble tout court, et donc qu'il l'est sur tout autre type d'ordinateur ou de machine -ce qui est une conséquence hyper puissante.
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 (?)

Par contre, la notion de machine de Turing non-déterministe est importante. Une machine de Turing "normale" (ou déterministe) passe, à chaque étape, d'un état à un seul autre état, en partant d'un état initial pour aboutir à un unique état final. L'ensemble de tous ses états intermédiaires se succèdent linéairement dans le temps, comme les maillons d'une chaîne. Une machine de Turing non-déterministe, par contre, peut passer d'un état à plusieurs autres états en parallèle, et ce à chaque étape de son exécution. C'est comme si une telle machine pouvait explorer différentes pistes simultanément. L'ensemble de ses états intermédiaires ne se succèdent pas linéairement, mais sous la forme d'un arbre de décision dont les branches se démultiplient constamment.
Ok...
Si théoriquement c'est possible, est-ce que cela n'implique pas un principe de pondération de la donnée en entrée ?
(je fais l'analogie avec ce que je comprends des réseaux de neurones formels, mais ça ne doit pas être ça... )

Qu'est-ce qu'un problème de décision ?
Etc.
Ok, très clair !

Qu'est-ce que la complexité d'un algorithme ?
[...]
La question est savoir comment le temps d'exécution augmente quand la taille de l'input augmente : augmente-t-il un peu, beaucoup, à la folie ? C'est là qu'interviennent les mathématiques : si la taille de l'input est notée n, alors le temps d'exécution sur une certaine machine de Turing (déterministe ou pas) est une fonction de n. Si cette fonction est polynomiale en n (par exemple, 2n+1, n², n³, ...), alors on dira que l'algorithme est de complexité polynomiale (sur cette machine de Turing). Si, par contre, cette fonction n'est pas polynomiale en n (par exemple, 2n, qui est une exponentielle en n), alors on dira que l'algorithme n'est pas de complexité polynomiale (sur cette machine de Turing).
Ok ! Voila donc ma "limite".
Au passage, j'apprends qu'il y a une balise BBCode pour écrire les exposants.

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

Je tente un truc. Quand tu dis :
AS a écrit:Avant de parler de la classe NP, il faut d'abord définir ce qu'est un problème de décision "vérifiable" (ce qui est moins exigeant que "résoluble"). Un problème de décision (portant sur un input X) est (algorithmiquement) vérifiable s'il existe un algorithme (sur une machine de Turing) qui détecte les valeurs de X qui entraînent la réponse "oui".
... 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) ? :
Bergame a écrit:Au départ, une conjecture de Hilbert : Il existe un algorithme universel capable de résoudre tout problème mathématique qu'on lui poserait, c'est-à-dire capable de déterminer, pour n'importe quelle proposition mathématique, si elle est vraie ou fausse.
Turing aborde la question un peu autrement : Existe-t-il un algorithme capable de calculer la décidabilité d'une proposition mathématique ? (je ne suis pas sûr de bien voir la différence, d'ailleurs)

AS a écrit:un problème résoluble en temps polynomial sur une machine non-déterministe, est vérifiable en temps polynomial sur une machine déterministe (et ça, c'est accessible via nos ordinateurs). De tels problèmes sont, par définition, de classe NP. La différence entre les classes P et NP est donc celle entre les notions de "résoluble" et de "vérifiable" (tous deux en temps polynomial).
Je tente de comprendre.
Le "problème" spécifique d'une machine non-déterministe n'est pas tant la taille de l'input n que le nombre d'états internes, démultiplié. L'idée en est que si on était capable de construire une machine de Turing non-déterministe, elle serait capable de traiter un même échantillon n plus rapidement qu'une machine déterministe, càd elle serait capable de résoudre un même problème plus rapidement.

Non, ça ne doit pas être ça. Je ne vois pas le lien avec ton exemple du mot de passe :
Beaucoup de problèmes importants sont de classe NP. Par exemple : le problème de cracker un mot de passe. Si l'on possède le bon mot de passe, il est facile de vérifier que c'est le bon. Par contre, il est très difficile de trouver, à partir de rien, le bon mot de passe : si le mot de passe est long et complexe, il faudrait, dans l'état de nos connaissances, un temps déraisonnablement long pour le cracker.
D'accord, mais ça, c'est le même exemple que le sudoku ? A raison d'un mot de passe très simple à 8 lettres, on a déjà, euh, (8x26)8 combinaisons possibles, si je ne me trompe ? Donc ok, on a là un problème de complexité non-polynomiale, càd de classe NP (?) Mais, en somme, qu'est-ce qu'ajoute au raisonnement la machine non-déterministe ?

_________________
...que vont charmant masques et bergamasques...
Bergame
Bergame
Persona
Persona

Nombre de messages : 5033
Date d'inscription : 03/09/2007

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par Saint-Ex Dim 17 Mar 2024 - 14:51

.

À Bergame et AntiSubjectiviste :

Bien que je ne participe pas à votre discussion (en fait, j'en serais incapable), sachez que je la suis avec un intérêt que je serais incapable de dissimuler.

Voilà qui me plait par la matérialité absolue qui s'en dégage absolument. C'est dans ce genre de matérialité que je vois le développement intelligent de l'intelligence. (N'allez pas confondre mon enthousiasme avec quelque flatterie, sinon je ne vous parle plus !)

Je vais vous relire attentivement, tiens !

.
Saint-Ex
Saint-Ex
Digressi(f/ve)
Digressi(f/ve)

Nombre de messages : 1654
Date d'inscription : 01/07/2023

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

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

AntiSubjectiviste
Digressi(f/ve)
Digressi(f/ve)

Nombre de messages : 170
Date d'inscription : 16/07/2022

Revenir en haut Aller en bas

Temps polynomial Empty Re: Temps polynomial

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Page 1 sur 2 1, 2  Suivant

Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum