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

Que décrit le temps d'exécution en moyenne ?

  1. ALe temps pour une entrée de longueur moyenne
  2. BLe temps espéré selon une distribution donnée des entrées de taille n
  3. CLe temps sur l'ordinateur le plus répandu
  4. DLa valeur intermédiaire entre les temps d'exécution du meilleur et du pire cas
2.Facile

Quelle notation décrit une borne supérieure de la croissance ?

  1. AGrand Thêta (Big Theta)
  2. BPetit oméga (little omega)
  3. CGrand O (Big O)
  4. DGrand Oméga (Big Omega)
3.Facile

L'accès à un élément d'un tableau par son indice prend :

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

Un algorithme glouton :

  1. AN'utilise que la récursivité
  2. BDonne toujours la solution optimale
  3. CEssaie toutes les solutions possibles
  4. DFait le meilleur choix local à chaque étape
5.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 de longueur 2
  3. CUn tableau déjà trié
  4. DUn tableau dont tous les éléments sont distincts
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 a peu de surcoût et est rapide sur les entrées petites ou presque triées
  2. BLe tri par insertion est en O(n log n) dans le pire cas
  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. AChoisir le pivot uniformément au hasard
  2. BToujours choisir le premier élément
  3. CN'utiliser la récursivité que sur la partie gauche
  4. DTrier l'entrée avant d'exécuter le tri rapide
8.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

Corrigé

  1. 1. B · Le temps espéré selon une distribution donnée des entrées de taille n
  2. 2. C · Grand O (Big O)
  3. 3. D · O(1)
  4. 4. D · Fait le meilleur choix local à chaque étape
  5. 5. C · Un tableau déjà trié
  6. 6. A · Le tri par insertion a peu de surcoût et est rapide sur les entrées petites ou presque triées
  7. 7. A · Choisir le pivot uniformément au hasard
  8. 8. C · Tout problème de NP pourrait être résolu en temps polynomial, donc P = NP

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