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

Quelle est la complexité temporelle du tri fusion dans le pire cas ?

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

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 insère chaque élément dans une partie triée croissante par décalages
3. CIl divise le tableau en deux moitiés et les fusionne
4. DIl échange à plusieurs reprises les éléments voisins mal ordonnés

La complexité spatiale mesure :

1. ALa taille physique de l'ordinateur
2. BLa quantité de mémoire dont un algorithme a besoin lorsque la taille de l'entrée augmente
3. CL'espace disque du fichier du programme une fois compilé
4. DLe nombre de lignes de code

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

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

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

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

Quelle est la complexité temporelle de l'algorithme standard de programmation dynamique pour la plus longue sous-séquence commune de chaînes de longueurs m et n ?

1. AO(mn log n)
2. BO(mn)
3. CO(m + n)
4. DO(2^m+n)

Quelles sont les deux choses à montrer pour prouver qu'un problème de décision X est NP-complet ?

1. AX n'a pas d'algorithme polynomial, et X est décidable
2. BX est dans P, et X se réduit à SAT
3. CX est dans NP, et un problème NP-complet connu se réduit à X en temps polynomial
4. DX se réduit à un problème de P, et X est dans NP

Qu'a établi le théorème de Cook-Levin ?

1. ATout problème NP peut être résolu en temps exponentiel
2. BLe problème de satisfiabilité booléenne (SAT) est NP-complet
3. CLe problème de l'arrêt est indécidable
4. DP est différent de NP