Fiche d’exercices de Algorithmes et complexité avec corrigé

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

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

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 sur un ordinateur lent
3. CLe temps maximal sur toutes les entrées de taille n
4. DLe temps espéré sur une entrée aléatoire de taille n

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

Quelle est la complexité temporelle du calcul du n-ième nombre de Fibonacci avec une table remplie de bas en haut ?

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

Environ combien de comparaisons la recherche dichotomique nécessite-t-elle dans le pire cas sur un tableau trié de 1,000,000 d'éléments ?

1. AEnviron 100
2. BEnviron 20
3. CEnviron 1,000
4. DEnviron 500,000

La programmation dynamique est utile lorsqu'un problème présente :

1. AAucun sous-problème, de sorte qu'il peut être résolu en une seule étape
2. BUne seule boucle
3. CUniquement des entrées aléatoires
4. DDes sous-problèmes qui se chevauchent et une sous-structure optimale

Quel énoncé sur la notation petit o est correct ?

1. A2n = o(n), car 2n croît lentement
2. Bn² = o(n)
3. Cn = o(n), puisque toute fonction est un petit o d'elle-même
4. Dn = o(n²), mais n n'est pas o(n)

Quel algorithme trouve un arbre couvrant de poids minimal en ajoutant de façon répétée l'arête la moins coûteuse qui ne forme pas de cycle ?

1. AL'algorithme de Kruskal
2. BFloyd-Warshall
3. CL'algorithme de Dijkstra
4. DL'algorithme de Prim à partir d'un seul nœud