Remerciez-le!

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

Examen complexit 2023 solution

U I K Tiaret Faculté MI Département Informatique Évaluation Complexité algorithmique Sem Durée h Exercice pts Donnez une description formelle du problème du sac-à-dos Tel que Que signi ?e l ? étape non déterminisme lors de la résolution d ? un problème NP Générer de manière aléatoire une solution candidate certi ?cat ? Soit les algorithmes suivants A int count for int i n i i for int j j i j count B int count for int i i n i i count b Combien de fois exactement l ? opération count ? est exécutée A n B logn c Quelle est l ? ordre de grandeur de chaque algorithme c'est-à- dire ? A ? n B ? logN Exercice pts Résoudre avec la méthode maitre a T n T n n cas O n b T n T n n cas O n logn ? Cas si f n O nlogba- ? pour ? alors T n ? nlogba ? Cas si f n ? nlogba alors T n ? nlogba lgn ? Cas si f n ? nlogba ? pour ? et si af n b ? c f n pour c et tout n su ?samment large alors T n ? f n CU I K Tiaret Faculté MI Département Informatique Résoudre T n T n n ? en utilisant la méthode d'itération O n logn Exercice pts Soit le graphe non orienté G suivant Sem Durée h En utilisant l ? algorithme de Kruskal déterminer le minimum spanning tree Quel est son coût total Le coût total est Décrivez brièvement en lignes comment trouver le maximum spanning tree Le maximum spanning tree peut être calculé en multipliant les poids de chaque arête par - et en appliquant par la suite l'algorithme de Kruskal C