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

Quel est le grand O de 3n² + 5n + 2 ?

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

Quelle stratégie de conception utilise le tri fusion ?

1. ADiviser pour régner
2. BLa programmation dynamique
3. CLe choix glouton
4. DLa force brute

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 fusion
3. CTri par tas
4. DTri à bulles

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 se termine le plus tôt, puis recommencer avec les activités compatibles
2. BChoisir d'abord l'activité ayant le moins de chevauchements, puis recommencer avec les activités compatibles
3. CChoisir l'activité qui commence le plus tôt
4. DChoisir d'abord l'activité la plus courte

Quel espace de pile utilise une fonction factorielle récursive simple fact(n) = n × fact(n − 1) ?

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

Combien de niveaux comporte la récursion du tri fusion pour un tableau de n éléments ?

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

Quelle est la solution de la récurrence T(n) = 2T(n/2) + n log n ?

1. AΘ(n²)
2. BΘ(n)
3. CΘ(n log n)
4. DΘ(n log² n)

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

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