Fiche d’exercices de Algorithmes et complexité avec corrigé

Quelle notation décrit une borne inférieure de croissance ?

1. AO (grand O)
2. BΘ (grand Thêta)
3. CΩ (grand Oméga)
4. Do (petit o)

Une boucle commence avec i = 1 et double i à chaque itération jusqu'à ce que i > n. Combien d'itérations effectue-t-elle ?

1. AEnviron n
2. BEnviron log₂ n
3. CEnviron n²
4. DEnviron n / 2

Quelle notation décrit une borne supérieure de la croissance ?

1. APetit oméga (little omega)
2. BGrand Thêta (Big Theta)
3. CGrand Oméga (Big Omega)
4. DGrand O (Big O)

Quelle est la complexité temporelle de l'algorithme de Bellman-Ford sur un graphe à V sommets et E arêtes ?

1. AO(V³ × E)
2. BO(V × E)
3. CO(V + E)
4. DO(E log V)

Vous triez une fois un tableau de n éléments, puis répondez à k requêtes d'appartenance par recherche dichotomique. Quel est le coût total ?

1. AO(n + k)
2. BO(k n log n)
3. CO(nk)
4. DO(n log n + k log n)

La programmation dynamique est utile lorsqu'un problème présente :

1. AUniquement des entrées aléatoires
2. BDes sous-problèmes qui se chevauchent et une sous-structure optimale
3. CUne seule boucle
4. DAucun sous-problème, de sorte qu'il peut être résolu en une seule étape

La multiplication de Karatsuba vérifie T(n) = 3T(n/2) + O(n). Quelle en est la solution ?

1. AΘ(n^{log₂ 3}), soit environ n^1,585
2. BΘ(n²)
3. CΘ(n log n)
4. DΘ(n³)

Comment le problème du voyageur de commerce est-il classé ?

1. AIl est dans P car l'algorithme de Dijkstra le résout en visitant chaque ville une seule fois
2. BLa version décisionnelle est dans P mais la version d'optimisation est NP-complète
3. CIl est indécidable
4. DLa version décisionnelle est NP-complète et la version d'optimisation est NP-difficile