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

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

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

Qu'exige la recherche dichotomique de son entrée ?

  1. ALe tableau doit être trié
  2. BLa longueur du tableau doit être une puissance de deux
  3. CLe tableau ne doit contenir que des nombres positifs
  4. DLe tableau ne doit pas avoir plus de 1000 éléments
3.Facile

Quelle est la complexité temporelle dans le pire cas du tri par insertion ?

  1. AO(n)
  2. BO(n log n)
  3. CO(n²)
  4. DO(log n)
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(n²)
  2. BO(dn log k)
  3. CO(d(n + k))
  4. DO(n log n)
5.Moyen

Le parcours en largeur (BFS) sur un graphe non pondéré trouve :

  1. ALes plus courts chemins dans les graphes qui contiennent des poids d'arêtes négatifs
  2. BUn ordre topologique dans tous les graphes
  3. CLes plus courts chemins en nombre d'arêtes depuis le nœud de départ
  4. DL'arbre couvrant de poids minimal
6.Moyen

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

Que se passerait-il si quelqu'un trouvait un algorithme en temps polynomial pour un problème NP-complet ?

  1. ASeul ce problème passerait dans P
  2. BTous les algorithmes en temps exponentiel s'exécuteraient immédiatement en temps linéaire
  3. CTout problème de NP pourrait être résolu en temps polynomial, donc P = NP
  4. DLe problème de l'arrêt deviendrait décidable
8.Difficile

L'algorithme de Strassen multiplie des matrices en utilisant 7 au lieu de 8 multiplications récursives de blocs de taille moitié. Quel est son temps d'exécution ?

  1. AΘ(n³)
  2. BΘ(n² log n)
  3. CΘ(nlog₂ 7), soit environ n2,81
  4. DΘ(n2)

Corrigé

  1. 1. A · O(n²)
  2. 2. A · Le tableau doit être trié
  3. 3. C · O(n²)
  4. 4. C · O(d(n + k))
  5. 5. C · Les plus courts chemins en nombre d'arêtes depuis le nœud de départ
  6. 6. B · Le glouton utilise 3 pièces ; l'optimum est 2
  7. 7. C · Tout problème de NP pourrait être résolu en temps polynomial, donc P = NP
  8. 8. C · Θ(nlog₂ 7), soit environ n2,81

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