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

Une boucle commence avec i = 1 et double i à chaque itération jusqu'à ce que i > n. Combien d'itérations effectue-t-elle ?

  1. AEnviron log₂ n
  2. BEnviron n / 2
  3. CEnviron n
  4. DEnviron n²
2.Facile

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

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

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

  1. ALe temps sur un ordinateur lent
  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 la plus petite entrée
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(1)
  2. BO(log n)
  3. CO(n)
  4. DO(n²)
5.Moyen

Un tri rapide utilise toujours le premier élément comme pivot. Sur quelle entrée présente-t-il son comportement de pire cas ?

  1. AUn tableau de longueur 2
  2. BUn tableau dans un ordre aléatoire
  3. CUn tableau déjà trié
  4. DUn tableau dont tous les éléments sont distincts
6.Moyen

Que calcule l'algorithme de Floyd-Warshall, et en combien de temps ?

  1. ALes plus courts chemins depuis un sommet source vers tous les autres en O(V + E)
  2. BUn ordre topologique en O(V²)
  3. CLes plus courts chemins entre toutes les paires de sommets en O(V³)
  4. DUn arbre couvrant de poids minimal en O(E log V)
7.Difficile

Pourquoi l'algorithme de Dijkstra peut-il donner des résultats faux lorsque certains poids d'arêtes sont négatifs ?

  1. AIl entre dans une boucle infinie à chaque arête négative
  2. BLes nombres négatifs ne peuvent pas être stockés dans une file de priorité
  3. CIl ne fonctionne que sur les graphes non orientés
  4. DUn sommet est définitivement fixé lorsqu'il est extrait, mais une arête négative ultérieure pourrait encore lui donner un chemin plus court
8.Difficile

Quelle est la différence entre un problème indécidable et un problème intraitable ?

  1. ALes deux signifient que le problème n'a aucun algorithme
  2. BLes problèmes intraitables ne peuvent être résolus par aucun algorithme, tandis que les indécidables demandent seulement un temps exponentiel
  3. CLes problèmes indécidables sont dans NP, tandis que les problèmes intraitables sont dans P
  4. DUn problème indécidable n'a aucun algorithme valable pour toutes les entrées ; un problème intraitable en a un, mais il est trop lent

Corrigé

  1. 1. A · Environ log₂ n
  2. 2. D · O(n log n)
  3. 3. C · Le temps maximal sur toutes les entrées de taille n
  4. 4. A · O(1)
  5. 5. C · Un tableau déjà trié
  6. 6. C · Les plus courts chemins entre toutes les paires de sommets en O(V³)
  7. 7. D · Un sommet est définitivement fixé lorsqu'il est extrait, mais une arête négative ultérieure pourrait encore lui donner un chemin plus court
  8. 8. D · Un problème indécidable n'a aucun algorithme valable pour toutes les entrées ; un problème intraitable en a un, mais il est trop lent

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