CCU Graduate Algorithm 2015 NP-completeness II

Valeur des informations & solidité de l’argumentation

La valeur des informations est élevée car le cours explique en profondeur deux réductions classiques, fondamentale pour comprendre la théorie de la complexité. L’argumentation est solide : chaque étape de la réduction est motivée, les invariances sont explicitées, et la preuve de correction est menée avec soin dans les deux sens (si la réponse est oui d’un côté, alors oui de l’autre, et réciproquement). Le professeur souligne les pièges à éviter (par exemple, la simple suppression des directions dans le second exemple) ce qui renforce la compréhension. Le raisonnement est rigoureux et adapté à un public avancé.

Rigueur scientifique, qualité des sources, adéquation du titre

La rigueur scientifique est bonne : les résultats sont conformes aux connaissances établies en complexité algorithmique, et les réductions présentées sont des exemples canoniques issus de la littérature (Cook, Karp). Cependant, aucune source précise n’est citée pendant le cours, et la description ne fournit aucun lien. Le titre est adéquat et reflète exactement le contenu. Une légère réserve porte sur la mention du problème de tri de crêpes, dont le statut NP-complet n’est pas définitivement établi (l’annonce de 2011 reste contestée), mais l’enseignant nuance correctement son propos.

Le titre correspond au contenu : il s'agit bien d'un cours de cycle supérieur sur la NP-complétude, deuxième partie, avec des exemples de réductions et la discussion de problèmes ouverts.

8/10

La présentation est claire et rigoureuse, fondée sur des résultats bien établis (preuves de Cook et Karp, exemples classiques de réductions). Quelques affirmations sur des problèmes ouverts, notamment le tri de crêpes, sont à nuancer mais restent globalement exactes. La démarche pédagogique est solide.

Repères établis par PSI à partir de la transcription : le créateur n'a pas défini de chapitres.

• 00:00Rappel des définitions de NP, NP-difficile, NP-complet et de la stratégie de preuve par réduction.
• 05:00Explication de la démarche : choisir un problème NP-complet connu et construire une réduction.
• 10:00Premier exemple : réduction du cycle hamiltonien au problème du voyageur de commerce (TSP) avec pondération des arêtes.
• 20:00Démonstration de la correction de la réduction en analysant les cas oui/non.
• 25:00Deuxième exemple : réduction du cycle hamiltonien dirigé au non dirigé à l'aide de nœuds auxiliaires et de contraintes de direction.
• 40:00Discussion des problèmes ouverts (isomorphisme de graphes, tri de crêpes) et conclusion du cours.

• Théorème de Cook-Levin — Cité comme la première preuve de NP-complétude (SAT).
• 21 problèmes NP-complets de Karp — Mentionné comme l'extension des résultats de Cook à d'autres problèmes.