Quiz: Introduction aux algorithmes et complexité — 9 domande

1. Quelle est la définition correcte d’un algorithme ?

A. Une suite finie d’instructions précises permettant de résoudre un problème ou d’accomplir une tâche spécifique

B. Une série d’instructions qui peut être infinie si le problème est complexe

C. Un ensemble d’instructions non ordonnées pouvant être exécutées par une machine ou un humain

D. Une méthode approximative pour résoudre un problème sans garantie de terminaison

Answer: (A)

Spiegazione

L’algorithme est défini comme une suite finie d’instructions précises permettant de résoudre un problème ou d’accomplir une tâche spécifique, ce qui correspond à la réponse 0. Les autres options proposent des idées incorrectes ou incomplètes, comme l’infinité, le non-ordre ou l’approximatif.

2. Quelle est la propriété essentielle d’un algorithme selon le cours?

A. Il doit être infini pour couvrir tous les cas possibles

B. Il doit être déterministe, fini et non ambigu

C. Il doit contenir au moins une boucle non bornée

D. Il doit toujours utiliser des structures conditionnelles

Answer: (B)

Spiegazione

Un algorithme doit être déterministe, fini et non ambigu pour garantir qu'il cache une logique claire, qu'il se termine et qu'il produit un résultat cohérent pour une même entrée.

3. Quel est le rôle principal de la propriété de finitude d’un algorithme ?

A. Garantir que l’algorithme produise toujours le même résultat pour une même entrée

B. Assurer que l’algorithme se termine après un nombre fini d’étapes

C. Permettre à l’algorithme d’être utilisé dans des systèmes en temps réel

D. Rendre l’algorithme plus facile à comprendre pour les humains

Answer: (B)

Spiegazione

La propriété de finitude garantit que l’algorithme se termine après un nombre fini d’étapes, ce qui est essentiel pour assurer qu’il ne tourne pas indéfiniment et qu’il résout le problème dans un temps raisonnable.

4. Quelle notation Big O exprime une complexité critique minimale, constante, dans l’analyse d’un algorithme?

A. O(n²)

B. O(log n)

C. O(1)

D. O(n)

Answer: (C)

Spiegazione

O(1) signifie que l’algorithme a une complexité constante, indépendante de la taille des données, ce qui est souvent considéré comme optimal en termes de temps d’exécution.

5. En quoi la structure de contrôle et la syntaxe diffèrent-elles ou se ressemblent-elles dans un programme informatique?

A. La syntaxe est une propriété du langage, alors que la structure de contrôle est une propriété de l'algorithme.

B. Les deux sont identiques, car la syntaxe définit la manière dont les structures de contrôle sont écrites.

C. La structure de contrôle est une propriété du langage, alors que la syntaxe désigne la logique de l'algorithme.

D. La syntaxe concerne la forme d'écriture des structures de contrôle, tandis que la structure de contrôle désigne leur fonction logique.

Answer: (D)

Spiegazione

La syntaxe concerne la manière dont les éléments de contrôle (if, for, while) sont écrits dans le langage, tandis que la structure de contrôle désigne leur rôle dans la gestion du flux d'exécution. La bonne réponse indique cette distinction claire.

6. Quelle structure de contrôle permet de répéter un bloc d’instructions un nombre limitée de fois?

A. La boucle while

B. La boucle for (bornée)

C. La condition if-else

D. La structure switch-case

Answer: (B)

Spiegazione

La boucle for (bornée) est utilisée pour répéter un bloc d'instructions un nombre fixe de fois, contrairement à while qui se répète tant qu'une condition est vraie.

7. Qu'est-ce qui différencie la recherche séquentielle de la recherche dichotomique?

A. La recherche séquentielle nécessite que la liste soit triée, pas la dichotomique

B. La recherche dichotomique divise l’espace de recherche par deux à chaque étape, contrairement à la séquentielle

C. La recherche séquentielle a une complexité O(log n), tandis que la dichotomique est O(n)

D. La recherche dichotomique est moins efficace que la séquentielle sur une liste triée

Answer: (B)

Spiegazione

La recherche dichotomique divise l’espace de recherche par deux à chaque étape, ce qui la rend plus efficace (complexité O(log n)) sur les listes triées par rapport à la recherche séquentielle.

8. Selon le cours, quel auteur a introduit la notion de complexité algorithmique en 1965?

A. Donald Knuth

B. Leslie Valiant

C. Leibniz

D. Graham Leuschner

Spiegazione

Leslie Valiant a développé la théorie de la complexité en 1965, contribuant à la formalisation de l’analyse de la performance des algorithmes.

9. Quel est le but principal de l’analyse de complexité d’un algorithme?

A. Optimiser son code en utilisant les langages de programmation modernes

B. Mesurer le temps ou l’espace que l’algorithme utilise pour évaluer son efficacité

C. Réduire la taille de la mémoire physique utilisée par le programme

D. Augmenter l’efficacité des structures de contrôle conditionnelles

Answer: (B)

Spiegazione

L’analyse de complexité a pour objectif d’évaluer le temps ou l’espace utilisés par un algorithme pour déterminer son efficacité, ce qui est crucial pour l’optimisation.