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 signifie qu'une opération s'exécute en temps O(1) ?

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

Qu'est-ce que la mémoïsation ?

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

Combien de mémoire supplémentaire utilise un tri fusion standard sur tableau ?

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

Quelle est la complexité temporelle de l'algorithme de Bellman-Ford sur un graphe à V sommets et E arêtes ?

  1. AO(V × E)
  2. BO(E log V)
  3. CO(V³ × E)
  4. DO(V + E)
5.Moyen

Dans le problème de sélection d'activités, quelle règle gloutonne donne toujours un nombre maximal d'activités sans chevauchement ?

  1. AChoisir l'activité qui se termine le plus tôt, puis recommencer avec les activités compatibles
  2. BChoisir l'activité qui commence le plus tôt
  3. CChoisir d'abord l'activité la plus courte
  4. DChoisir d'abord l'activité ayant le moins de chevauchements, puis recommencer avec les activités compatibles
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(n²)
  2. BO(log n)
  3. CO(n log n)
  4. DO(n)
7.Difficile

L'algorithme de Strassen multiplie des matrices en utilisant 7 au lieu de 8 multiplications récursives de blocs de taille moitié. Quel est son temps d'exécution ?

  1. AΘ(nlog₂ 7), soit environ n2,81
  2. BΘ(n³)
  3. CΘ(n2)
  4. DΘ(n² log 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(2ⁿ) 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(n) en temps et O(1) en espace

Corrigé

  1. 1. C · Son temps d'exécution n'augmente pas avec la taille de l'entrée
  2. 2. C · Stocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire
  3. 3. B · O(n)
  4. 4. A · O(V × E)
  5. 5. A · Choisir l'activité qui se termine le plus tôt, puis recommencer avec les activités compatibles
  6. 6. D · O(n)
  7. 7. A · Θ(nlog₂ 7), soit environ n2,81
  8. 8. D · O(n) en temps et O(1) en espace

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