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

Fiche d’exercices de Algorithmes et complexité gratuite et imprimable : 8 exercices, du niveau facile au niveau examen, avec corrigé. Imprimez-la ou enregistrez-la en PDF.

Nouvelle ficheS’entraîner en ligne avec indices

Pour les enseignants : gratuite à imprimer, copier et utiliser en classe. Chaque nouvelle fiche a de nouvelles valeurs et son propre corrigé. Un lien vers ExamProblems sur la page de votre cours est apprécié.

Nom: ____________________   Date: ____________

1.Facile

Un algorithme comportant deux boucles imbriquées, chacune exécutée n fois, a généralement quelle complexité ?

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

Quelle est la complexité temporelle de la recherche de la plus grande valeur dans un tableau non trié de n nombres ?

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

Un algorithme en O(n) prend 3 secondes pour n = 1 million. Combien de temps prend-il environ pour n = 2 millions ?

  1. A9 secondes
  2. B6 secondes
  3. C3 secondes
  4. D12 secondes
4.Moyen

Quel est le temps d'exécution du tri par base LSD sur n entiers de d chiffres en base k ?

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

La complexité temporelle de la version récursive naïve de Fibonacci (fib(n) = fib(n−1) + fib(n−2)) est :

  1. ALinéaire
  2. BLogarithmique
  3. CConstante
  4. DExponentielle
6.Moyen

Quelle est la complexité temporelle de : pour i = 1 à n : (j = 1 ; tant que j < n : j = j × 2) ?

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

Un problème est NP-complet s'il :

  1. AEst résoluble en temps polynomial
  2. BEst hors de NP mais plus difficile que tous les problèmes NP, comme le problème de l'arrêt
  3. CAppartient à NP et si tout problème NP se réduit à lui en temps polynomial
  4. DEst impossible à résoudre
8.Difficile

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

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

Corrigé

  1. 1. C · O(n²)
  2. 2. A · O(n)
  3. 3. B · 6 secondes
  4. 4. B · O(d(n + k))
  5. 5. D · Exponentielle
  6. 6. A · O(n log n)
  7. 7. C · Appartient à NP et si tout problème NP se réduit à lui en temps polynomial
  8. 8. C · Le problème de satisfiabilité booléenne (SAT) est NP-complet

Corrigés complets pas à pas : entraînez-vous sur ce thème sur examproblems.com.