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

Qu'est-ce qu'un algorithme de force brute ?

1. AUn algorithme qui essaie toutes les solutions candidates possibles
2. BUn algorithme qui s'exécute sur de nombreux processeurs
3. CUn algorithme qui devine une réponse au hasard
4. DUn algorithme qui utilise toujours la récursion

Combien de mémoire supplémentaire utilise un tri fusion standard sur tableau ?

1. AO(n²)
2. BO(1)
3. CO(n)
4. DO(log n)

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 n / 2
3. CEnviron n²
4. DEnviron log₂ n

Comment l'algorithme de Prim construit-il un arbre couvrant de poids minimal ?

1. AIl supprime l'arête la plus chère jusqu'à ce qu'il ne reste plus de cycle
2. BIl trie toutes les arêtes par poids et ajoute chacune d'elles sauf si elle formait un cycle dans la forêt
3. CIl fait croître un seul arbre à partir d'un sommet de départ, en ajoutant l'arête la moins chère qui sort de l'arbre
4. DIl exécute un parcours en largeur et conserve l'arbre du BFS

Quelle est la complexité temporelle amortie de l'ajout en fin de tableau dynamique qui double sa capacité lorsqu'il est plein ?

1. AO(n²)
2. BO(n)
3. CO(log n)
4. DO(1)

Quelle est la solution de la récurrence T(n) = 2T(n/2) + O(1) ?

1. AO(n log n)
2. BO(n)
3. CO(log n)
4. DO(n²)

Pourquoi la recherche dichotomique ne s'exécute-t-elle pas en O(log n) sur une liste simplement chaînée ?

1. AAtteindre l'élément du milieu prend O(n) étapes, faute d'accès direct par indice
2. BLes listes chaînées ne peuvent pas être triées
3. CLes comparaisons sur les nœuds d'une liste chaînée sont plus lentes
4. DLa recherche dichotomique nécessite au moins deux fois plus de mémoire

Quelle est la solution de la récurrence T(n) = 2T(n/2) + n log n ?

1. AΘ(n log² n)
2. BΘ(n²)
3. CΘ(n log n)
4. DΘ(n)