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. ALibérer la mémoire après le retour d'une fonction
  2. BConvertir automatiquement une récursion en boucle équivalente, si bien qu'aucune pile d'appels n'est nécessaire
  3. CÉcrire des commentaires à côté de chaque ligne de code
  4. DStocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire
2.Facile

Quelles sont les trois étapes d'un algorithme « diviser pour régner » ?

  1. ADeviner, vérifier, recommencer
  2. BDiviser, régner, combiner
  3. CTrier, chercher, renvoyer
  4. DLire, calculer, écrire
3.Facile

Que signifie qu'une opération s'exécute en temps O(1) ?

  1. AElle prend toujours exactement une seconde
  2. BSon temps d'exécution n'augmente pas avec la taille de l'entrée
  3. CElle ne peut être exécutée qu'une seule fois
  4. DElle traite exactement un élément par seconde de temps d'exécution
4.Moyen

Que mesure l'analyse amortie ?

  1. ALe coût d'un algorithme sur la meilleure entrée
  2. BLe coût espéré sur des entrées aléatoires
  3. CLe coût moyen par opération sur une suite d'opérations de pire cas
  4. DLe coût de l'unique opération la plus chère, où qu'elle se trouve dans la suite
5.Moyen

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

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

Quelle est la complexité temporelle du calcul du n-ième nombre de Fibonacci avec une table remplie de bas en haut ?

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

D'après le théorème maître, T(n) = 8T(n/2) + O(n²) a pour solution :

  1. AΘ(n² log n)
  2. BΘ(n log n)
  3. CΘ(n³)
  4. DΘ(n²)
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(n) en temps et O(1) en espace
  2. BO(n) en temps et O(n) en espace
  3. CO(log n) en temps et O(n) en espace
  4. DO(2ⁿ) en temps et O(1) en espace

Corrigé

  1. 1. D · Stocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire
  2. 2. B · Diviser, régner, combiner
  3. 3. B · Son temps d'exécution n'augmente pas avec la taille de l'entrée
  4. 4. C · Le coût moyen par opération sur une suite d'opérations de pire cas
  5. 5. A · Des logarithmes de bases différentes ne diffèrent que d'un facteur constant
  6. 6. A · O(n)
  7. 7. C · Θ(n³)
  8. 8. A · O(n) en temps et O(1) en espace

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