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

Quelle stratégie de conception utilise le tri fusion ?

  1. ALe choix glouton
  2. BLa force brute
  3. CLa programmation dynamique
  4. DDiviser pour régner
2.Facile

Que signifie f(n) = Θ(g(n)) ?

  1. Af croît au même rythme que g, bornée en haut et en bas par des multiples constants de g
  2. Bf croît strictement plus vite que g
  3. Cf est toujours plus petite que g pour tout n, donc g la borne par le haut mais jamais par le bas
  4. Df croît strictement moins vite que g
3.Facile

Qu'est-ce qu'un algorithme ?

  1. AUne suite finie d'étapes bien définies qui résout un problème
  2. BUn langage de programmation conçu pour écrire des formules mathématiques
  3. CUne structure de données qui stocke des nombres
  4. DTout programme informatique doté d'une interface graphique
4.Moyen

La borne inférieure du tri par comparaisons dans le pire cas est :

  1. AΩ(n²)
  2. BΩ(n log n)
  3. CΩ(log n)
  4. DΩ(n)
5.Moyen

Vous triez une fois un tableau de n éléments, puis répondez à k requêtes d'appartenance par recherche dichotomique. Quel est le coût total ?

  1. AO(nk)
  2. BO(k n log n)
  3. CO(n log n + k log n)
  4. DO(n + k)
6.Moyen

Le parcours en largeur (BFS) sur un graphe non pondéré trouve :

  1. AUn ordre topologique dans tous les graphes
  2. BLes plus courts chemins en nombre d'arêtes depuis le nœud de départ
  3. CLes plus courts chemins dans les graphes qui contiennent des poids d'arêtes négatifs
  4. DL'arbre couvrant de poids minimal
7.Difficile

Pour montrer qu'un nouveau problème X est NP-difficile, que faut-il faire ?

  1. ARéduire un problème NP-difficile connu à X en temps polynomial
  2. BMontrer que X peut être vérifié en temps polynomial
  3. CRéduire X à un problème NP-difficile connu en temps polynomial
  4. DMontrer que X n'a pas d'algorithme polynomial pour les petites entrées
8.Difficile

Quelle définition de la classe NP est correcte ?

  1. ALes problèmes de décision dont les réponses « oui » peuvent être vérifiées en temps polynomial à l'aide d'un certificat
  2. BLes problèmes qu'aucun algorithme ne peut résoudre
  3. CLes problèmes qui ne peuvent pas être résolus en temps polynomial
  4. DLes problèmes qui ne sont pas polynomiaux

Corrigé

  1. 1. D · Diviser pour régner
  2. 2. A · f croît au même rythme que g, bornée en haut et en bas par des multiples constants de g
  3. 3. A · Une suite finie d'étapes bien définies qui résout un problème
  4. 4. B · Ω(n log n)
  5. 5. C · O(n log n + k log n)
  6. 6. B · Les plus courts chemins en nombre d'arêtes depuis le nœud de départ
  7. 7. A · Réduire un problème NP-difficile connu à X en temps polynomial
  8. 8. A · Les problèmes de décision dont les réponses « oui » peuvent être vérifiées en temps polynomial à l'aide d'un certificat

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