Remerciez-le!

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

Corrigeinterro2011 12 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 IL Module ? ? Algorithmique Avancée et Complexité ? ? Date Corrigé de l ? i

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 IL Module ? ? Algorithmique Avancée et Complexité ? ? Date Corrigé de l ? interrogation Exercice points Soit f n n logn le nombre d ? opérations élémentaires du pire cas d ? un algorithme A Montrez que f n O n A- t-on f n ? n Expliquez Solution Pour montrer que f n O n il su ?t de trouver c et n ? ou de montrer leur existence tels que ? n ?n f n ?c n nlogn ?cn on divise les deux membres par n ?c donc le c et le n demandés existent Prendre c et n Conclusion on a bien f n O n Pour avoir f n ? n vu qu ? on a déjà f n O n il faut avoir en plus n O f n Tentons donc de montrer n O nlogn en cherchant c et n ? tels que ? n ?n n ?cnlogn n ?c nlogn on divise les deux membres par c n ? donc le c et le n demandés n ? existent pas on ne peut pas trouver de c tel que ? ? ? ? Conclusion f n ? n Exercice points Soient A A et A trois algorithmes conçus pour la même t? che T et dont les nombres d ? opérations élémentaires du pire cas sont respectivement f n n logn f n n et f n n Comparez les complexités des trois algorithmes Expliquez Solution f n n logn ? n logn f n n ? n f n n ? n Pour les grandes valeurs de n n logn est négligeable devant qui à son tour est négligeable devant n Donc l ? ordre décroissant de préférence des trois complexités est ? n logn ? n ? n la complexité de l ? algorithme A est meilleure que celle de l ? algorithme A qui à son tour est meilleure que celle de l ? algorithme A Page sur CExercice points Illustrez à l ? aide d ? un exemple la notion d ? instance d ? un problème 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 Donnez un algorithme polynômial de validation pour le problème SubsetSum somme de sous- ensemble suivant Description un ensemble S a an de n entiers et un entier m Question S admet-il un sous-ensemble dont la somme des éléments est m Justi ?ez la polynômialité de l ? algorithme Solution Pour les questions et voir cours Question nous donnons ci-après sous forme d ? une fonction booléenne un algorithme de validation validationsubs pour le problème SubsetSum l ? algorithme aura comme arguments un certi ?cat c et une instance I de SubsetSum l ? instance I est une paire S m