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

Quelle stratégie de conception utilise le tri fusion ?

1. ADiviser pour régner
2. BLe choix glouton
3. CLa force brute
4. DLa programmation dynamique

Lequel de ces temps d'exécution est polynomial ?

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

Laquelle de ces fonctions croît le plus lentement quand n devient grand ?

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

Quel est le temps d'exécution du tri par base LSD sur n entiers de d chiffres en base k ?

1. AO(n log n)
2. BO(n²)
3. CO(d(n + k))
4. DO(dn log k)

Quelle est la complexité temporelle de l'algorithme standard de programmation dynamique pour la plus longue sous-séquence commune de chaînes de longueurs m et n ?

1. AO(2^m+n)
2. BO(mn log n)
3. CO(m + n)
4. DO(mn)

Avec des pièces de 1, 3 et 4 et un montant de 6, combien de pièces utilise la méthode gloutonne « la plus grosse pièce d'abord », comparée à l'optimum ?

1. ALe glouton utilise 4 pièces ; l'optimum est 3
2. BLe glouton utilise 3 pièces ; l'optimum est 3
3. CLe glouton utilise 3 pièces ; l'optimum est 2
4. DLe glouton utilise 2 pièces ; l'optimum est 2

Pourquoi toute recherche par comparaisons dans un tableau trié nécessite-t-elle Ω(log n) comparaisons dans le pire cas ?

1. AUn arbre de décision à n issues possibles doit avoir une profondeur d'au moins log₂ n
2. BLa recherche dichotomique est le seul algorithme possible, et elle nécessite log₂ n comparaisons
3. CChaque élément doit être comparé au moins une fois
4. DChaque comparaison prend un temps logarithmique

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

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