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

Une boucle commence avec i = 1 et double i à chaque itération jusqu'à ce que i > n. Combien d'itérations effectue-t-elle ?

1. AEnviron n
2. BEnviron log₂ n
3. CEnviron n / 2
4. DEnviron n²

Quel est le temps d'exécution du tri par comptage pour n entiers compris entre 0 et k ?

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

Quel est le grand O de 3n² + 5n + 2 ?

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

Quelle est la complexité temporelle du tri rapide (quicksort) dans le pire cas ?

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

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

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

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

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

Lequel de ces problèmes de satisfiabilité est connu pour être résoluble en temps polynomial ?

1. A3-SAT, où chaque clause a exactement trois littéraux
2. BLa satisfiabilité de circuits
3. CSAT général sur des formules en forme normale conjonctive
4. D2-SAT, où chaque clause a au plus deux littéraux

Le tri par insertion s'exécute en O(n) sur une entrée triée. Cela contredit-il la borne inférieure Ω(n log n) des tris par comparaisons ?

1. ANon, car le tri par insertion n'est pas un tri par comparaisons
2. BOui, la borne inférieure est donc fausse
3. COui, mais seulement pour les tableaux de moins de 100 éléments
4. DNon, la borne inférieure s'applique au pire cas sur toutes les entrées, pas à chaque entrée