Algorithme Polynomial-Temps

[invite238d83df]

Bonsoir,

Je veux vous poser deux questions.

Qu’est ce qu’un algorithme Polynomial-Temps ?

Qu’est ce qu’est un problème indécidable?

Merci beaucoup
-----

[invite4492c379]

Hello,

Quel est ton niveau (collège, lycée, es) ?

[invite238d83df]

Bonsoir,

Je fais un master imagerie vision et nous avons un cour qui s'appelle Aide a la decision,mais je n'ai pas compri ca.

Merci

[invite4492c379]

Bonsoir,

Je fais un master imagerie vision et nous avons un cour qui s'appelle Aide a la decision,mais je n'ai pas compri ca.

Merci

OK,

en fait on essaye toujours d'exprimer le temps que prend un algo en fonction de ses entrée. Un algo qui s'exécute en temps polynomial est tout simplement un algo dont le temps d'exécution est proportionnel à un polynôme en fonction des entrées.
Généralement il est difficile d'obtenir une expression de ce polynôme, c'est pourquoi on introduit les notation en O (grand o). Un algo en temps polynomial est donc un algo dont le temps d'exécution est en O(n^k), le cas k=1 est nommé linéaire (mais reste polynomial). Un exemple sera plus parlant.
Il existe différents algorithme de tri de tableau, pour en mesurer l'efficacité on va essayer de calculer le temps mis pour trier un tableau en fonction du nombre n d'éléments.
Le tri à bulles a une complexité moyenne en O(n²), cela signifie que si tu doubles la taille du tableau, tu mettras quatre fois plus de temps pour le trier. Le tri à bulles s'exécute en temps polynomial (ici on dit aussi quadratique)
Rechercher une valeur dans un tableau non trié se fait en O(n) (au pire il faut lire toutes les données dans le tableau), il est polynomial (même linéaire). Si le tableau est deux fois plus grand, tu mettras deux plus de temps en moyenne.

Pour la seconde question, dans le cadre de la complexité, on dit qu'un problème de décision est décidable s'il existe un algorithme qui en temps fini dit si oui ou non une instance est solution d'un problème ; par exemple on peut dire si un tableau donné est trié ou non (=vérifier).
Un problème indécidable est tout simplement un problème pour lequel aucun algorithme qui vérifie si une instance est solution du problème existe. L'exemple classique est qu'il n'existe aucun algorithme général qui puisse dire si un programme quelconque donné termine ou s'il boucle sans fin.

Tu me dis si je ne suis pas assez clair ou trop confus

[A voir en vidéo sur Futura]

[invite238d83df]

merci beaucoup