QCM : Algorithmique et bases de Python — 43 questions

Explication

Un algorithme transforme une information symbolique d’entrée en une information symbolique de sortie par un nombre fini d’opérations élémentaires. Ces opérations doivent être réalisables en temps fini ; une infinité d’opérations ne constitue donc pas un algorithme exécutable.

Explication

Un algorithme exécutable doit comporter un nombre fini d’opérations élémentaires. Un procédé demandant une infinité d’opérations ne peut pas être exécuté comme tel par un ordinateur.

Explication

La description effective précise le nom, les spécifications, les entrées, les sorties, les préconditions et les opérations élémentaires. Ces opérations doivent aussi être correctement indentées et commentées, ce qui justifie les cinq réponses exactes.

Explication

L’implémentation traduit un algorithme écrit en pseudo-code dans un langage effectivement compris par une machine. Le pseudo-code décrit l’algorithme, tandis que le code exécutable réalise cette traduction ; les autres propositions inversent ou déforment cette distinction.

Explication

La programmation impérative enchaîne des opérations qui modifient l’état des données. La programmation fonctionnelle emboîte des fonctions et utilise des données immuables ; elle ne se définit donc pas par la modification successive de l’état.

Explication

La complexité étudie le temps nécessaire à l’exécution complète d’un algorithme ainsi que la mémoire mobilisée pendant cette exécution. Elle ne se limite donc pas à la durée d’exécution.

Explication

Les quatre critères essentiels sont la spécification, la terminaison, la correction et la complexité. La lisibilité et la portabilité peuvent être utiles, mais elles ne font pas partie des quatre critères énumérés ici.

Explication

Le type int représente les entiers, tandis que float représente des nombres flottants qui approchent les réels. Les deux types ne correspondent donc pas respectivement aux caractères et aux nombres complexes.

Explication

Pour une division euclidienne par un entier strictement positif, on a $a=qb+r$ avec $0\leqslant r<b$. Le quotient peut être négatif, tandis que le reste reste compris entre zéro inclus et le diviseur exclu.

Explication

En Python, l’opérateur // fournit le quotient de la division euclidienne, % fournit le reste et / produit un flottant. Les propositions qui attribuent le reste à // ou un quotient entier à / sont donc incorrectes.

Explication

Les flottants sont représentés en base 2 avec une précision limitée, ce qui peut provoquer des arrondis à chaque opération. Ainsi, $0.1+0.2-0.3$ peut donner $5.551115123125783\mathrm{e}{-17}$ plutôt que zéro exactement.

Explication

Une chaîne est une valeur de type str délimitée par des guillemets simples ou doubles. L’opérateur + concatène deux chaînes, tandis que la multiplication par un entier répète la chaîne. Un booléen possède les deux valeurs True et False, et la conversion vers une chaîne relève de str.

Explication

Le type booléen possède exactement deux valeurs distinctes : True et False. Les valeurs textuelles et numériques appartiennent à d’autres types, tandis que les conversions int et float concernent respectivement les entiers et les flottants.

Explication

L’affectation évalue l’expression située à droite, puis stocke le résultat dans la variable située à gauche. Elle est donc orientée, contrairement à une égalité mathématique symétrique.

Explication

Python possède un typage dynamique : une même variable peut recevoir successivement des valeurs de types différents. Lors d’une nouvelle affectation, la valeur précédente est remplacée dans cette variable.

Explication

Une fonction reçoit des valeurs en entrée et peut renvoyer une valeur en sortie. Une liste est ordonnée, écrite entre crochets et indexée à partir de 0. L’accès t[k] est valide pour les indices compris entre 0 et n-1.

Explication

Une liste Python est ordonnée, délimitée par des crochets et indexée de 0 à sa longueur moins 1. Pour une liste de longueur n, un indice hors de l’intervalle valide provoque l’exception list index out of range.

Explication

L’opérateur and évalue d’abord sa première opérande et ne poursuit avec la seconde que si la première est vraie. Dans une structure conditionnelle, elif teste d’autres conditions et else correspond au cas où aucune condition précédente n’est vraie.

Explication

Python évalue les conditions if et elif dans l’ordre et exécute le premier bloc vrai. Les blocs elif suivants ne sont pas exécutés, tandis qu'else intervient lorsqu’aucune condition n’est vraie.

Explication

Le bloc associé à la première condition vraie est exécuté, puis les branches suivantes ne le sont pas. Si aucune condition n’est vérifiée, Python exécute le bloc else ; le bloc conditionnel reste délimité par une indentation uniforme.

Explication

Une boucle for est adaptée lorsque le nombre d’itérations est connu avant son démarrage. Dans range(a,b), la borne de départ est incluse et la borne b est exclue ; l’accumulateur d’une somme commence à zéro.

Explication

La boucle for parcourt les valeurs de la séquence produite par range, dont la borne finale est exclue. Une somme s’accumule à partir de zéro, tandis qu’un produit s’initialise à un ; l’itération ajoute ensuite chaque terme.

Explication

