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

Comment appelle-t-on une croissance en O(2ⁿ) ?

  1. ALogarithmique
  2. BLinéaire
  3. CPolynomiale
  4. DExponentielle
2.Facile

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

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

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

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

Un algorithme glouton :

  1. ADonne toujours la solution optimale
  2. BN'utilise que la récursivité
  3. CEssaie toutes les solutions possibles
  4. DFait le meilleur choix local à chaque étape
5.Moyen

Pourquoi la programmation dynamique n'apporte-t-elle aucune accélération réelle au tri fusion ?

  1. ALe tri fusion n'a pas de structure récursive
  2. BLe tri fusion est déjà en O(n)
  3. CLa programmation dynamique ne fonctionne que sur les problèmes de graphes, pas sur les tableaux
  4. DSes sous-problèmes ne se chevauchent pas, il n'y a donc rien à réutiliser
6.Moyen

Combien de niveaux comporte la récursion du tri fusion pour un tableau de n éléments ?

  1. AEnviron √n
  2. BEnviron log₂ n
  3. CEnviron n / 2
  4. DEnviron n
7.Difficile

Pour quelle variante du problème du sac à dos la règle gloutonne « prendre les objets par ordre de valeur par unité de poids » donne-t-elle toujours une réponse optimale ?

  1. ALe sac à dos fractionnaire, où les objets peuvent être fractionnés
  2. BLes deux variantes
  3. CLe sac à dos 0/1, où les objets doivent toujours être pris entiers
  4. DAucune des deux variantes
8.Difficile

Quelles sont les deux choses à montrer pour prouver qu'un problème de décision X est NP-complet ?

  1. AX n'a pas d'algorithme polynomial, et X est décidable
  2. BX est dans NP, et un problème NP-complet connu se réduit à X en temps polynomial
  3. CX est dans P, et X se réduit à SAT
  4. DX se réduit à un problème de P, et X est dans NP

Corrigé

  1. 1. D · Exponentielle
  2. 2. B · Grand O (Big O)
  3. 3. B · O(n²)
  4. 4. D · Fait le meilleur choix local à chaque étape
  5. 5. D · Ses sous-problèmes ne se chevauchent pas, il n'y a donc rien à réutiliser
  6. 6. B · Environ log₂ n
  7. 7. A · Le sac à dos fractionnaire, où les objets peuvent être fractionnés
  8. 8. B · X est dans NP, et un problème NP-complet connu se réduit à X en temps polynomial

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