Podcast
Questions and Answers
Comment est défini un problème dans le contexte de la théorie de la NP-complétude?
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)?
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?
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?
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?
Quelle est la classe de problèmes pour lesquels il existe une solution efficace connue?
Quelle est la classe de problèmes pour lesquels il existe une solution efficace connue?
Un problème est défini par une question spécifique sur des données connues
Un problème est défini par une question spécifique sur des données connues
Le problème de Satisfiabilité Booléenne -SAT- est prouvé être un problème NP-complet selon COOK (1971)
Le problème de Satisfiabilité Booléenne -SAT- est prouvé être un problème NP-complet selon COOK (1971)
Le problème du circuit Hamiltonien est un exemple de problème NP-complet
Le problème du circuit Hamiltonien est un exemple de problème NP-complet
La classe NP-complet a été introduite par COOK en 1971
La classe NP-complet a été introduite par COOK en 1971
Qu'est-ce qu'un problème NP-complet?
Qu'est-ce qu'un problème NP-complet?
Comment est défini un problème dans le contexte de la théorie de la NP-complétude?
Comment est défini un problème dans le contexte de la théorie de la NP-complétude?
La théorie de la NP-complétude a été introduite par COOK en 1972
La théorie de la NP-complétude a été introduite par COOK en 1972
Qu'est-ce que le problème du circuit Hamiltonien (PCH)?
Qu'est-ce que le problème du circuit Hamiltonien (PCH)?
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?
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?
Quelle est la classe de problèmes pour lesquels il existe une solution efficace connue?
Quelle est la classe de problèmes pour lesquels il existe une solution efficace connue?
