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 fusion
3. CTri à bulles
4. DTri par tas

Quelle stratégie de conception utilise le tri fusion ?

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

Combien de mémoire supplémentaire utilise un tri fusion standard sur tableau ?

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

Quel algorithme trouve les plus courts chemins depuis une source dans un graphe dont les poids des arêtes sont positifs ou nuls ?

1. ALe parcours en profondeur (DFS)
2. BL'algorithme de Dijkstra
3. CL'algorithme de Kruskal
4. DBellman-Ford est nécessaire dans tous les cas

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. BUn ordre topologique en O(V²)
3. CLes plus courts chemins depuis un sommet source vers tous les autres en O(V + E)
4. DUn arbre couvrant de poids minimal en O(E log V)

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)

Les plus courts chemins simples peuvent être trouvés en temps polynomial. Que sait-on de la recherche du plus long chemin simple entre deux sommets dans un graphe quelconque ?

1. AC'est indécidable
2. BOn peut le résoudre avec l'algorithme de Dijkstra en prenant l'opposé des poids
3. CC'est toujours résoluble en O(V + E)
4. DC'est NP-difficile

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)