Examen 2004 5
Examen 2004 5
Examen 2004 5
porter un butin de plus grande valeur possible mais il ne peut porter que W
kilogrammes dans son sac-à-dos. On cherche un algorithme qui lui permette de
On suppose dans cet exercice, qu'il n'est pas possible de découper les objets.
que (d'un sous-ensemble) des i premiers ob jets, et s'il pèse moins que w kilo-
grammes.
1.2 Algorithme 1
ité?
1.3 Algorithme 2
On suppose maintenant que le voleur peut ne prendre qu'une fraction d'un objet
et n'est plus obligé de prendre l'ob jet tout entier comme précédemment, ou de
le laisser.
1
2.1 Algorithme
Proposer un algorithme glouton dans ce cas (on pourra raisonner sur la valeur
2.2 Optimalité
3 Exercice 3: k -SAT
Pour un entier k , on appelera k -SAT le problème qui prend en entrée une formule
booléenne sous forme normale conjonctive à m clauses et n-variables, où chaque
clause est la disjonction d'exactement k -littéraux, et doit décider si la formule
est satisfaisable.
3.1 ≤ k -SAT
Montrer proprement en admettant la NP-complétude de 3-SAT que ≤ 4-SAT
est NP-complet.
3.2 k -SAT
Montrer proprement en admettant la NP-complétude de 3-SAT que 4-SAT est
NP-complet.
que le problème de déterminer si on peut les placer autour d'une table circulaire
admise) en cours.