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

Quel algorithme de tri échange de façon répétée les éléments adjacents qui sont dans le mauvais ordre ?

1. ATri rapide (quicksort)
2. BTri par tas
3. CTri fusion
4. DTri à bulles

Quelle stratégie de conception utilise le tri fusion ?

1. ALa programmation dynamique
2. BDiviser pour régner
3. CLa force brute
4. DLe choix glouton

Quelle est la complexité temporelle de la recherche dichotomique dans un tableau trié ?

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

Est-il correct de dire qu'un algorithme en O(n²) est aussi en O(n³) ?

1. ANon, car n³ est plus petit que n² pour n grand
2. BOui, mais seulement si n est inférieur à 100
3. COui, car le grand O est une borne supérieure et n² ne croît pas plus vite que n³
4. DNon, car le grand O doit toujours donner le taux de croissance exact de la fonction

Quel énoncé sur une fonction récursive sans cas de base atteignable est correct ?

1. ALe compilateur la transforme toujours en une boucle qui se termine sans danger
2. BElle s'exécute en temps O(1)
3. CElle continue de s'appeler jusqu'au débordement de la pile d'appels
4. DElle renvoie automatiquement 0

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

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

Un problème est NP-complet s'il :

1. AEst impossible à résoudre
2. BEst hors de NP mais plus difficile que tous les problèmes NP, comme le problème de l'arrêt
3. CAppartient à NP et si tout problème NP se réduit à lui en temps polynomial
4. DEst résoluble en temps polynomial

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

1. AX n'a pas d'algorithme polynomial, et X est décidable
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 se réduit à un problème de P, et X est dans NP