✦ COGNITIA · Cours interactif

Algorithmes : puissance, limites et performance

Comprendre ce qu’un ordinateur peut résoudre, mesurer l’efficacité des algorithmes et repousser les limites du calcul.

Chapitre 10 / 12

Problèmes NP-complets

Certificats, réductions et SAT

Le cours présente NP, les transformations polynomiales, SAT, le théorème de Cook et l’exemple du Sudoku.

💡 À retenir : Ne pas confondre NP avec « non polynomial » : NP concerne la vérification polynomiale des certificats.

🧩 Vérification d’une formule SAT

Exemple pédagogique complémentaire : F = (A ∨ B) ∧ (¬A ∨ C). Testez une affectation des variables.