Home Admin Dvpts Leçons Livres Retours
Login Sign up

28 - Formules du calcul propositionnel : représentation, formes normales, satisfiabilité. Applications.2022

Rapport du jury 2019

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.

Afficher les anciens rapports

Développements

5 2-SAT est NL-dur
5 Application du théorème de compacité
5 3-SAT NP complet, 2-SAT dans P
5 Groupes totalement ordonnable
5 Théorème de compacité du calcul propositionnel
5 Graphes et formules logiques : 2-SAT est NL-complet, CLIQUE est NP-complet
4 Théorème de Cook
3 NP-Complétude de HAM-PATH

Plans

Rajouter une version
Utilisateur : sieghttct
Télécharger
Références :
Logique mathématique Tome 1
Logique et fondements de l'informatique
Computational Complexity: A Modern Approach
Computational complexity
Topologie
Utilisateur : Promo ENSL 2015
Télécharger
Oral blanc
Références :
Utilisateur : Timothée
Télécharger
Oral blanc
Références :
Fondements mathématiques de l'informatique
Logique mathématique Tome 1
Logique mathématique Tome 2
Introduction to the theory of computation
Utilisateur : Promo ENSL 2016
Télécharger
Références :

Retours