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

(2016) 928

Dernier rapport du Jury :

(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 :

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 :

Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest (utilisée dans 49 versions au total)
Computers and intractability, Garey, Johnson (utilisée dans 3 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)