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

Qu'est-ce qu'un algorithme ?

1. AUne suite finie d'étapes bien définies qui résout un problème
2. BUn langage de programmation conçu pour écrire des formules mathématiques
3. CTout programme informatique doté d'une interface graphique
4. DUne structure de données qui stocke des nombres

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

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

La complexité spatiale mesure :

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

Que mesure l'analyse amortie ?

1. ALe coût d'un algorithme sur la meilleure entrée
2. BLe coût de l'unique opération la plus chère, où qu'elle se trouve dans la suite
3. CLe coût moyen par opération sur une suite d'opérations de pire cas
4. DLe coût espéré sur des entrées aléatoires

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, mais seulement si n est inférieur à 100
3. COui, car le grand O est une borne supérieure et n² ne croît pas plus vite que n³
4. DNon, car le grand O doit toujours donner le taux de croissance exact de la fonction

Pourquoi de nombreuses routines de tri des bibliothèques passent-elles au tri par insertion pour les très petits sous-tableaux ?

1. ALe tri par insertion est en O(n log n) dans le pire cas
2. BLe tri par insertion utilise moins de mémoire que tout autre algorithme de tri sur les grandes entrées
3. CLe tri par insertion a peu de surcoût et est rapide sur les entrées petites ou presque triées
4. DLes algorithmes récursifs ne peuvent pas traiter les tableaux de moins de 10 éléments

Quels sont les coûts en temps et en espace du calcul du n-ième nombre de Fibonacci avec une boucle qui ne conserve que les deux dernières valeurs ?

1. AO(n) en temps et O(1) en espace
2. BO(2ⁿ) en temps et O(1) en espace
3. CO(n) en temps et O(n) en espace
4. DO(log n) en temps et O(n) en espace

Quelle est la complexité temporelle de la construction d'un tas binaire à partir de n éléments non triés avec la méthode ascendante (bottom-up) ?

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