Pour range(a,b), les valeurs vont de a jusqu’à b-1. Pour une somme, l’accumulateur commence à zéro et reçoit chaque terme successivement ; une boucle for est bornée car son nombre d’itérations est connu avant l’entrée.

Explication

La boucle for convient lorsque le nombre d’itérations est connu, tandis que while répète un bloc tant qu’une condition est vérifiée. Une boucle while peut donc avoir une durée inconnue et même ne pas terminer si la condition reste vraie.

Explication

L’algorithme d’Euclide remplace successivement (a,b) par (b,a mod b) tant que b est positif, puis renvoie a. Un variant entier positif décroissant permet, quant à lui, de justifier la terminaison d’une boucle while.

Explication

Une boucle while peut être infinie lorsque sa condition demeure vraie. Dans int_sqrt(n), la valeur recherchée est le dernier a satisfaisant $a^2\leq n$, obtenu après l’arrêt de l’incrémentation ; un variant positif strictement décroissant aide à démontrer la terminaison.

Explication

Python utilise le typage dynamique et le duck typing : le type n’a pas à être déclaré obligatoirement si les opérations nécessaires sont disponibles. Une signature comme `est_pair(n: int) -> bool` reste une indication documentaire.

Explication

Une variable globale peut être lue dans une fonction lorsqu’elle n’est pas masquée. Sa modification depuis cette fonction exige la déclaration `global`, tandis qu’une variable locale appartient à l’appel en cours.

Explication

Une fonction récursive s’appelle elle-même sur un problème similaire de taille strictement inférieure. Elle doit prévoir un cas de base et atteindre celui-ci en un nombre fini d’appels.

Explication

Pour $n=2p+r$, l’exposant pair utilise $(x^p)^2$, tandis que l’exposant impair ajoute le facteur $x$. Le cas $x^0=1$ fournit la base de l’exponentiation rapide.

Explication

Pour $n=2^p$, l’exponentiation rapide demande $2+p$ multiplications, soit 12 pour $x^{1024}$. L’algorithme naïf en demande $n-1$, donc 1023 dans ce cas.

Explication

Les tours de Hanoï comportent trois tiges et des disques initialement ordonnés du plus grand au plus petit. Un seul disque est déplacé à chaque étape, et un disque plus grand ne peut pas être posé sur un plus petit.

Explication

À chaque génération $n\geq 1$, la construction comprend quatre tracés de génération $n-1$, chacun de longueur $a/3$, avec les rotations indiquées entre les tracés. La génération précédente et la longueur réduite sont donc toutes deux utilisées dans l’appel récursif.

Explication

Pour la génération $0$, le programme trace directement un segment de longueur $a$. La construction en quatre parties et la longueur $a/3$ concernent les générations supérieures.

Explication

Une liste Python est ordonnée, s’écrit entre crochets et sépare ses valeurs par des virgules. Ses indices commencent à $0$ et se terminent à $n-1$ pour une liste de $n$ éléments.

Explication

La recherche séquentielle parcourt les indices admissibles et compare chaque élément à $x$. Elle renvoie $True$ dès qu’une égalité est trouvée et $False$ lorsque le parcours se termine sans égalité.

Explication

L’algorithme de Hörner réalise exactement $n+1$ multiplications. La recherche dichotomique conserve une tranche contenant la cible et compare celle-ci à l’élément médian ; les deux autres affirmations confondent les coûts des méthodes d’évaluation.

Explication

La méthode naïve recalcule les puissances et demande $\frac{(n+1)(n+2)}{2}$ multiplications. L’évaluation progressive demande $2(n+1)$ multiplications, tandis que Hörner en demande $n+1$ ; la recherche dichotomique utilise une tranche et non toute la liste à chaque étape.

Explication

Le tri par sélection effectue exactement $\frac{n(n-1)}{2}$ comparaisons et $n-1$ échanges. Ces comparaisons ne dépendent pas de l’ordre initial ; les bornes données pour le tri par insertion concernent une autre méthode.

Explication

Le tri par insertion effectue au plus $\frac{n(n-1)}{2}$ comparaisons. Il en effectue exactement $n-1$ sur une liste déjà triée et exactement $\frac{n(n-1)}{2}$ sur une liste décroissante ; son coût dépend donc de l’ordre initial.

Explication

Une pile applique LIFO, tandis qu’une file applique FIFO. Un dictionnaire est indexé par des clés distinctes, et un graphe non orienté utilise des arêtes entre sommets sans orientation ; les autres affirmations inversent ou déforment ces définitions.

Explication

Un dictionnaire associe des clés distinctes à des valeurs et permet l’accès par clé. Il ne repose pas sur des indices comme une séquence, et un graphe non orienté est défini par un ensemble de sommets et un ensemble de paires de sommets distincts.

Explication

Dans un graphe non orienté, $\{x,y\}$ permet le passage dans les deux sens. Un chemin de longueur $n$ contient $n+1$ sommets et chaque paire successive forme une arête ; sa longueur compte donc les arêtes parcourues.