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

Quelle classe de complexité croît le plus vite pour de grandes valeurs de n ?

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

On dit généralement qu'un problème est traitable (« tractable ») si :

1. AIl ne peut être résolu qu'en essayant toutes les possibilités
2. BIl peut être résolu en temps polynomial
3. CIl n'a pas de solution
4. DIl peut être résolu en temps constant

Quelle stratégie de conception utilise le tri fusion ?

1. ALe choix glouton
2. BLa programmation dynamique
3. CDiviser pour régner
4. DLa force brute

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

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

Que mesure l'analyse amortie ?

1. ALe coût de l'unique opération la plus chère, où qu'elle se trouve dans la suite
2. BLe coût moyen par opération sur une suite d'opérations de pire cas
3. CLe coût d'un algorithme sur la meilleure entrée
4. DLe coût espéré sur des entrées aléatoires

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

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

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 log n)
3. CΘ(n²)
4. DΘ(n³)

Quelle définition de la classe NP est correcte ?

1. ALes problèmes qui ne sont pas polynomiaux
2. BLes problèmes qui ne peuvent pas être résolus en temps polynomial
3. CLes problèmes de décision dont les réponses « oui » peuvent être vérifiées en temps polynomial à l'aide d'un certificat
4. DLes problèmes qu'aucun algorithme ne peut résoudre