Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Td8 optimisation combinatoire

TD Optimisation Combinatoire Louis Dublois louis dublois gmail com Université Paris-Dauphine CTD Correction DM CE SAT SAT Un ensemble X de n variables binaires x xn et une formule qui est la conjonction de m clauses C Cm chacune composée d ? au plus litéraux E SAT Restriction du problème SAT o? chaque clauses Cj contient exaxctement litéraux Existe-t-il une a ?ectation des valeurs true et false aux variables de X telle que est satisfaite CE SAT ?? NP Montrer que E SAT est dans NP CE SAT ?? NP Input Une formule de n variables x xn et m clauses C Cm chacune composée d ? exactement litéraux et une a ?ectation ? des variables de Output Oui si ? satisfait sinon Non Pour toute clause Cj dans faire b false Pour toute variable x dans Cj faire Si ? x satisfait Cj faire b true Si b false faire Retourner Non Retourner Oui Véri ?e si ? satisfait en temps O m Theorem E SAT est dans NP C SAT ? T E SAT Créer une réduction polynomiale de Turing SAT ? T E SAT et présenter cette réduction sous forme d ? algorithme C SAT ? T E SAT Soit une instance de SAT avec n variables x xn et m clauses C Cm On veut construire une instance de E SAT i e o? chaque clause de a exactement litéraux Pour toute clause Cj de Si Cj OK Si Cj i e Cj x ?? x alors on supprime Cj et on ajoute les deux clauses x ?? x ?? y ?? x ?? x ?? y Si Cj i e Cj x alors on supprime Cj et on ajoute les quatre clauses x ?? y ?? y ?? x ?? y ?? y ?? x ?? y ?? y ?? x ?? y ?? y C SAT ? T E SAT Input Une formule de SAT composé de n variables x xn et m clauses C Cm Output Une instance de E SAT Pour toute clause Cj dans faire Si Cj Cj x ?? x faire Créer Cj x ?? x ?? y et Cj x ?? x ?? y Cj ?? Cj ?? Cj Si Cj Cj x faire Créer Cj x ?? y ?? y Cj x ?? y ?? y Cj x ?? y ?? y et Cj x ?? y ?? y Cj ?? Cj Cj Cj Cj Retourner Algorithme en O m CExactitude SAT ? T E SAT Prouver que cette réduction est correcte CExactitude SAT ? T E SAT Démonstration Supposons que est satis ?able Considérons n ? importe quelle clause Cj de Si Cj alors Cj est aussi satis ?able dans Si Cj alors x ou x satisfait Cj et les deux clauses Cj et Cj sont satisfaites dans Si Cj alors x satisfait Cj et les quatre clauses Cj Cj sont satisfaites dans Donc est satisfaite CExactitude SAT ? T E SAT Démonstration Supposons que est satisfaite