QCM : Graphes et programmation dynamique (58 questions)

Explication

Les triples guillemets ou triples apostrophes permettent notamment d’écrire une chaîne sur plusieurs lignes. Les guillemets ordinaires délimitent une chaîne simple, tandis que \n représente un retour à la ligne dans la chaîne sans remplacer cette délimitation.

Explication

Une chaîne est immuable : on ne peut pas remplacer directement un caractère par une affectation à un indice. Les listes, contrairement aux chaînes, acceptent la modification d’un élément ; l’indexation d’une chaîne reste possible en lecture.

Explication

Les opérateurs booléens évaluent de gauche à droite et `and` s’arrête dès qu’un opérande faux détermine le résultat. Évaluer `calculer()` systématiquement ignore le court-circuit, tandis que l’inversion relève de `not`.

Explication

`range(a, b, pas)` produit les termes `a + k·pas` strictement inférieurs à `b` : ici, 2, 5 et 8. Inclure 11 oublie que la borne supérieure est exclue, et compter de un en un néglige le pas de 3.

Explication

Une fonction définie avec `def` peut prendre plusieurs paramètres et l’instruction `return` n’est pas obligatoire. Imposer une valeur renvoyée confond fonction et procédure, et le nombre ou le type des paramètres n’impose pas ces contraintes.

Explication

Sans déclaration `global`, une variable à laquelle la fonction affecte une valeur est locale ; l’affectation de 3 ne modifie donc pas la variable extérieure, qui reste à 1. Une déclaration `global` serait nécessaire pour viser cette variable globale.

Explication

Une liste est ordonnée, peut contenir des éléments de types différents et permet de modifier ses éléments. Le tuple est non modifiable, l’ensemble n’est pas une séquence ordonnée par indice et le dictionnaire associe des clés à des valeurs.

Explication

L’expression `l + [8]` produit une nouvelle liste sans changer `l`, tandis que `append(9)` modifie directement la liste. Inclure 8 revient à croire que la concaténation agit en place; ne pas inclure 9 revient à traiter `append` comme une opération non modificatrice.

Explication

Plusieurs valeurs renvoyées séparées par des virgules forment un tuple, dont les éléments ne sont pas modifiables. Le traiter comme une liste confond les deux structures; l’affectation à `result` ne change pas la nature du tuple.

Explication

`b` reste un alias de l’objet initial `[1, 2]` : réaffecter `a` fait pointer cette variable vers un autre objet, sans modifier l’objet initial. Croire que `b` suit la nouvelle valeur confond réaffectation et modification en place.

Explication

Avec `import math as m`, l’accès aux objets du module se fait au moyen de son alias, donc `m.sqrt(25)`. Appeler `sqrt` sans préfixe suppose une importation directe, tandis que `math` n’est pas le nom utilisé après l’alias.

Explication

Le mode « a » ajoute à la fin du fichier existant et crée le fichier s’il n’existe pas. Le mode « w » vide le fichier à l’ouverture, tandis que le mode « r » sert à lire.

Explication

`DictReader` produit des dictionnaires dont les clés proviennent de la première ligne ou des `fieldnames`. `reader` renvoie des lignes sous forme de listes; `fieldnames` fournit les noms de champs mais n’est pas le lecteur CSV.

Explication

Une assertion contrôle une condition et déclenche `AssertionError` si celle-ci est fausse. Renvoyer `False` confond contrôle et résultat booléen, `TypeError` attribue le mauvais type d’exception, et poursuivre l’exécution ignore l’échec du contrôle.

Explication

Le partitionnement teste une valeur représentative d’un sous-ensemble, tandis que les tests aux limites vérifient les bornes et les valeurs juste au-delà. Traiter 14 comme une frontière confond représentativité et borne; classer les frontières comme partitionnement inverse les méthodes, et isoler certaines valeurs limite n’en change pas la nature.

Explication

Le test d’appartenance renvoie `True` dès qu’un élément égal est trouvé, et `False` si tout le parcours s’achève sans résultat. Renvoyer un indice correspond à une recherche de position, inverser les booléens inverse le résultat, et poursuivre après la découverte oublie l’arrêt immédiat.

