Remerciez-le!

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

U.I.K. Tiaret 2022/2023 Faculté MI Sem. 1 Département Informatique Durée 1h :30

U.I.K. Tiaret 2022/2023 Faculté MI Sem. 1 Département Informatique Durée 1h :30 Évaluation Complexité algorithmique Exercice 1 (6 pts) 1. Donnez une description formelle du problème du sac-à-dos 2. Que signifie 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 («certificat») 3. Soit les algorithmes suivants : A/ int count = 0; for (int i = n; i > 0; i \= 2) { for (int j = 0; j < i; j++) { count++; } } b) Combien de fois exactement l’opération « count++ » est exécutée ? A/ 2n B/ logn+1 c) Quelle est l’ordre de grandeur de chaque algorithme (c'est-à-dire (?)) A/ (n) B/ (logN) Exercice 2 (8 pts) 1. Résoudre avec la méthode maitre a) T (n) = 16 T(n/4) + n cas 1 => O(n2) b) T (n) = 3 T(n/3) + n/2 cas 2 => O(n logn) • Cas 1:si f(n) = O(nlog b a-) pour > 0, alors: T(n) = (nlog b a) • Cas 2:si f(n) =  (nlog b a), alors: T(n) =  (nlog b a lgn) • Cas 3:si f(n) =  (nlog b a+) pour > 0, et si af(n/b) ≤ c f(n) pour c < 1 et tout n suffisamment large, alors: T(n) =  (f(n)) B/ int count = 0; for (int i = 1; i <=n; i = i*2) { count++; } Tel que U.I.K. Tiaret 2022/2023 Faculté MI Sem. 1 Département Informatique Durée 1h :30 2. Résoudre « T(n)= 2 T(n/2) + n » en utilisant la méthode d'itération. O(n logn) Exercice 3 (6 pts) Soit le graphe non orienté G suivant 1. En utilisant l’algorithme de Kruskal déterminer le minimum spanning tree, Quel est son coût total ? Le coût total est 21 2. Décrivez brièvement (en 2 lignes) comment trouver le maximum spanning tree. Le maximum spanning tree peut être calculé en multipliant les poids de chaque arête par -1 et en appliquant par la suite l'algorithme de Kruskal uploads/s1/ examen-complexit-2023-solution.pdf