QCM : Algorithmique et complexité — 25 questions

Explication

Un algorithme organise des instructions dans un ordre permettant d’obtenir un résultat visé. Un langage de programmation sert plutôt à traduire ou exécuter cet algorithme.

Explication

L’algorithmique étudie les méthodes et les règles qui permettent de concevoir des algorithmes. La traduction dans Python correspond à la programmation, et non à la définition de l’algorithmique.

Explication

Les données d’entrée alimentent l’algorithme avant ou pendant son exécution, puis le traitement produit les données de sortie. Confondre ces rôles inverse le sens du fonctionnement algorithmique.

Explication

Un programme est l’implémentation d’un algorithme dans un langage tel que Python ou Java. L’algorithme précède donc sa traduction informatique, plutôt que l’inverse.

Explication

Knuth associe notamment la finitude, la précision des actions, l’acceptation d’entrées, la production de sorties et l’exécutabilité en temps fini. Le langage Python et la recherche dans un tableau ne sont pas des exigences générales de sa définition.

Explication

Lorsque le reste vaut zéro, le dernier diviseur n est le PGCD recherché. La poursuite des divisions intervient lorsque le reste est différent de zéro.

Explication

Euclide a décrit un algorithme permettant de calculer le PGCD de deux entiers. La recherche dans un tableau trié relève d’une autre méthode algorithmique, la recherche dichotomique.

Explication

La complexité quantifie les opérations arithmétiques, logiques et affectations nécessaires à l’exécution. La correction désigne plutôt l’obtention du résultat attendu, ce qui constitue une notion différente.

Explication

Une complexité linéaire croît selon une expression affine de la forme $\alpha n+\beta$ et se note $O(n)$. L’expression quadratique proposée croît selon $n^2$ et correspond donc à une autre classe de complexité.

Explication

Une complexité quadratique comporte un terme dominant en $n^2$ et s’écrit $\alpha n^2+\beta n+\gamma$, avec une notation en $O(n^2)$. Une expression affine en $n$ décrit une croissance linéaire, et non quadratique.

Explication

La recherche linéaire parcourt les éléments l’un après l’autre jusqu’au succès ou à la fin du tableau, ce qui conduit à un coût linéaire dans le pire cas. La division en deux intervalles caractérise la recherche dichotomique et suppose un espace ordonné.

Explication

Le calcul séquentiel d’un maximum conserve une référence, puis la remplace lorsqu’un élément plus grand est rencontré. Additionner les valeurs relève plutôt du calcul d’une somme ou d’une moyenne.

Explication

La recherche dichotomique divise successivement un espace ordonné en deux parties afin de décider quelle moitié conserver. Un tableau non trié ne permet pas cette décision fiable, même si ses valeurs sont distinctes.

Explication

Dans un espace ordonné croissant, une valeur recherchée inférieure à l’élément central se trouve potentiellement dans la moitié gauche. La moitié droite est conservée lorsque l’élément central est inférieur à la valeur recherchée.

Explication

Chaque étape de la recherche dichotomique réduit l’intervalle à examiner environ de moitié, ce qui produit une complexité logarithmique $O(\log n)$. Cette croissance est généralement inférieure à celle d’un parcours linéaire en $O(n)$.

Explication

Le tri par insertion maintient une partie déjà ordonnée et décale les éléments précédents plus grands pour insérer le nouvel élément. La recherche du minimum suivie d’un échange caractérise plutôt le tri par sélection.

Explication

Un tableau trié à l’envers oblige le tri par insertion à effectuer un grand nombre de décalages, ce qui donne une complexité quadratique $O(n^2)$. Les tableaux presque triés peuvent en revanche être traités plus rapidement.

Explication

Le tri par sélection recherche le minimum dans la partie non triée, l’échange avec la position courante, puis répète ce procédé. Le décalage des éléments précédents correspond au mécanisme du tri par insertion.

Explication

Un variant est une quantité entière positive ou nulle qui diminue strictement à chaque passage dans la boucle. Une quantité qui augmente ne permet pas de montrer directement qu’une suite d’itérations doit s’arrêter.

Explication

Le variant décroît strictement tout en restant positif ou nul, et une telle décroissance ne peut se poursuivre indéfiniment parmi les entiers. La terminaison ne repose pas sur un nombre fixé d’itérations valable pour toutes les entrées.

Explication

Un algorithme glouton prend à chaque étape une décision locale qui paraît la meilleure et conserve ses décisions précédentes. L’énumération de toutes les solutions relève plutôt d’une recherche exhaustive ou par force brute.

Explication

Les choix locaux d’un algorithme glouton peuvent produire une solution améliorée mais non optimale globalement; certaines structures particulières permettent toutefois d’obtenir l’optimum. L’examen de toutes les combinaisons décrit une approche exhaustive, pas une stratégie gloutonne.

Explication

La stratégie gloutonne choisit 50, puis six pièces de 2 et une pièce de 1, soit huit pièces ou billets. La combinaison de trois pièces de 20, d’une pièce de 2 et d’une pièce de 1 utilise cinq pièces et constitue l’optimum global.

Explication

Les k plus proches voisins relèvent de l’apprentissage supervisé et s’appuient donc sur des données dont la classe est connue. Les données non classées correspondent plutôt à une approche non supervisée, qui ne fournit pas directement les catégories attendues.

Explication

L’algorithme trie les données selon leur distance à la cible, extrait les k premières et attribue la classification majoritaire parmi ces voisins. La proximité sert donc à sélectionner les exemples, tandis que la majorité sert à décider de la classe.