Errata

Cette page recense les erreurs trouvées à ce jour (mais pas les typos). Vous pouvez signaler une erreur en écrivant à contact(at)informatique-mpi.fr.

• page 565 : Il faut remplacer « nous dit qu'un entier n est premier si et seulement si » par « nous dit que si un entier n est premier alors nécessairement » (signalé par Nathaniel Carré)
• page 638, preuve de la propriété 10.3 : Il faut raisonner par cas sur v(l) et non sur v(φ). (signalé par Daphné Kany)
• page 686, exercice 175 : Dans l'énoncé de la question 1, il faut définir 𝜑 comme la conjonction x ∧ y. Dans l'énoncé de la question 2, il faut définir ω comme l'équivalence 𝜑 ↔ 𝜓. (signalé par Tom Brouillet)
• page 1001, corrigé exercice 125 : Le code proposé dans la solution est bien un parcours de graphe, avec la complexité annoncée, mais ce n'est pas un parcours en profondeur. Pour une implémentation correcte de dfs_stack, voir le code en ligne. (signalé par Nathaniel Carré)
• page 1066, corrigé exercice 229 : Une clause SAT est une disjonction. Dans la correction de la question 2 on s'intéresse donc à la clause ℓ₁∨ℓ₂∨ℓ₃ et on complète les cas particuliers d'une clause unaire ou d'une clause binaire en ℓ₁∨ℓ₁∨ℓ₁ et ℓ₁∨ℓ₁∨ℓ₂. (signalé par Nazar Chernyak)