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

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

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

Que vaut log₂ 1024 ?

1. A512
2. B32
3. C12
4. D10

Qu'est-ce que la mémoïsation ?

1. ALibérer la mémoire après le retour d'une fonction
2. BConvertir automatiquement une récursion en boucle équivalente, si bien qu'aucune pile d'appels n'est nécessaire
3. CÉcrire des commentaires à côté de chaque ligne de code
4. DStocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire

La programmation dynamique est utile lorsqu'un problème présente :

1. AAucun sous-problème, de sorte qu'il peut être résolu en une seule étape
2. BDes sous-problèmes qui se chevauchent et une sous-structure optimale
3. CUne seule boucle
4. DUniquement des entrées aléatoires

Un tri rapide utilise toujours le premier élément comme pivot. Sur quelle entrée présente-t-il son comportement de pire cas ?

1. AUn tableau dans un ordre aléatoire
2. BUn tableau déjà trié
3. CUn tableau de longueur 2
4. DUn tableau dont tous les éléments sont distincts

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

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

Comment l'algorithme de Bellman-Ford détecte-t-il un cycle de poids négatif accessible depuis la source ?

1. AIl exécute deux fois l'algorithme de Dijkstra et compare les deux résultats de distances
2. BAprès V − 1 tours, il vérifie si une arête peut encore être relâchée
3. CIl vérifie si une arête a un poids négatif
4. DIl compte les cycles par un parcours en profondeur

Quelle définition de la classe P est correcte ?

1. ALes problèmes de décision résolubles par un algorithme déterministe en temps polynomial
2. BLes problèmes qui peuvent être résolus en parallèle
3. CLes problèmes dont les solutions peuvent être vérifiées mais jamais trouvées en temps polynomial
4. DLes problèmes qui demandent un temps exponentiel sur tout ordinateur