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

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

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

Un algorithme comportant deux boucles imbriquées, chacune exécutée n fois, a généralement quelle complexité ?

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

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

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

La borne inférieure du tri par comparaisons dans le pire cas est :

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

Vous triez une fois un tableau de n éléments, puis répondez à k requêtes d'appartenance par recherche dichotomique. Quel est le coût total ?

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

Que calcule l'algorithme de Floyd-Warshall, et en combien de temps ?

1. ALes plus courts chemins entre toutes les paires de sommets en O(V³)
2. BLes plus courts chemins depuis un sommet source vers tous les autres en O(V + E)
3. CUn arbre couvrant de poids minimal en O(E log V)
4. DUn ordre topologique en O(V²)

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

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

Le tri topologique n'est possible que pour :

1. ALes graphes orientés acycliques (DAG)
2. BLes graphes à poids négatifs
3. CLes graphes complets
4. DLes graphes non orientés