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

Quel est le grand O de 3n² + 5n + 2 ?

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

Quelle est la complexité temporelle de la recherche de la plus grande valeur dans un tableau non trié de n nombres ?

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

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

  1. AΘ (grand Thêta)
  2. BO (grand O)
  3. CΩ (grand Oméga)
  4. Do (petit o)
4.Moyen

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

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

Quel algorithme trouve les plus courts chemins depuis une source dans un graphe dont les poids des arêtes sont positifs ou nuls ?

  1. AL'algorithme de Dijkstra
  2. BLe parcours en profondeur (DFS)
  3. CL'algorithme de Kruskal
  4. DBellman-Ford est nécessaire dans tous les cas
6.Moyen

Quel est le temps d'exécution du tri par base LSD sur n entiers de d chiffres en base k ?

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

Le problème de l'arrêt montre que :

  1. ACertains programmes s'exécutent plus vite sur des ordinateurs plus rapides, donc l'arrêt dépend du matériel
  2. BIl faut éviter les boucles
  3. CAucun algorithme ne peut décider, pour tout programme et toute entrée, si le programme s'arrête
  4. DTout programme finit par s'arrêter
8.Difficile

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

  1. AUn 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
  2. BLes deux signifient que le problème n'a aucun algorithme
  3. CLes problèmes indécidables sont dans NP, tandis que les problèmes intraitables sont dans P
  4. DLes problèmes intraitables ne peuvent être résolus par aucun algorithme, tandis que les indécidables demandent seulement un temps exponentiel

Corrigé

  1. 1. B · O(n²)
  2. 2. C · O(n)
  3. 3. C · Ω (grand Oméga)
  4. 4. D · Elle continue de s'appeler jusqu'au débordement de la pile d'appels
  5. 5. A · L'algorithme de Dijkstra
  6. 6. D · O(d(n + k))
  7. 7. C · Aucun algorithme ne peut décider, pour tout programme et toute entrée, si le programme s'arrête
  8. 8. A · 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.