Explication

Comme 17 est supérieur à la valeur 12 au milieu, la recherche dichotomique conserve la moitié droite et exclut le milieu en plaçant la borne gauche à l’indice suivant. Reculer la borne droite choisit la mauvaise moitié, garder le milieu ne l’exclut pas, et un parcours séquentiel n’est pas la mise à jour dichotomique.

Explication

La recherche teste les positions de départ possibles et compare les caractères du mot successivement; elle s’arrête lorsqu’une correspondance est trouvée ou qu’il ne reste pas assez de chaîne. Limiter la recherche au début manque des occurrences, comparer les chaînes entières n’effectue pas la comparaison caractère par caractère, et poursuivre après la dernière position possible dépasse les départs valides.

Explication

Le comptage avec chevauchement examine chaque position de départ successive; le comptage sans chevauchement reprend à la position située après le mot trouvé. Inverser ces déplacements échange les deux méthodes, avancer de la longueur du mot dans les deux cas ne respecte pas le parcours successif avec chevauchement, et séparer les départs pairs et impairs n’est pas la règle.

Explication

La complexité temporelle mesure le temps de calcul en fonction des données d’entrée, alors que la complexité spatiale concerne la mémoire utilisée. La complexité maximale désigne un cas de coût parmi les entrées, et la complexité asymptotique décrit une croissance.

Explication

La complexité asymptotique décrit l’ordre de croissance du coût pour de grandes tailles d’entrée en ignorant les constantes multiplicatives et les termes de moindre ordre. Le coût exact conserve les constantes, la complexité spatiale porte sur la mémoire et la complexité moyenne pondère les coûts par les probabilités des entrées.

Explication

La notation $\Theta(n^2)$ indique que le coût est encadré asymptotiquement par des constantes multiples de $n^2$. $O(n^2)$ ne fournit qu’une majoration, $\Omega(n^2)$ qu’une minoration, et l’égalité exacte ne découle pas de cet encadrement.

Explication

La preuve d’une boucle établit un invariant, prouve la terminaison — notamment avec un variant entier strictement décroissant pour une boucle while — puis vérifie que la sortie correspond au résultat attendu. Montrer seulement la terminaison ou seulement l’invariant ne suffit pas à démontrer la correction complète.

Explication

Une liste dynamique peut varier en nombre d’éléments, tandis qu’un tableau a une taille fixe. Le caractère homogène ou contigu concerne les éléments et leur organisation mémoire, pas une capacité variable.

Explication

L’adresse se calcule par $debut + k \times taille$, donc $1000 + 5 \times 8 = 1040$. La valeur 1005 ajoute la position sans tenir compte de la taille, 1008 ne tient compte que d’un élément et 1048 applique une position de 6.

Explication

Une liste simplement chaînée donne facilement accès à son début, mais il faut parcourir les éléments précédents pour atteindre une position donnée. Le calcul direct d’adresse correspond au tableau contigu, le lien précédent à la liste doublement chaînée, et la suppression devient possible une fois la position atteinte.

Explication

Le type `list` de Python utilise un tableau d’adresses et réserve de la capacité afin que les ajouts en fin soient en temps amorti constant. Une chaîne de nœuds décrit une liste chaînée, le décalage concerne la suppression ou l’insertion intermédiaire, et une taille fixe empêcherait l’agrandissement.

Explication

Une pile fonctionne selon le principe LIFO : le dernier objet ajouté est le premier récupéré et supprimé. X correspondrait à une file FIFO, tandis que Y confond l’ordre d’accès avec l’ordre d’insertion.

Explication

Une file suit le principe FIFO : le premier arrivé est le premier récupéré et supprimé, donc Lina est servie en premier. Noé serait choisi en appliquant LIFO, et Marc en privilégiant à tort la position intermédiaire.

Explication

