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

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

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

Que signifie f(n) = Θ(g(n)) ?

1. Af croît strictement moins vite que g
2. Bf est toujours plus petite que g pour tout n, donc g la borne par le haut mais jamais par le bas
3. Cf croît strictement plus vite que g
4. Df croît au même rythme que g, bornée en haut et en bas par des multiples constants de g

L'accès à un élément d'un tableau par son indice prend :

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

Un algorithme glouton :

1. ADonne toujours la solution optimale
2. BEssaie toutes les solutions possibles
3. CN'utilise que la récursivité
4. DFait le meilleur choix local à chaque étape

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

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

Quelle est la complexité temporelle du tri rapide (quicksort) dans le pire cas ?

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

Pourquoi l'algorithme de Dijkstra peut-il donner des résultats faux lorsque certains poids d'arêtes sont négatifs ?

1. AIl ne fonctionne que sur les graphes non orientés
2. BLes nombres négatifs ne peuvent pas être stockés dans une file de priorité
3. CIl entre dans une boucle infinie à chaque arête négative
4. DUn sommet est définitivement fixé lorsqu'il est extrait, mais une arête négative ultérieure pourrait encore lui donner un chemin plus court

Qu'a établi le théorème de Cook-Levin ?

1. ATout problème NP peut être résolu en temps exponentiel
2. BLe problème de l'arrêt est indécidable
3. CLe problème de satisfiabilité booléenne (SAT) est NP-complet
4. DP est différent de NP