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

Qu'est-ce que la récursivité ?

1. AUne méthode de tri
2. BUn type de structure de données
3. CUne boucle qui ne se termine jamais
4. DUne fonction qui s'appelle elle-même sur des entrées plus petites

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

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

Quelle est la complexité temporelle de la recherche dichotomique dans un tableau trié ?

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

Comment l'algorithme de Prim construit-il un arbre couvrant de poids minimal ?

1. AIl supprime l'arête la plus chère jusqu'à ce qu'il ne reste plus de cycle
2. BIl trie toutes les arêtes par poids et ajoute chacune d'elles sauf si elle formait un cycle dans la forêt
3. CIl exécute un parcours en largeur et conserve l'arbre du BFS
4. DIl fait croître un seul arbre à partir d'un sommet de départ, en ajoutant l'arête la moins chère qui sort de l'arbre

Quel énoncé sur une fonction récursive sans cas de base atteignable est correct ?

1. AElle s'exécute en temps O(1)
2. BElle renvoie automatiquement 0
3. CElle continue de s'appeler jusqu'au débordement de la pile d'appels
4. DLe compilateur la transforme toujours en une boucle qui se termine sans danger

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

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

L'algorithme de programmation dynamique de Held-Karp résout exactement le problème du voyageur de commerce. Quel est son temps d'exécution pour n villes ?

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

Quel est le temps d'exécution de l'algorithme de Dijkstra avec un tas binaire sur un graphe à V sommets et E arêtes ?

1. AO(V³)
2. BO(V + E)
3. CO(V × E)
4. DO((V + E) log V)