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

Combien de mémoire supplémentaire utilise un tri fusion standard sur tableau ?

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

Lequel de ces temps d'exécution est polynomial ?

1. AO(n!)
2. BO(nⁿ)
3. CO(2ⁿ)
4. DO(n³)

La complexité spatiale mesure :

1. ALa taille physique de l'ordinateur
2. BL'espace disque du fichier du programme une fois compilé
3. CLe nombre de lignes de code
4. DLa quantité de mémoire dont un algorithme a besoin lorsque la taille de l'entrée augmente

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

Est-il correct de dire qu'un algorithme en O(n²) est aussi en O(n³) ?

1. ANon, car n³ est plus petit que n² pour n grand
2. BOui, car le grand O est une borne supérieure et n² ne croît pas plus vite que n³
3. COui, mais seulement si n est inférieur à 100
4. DNon, car le grand O doit toujours donner le taux de croissance exact de la fonction

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

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

2²ⁿ est-il dans O(2ⁿ) ?

1. ANon, car 2²ⁿ croît plus lentement que 2ⁿ
2. BOui, car les deux sont exponentiels
3. COui, car les facteurs constants dans l'exposant sont toujours ignorés en grand O
4. DNon, car 2²ⁿ = 4ⁿ et 4ⁿ / 2ⁿ = 2ⁿ croît sans borne

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

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