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(2ⁿ)
  4. DO(n!)
2.Facile

Qu'est-ce que la récursivité ?

  1. AUne fonction qui s'appelle elle-même sur des entrées plus petites
  2. BUne boucle qui ne se termine jamais
  3. CUn type de structure de données
  4. DUne méthode de tri
3.Facile

Que signifie qu'une opération s'exécute en temps O(1) ?

  1. ASon temps d'exécution n'augmente pas avec la taille de l'entrée
  2. BElle ne peut être exécutée qu'une seule fois
  3. CElle traite exactement un élément par seconde de temps d'exécution
  4. DElle prend toujours exactement une seconde
4.Moyen

Quel algorithme de tri est stable ?

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

Quelle est la solution de la récurrence T(n) = T(n − 1) + O(n) ?

  1. AO(2ⁿ)
  2. BO(n²)
  3. CO(n log n)
  4. DO(n)
6.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 log n)
  2. BO(n)
  3. CO(log n)
  4. DO(n²)
7.Difficile

Le tri topologique n'est possible que pour :

  1. ALes graphes à poids négatifs
  2. BLes graphes non orientés
  3. CLes graphes orientés acycliques (DAG)
  4. DLes graphes complets
8.Difficile

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

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

Corrigé

  1. 1. A · O(n³)
  2. 2. A · Une fonction qui s'appelle elle-même sur des entrées plus petites
  3. 3. A · Son temps d'exécution n'augmente pas avec la taille de l'entrée
  4. 4. B · Tri fusion
  5. 5. B · O(n²)
  6. 6. B · O(n)
  7. 7. C · Les graphes orientés acycliques (DAG)
  8. 8. A · Aucun algorithme ne peut décider, pour tout programme et toute entrée, si le programme s'arrête

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