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 mémoïsation ?

  1. AStocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire
  2. BConvertir automatiquement une récursion en boucle équivalente, si bien qu'aucune pile d'appels n'est nécessaire
  3. CLibérer la mémoire après le retour d'une fonction
  4. DÉcrire des commentaires à côté de chaque ligne de code
2.Facile

Lequel de ces temps d'exécution est polynomial ?

  1. AO(2ⁿ)
  2. BO(n!)
  3. CO(n³)
  4. DO(nⁿ)
3.Facile

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

  1. ALinéaire
  2. BPolynomiale
  3. CLogarithmique
  4. DExponentielle
4.Moyen

Est-il correct de dire qu'un algorithme en O(n²) est aussi en O(n³) ?

  1. ANon, car le grand O doit toujours donner le taux de croissance exact de la fonction
  2. BOui, mais seulement si n est inférieur à 100
  3. CNon, car n³ est plus petit que n² pour n grand
  4. DOui, car le grand O est une borne supérieure et n² ne croît pas plus vite que n³
5.Moyen

Vous triez une fois un tableau de n éléments, puis répondez à k requêtes d'appartenance par recherche dichotomique. Quel est le coût total ?

  1. AO(nk)
  2. BO(n + k)
  3. CO(n log n + k log n)
  4. DO(k n log n)
6.Moyen

Dans un tableau trié, vous cherchez deux éléments dont la somme vaut une cible en déplaçant un pointeur depuis chaque extrémité vers l'intérieur. Quelle est la complexité temporelle ?

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

Pour montrer qu'un nouveau problème X est NP-difficile, que faut-il faire ?

  1. AMontrer que X n'a pas d'algorithme polynomial pour les petites entrées
  2. BMontrer que X peut être vérifié en temps polynomial
  3. CRéduire X à un problème NP-difficile connu en temps polynomial
  4. DRéduire un problème NP-difficile connu à X en temps polynomial
8.Difficile

Quels sont les coûts en temps et en espace du calcul du n-ième nombre de Fibonacci avec une boucle qui ne conserve que les deux dernières valeurs ?

  1. AO(log n) en temps et O(n) en espace
  2. BO(n) en temps et O(n) en espace
  3. CO(n) en temps et O(1) en espace
  4. DO(2ⁿ) en temps et O(1) en espace

Corrigé

  1. 1. A · Stocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire
  2. 2. C · O(n³)
  3. 3. D · Exponentielle
  4. 4. D · Oui, car le grand O est une borne supérieure et n² ne croît pas plus vite que n³
  5. 5. C · O(n log n + k log n)
  6. 6. B · O(n)
  7. 7. D · Réduire un problème NP-difficile connu à X en temps polynomial
  8. 8. C · O(n) en temps et O(1) en espace

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