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

Laquelle de ces fonctions croît le plus lentement quand n devient grand ?

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

Quelles sont les trois étapes d'un algorithme « diviser pour régner » ?

  1. ATrier, chercher, renvoyer
  2. BLire, calculer, écrire
  3. CDeviner, vérifier, recommencer
  4. DDiviser, régner, combiner
3.Facile

Quel est le grand O de 3n² + 5n + 2 ?

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

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

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

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

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

Un tri rapide utilise toujours le premier élément comme pivot. Sur quelle entrée présente-t-il son comportement de pire cas ?

  1. AUn tableau dans un ordre aléatoire
  2. BUn tableau dont tous les éléments sont distincts
  3. CUn tableau de longueur 2
  4. DUn tableau déjà trié
7.Difficile

Pourquoi toute recherche par comparaisons dans un tableau trié nécessite-t-elle Ω(log n) comparaisons dans le pire cas ?

  1. ALa recherche dichotomique est le seul algorithme possible, et elle nécessite log₂ n comparaisons
  2. BChaque comparaison prend un temps logarithmique
  3. CChaque élément doit être comparé au moins une fois
  4. DUn arbre de décision à n issues possibles doit avoir une profondeur d'au moins log₂ n
8.Difficile

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

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

Corrigé

  1. 1. B · O(log n)
  2. 2. D · Diviser, régner, combiner
  3. 3. C · O(n²)
  4. 4. B · O(n³)
  5. 5. C · O(log n)
  6. 6. D · Un tableau déjà trié
  7. 7. D · Un arbre de décision à n issues possibles doit avoir une profondeur d'au moins log₂ n
  8. 8. D · 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.