Introduction à la NP-complétude
15 Questions
2 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Comment est défini un problème dans le contexte de la théorie de la NP-complétude?

  • Par une question générale sur des données dont les valeurs sont inconnues
  • Par une réponse générale à des données dont les valeurs sont connues
  • Par une instance spécifiant des données et une question correspondant à l'état final (correct)
  • Par une instance spécifiant des données et une réponse correspondant à l'état final

    • Qu'est-ce qu'un problème NP-complet selon COOK (1971)?

  • Un problème pour lequel il existe une solution efficace
  • Un problème pour lequel il n'existe pas de solution efficace connue (correct)
  • Un problème pour lequel il existe une solution, mais sa complexité n'est pas connue
  • Un problème dont la complexité est connue

    • Quel exemple de problème est donné dans le texte?

  • Le problème du circuit Hamiltonien (PCH) (correct)
  • Le problème du voyageur de commerce (TSP)
  • Le problème du tri par insertion
  • Le problème du sac à dos (Knapsack problem)

    • Qui a introduit la théorie de la NP-complétude en prouvant que le problème de Satisfiabilité Booléenne -SAT- est un problème NP-complet?

    <p>COOK (1971)</p> Signup and view all the answers

    Quelle est la classe de problèmes pour lesquels il existe une solution efficace connue?

    <p>La classe P</p> Signup and view all the answers

    Un problème est défini par une question spécifique sur des données connues

    <p>False</p> Signup and view all the answers

    Le problème de Satisfiabilité Booléenne -SAT- est prouvé être un problème NP-complet selon COOK (1971)

    <p>True</p> Signup and view all the answers

    Le problème du circuit Hamiltonien est un exemple de problème NP-complet

    <p>False</p> Signup and view all the answers

    La classe NP-complet a été introduite par COOK en 1971

    <p>True</p> Signup and view all the answers

    Qu'est-ce qu'un problème NP-complet?

    <p>Un problème NP-complet est un problème pour lequel il existe une solution vérifiable en temps polynomial et pour lequel tout autre problème NP peut se réduire en temps polynomial.</p> Signup and view all the answers

    Comment est défini un problème dans le contexte de la théorie de la NP-complétude?

    <p>Un problème est défini par une question générale sur des données dont les valeurs sont inconnues. Formellement, un problème est décrit par une instance spécifiant des données et une question correspondant à l'état final à atteindre ou des conditions à satisfaire.</p> Signup and view all the answers

    La théorie de la NP-complétude a été introduite par COOK en 1972

    <p>False</p> Signup and view all the answers

    Qu'est-ce que le problème du circuit Hamiltonien (PCH)?

    <p>Le problème du circuit Hamiltonien (PCH) consiste à déterminer si un graphe non orienté contient un circuit qui passe exactement une fois par chaque sommet du graphe.</p> Signup and view all the answers

    Qui a introduit la théorie de la NP-complétude en prouvant que le problème de Satisfiabilité Booléenne -SAT- est un problème NP-complet?

    <p>COOK (1971) a introduit la théorie de la NP-complétude en prouvant que le problème de Satisfiabilité Booléenne -SAT- est un problème NP-complet.</p> Signup and view all the answers

    Quelle est la classe de problèmes pour lesquels il existe une solution efficace connue?

    <p>La classe P est celle pour laquelle il existe une solution efficace connue, c'est-à-dire un algorithme qui résout le problème en temps polynomial.</p> Signup and view all the answers

    More Like This

    Journey into the Mind
    5 questions

    Journey into the Mind

    FancierJudgment avatar
    FancierJudgment
    Open System Theories and Agile Quiz
    10 questions

    Open System Theories and Agile Quiz

    BeneficentTheme avatar
    BeneficentTheme
    Apprendre la théorie du modèle de bias-variance
    8 questions

    Apprendre la théorie du modèle de bias-variance

    TenaciousVerdelite avatar
    TenaciousVerdelite
    Biochimie : Complexe IV et théorie chimio-osmotique
    22 questions

    Biochimie : Complexe IV et théorie chimio-osmotique

    AppreciativeTelescope avatar
    AppreciativeTelescope
    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser