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

Lequel de ces temps d'exécution est polynomial ?

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

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

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

Comment fonctionne le tri par sélection ?

1. AIl cherche à plusieurs reprises le minimum de la partie non triée et l'échange vers l'avant
2. BIl divise le tableau en deux moitiés et les fusionne
3. CIl insère chaque élément dans une partie triée croissante par décalages
4. DIl échange à plusieurs reprises les éléments voisins mal ordonnés

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

1. AO(1)
2. BO(n)
3. CO(n log n)
4. DO(log 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)

Une fonction exécute une boucle de n itérations, puis, séparément, une autre boucle de n itérations. Quelle est sa complexité temporelle ?

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

Le problème du sac à dos 0/1 résolu par programmation dynamique prend un temps O(nW). Pourquoi dit-on qu'il est pseudo-polynomial ?

1. AW est un nombre, donc le temps est exponentiel en le nombre de bits utilisés pour écrire W
2. BParce que l'algorithme est probabiliste et que son temps d'exécution varie à chaque entrée
3. CParce qu'il ne fonctionne que pour W = 0
4. DParce que n est toujours petit

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

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