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

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

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

L'accès à un élément d'un tableau par son indice prend :

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

Quel algorithme de tri choisit un pivot et partitionne le tableau en éléments plus petits et plus grands ?

1. ALe tri à bulles
2. BLe tri rapide (quicksort)
3. CLe tri fusion
4. DLe tri par insertion

Quelle est la complexité temporelle de : pour i = 1 à n : (j = 1 ; tant que j < n : j = j × 2) ?

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

Combien de niveaux comporte la récursion du tri fusion pour un tableau de n éléments ?

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

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

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

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

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

Pourquoi l'algorithme de Dijkstra peut-il donner des résultats faux lorsque certains poids d'arêtes sont négatifs ?

1. AUn sommet est définitivement fixé lorsqu'il est extrait, mais une arête négative ultérieure pourrait encore lui donner un chemin plus court
2. BIl ne fonctionne que sur les graphes non orientés
3. CLes nombres négatifs ne peuvent pas être stockés dans une file de priorité
4. DIl entre dans une boucle infinie à chaque arête négative