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

Qu'est-ce qu'un algorithme de force brute ?

1. AUn algorithme qui essaie toutes les solutions candidates possibles
2. BUn algorithme qui s'exécute sur de nombreux processeurs
3. CUn algorithme qui utilise toujours la récursion
4. DUn algorithme qui devine une réponse au hasard

Quelle est la complexité temporelle de la recherche dichotomique dans un tableau trié ?

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

Quelle est la complexité temporelle de la recherche linéaire dans un tableau non trié de n éléments (pire cas) ?

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

La borne inférieure du tri par comparaisons dans le pire cas est :

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

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

Quel algorithme trouve les plus courts chemins depuis une source dans un graphe dont les poids des arêtes sont positifs ou nuls ?

1. AL'algorithme de Kruskal
2. BBellman-Ford est nécessaire dans tous les cas
3. CL'algorithme de Dijkstra
4. DLe parcours en profondeur (DFS)

Quelle affirmation concernant P et NP est correcte ?

1. ANP signifie « non polynomial »
2. BLes solutions des problèmes NP ne peuvent pas être vérifiées rapidement
3. CTout problème de P appartient aussi à NP
4. DIl a été démontré que P ≠ NP

Quelle technique donne au tri rapide un temps d'exécution espéré en O(n log n) pour toute entrée ?

1. ATrier l'entrée avant d'exécuter le tri rapide
2. BToujours choisir le premier élément
3. CN'utiliser la récursivité que sur la partie gauche
4. DChoisir le pivot uniformément au hasard