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

Quelle notation décrit une borne supérieure de la croissance ?

1. AGrand Thêta (Big Theta)
2. BPetit oméga (little omega)
3. CGrand Oméga (Big Omega)
4. DGrand O (Big O)

Un algorithme comportant deux boucles imbriquées, chacune exécutée n fois, a généralement quelle complexité ?

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

Qu'est-ce que la mémoïsation ?

1. AStocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire
2. BLibérer la mémoire après le retour d'une fonction
3. CConvertir automatiquement une récursion en boucle équivalente, si bien qu'aucune pile d'appels n'est nécessaire
4. DÉcrire des commentaires à côté de chaque ligne de code

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(mn)
2. BO(m + n)
3. CO(mn log n)
4. DO(2^m+n)

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

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

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

1. ABellman-Ford est nécessaire dans tous les cas
2. BL'algorithme de Dijkstra
3. CLe parcours en profondeur (DFS)
4. DL'algorithme de Kruskal

Quelle définition de la classe NP est correcte ?

1. ALes problèmes qui ne peuvent pas être résolus en temps polynomial
2. BLes problèmes de décision dont les réponses « oui » peuvent être vérifiées en temps polynomial à l'aide d'un certificat
3. CLes problèmes qu'aucun algorithme ne peut résoudre
4. DLes problèmes qui ne sont pas polynomiaux

Quelle affirmation concernant P et NP est correcte ?

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