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

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

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

Quelle est la complexité temporelle du tri fusion dans le pire cas ?

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

Que vaut log₂ 1024 ?

  1. A512
  2. B32
  3. C10
  4. D12
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. BLe compilateur la transforme toujours en une boucle qui se termine sans danger
  3. CElle continue de s'appeler jusqu'au débordement de la pile d'appels
  4. DElle renvoie automatiquement 0
5.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. BLes plus courts chemins en nombre d'arêtes depuis le nœud de départ
  3. CUn ordre topologique dans tous les graphes
  4. DL'arbre couvrant de poids minimal
6.Moyen

Que calcule l'algorithme de Floyd-Warshall, et en combien de temps ?

  1. ALes plus courts chemins depuis un sommet source vers tous les autres en O(V + E)
  2. BLes plus courts chemins entre toutes les paires de sommets en O(V³)
  3. CUn arbre couvrant de poids minimal en O(E log V)
  4. DUn ordre topologique en O(V²)
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. BIl est dans P car l'algorithme de Dijkstra le résout en visitant chaque ville une seule fois
  3. CIl est indécidable
  4. DLa version décisionnelle est dans P mais la version d'optimisation est NP-complète
8.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. BAucun algorithme ne peut décider, pour tout programme et toute entrée, si le programme s'arrête
  3. CTout programme finit par s'arrêter
  4. DIl faut éviter les boucles

Corrigé

  1. 1. B · Le temps maximal sur toutes les entrées de taille n
  2. 2. C · O(n log n)
  3. 3. C · 10
  4. 4. C · Elle continue de s'appeler jusqu'au débordement de la pile d'appels
  5. 5. B · Les plus courts chemins en nombre d'arêtes depuis le nœud de départ
  6. 6. B · Les plus courts chemins entre toutes les paires de sommets en O(V³)
  7. 7. A · La version décisionnelle est NP-complète et la version d'optimisation est NP-difficile
  8. 8. B · 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.