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. ALinéaire
  2. BPolynomiale
  3. CExponentielle
  4. DLogarithmique
2.Facile

Qu'est-ce que le cas de base d'une fonction récursive ?

  1. AL'appel qui utilise le plus de mémoire
  2. BLe cas avec l'entrée la plus grande, traité avant tout appel récursif
  3. CUn cas traité directement, sans nouvel appel récursif
  4. DLa première ligne de la fonction
3.Facile

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

  1. ALa valeur intermédiaire entre les temps d'exécution du meilleur et du pire cas
  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. DLe temps sur l'ordinateur le plus répandu
4.Moyen

Pourquoi omet-on généralement la base du logarithme dans la notation grand O, comme dans O(log n) ?

  1. ALa base n'a d'importance que pour n petit
  2. BLes logarithmes sont toujours arrondis à l'entier
  3. CDes logarithmes de bases différentes ne diffèrent que d'un facteur constant
  4. DTous les logarithmes en informatique sont en base 10, elle est donc implicite
5.Moyen

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

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

Une fonction exécute une boucle de n itérations, puis, séparément, une autre boucle de n itérations. Quelle est sa complexité temporelle ?

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

Pourquoi une recherche dans une table de hachage est-elle en O(1) en moyenne mais en O(n) dans le pire cas ?

  1. ADe nombreuses clés peuvent entrer en collision dans le même compartiment
  2. BLes fonctions de hachage sont lentes
  3. CLes clés doivent d'abord être triées
  4. DL'accès aux tableaux est en O(n)
8.Difficile

Le problème du sac à dos 0/1 résolu par programmation dynamique prend un temps O(nW). Pourquoi dit-on qu'il est pseudo-polynomial ?

  1. AParce que l'algorithme est probabiliste et que son temps d'exécution varie à chaque entrée
  2. BW est un nombre, donc le temps est exponentiel en le nombre de bits utilisés pour écrire W
  3. CParce qu'il ne fonctionne que pour W = 0
  4. DParce que n est toujours petit

Corrigé

  1. 1. C · Exponentielle
  2. 2. C · Un cas traité directement, sans nouvel appel récursif
  3. 3. B · Le temps espéré selon une distribution donnée des entrées de taille n
  4. 4. C · Des logarithmes de bases différentes ne diffèrent que d'un facteur constant
  5. 5. B · O(n²)
  6. 6. A · O(n)
  7. 7. A · De nombreuses clés peuvent entrer en collision dans le même compartiment
  8. 8. B · W est un nombre, donc le temps est exponentiel en le nombre de bits utilisés pour écrire W

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