Leçon 928 : Problèmes NP-complets : exemples et réduction.

(2019) 928
(2021) 928

Dernier rapport du Jury :

(2019 : 928 - Problèmes NP-complets : exemples et réductions.) L’objectif ne doit pas être de dresser un catalogue le plus exhaustif possible ; en revanche, pour chaque exemple, il est attendu que le candidat puisse au moins expliquer clairement le problème considéré, et indiquer de quel autre problème une réduction permet de prouver sa NP-complétude. $\\$ Les exemples de réduction polynomiale seront autant que possible choisis dans des domaines variés : graphes, arithmétique, logique, etc. Si les dessins sont les bienvenus lors du développement, le jury attend une définition claire et concise de la fonction associant, à toute instance du premier problème, une instance du second ainsi que la preuve rigoureuse que cette fonction permet la réduction choisie et que les candidats sachent préciser comment sont représentées les données. $\\$ Il peut être bienvenu de présenter un exemple de problème NP-complet dans sa généralité qui devient P si on contraint davantage les hypothèses, ou encore un algorithme P approximant un problème NP-complet.

(2017 : 928 - Problèmes NP-complets : exemples et réductions.) L’objectif ne doit pas être de dresser un catalogue le plus exhaustif possible ; en revanche, pour chaque exemple, il est attendu que le candidat puisse au moins expliquer clairement le problème considéré, et indiquer de quel autre problème une réduction permet de prouver sa NP-complétude. Les exemples de réduction polynomiale seront autant que possible choisis dans des domaines variés : graphes, arithmétique, logique, etc. Un exemple de problème NP-complet dans sa généralité qui devient P si on contraint davantage les hypothèses pourra être présenté, ou encore un algorithme P approximant un problème NP-complet. Si les dessins sont les bienvenus lors du développement, le jury attend une définition claire et concise de la fonction associant, à toute instance du premier problème, une instance du second ainsi que la preuve rigoureuse que cette fonction permet la réduction choisie.
(2015 : 928 - Problème NP-complets : exemples de réductions.) L'objectif ne doit pas être de dresser un catalogue le plus exhaustif possible ; en revanche, pour chaque exemple, il est attendu que le candidat puisse au moins expliquer clairement le problème considéré, et indiquer de quel autre problème une réduction permet de prouver sa NP-complétude. Les exemples de réduction seront autant que possible choisis dans des domaines variés : graphes, arithmétique, logique, etc. Un exemple de problème NP-complet dans sa généralité qui devient P si on contraint davantage les hypothèses pourra être présenté, ou encore un algorithme P approximant un problème NP-complet. Si les dessins sont les bienvenus lors du développement, le jury attend une définition claire et concise de la fonction associant, à toute instance du premier problème, une instance du second ainsi que la preuve rigoureuse que cette fonction permet la réduction choisie.

Développements :

Plans/remarques :

2018 : Leçon 928 - Problèmes NP-complets : exemples et réductions.


2016 : Leçon 928 - Problème NP-complets : exemples de réductions.


2015 : Leçon 928 - Problème NP-complets : exemples de réductions.


Retours d'oraux :

Pas de retours pour cette leçon.

Références utilisées dans les versions de cette leçon :

Computers and intractability, Garey, Johnson (utilisée dans 3 versions au total)
Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest (utilisée dans 49 versions au total)
A Guide to Algorithm Design: Paradigms, Methods, and Complexity Analysis, Anne Benoît, Yves Robert, Frédéric Vivien (utilisée dans 5 versions au total)
Introduction to the theory of computation , Sipser (utilisée dans 12 versions au total)
New NP-hard and NP-complete polynomial and integer divisibility, Plaisted (utilisée dans 1 versions au total)
Backtrack: An O(1) expected time algorithm for the graph coloring problem, Wilf (utilisée dans 1 versions au total)