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

Que décrit le temps d'exécution dans le pire cas d'un algorithme ?

  1. ALe temps sur la plus petite entrée
  2. BLe temps espéré sur une entrée aléatoire de taille n
  3. CLe temps maximal sur toutes les entrées de taille n
  4. DLe temps sur un ordinateur lent
2.Facile

Quel est le grand O de 3n² + 5n + 2 ?

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

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

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

Quelle est la complexité temporelle amortie de l'ajout en fin de tableau dynamique qui double sa capacité lorsqu'il est plein ?

  1. AO(n)
  2. BO(log n)
  3. CO(1)
  4. DO(n²)
5.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. BDes logarithmes de bases différentes ne diffèrent que d'un facteur constant
  3. CLes logarithmes sont toujours arrondis à l'entier
  4. DTous les logarithmes en informatique sont en base 10, elle est donc implicite
6.Moyen

Que mesure l'analyse amortie ?

  1. ALe coût espéré sur des entrées aléatoires
  2. BLe coût de l'unique opération la plus chère, où qu'elle se trouve dans la suite
  3. CLe coût d'un algorithme sur la meilleure entrée
  4. DLe coût moyen par opération sur une suite d'opérations de pire cas
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. BSeul ce problème passerait dans P
  3. CLe problème de l'arrêt deviendrait décidable
  4. DTout problème de NP pourrait être résolu en temps polynomial, donc P = NP
8.Difficile

Quelle définition de la classe P est correcte ?

  1. ALes problèmes de décision résolubles par un algorithme déterministe en temps polynomial
  2. BLes problèmes dont les solutions peuvent être vérifiées mais jamais trouvées en temps polynomial
  3. CLes problèmes qui peuvent être résolus en parallèle
  4. DLes problèmes qui demandent un temps exponentiel sur tout ordinateur

Corrigé

  1. 1. C · Le temps maximal sur toutes les entrées de taille n
  2. 2. B · O(n²)
  3. 3. A · O(n log n)
  4. 4. C · O(1)
  5. 5. B · Des logarithmes de bases différentes ne diffèrent que d'un facteur constant
  6. 6. D · Le coût moyen par opération sur une suite d'opérations de pire cas
  7. 7. D · Tout problème de NP pourrait être résolu en temps polynomial, donc P = NP
  8. 8. A · Les problèmes de décision résolubles par un algorithme déterministe en temps polynomial

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