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

La complexité spatiale mesure :

  1. ALe nombre de lignes de code
  2. BLa taille physique de l'ordinateur
  3. CLa quantité de mémoire dont un algorithme a besoin lorsque la taille de l'entrée augmente
  4. DL'espace disque du fichier du programme une fois compilé
2.Facile

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

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

Combien de mémoire supplémentaire utilise un tri fusion standard sur tableau ?

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

La récurrence T(n) = 2T(n/2) + O(n) a pour solution :

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

Que calcule l'algorithme de Floyd-Warshall, et en combien de temps ?

  1. ALes plus courts chemins entre toutes les paires de sommets en O(V³)
  2. BUn arbre couvrant de poids minimal en O(E log V)
  3. CUn ordre topologique en O(V²)
  4. DLes plus courts chemins depuis un sommet source vers tous les autres en O(V + E)
6.Moyen

Pourquoi de nombreuses routines de tri des bibliothèques passent-elles au tri par insertion pour les très petits sous-tableaux ?

  1. ALe tri par insertion est en O(n log n) dans le pire cas
  2. BLe tri par insertion a peu de surcoût et est rapide sur les entrées petites ou presque triées
  3. CLe tri par insertion utilise moins de mémoire que tout autre algorithme de tri sur les grandes entrées
  4. DLes algorithmes récursifs ne peuvent pas traiter les tableaux de moins de 10 éléments
7.Difficile

Quelle technique donne au tri rapide un temps d'exécution espéré en O(n log n) pour toute entrée ?

  1. ATrier l'entrée avant d'exécuter le tri rapide
  2. BN'utiliser la récursivité que sur la partie gauche
  3. CToujours choisir le premier élément
  4. DChoisir le pivot uniformément au hasard
8.Difficile

D'après le théorème maître, T(n) = 8T(n/2) + O(n²) a pour solution :

  1. AΘ(n log n)
  2. BΘ(n²)
  3. CΘ(n³)
  4. DΘ(n² log n)

Corrigé

  1. 1. C · La quantité de mémoire dont un algorithme a besoin lorsque la taille de l'entrée augmente
  2. 2. C · O(n²)
  3. 3. C · O(n)
  4. 4. B · O(n log n)
  5. 5. A · Les plus courts chemins entre toutes les paires de sommets en O(V³)
  6. 6. B · Le tri par insertion a peu de surcoût et est rapide sur les entrées petites ou presque triées
  7. 7. D · Choisir le pivot uniformément au hasard
  8. 8. C · Θ(n³)

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