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

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

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

Que vaut log₂ 1024 ?

1. A32
2. B12
3. C10
4. D512

Comment fonctionne le tri par sélection ?

1. AIl divise le tableau en deux moitiés et les fusionne
2. BIl cherche à plusieurs reprises le minimum de la partie non triée et l'échange vers l'avant
3. CIl insère chaque élément dans une partie triée croissante par décalages
4. DIl échange à plusieurs reprises les éléments voisins mal ordonnés

Un tri rapide utilise toujours le premier élément comme pivot. Sur quelle entrée présente-t-il son comportement de pire cas ?

1. AUn tableau dont tous les éléments sont distincts
2. BUn tableau de longueur 2
3. CUn tableau déjà trié
4. DUn tableau dans un ordre aléatoire

Une fonction exécute une boucle de n itérations, puis, séparément, une autre boucle de n itérations. Quelle est sa complexité temporelle ?

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

Quelle est la complexité temporelle de l'algorithme standard de programmation dynamique pour la plus longue sous-séquence commune de chaînes de longueurs m et n ?

1. AO(m + n)
2. BO(mn)
3. CO(mn log n)
4. DO(2^m+n)

Le problème de l'arrêt montre que :

1. ATout programme finit par s'arrêter
2. BCertains programmes s'exécutent plus vite sur des ordinateurs plus rapides, donc l'arrêt dépend du matériel
3. CAucun algorithme ne peut décider, pour tout programme et toute entrée, si le programme s'arrête
4. DIl faut éviter les boucles

Un problème est NP-complet s'il :

1. AAppartient à NP et si tout problème NP se réduit à lui en temps polynomial
2. BEst résoluble en temps polynomial
3. CEst hors de NP mais plus difficile que tous les problèmes NP, comme le problème de l'arrêt
4. DEst impossible à résoudre