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

Quel est le temps d'exécution du tri par comptage pour n entiers compris entre 0 et k ?

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

Quelle notation décrit une borne inférieure de croissance ?

1. AΘ (grand Thêta)
2. BO (grand O)
3. Co (petit o)
4. DΩ (grand Oméga)

Quelle classe de complexité croît le plus vite pour de grandes valeurs de n ?

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

La récurrence T(n) = 2T(n/2) + O(n) a pour solution :

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

Que mesure l'analyse amortie ?

1. ALe coût moyen par opération sur une suite d'opérations de pire cas
2. BLe coût espéré sur des entrées aléatoires
3. CLe coût d'un algorithme sur la meilleure entrée
4. DLe coût de l'unique opération la plus chère, où qu'elle se trouve dans la suite

Comment l'algorithme de Prim construit-il un arbre couvrant de poids minimal ?

1. AIl exécute un parcours en largeur et conserve l'arbre du BFS
2. BIl trie toutes les arêtes par poids et ajoute chacune d'elles sauf si elle formait un cycle dans la forêt
3. CIl fait croître un seul arbre à partir d'un sommet de départ, en ajoutant l'arête la moins chère qui sort de l'arbre
4. DIl supprime l'arête la plus chère jusqu'à ce qu'il ne reste plus de cycle

Quel est le temps d'exécution de l'algorithme de Dijkstra avec un tas binaire sur un graphe à V sommets et E arêtes ?

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

Lequel de ces problèmes de satisfiabilité est connu pour être résoluble en temps polynomial ?

1. A3-SAT, où chaque clause a exactement trois littéraux
2. B2-SAT, où chaque clause a au plus deux littéraux
3. CSAT général sur des formules en forme normale conjonctive
4. DLa satisfiabilité de circuits