Remerciez-le!

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

Corrigeinterro2012 13 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 n n n le nombre d ? opérations élémentaires du pire cas d ? un algorithme A Montrez que f n O n n A-t-on f n ? n n Expliquez Solution Pour montrer que f n O n n il su ?t de trouver n et c ? ou de montrer leur existence tels que ? n ?n f n ?cn n n n n n ?cn n on divise les deux membres par n n ?c donc le c et le n demandés existent Conclusion on a bien f n O n n Pour avoir f n ? n n vu qu ? on a déjà f n O n n il faut avoir en plus n n O f n Tentons donc de montrer n n O n n n n en cherchant n et c ? tels que ? n ?n n n ?c n n n n n n ?c n n n n on divise les deux membres par c n n ? Prendre et n donc c et n Conclusion f n ? n n Exercice points Soient A A A et A quatre 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 f n n et f n n Comparez les complexités des quatre algorithmes Expliquez Solution f n ? n logn f n ? n f n ? n f n ? n donc ? n ? n logn ? n ? n l ? algorithme A est ? meilleur que l ? algorithme A qui est meilleur que l ? algorithme A qui est meilleur que l ? algorithme A Page sur CExercice points On considère le graphe suivant E A F B D G C H I J Donnez un arbre de recouvrement issu d ? un parcours en profondeur d ? abord du graphe Donnez l ? ordre dans lequel le parcours considéré a visité les sommets du graphe Déduire des questions précédentes l ? arbre de recouvrement ordonné issu du parcours considéré le parcours en profondeur d ? abord de l ? arbre ordonné doit visiter les sommets dans l ? ordre dans lequel ils l ? ont été par le parcours considéré du graphe Solution E A F B D G C H I J ABDCHIEFGJ A B E D F C G H J I Exercice points On considère le problème de décision PARTITION suivant ? Description un ensemble d ? entiers ? Question Peut- on partitionner l ? ensemble en trois sous-ensembles de même somme Le but de l ? exercice est de trouver un algorithme polynômial de