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 algorithme de tri échange de façon répétée les éléments adjacents qui sont dans le mauvais ordre ?

  1. ATri rapide (quicksort)
  2. BTri fusion
  3. CTri à bulles
  4. DTri par tas
2.Facile

Que vaut log₂ 1024 ?

  1. A512
  2. B10
  3. C12
  4. D32
3.Facile

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

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

Que signifie qu'un problème possède une sous-structure optimale ?

  1. AUne solution optimale peut être construite à partir de solutions optimales de ses sous-problèmes
  2. BTous les sous-problèmes ont la même taille
  3. CLe problème a exactement une solution optimale, que partagent tous les sous-problèmes
  4. DLe problème peut être résolu en temps constant
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 dont tous les éléments sont distincts
  2. BUn tableau déjà trié
  3. CUn tableau de longueur 2
  4. DUn tableau dans un ordre aléatoire
6.Moyen

Dans le problème de sélection d'activités, quelle règle gloutonne donne toujours un nombre maximal d'activités sans chevauchement ?

  1. AChoisir l'activité qui se termine le plus tôt, puis recommencer avec les activités compatibles
  2. BChoisir d'abord l'activité ayant le moins de chevauchements, puis recommencer avec les activités compatibles
  3. CChoisir l'activité qui commence le plus tôt
  4. DChoisir d'abord l'activité la plus courte
7.Difficile

Le problème de l'arrêt montre que :

  1. ATout programme finit par s'arrêter
  2. BIl faut éviter les boucles
  3. CAucun algorithme ne peut décider, pour tout programme et toute entrée, si le programme s'arrête
  4. DCertains programmes s'exécutent plus vite sur des ordinateurs plus rapides, donc l'arrêt dépend du matériel
8.Difficile

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

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

Corrigé

  1. 1. C · Tri à bulles
  2. 2. B · 10
  3. 3. B · Le temps espéré selon une distribution donnée des entrées de taille n
  4. 4. A · Une solution optimale peut être construite à partir de solutions optimales de ses sous-problèmes
  5. 5. B · Un tableau déjà trié
  6. 6. A · Choisir l'activité qui se termine le plus tôt, puis recommencer avec les activités compatibles
  7. 7. C · Aucun algorithme ne peut décider, pour tout programme et toute entrée, si le programme s'arrête
  8. 8. D · Θ(n log² n)

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