Remerciez-le!

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

Corrige interro Université des Sciences et de la Technologie Houari Boumediène Faculté d ? Electronique et d ? Informatique Département d ? Informatique LMD Master ère Année RSD Module ? ? Algorithmique Avancée et Complexité ? ? Corrigé de l ? interrogati

Université des Sciences et de la Technologie Houari Boumediène Faculté d ? Electronique et d ? Informatique Département d ? Informatique LMD Master ère Année RSD Module ? ? Algorithmique Avancée et Complexité ? ? Corrigé de l ? interrogation Exercice complexité du tri On considère l ? algorithme suivant de tri par insertion d ? un tableau A de n entiers Entrée Un tableau A de n entiers Sortie Le tableau A trié par ordre croissant TRI- INSERTION A Pour j à n clé A j i j- Tant que i et A i clé A i A i i i- A i clé Calculez en fonction de n le nombre T n d ? opérations dans le pire des cas de l ? algorithme Expliquez Réponse TRI-INSERTION A Pour j à n a clé A j b i j- c Tant que i et A i clé i A i A i ii i i- iii d A i clé e CInstruction a b c c i c ii d Nombre d ? opérations Nombre de fois n- n- n- n- Le nombre total d ? opérations de l ? algorithme dans le pire des cas est donc T n n- n- n- Trouvez une fonction f n nk k constante véri ?ant T n O f n et f n O T n Expliquez Réponse La fonction f demandée est f n T n O f n Il su ?t de trouver un entier n ? et une constante réelle c ? tels que pour tout n ? n on ait T n ? c f n c ? est-à-dire ou encore ? c prendre n et c f n O T n Il su ?t de trouver un entier n ? et une constante réelle c ? tels que pour tout n ? n on ait f n ? c T n c ? est-à-dire ou encore ? c prendre n et c Que pouvez-vous déduire de la réponse à la question Réponse On déduit de la réponse à la question que T n f Exercice NP-complétude Illustrez à travers un exemple la notion d ? instance d ? un problème Réponse Le problème SAT o Description une conjonction de m clauses construites à partir de n propositions atomiques o Question la conjonction est-elle satis ?able Instance du problème SAT o La conjonction p q p r p q r C Dé ?nissez les notions suivantes de la théorie de la NP-complétude a Certi ?cat b Algorithme de validation c La classe NP d Problème NP- complet Réponse voir cours Donnez un algorithme polynomial de validation pour le problème SAT SATis ?abilité Utilisez la terminologie vue en TP en TD et en cours Expliquez Réponse L ? algorithme de validation est comme suit Il est écrit sous forme d ? une fonction booléenne à quatre entrées n m C et inst Le triplet n m C donne l ? instance du problème le nombre n de