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

Une boucle commence avec i = 1 et double i à chaque itération jusqu'à ce que i > n. Combien d'itérations effectue-t-elle ?

1. AEnviron n²
2. BEnviron log₂ n
3. CEnviron n
4. DEnviron n / 2

Quel algorithme de tri échange de façon répétée les éléments adjacents qui sont dans le mauvais ordre ?

1. ATri rapide (quicksort)
2. BTri à bulles
3. CTri fusion
4. DTri par tas

Que signifie qu'une opération s'exécute en temps O(1) ?

1. AElle traite exactement un élément par seconde de temps d'exécution
2. BElle prend toujours exactement une seconde
3. CElle ne peut être exécutée qu'une seule fois
4. DSon temps d'exécution n'augmente pas avec la taille de l'entrée

Avec des pièces de 1, 3 et 4 et un montant de 6, combien de pièces utilise la méthode gloutonne « la plus grosse pièce d'abord », comparée à l'optimum ?

1. ALe glouton utilise 2 pièces ; l'optimum est 2
2. BLe glouton utilise 4 pièces ; l'optimum est 3
3. CLe glouton utilise 3 pièces ; l'optimum est 2
4. DLe glouton utilise 3 pièces ; l'optimum est 3

Dans le problème de sélection d'activités, quelle règle gloutonne donne toujours un nombre maximal d'activités sans chevauchement ?

1. AChoisir l'activité qui commence le plus tôt
2. BChoisir d'abord l'activité la plus courte
3. CChoisir l'activité qui se termine le plus tôt, puis recommencer avec les activités compatibles
4. DChoisir d'abord l'activité ayant le moins de chevauchements, puis recommencer avec les activités compatibles

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. CUn ordre topologique dans tous les graphes
4. DLes plus courts chemins en nombre d'arêtes depuis le nœud de départ

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

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

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