Algorithme Polynomial-Temps
Répondre à la discussion
Affichage des résultats 1 à 5 sur 5

Algorithme Polynomial-Temps



  1. #1
    invite238d83df

    Algorithme Polynomial-Temps


    ------

    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

    -----

  2. #2
    invite4492c379

    Re : Algorithme Polynomial-Temps

    Hello,

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

  3. #3
    invite238d83df

    Re : Algorithme Polynomial-Temps

    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

  4. #4
    invite4492c379

    Re : Algorithme Polynomial-Temps

    Citation Envoyé par kin21 Voir le message
    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(nk), 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

  5. A voir en vidéo sur Futura
  6. #5
    invite238d83df

    Re : Algorithme Polynomial-Temps

    merci beaucoup

Discussions similaires

  1. Toboggan polynomial
    Par invite50030703 dans le forum Mathématiques du collège et du lycée
    Réponses: 6
    Dernier message: 25/07/2011, 12h25
  2. Algorithme avec contrainte de temps
    Par invite8928d6a6 dans le forum Programmation et langages, Algorithmique
    Réponses: 4
    Dernier message: 17/04/2011, 10h14
  3. algorithme et temps
    Par Jiav dans le forum Epistémologie et Logique (archives)
    Réponses: 22
    Dernier message: 21/03/2009, 21h01
  4. Défi polynomial
    Par MMu dans le forum Mathématiques du supérieur
    Réponses: 13
    Dernier message: 20/08/2007, 16h34
  5. anneau polynomial
    Par chentouf dans le forum Mathématiques du supérieur
    Réponses: 47
    Dernier message: 09/07/2007, 19h50