Introduction à la NP-complétude

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson
Download our mobile app to listen on the go
Get App

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) (A)</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 (B)</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 (B)</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 (A)</p> Signup and view all the answers

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

<p>False (B)</p> Signup and view all the answers

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

<p>True (A)</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 (B)</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

Flashcards are hidden until you start studying

More Like This

Journey into the Mind
5 questions

Journey into the Mind

FancierJudgment avatar
FancierJudgment
Teorie e Tecniche della Comunicazione
48 questions
Use Quizgecko on...
Browser
Browser