Dans un graphe orienté, un arc est un couple ordonné, de sorte que l’ordre de U et V compte; dans un graphe non orienté, une arête est un ensemble où l’ordre ne compte pas. L’ensemble pour l’arc inverse ces notions, et une arête n’acquiert pas d’orientation.

Explication

Le parcours en largeur explore par niveaux et permet d’obtenir les distances minimales depuis le sommet de départ ainsi qu’un prédécesseur pour reconstruire un chemin. Le parcours en profondeur n’est pas la méthode décrite pour cette détermination par niveaux; les degrés comptent des arcs et la matrice représente les liens.

Explication

Dans ce parcours en largeur, I se trouve à distance 2 de A; les sommets B et H sont à distance 1, tandis qu'E, F et G sont à distance 3. Attribuer 0 à I confond sa distance avec celle du sommet de départ.

Explication

Un graphe orienté est défini par $G=(S,A)$ : $S$ rassemble les sommets et $A$ les couples ordonnés de sommets appelés arcs. Inverser S et A échange leurs rôles, tandis que des ensembles non ordonnés décrivent des arêtes non orientées.

Explication

Le parcours en profondeur poursuit une branche aussi loin que possible avant de revenir sur ses pas. Visiter les sommets par distance évoque le parcours en largeur, tandis que le nombre de voisins et le retour au départ ne définissent pas sa progression.

Explication

Le parcours choisit le premier voisin non vu, l’ajoute aux successeurs du sommet courant, mémorise son prédécesseur et l’empile. Choisir le plus éloigné confond l’ordre prescrit avec un critère de distance; épuiser tous les voisins ou les empiler ensemble ne correspond pas à cette étape.

Explication

Dijkstra calcule les plus courtes distances lorsque tous les poids sont positifs ou nuls; une arête négative ne respecte pas cette condition. Un poids négatif n’est pas un poids nul, la connexité ne supprime pas cette contrainte et l’algorithme peut traiter des graphes orientés ou non.

Explication

À chaque tour, Dijkstra choisit le sommet non exploré de distance provisoire minimale, donc celui associé à 6. Choisir la distance maximale inverse le critère; le nombre de voisins et la proximité estimée de la destination ne déterminent pas ce choix.

Explication

A* évalue les sommets selon un coût qui combine la distance déjà parcourue depuis l’origine et une heuristique vers la destination. Utiliser la distance seule correspond au critère de Dijkstra, tandis que l’heuristique seule ou le nombre de voisins ne constitue pas le critère décrit.

Explication

A* calcule le coût par $\operatorname{cout}(S)=d(S)+h(S)$; ici, $8+3=13$. La valeur 5 provient d’une soustraction, 3 ignore la distance parcourue et 24 résulte d’une multiplication.

Explication

La programmation dynamique exploite le chevauchement des sous-problèmes en conservant leurs résultats pour éviter de les recalculer. L’indépendance caractérise plutôt le diviser pour régner, le choix local relève du glouton et l’énumération sans mémorisation ne réutilise pas les calculs.

Explication

Le glouton choisit 6, puis deux pièces de 1 : il utilise trois pièces alors que 4 + 4 en demande deux. La garantie d’optimalité est l’erreur associée à l’idée que le choix glouton suffit, la programmation dynamique compare les sous-problèmes et le choix répété de la pièce de 1 ne suit pas la règle gloutonne.

Explication

Pour chaque pièce admissible, on ajoute une pièce au meilleur résultat pour le montant restant, puis on choisit le minimum. Omettre le terme 1 oublie la pièce utilisée, le maximum inverse l’objectif, et inclure une pièce supérieure à $n$ crée un montant restant non admissible.

Explication

Le meilleur trajet vient du prédécesseur ayant le gain maximal, auquel on ajoute la valeur de la case : $a_{i,j}+\max(7,10)=a_{i,j}+10$. Le minimum choisit le mauvais prédécesseur, la somme cumule deux trajets incompatibles et le gain 10 omet la case d’arrivée.

Explication

Une partition équilibrée vise à rapprocher autant que possible les sommes des deux sous-listes. Avoir le même nombre d’éléments ne garantit pas des sommes proches, maximiser une somme ne minimise pas leur écart, et l’alternance n’est pas le critère d’équilibre.

