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

Que vaut log₂ 1024 ?

1. A32
2. B12
3. C512
4. D10

Quelle est la complexité temporelle dans le pire cas du tri par insertion ?

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

Quelle est la complexité temporelle du tri fusion dans le pire cas ?

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

Quel algorithme de tri est stable ?

1. ATri par sélection (version habituelle)
2. BTri fusion
3. CTri rapide (version en place habituelle)
4. DTri par tas

Pourquoi de nombreuses routines de tri des bibliothèques passent-elles au tri par insertion pour les très petits sous-tableaux ?

1. ALes algorithmes récursifs ne peuvent pas traiter les tableaux de moins de 10 éléments
2. BLe tri par insertion a peu de surcoût et est rapide sur les entrées petites ou presque triées
3. CLe tri par insertion utilise moins de mémoire que tout autre algorithme de tri sur les grandes entrées
4. DLe tri par insertion est en O(n log n) dans le pire cas

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²)

Quelles sont les deux choses à montrer pour prouver qu'un problème de décision X est NP-complet ?

1. AX se réduit à un problème de P, et X est dans NP
2. BX est dans NP, et un problème NP-complet connu se réduit à X en temps polynomial
3. CX est dans P, et X se réduit à SAT
4. DX n'a pas d'algorithme polynomial, et X est décidable

L'algorithme de programmation dynamique de Held-Karp résout exactement le problème du voyageur de commerce. Quel est son temps d'exécution pour n villes ?

1. AO(n² 2ⁿ)
2. BO(n!)
3. CO(2^n²)
4. DO(n³)