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

La complexité spatiale mesure :

  1. ALa taille physique de l'ordinateur
  2. BLa quantité de mémoire dont un algorithme a besoin lorsque la taille de l'entrée augmente
  3. CLe nombre de lignes de code
  4. DL'espace disque du fichier du programme une fois compilé
2.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
3.Facile

Quelle notation décrit une borne supérieure de la croissance ?

  1. AGrand Oméga (Big Omega)
  2. BGrand Thêta (Big Theta)
  3. CPetit oméga (little omega)
  4. DGrand O (Big O)
4.Moyen

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

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

Pourquoi omet-on généralement la base du logarithme dans la notation grand O, comme dans O(log n) ?

  1. ADes logarithmes de bases différentes ne diffèrent que d'un facteur constant
  2. BTous les logarithmes en informatique sont en base 10, elle est donc implicite
  3. CLes logarithmes sont toujours arrondis à l'entier
  4. DLa base n'a d'importance que pour n petit
6.Moyen

Quel algorithme de tri est stable ?

  1. ATri par sélection (version habituelle)
  2. BTri par tas
  3. CTri rapide (version en place habituelle)
  4. DTri fusion
7.Difficile

Quel énoncé sur la sélection du k-ième plus petit élément d'un tableau non trié est correct ?

  1. AQuickselect s'exécute en O(log n) dans le pire cas, car il ne récurse que d'un seul côté du pivot
  2. BLa sélection n'est possible qu'en O(n²)
  3. CQuickselect s'exécute en O(n) en espérance, et la médiane des médianes garantit O(n) dans le pire cas
  4. DLa sélection exige toujours Ω(n log n) car elle nécessite un tri
8.Difficile

Lequel de ces problèmes de satisfiabilité est connu pour être résoluble en temps polynomial ?

  1. ALa satisfiabilité de circuits
  2. B3-SAT, où chaque clause a exactement trois littéraux
  3. CSAT général sur des formules en forme normale conjonctive
  4. D2-SAT, où chaque clause a au plus deux littéraux

Corrigé

  1. 1. B · La quantité de mémoire dont un algorithme a besoin lorsque la taille de l'entrée augmente
  2. 2. A · Environ log₂ n
  3. 3. D · Grand O (Big O)
  4. 4. B · O(n²)
  5. 5. A · Des logarithmes de bases différentes ne diffèrent que d'un facteur constant
  6. 6. D · Tri fusion
  7. 7. C · Quickselect s'exécute en O(n) en espérance, et la médiane des médianes garantit O(n) dans le pire cas
  8. 8. D · 2-SAT, où chaque clause a au plus deux littéraux

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