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 la mémoïsation ?

  1. ALibérer la mémoire après le retour d'une fonction
  2. BÉcrire des commentaires à côté de chaque ligne de code
  3. CStocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire
  4. DConvertir automatiquement une récursion en boucle équivalente, si bien qu'aucune pile d'appels n'est nécessaire
2.Facile

Quelle est la complexité temporelle du parcours en profondeur d'un graphe stocké sous forme de listes d'adjacence ?

  1. AO(V + E)
  2. BO(E log V)
  3. CO(V²)
  4. DO(V × E)
3.Facile

Quelles sont les trois étapes d'un algorithme « diviser pour régner » ?

  1. ADiviser, régner, combiner
  2. BTrier, chercher, renvoyer
  3. CDeviner, vérifier, recommencer
  4. DLire, calculer, écrire
4.Moyen

Pourquoi la programmation dynamique n'apporte-t-elle aucune accélération réelle au tri fusion ?

  1. ALe tri fusion n'a pas de structure récursive
  2. BSes sous-problèmes ne se chevauchent pas, il n'y a donc rien à réutiliser
  3. CLa programmation dynamique ne fonctionne que sur les problèmes de graphes, pas sur les tableaux
  4. DLe tri fusion est déjà en O(n)
5.Moyen

Quelle est la complexité temporelle de : pour i = 1 à n : pour j = 1 à i : faire un travail O(1) ?

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

Dans le problème de sélection d'activités, quelle règle gloutonne donne toujours un nombre maximal d'activités sans chevauchement ?

  1. AChoisir l'activité qui se termine le plus tôt, puis recommencer avec les activités compatibles
  2. BChoisir l'activité qui commence le plus tôt
  3. CChoisir d'abord l'activité la plus courte
  4. DChoisir d'abord l'activité ayant le moins de chevauchements, puis recommencer avec les activités compatibles
7.Difficile

La multiplication de Karatsuba vérifie T(n) = 3T(n/2) + O(n). Quelle en est la solution ?

  1. AΘ(n log n)
  2. BΘ(n²)
  3. CΘ(n3)
  4. DΘ(nlog₂ 3), soit environ n1,585
8.Difficile

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

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

Corrigé

  1. 1. C · Stocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire
  2. 2. A · O(V + E)
  3. 3. A · Diviser, régner, combiner
  4. 4. B · Ses sous-problèmes ne se chevauchent pas, il n'y a donc rien à réutiliser
  5. 5. C · O(n²)
  6. 6. A · Choisir l'activité qui se termine le plus tôt, puis recommencer avec les activités compatibles
  7. 7. D · Θ(nlog₂ 3), soit environ n1,585
  8. 8. D · Le problème de satisfiabilité booléenne (SAT) est NP-complet

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