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

Un algorithme en O(n) prend 3 secondes pour n = 1 million. Combien de temps prend-il environ pour n = 2 millions ?

  1. A9 secondes
  2. B6 secondes
  3. C3 secondes
  4. D12 secondes
2.Facile

Un algorithme comportant deux boucles imbriquées, chacune exécutée n fois, a généralement quelle complexité ?

  1. AO(n)
  2. BO(n²)
  3. CO(2n)
  4. DO(log n)
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 traite exactement un élément par seconde de temps d'exécution
  4. DElle ne peut être exécutée qu'une seule fois
4.Moyen

Comment l'algorithme de Prim construit-il un arbre couvrant de poids minimal ?

  1. AIl trie toutes les arêtes par poids et ajoute chacune d'elles sauf si elle formait un cycle dans la forêt
  2. BIl supprime l'arête la plus chère jusqu'à ce qu'il ne reste plus de cycle
  3. CIl fait croître un seul arbre à partir d'un sommet de départ, en ajoutant l'arête la moins chère qui sort de l'arbre
  4. DIl exécute un parcours en largeur et conserve l'arbre du BFS
5.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, car le grand O est une borne supérieure et n² ne croît pas plus vite que n³
  3. CNon, car n³ est plus petit que n² pour n grand
  4. DOui, mais seulement si n est inférieur à 100
6.Moyen

La récurrence T(n) = 2T(n/2) + O(n) a pour solution :

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

Le tri par insertion s'exécute en O(n) sur une entrée triée. Cela contredit-il la borne inférieure Ω(n log n) des tris par comparaisons ?

  1. AOui, la borne inférieure est donc fausse
  2. BNon, car le tri par insertion n'est pas un tri par comparaisons
  3. COui, mais seulement pour les tableaux de moins de 100 éléments
  4. DNon, la borne inférieure s'applique au pire cas sur toutes les entrées, pas à chaque entrée
8.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

Corrigé

  1. 1. B · 6 secondes
  2. 2. B · O(n²)
  3. 3. B · Son temps d'exécution n'augmente pas avec la taille de l'entrée
  4. 4. C · Il fait croître un seul arbre à partir d'un sommet de départ, en ajoutant l'arête la moins chère qui sort de l'arbre
  5. 5. B · Oui, car le grand O est une borne supérieure et n² ne croît pas plus vite que n³
  6. 6. B · O(n log n)
  7. 7. D · Non, la borne inférieure s'applique au pire cas sur toutes les entrées, pas à chaque entrée
  8. 8. D · Réduire un problème NP-difficile connu à X en temps polynomial

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