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

Qu'est-ce que la récursivité ?

  1. AUne boucle qui ne se termine jamais
  2. BUn type de structure de données
  3. CUne fonction qui s'appelle elle-même sur des entrées plus petites
  4. DUne méthode de tri
2.Facile

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

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

Quelle est la complexité temporelle du parcours en profondeur d'un graphe stocké sous forme de listes d'adjacence ?

  1. AO(V²)
  2. BO(V + E)
  3. CO(E log V)
  4. DO(V × E)
4.Moyen

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

  1. AO(n²)
  2. BO(n log n)
  3. CO(log n)
  4. DO(n)
5.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 utilise moins de mémoire que tout autre algorithme de tri sur les grandes entrées
  3. CLes algorithmes récursifs ne peuvent pas traiter les tableaux de moins de 10 éléments
  4. DLe tri par insertion a peu de surcoût et est rapide sur les entrées petites ou presque triées
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 d'abord l'activité la plus courte
  2. BChoisir l'activité qui se termine le plus tôt, puis recommencer avec les activités compatibles
  3. CChoisir l'activité qui commence le plus tôt
  4. DChoisir d'abord l'activité ayant le moins de chevauchements, puis recommencer avec les activités compatibles
7.Difficile

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

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

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

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

Corrigé

  1. 1. C · Une fonction qui s'appelle elle-même sur des entrées plus petites
  2. 2. A · O(1)
  3. 3. B · O(V + E)
  4. 4. D · O(n)
  5. 5. D · Le tri par insertion a peu de surcoût et est rapide sur les entrées petites ou presque triées
  6. 6. B · Choisir l'activité qui se termine le plus tôt, puis recommencer avec les activités compatibles
  7. 7. C · Tout problème de NP pourrait être résolu en temps polynomial, donc P = NP
  8. 8. B · 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.