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 qu'un algorithme ?

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

Que décrit le temps d'exécution dans le pire cas d'un algorithme ?

  1. ALe temps espéré sur une entrée aléatoire de taille n
  2. BLe temps maximal sur toutes les entrées de taille n
  3. CLe temps sur la plus petite entrée
  4. DLe temps sur un ordinateur lent
3.Facile

Qu'est-ce qu'un algorithme de force brute ?

  1. AUn algorithme qui devine une réponse au hasard
  2. BUn algorithme qui essaie toutes les solutions candidates possibles
  3. CUn algorithme qui utilise toujours la récursion
  4. DUn algorithme qui s'exécute sur de nombreux processeurs
4.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)
5.Moyen

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

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

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

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

Comment le problème du voyageur de commerce est-il classé ?

  1. ALa version décisionnelle est NP-complète et la version d'optimisation est NP-difficile
  2. BLa version décisionnelle est dans P mais la version d'optimisation est NP-complète
  3. CIl est indécidable
  4. DIl est dans P car l'algorithme de Dijkstra le résout en visitant chaque ville une seule fois
8.Difficile

L'algorithme de Strassen multiplie des matrices en utilisant 7 au lieu de 8 multiplications récursives de blocs de taille moitié. Quel est son temps d'exécution ?

  1. AΘ(n2)
  2. BΘ(n³)
  3. CΘ(n² log n)
  4. DΘ(nlog₂ 7), soit environ n2,81

Corrigé

  1. 1. D · Une suite finie d'étapes bien définies qui résout un problème
  2. 2. B · Le temps maximal sur toutes les entrées de taille n
  3. 3. B · Un algorithme qui essaie toutes les solutions candidates possibles
  4. 4. B · O(n²)
  5. 5. B · O(n)
  6. 6. C · Les plus courts chemins en nombre d'arêtes depuis le nœud de départ
  7. 7. A · La version décisionnelle est NP-complète et la version d'optimisation est NP-difficile
  8. 8. D · Θ(nlog₂ 7), soit environ n2,81

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