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

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

1. AConvertir automatiquement une récursion en boucle équivalente, si bien qu'aucune pile d'appels n'est nécessaire
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. DStocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire

Que vaut log₂ 1024 ?

1. A10
2. B32
3. C12
4. D512

Quelle notation décrit une borne inférieure de croissance ?

1. AΘ (grand Thêta)
2. BO (grand O)
3. CΩ (grand Oméga)
4. Do (petit o)

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 continue de s'appeler jusqu'au débordement de la pile d'appels
3. CElle renvoie automatiquement 0
4. DLe compilateur la transforme toujours en une boucle qui se termine sans danger

Quel espace de pile utilise une fonction factorielle récursive simple fact(n) = n × fact(n − 1) ?

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

Avec des pièces de 1, 3 et 4 et un montant de 6, combien de pièces utilise la méthode gloutonne « la plus grosse pièce d'abord », comparée à l'optimum ?

1. ALe glouton utilise 2 pièces ; l'optimum est 2
2. BLe glouton utilise 4 pièces ; l'optimum est 3
3. CLe glouton utilise 3 pièces ; l'optimum est 2
4. DLe glouton utilise 3 pièces ; l'optimum est 3

Quelle borne est correcte pour log(n!) ?

1. AΘ(n log n)
2. BΘ(n²)
3. CΘ(log n)
4. DΘ(n)

D'après le théorème maître, T(n) = 8T(n/2) + O(n²) a pour solution :

1. AΘ(n²)
2. BΘ(n³)
3. CΘ(n log n)
4. DΘ(n² log n)