Leçon 916 : Formules du calcul propositionnel : représentation, formes normales, satisfiabilité. Applications.

(2018) 916
(2020) 916

Dernier rapport du Jury :

(2019 : 916 - Formules du calcul propositionnel : représentation, formes normales, satisfiabilité. Applications.) Le jury attend des candidats qu’ils abordent les questions de la complexité de la satisfiabilité. Pour autant, les applications ne sauraient se réduire à la réduction de problèmes NP-complets à SAT. Une partie significative du plan doit être consacrée à la représentation des formules et à leurs formes normales.

(2017 : 916 - Formules du calcul propositionnel : représentation, formes normales, satisfabilité. Applications.) Le jury attend des candidats qu’ils abordent les questions de la complexité de la satisfiabilité. Pour autant, les applications ne sauraient se réduire à la réduction de problèmes NP-complets à SAT. Une partie significative du plan doit être consacrée à la représentation des formules et à leurs formes normales.
(2015 : 916 - Formules du calcul propositionnel : représentation, formes normales, satisfiabilité. Applications.) Le jury attend des candidats qu'ils abordent les questions de la complexité de la satisfiabilité. Pour autant, les applications ne sauraient se réduire à la réduction de problèmes NP-complets à SAT. Une partie significative du plan doit être consacrée à la représentation des formules et à leurs formes normales.

Développements :

Plans/remarques :

2018 : Leçon 916 - Formules du calcul propositionnel : représentation, formes normales, satisfiabilité. Applications.


2016 : Leçon 916 - Formules du calcul propositionnel : représentation, formes normales, satisfiabilité. Applications.


2015 : Leçon 916 - Formules du calcul propositionnel : représentation, formes normales, satisfiabilité. Applications.


Retours d'oraux :

Pas de retours pour cette leçon.

Références utilisées dans les versions de cette leçon :

Logique mathématique Tome 1, René Cori, Daniel Lascar (utilisée dans 4 versions au total)
Logique et fondements de l'informatique, Rougemont, Lassaigne (utilisée dans 6 versions au total)
Computational Complexity: A Modern Approach, Sanjeev Arora, Boaz Barak (utilisée dans 4 versions au total)
Computational complexity , Papadimitriou (utilisée dans 7 versions au total)
Topologie , Queffelec (utilisée dans 33 versions au total)
Fondements mathématiques de l'informatique , Stern (utilisée dans 3 versions au total)
Logique mathématique Tome 2, René Cori, Daniel Lascar (utilisée dans 7 versions au total)
Introduction to the theory of computation , Sipser (utilisée dans 12 versions au total)