CCU Graduate Algorithm 2024 10/11

Valeur des informations & solidité de l’argumentation

Le cours offre une valeur pédagogique indéniable : il explique en détail les réductions polynomiales, illustre avec des exemples concrets les erreurs de raisonnement fréquentes (comme la réduction incorrecte du cycle hamiltonien dirigé vers non dirigé) et décompose étape par étape la preuve positive de NP-complétude de 3-SAT. L’argumentation est solide et progressive : l’enseignant part de cas simples (clauses à 1 ou 2 littéraux) puis généralise avec des variables auxiliaires, en insistant sur l’équivalence logique entre l’instance originale et sa transformation. Pour 2-SAT, la démonstration est claire et s’appuie sur la notion de graphe d’implication, avec justification de la condition de satisfaisabilité via les composantes fortement connexes. La rigueur est bien présente : chaque transformation est accompagnée d’une vérification que les réponses oui/non sont identiques, ce qui est le cœur de la réduction.

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

Le contenu est scientifiquement rigoureux car il s’appuie sur des résultats classiques de la théorie de la complexité (théorème de Cook-Levin, articles de Karp). Cependant, la vidéo ne cite pas explicitement de sources externes ou de références bibliographiques ; elle se limite à des mentions orales de chercheurs (Cook, Karp, etc.). Le titre est parfaitement adéquat : il décrit une séance de cours d’algorithmique de niveau master, et le contenu correspond à l’étude de la NP-complétude. Aucun commentaire n’est fourni, donc aucune tendance de public ne peut être analysée.

Le titre indique un cours de troisième cycle en algorithmique, et le contenu correspond exactement à la théorie de la NP-complétude.

8/10

Cours magistral basé sur des théorèmes fondamentaux de la complexité (Cook-Levin, réductions de Karp). Les démonstrations sont rigoureuses mais aucune source externe n'est citée dans la vidéo.

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

• 00:00Introduction et rappel de la séance précédente sur les réductions et la NP-complétude
• 10:00Exemple de réduction du cycle hamiltonien dirigé vers non dirigé avec explication des erreurs à éviter
• 20:00Classification des problèmes en P, NP et NP-complets ; mention de problèmes non classés (isomorphisme de graphes, pancake flipping)
• 30:00Introduction au problème SAT et à sa forme générale
• 45:00Preuve que 3-SAT est NP-complet par réduction de SAT général avec variables auxiliaires
• 1:10:00Analyse de 2-SAT en P via le graphe d'implication et les composantes fortement connexes
• 1:30:00Résumé conclusif et devoir aux étudiants pour k-SAT avec k ≥ 4

• Théorème de Cook-Levin — Mentionné comme base de la NP-complétude de SAT
• Travaux de Richard Karp — Réductions polynomiales entre 21 problèmes NP-complets