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

Qu'est-ce que le cas de base d'une fonction récursive ?

  1. ALa première ligne de la fonction
  2. BUn cas traité directement, sans nouvel appel récursif
  3. CL'appel qui utilise le plus de mémoire
  4. DLe cas avec l'entrée la plus grande, traité avant tout appel récursif
2.Facile

Quelle notation décrit une borne inférieure de croissance ?

  1. AO (grand O)
  2. BΘ (grand Thêta)
  3. Co (petit o)
  4. DΩ (grand Oméga)
3.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
4.Moyen

La complexité temporelle de la version récursive naïve de Fibonacci (fib(n) = fib(n−1) + fib(n−2)) est :

  1. ALogarithmique
  2. BConstante
  3. CExponentielle
  4. DLinéaire
5.Moyen

Quel énoncé sur une fonction récursive sans cas de base atteignable est correct ?

  1. AElle continue de s'appeler jusqu'au débordement de la pile d'appels
  2. BLe compilateur la transforme toujours en une boucle qui se termine sans danger
  3. CElle renvoie automatiquement 0
  4. DElle s'exécute en temps O(1)
6.Moyen

Est-il correct de dire qu'un algorithme en O(n²) est aussi en O(n³) ?

  1. ANon, car n³ est plus petit que n² pour n grand
  2. BOui, car le grand O est une borne supérieure et n² ne croît pas plus vite que n³
  3. CNon, car le grand O doit toujours donner le taux de croissance exact de la fonction
  4. DOui, mais seulement si n est inférieur à 100
7.Difficile

Qu'a établi le théorème de Cook-Levin ?

  1. AP est différent de NP
  2. BLe problème de satisfiabilité booléenne (SAT) est NP-complet
  3. CTout problème NP peut être résolu en temps exponentiel
  4. DLe problème de l'arrêt est indécidable
8.Difficile

Prendre les deux extrémités de chaque arête d'un couplage maximal donne une couverture par sommets. Quelle est la qualité de cette couverture ?

  1. ADe qualité inconnue par rapport à l'optimum
  2. BAu plus log n fois le minimum
  3. CToujours une couverture par sommets minimale
  4. DAu plus deux fois la taille d'une couverture par sommets minimale

Corrigé

  1. 1. B · Un cas traité directement, sans nouvel appel récursif
  2. 2. D · Ω (grand Oméga)
  3. 3. C · Son temps d'exécution n'augmente pas avec la taille de l'entrée
  4. 4. C · Exponentielle
  5. 5. A · Elle continue de s'appeler jusqu'au débordement de la pile d'appels
  6. 6. B · Oui, car le grand O est une borne supérieure et n² ne croît pas plus vite que n³
  7. 7. B · Le problème de satisfiabilité booléenne (SAT) est NP-complet
  8. 8. D · Au plus deux fois la taille d'une couverture par sommets minimale

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