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

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

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

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

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

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

1. AO(k log n)
2. BO(n + k)
3. CO(n log n)
4. DO(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 3 pièces ; l'optimum est 3
3. CLe glouton utilise 3 pièces ; l'optimum est 2
4. DLe glouton utilise 4 pièces ; l'optimum est 3

Quelle est la complexité temporelle de la multiplication de deux matrices n × n avec la triple boucle standard ?

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

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)
4. DO(n log n)

Quelle affirmation concernant P et NP est correcte ?

1. AIl a été démontré que P ≠ NP
2. BLes solutions des problèmes NP ne peuvent pas être vérifiées rapidement
3. CNP signifie « non polynomial »
4. DTout problème de P appartient aussi à NP

Lequel de ces problèmes de satisfiabilité est connu pour être résoluble en temps polynomial ?

1. ASAT général sur des formules en forme normale conjonctive
2. B2-SAT, où chaque clause a au plus deux littéraux
3. C3-SAT, où chaque clause a exactement trois littéraux
4. DLa satisfiabilité de circuits