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

Un algorithme en O(n²) prend 1 seconde pour n = 1000. Combien de temps prend-il environ pour n = 2000 ?

1. A4 secondes
2. B8 secondes
3. C1 seconde
4. D2 secondes

Quel est le temps d'exécution du tri par comptage pour n entiers compris entre 0 et k ?

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

Qu'est-ce qu'un algorithme de force brute ?

1. AUn algorithme qui s'exécute sur de nombreux processeurs
2. BUn algorithme qui devine une réponse au hasard
3. CUn algorithme qui essaie toutes les solutions candidates possibles
4. DUn algorithme qui utilise toujours la récursion

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

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

Quel énoncé sur une fonction récursive sans cas de base atteignable est correct ?

1. AElle renvoie automatiquement 0
2. BElle continue de s'appeler jusqu'au débordement de la pile d'appels
3. CElle s'exécute en temps O(1)
4. DLe compilateur la transforme toujours en une boucle qui se termine sans danger

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 3 pièces ; l'optimum est 3
2. BLe glouton utilise 2 pièces ; l'optimum est 2
3. CLe glouton utilise 3 pièces ; l'optimum est 2
4. DLe glouton utilise 4 pièces ; l'optimum est 3

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. CP est différent de NP
4. DLe problème de l'arrêt est indécidable

Pour quelle variante du problème du sac à dos la règle gloutonne « prendre les objets par ordre de valeur par unité de poids » donne-t-elle toujours une réponse optimale ?

1. ALes deux variantes
2. BLe sac à dos fractionnaire, où les objets peuvent être fractionnés
3. CLe sac à dos 0/1, où les objets doivent toujours être pris entiers
4. DAucune des deux variantes