Explication

À chaque étape, les sommes possibles comprennent celles déjà atteintes et celles obtenues en ajoutant le nouvel élément, ici $6$. Ne garder que les nouvelles sommes oublie les sous-listes sans le 6, tandis que sélectionner directement la somme maximale ne suit pas la construction des sommes atteignables.

Explication

L’écart entre les deux groupes est minimisé en recherchant une sous-liste dont la somme est aussi proche que possible de la moitié du total, soit $31/2=15{,}5$. Viser 31 ne partage pas le total, privilégier le dépassement ignore la recherche de la somme atteignable inférieure ou égale à la moitié, et le quart correspond à une autre répartition.

Explication

Une sous-séquence conserve l’ordre des caractères de la chaîne, mais ceux-ci n’ont pas besoin d’être consécutifs. « xabc » inverse l’ordre, « bcdyx » aussi, tandis que « abq » contient un caractère absent.

Explication

La plus longue sous-séquence commune doit apparaître dans les deux chaînes en respectant l’ordre et avoir une longueur maximale. Une sous-chaîne contiguë impose une contrainte supplémentaire, et une suite commune quelconque n’est pas nécessairement la plus longue.

Explication

Le calcul des plus longues sous-séquences communes de préfixes est réutilisé pour des préfixes plus grands : ce chevauchement des sous-problèmes motive la programmation dynamique. L’absence de recouvrement, la contiguïté et le tri ne sont pas les raisons invoquées.

Explication

KNN attribue au nouvel objet la catégorie dominante parmi ses k voisins de référence les plus proches ; ici, A compte trois voisins sur cinq. Se fier au seul voisin le plus proche ou à la majorité de toute la base ne correspond pas à cette règle.

Explication

KNN calcule les distances au nouveau point, conserve les indices des k points les plus proches, puis renvoie la catégorie dominante parmi eux. La majorité de toute la base, le choix des points les plus éloignés ou l’utilisation d’un seul voisin modifie cette procédure.

Explication

La matrice de confusion compare les catégories détectées par l’algorithme, placées en lignes, aux catégories réelles, placées en colonnes, pour les données de test. Inverser les axes ou remplacer une catégorie par un effectif ou une distance ne respecte pas cette définition.

Explication

Les k-moyennes regroupent des points proches sans catégories de référence : c’est un apprentissage non supervisé. Les étiquettes connues relèvent du supervisé, la prédiction continue de la régression et les récompenses du renforcement.

Explication

Après le choix initial des centres, l’algorithme affecte chaque donnée au centre le plus proche, recalcule les barycentres, puis répète ces étapes jusqu’à stabilisation. Recalculer avant l’affectation inverse l’ordre, le centre le plus éloigné inverse le critère, et conserver les centres initiaux omet la mise à jour.

Explication

Il faut sélectionner l’attribut id dans CLIENTS et filtrer cette table avec ville = 'Toulouse'. La table PARTENAIRES ne porte pas la ville, le filtre partenaire ne correspond pas au critère demandé et email n’est pas l’identifiant.

Explication

Les clients concernés se retrouvent en reliant CLIENTS.id à PARTENAIRES.id_client, puis en filtrant partenaire sur SCEI et en sélectionnant email. Omettre la liaison ne rattache pas les partenaires aux clients, id de PARTENAIRES est un identifiant de suivi, et SCEI est une valeur de partenaire, pas de ville ni d’adresse électronique.

Explication

Dans CLIENTS, nom, prenom, ville et email sont des chaînes de caractères, tandis qu'id est un entier. Inclure id méconnaît son type, partenaire et id_client appartiennent à PARTENAIRES, et id_client n’est pas un attribut de CLIENTS.

Explication

PARTENAIRES.id_client reprend l’identifiant id du client dans la table CLIENTS afin d’associer le partenaire au bon client. La clé primaire de PARTENAIRES est son propre id, tandis que partenaire contient le nom du partenaire.