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

Lequel de ces temps d'exécution est polynomial ?

  1. AO(nⁿ)
  2. BO(n³)
  3. CO(n!)
  4. DO(2ⁿ)
2.Facile

Quel algorithme de tri échange de façon répétée les éléments adjacents qui sont dans le mauvais ordre ?

  1. ATri rapide (quicksort)
  2. BTri par tas
  3. CTri à bulles
  4. DTri fusion
3.Facile

La complexité spatiale mesure :

  1. ALe nombre de lignes de code
  2. BLa taille physique de l'ordinateur
  3. CL'espace disque du fichier du programme une fois compilé
  4. DLa quantité de mémoire dont un algorithme a besoin lorsque la taille de l'entrée augmente
4.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)
  4. DO(n log n)
5.Moyen

Quelle est la complexité temporelle du tri rapide (quicksort) dans le pire cas ?

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

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

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

Quelle définition de la classe NP est correcte ?

  1. ALes problèmes qu'aucun algorithme ne peut résoudre
  2. BLes problèmes qui ne sont pas polynomiaux
  3. CLes problèmes qui ne peuvent pas être résolus en temps polynomial
  4. DLes problèmes de décision dont les réponses « oui » peuvent être vérifiées en temps polynomial à l'aide d'un certificat
8.Difficile

Comment l'algorithme de Bellman-Ford détecte-t-il un cycle de poids négatif accessible depuis la source ?

  1. AIl vérifie si une arête a un poids négatif
  2. BAprès V − 1 tours, il vérifie si une arête peut encore être relâchée
  3. CIl compte les cycles par un parcours en profondeur
  4. DIl exécute deux fois l'algorithme de Dijkstra et compare les deux résultats de distances

Corrigé

  1. 1. B · O(n³)
  2. 2. C · Tri à bulles
  3. 3. D · La quantité de mémoire dont un algorithme a besoin lorsque la taille de l'entrée augmente
  4. 4. C · O(n)
  5. 5. B · O(n²)
  6. 6. B · Les plus courts chemins entre toutes les paires de sommets en O(V³)
  7. 7. D · Les problèmes de décision dont les réponses « oui » peuvent être vérifiées en temps polynomial à l'aide d'un certificat
  8. 8. B · Après V − 1 tours, il vérifie si une arête peut encore être relâchée

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