Exercices corrigés de NSI : le traitement de données en tables

a) Le dépaquetage x, y = point donne x valant 3 et y valant 7. La liste couleurs devient ['rouge', 'jaune', 'bleu'], car l'affectation d'un élément modifie la liste EN PLACE. Le dictionnaire devient {'nom': 'Ada', 'classe': '1G3', 'moyenne': 16.0, 'option': 'NSI'} : la première affectation remplace la valeur d'une clé existante, la seconde ajoute une clé qui n'existait pas. Les deux s'écrivent de la même façon, ce qui est commode mais explique aussi qu'une faute de frappe sur un nom de clé crée silencieusement une clé de plus au lieu de signaler une erreur.

b) L'erreur est un TypeError, avec un message du genre « tuple object does not support item assignment ». Le tuple est IMMUABLE : une fois créé, aucun de ses éléments ne peut être remplacé. Pour obtenir un point de coordonnées 5 et 7, il faut construire un nouveau tuple, par exemple point = (5, point[1]) ou point = (5, 7). On ne modifie pas un tuple, on le remplace.

c) Une liste est muable, sa taille et son contenu peuvent changer après création ; un tuple est immuable, il est figé. Deux situations où le tuple s'impose. D'abord, pour représenter un ENREGISTREMENT dont les champs ne changent pas de nature, comme un couple de coordonnées ou une date : le lecteur du code sait alors qu'aucune ligne ne viendra le modifier. Ensuite, quand la valeur doit servir de CLÉ de dictionnaire ou d'élément d'ensemble, ce que la question d explique.

d) La règle est qu'une clé de dictionnaire doit être HACHABLE, c'est-à-dire qu'on doit pouvoir en calculer une empreinte numérique stable dans le temps. Un objet muable ne peut pas l'être : si l'on rangeait la liste couleurs à l'emplacement calculé d'après son contenu, puis qu'on modifiait ce contenu, l'objet se retrouverait rangé au mauvais endroit et deviendrait introuvable. Le tuple, immuable, n'a pas ce problème. C'est donc l'immuabilité qui autorise l'usage comme clé, et non une propriété arbitraire du langage.

e) Les clés s'obtiennent par list(eleve.keys()), les valeurs par list(eleve.values()), et le test par 'option' in eleve. Ce test a un coût CONSTANT, c'est-à-dire indépendant du nombre de clés, parce qu'un dictionnaire n'est pas parcouru : la clé est transformée en empreinte, et l'empreinte donne directement l'emplacement où regarder. C'est exactement l'inverse d'un test d'appartenance dans une liste, qui parcourt les éléments un par un et coûte donc proportionnellement à leur nombre. Cette différence est le principal argument pour représenter une ligne de table par un dictionnaire plutôt que par une liste.

a) a et b valent tous deux [1, 2, 3, 4]. L'affectation b = a ne copie pas la liste : elle donne un SECOND NOM au même objet, comme le montre la partie gauche du schéma où les deux flèches aboutissent à la même boîte. Modifier l'objet par l'un des deux noms le modifie donc pour l'autre. Le langage ne signale rien, puisque rien d'anormal ne s'est produit de son point de vue.

b) c vaut [1, 2, 3] et d vaut [1, 2, 3, 4]. L'appel list(c) construit une NOUVELLE liste contenant les mêmes éléments, comme le montre la partie droite du schéma : deux boîtes distinctes. Modifier l'une n'a aucun effet sur l'autre. On obtient le même effet avec c[:] ou avec c.copy().

c) Oui, la table d'origine EST modifiée. list(table) construit bien une nouvelle liste, mais ses cases contiennent les MÊMES dictionnaires que l'original : on a copié le contenant, pas les contenus. copie[0] et table[0] désignent donc le même dictionnaire, et lui ajouter ou changer une clé se voit des deux côtés. C'est précisément le piège : le programmeur croit avoir protégé ses données parce qu'il a écrit une copie, alors qu'il n'a dupliqué qu'un niveau.

d) La copie de SURFACE duplique le conteneur mais partage les objets contenus ; la copie PROFONDE duplique récursivement tout ce qui est atteignable. Sans bibliothèque, pour une table de dictionnaires, on écrit : profonde = [dict(ligne) for ligne in table]. Chaque dict(ligne) construit un nouveau dictionnaire, si bien que ni la liste ni aucune des lignes n'est partagée. Cette expression suffit tant que les valeurs des dictionnaires sont elles-mêmes immuables, ce qui est le cas usuel d'une table chargée depuis un fichier.

e) Trier en place, avec table.sort(), modifie la liste de l'APPELANT, puisque la fonction en a reçu une référence et non une copie. L'appelant retrouve ses données dans un ordre qu'il n'a pas demandé, et souvent bien plus tard, ce qui rend le défaut très difficile à localiser. La bonne pratique tient en une phrase : une fonction qui renvoie un résultat ne doit pas modifier ses arguments, donc on écrit return sorted(table, key=...) et jamais table.sort().

a) Le premier élément est {'station': 'S01', 'ville': 'Montréal', 'temp': '-4.5', 'humidite': '72', 'altitude': '36'}. Toutes les valeurs sont des CHAÎNES de caractères, y compris celles qui ressemblent à des nombres : la méthode split ne fait que découper du texte, elle ne devine aucun type. C'est le point que les copies oublient le plus souvent.

b) table[2]['ville'] vaut 'Sherbrooke', la troisième station puisque l'indexation commence à zéro et que la ligne d'en-tête ne fait pas partie de la table. table[2]['temp'] + 1 provoque un TypeError : on tente d'additionner la chaîne '-7.8' et l'entier 1, ce que Python refuse. Le message parlera de concaténation entre str et int, formulation qui déroute alors qu'elle dit exactement le problème.

c) Il suffit de convertir après le découpage. On remplace la construction du dictionnaire par une boucle explicite : ligne_dict = {} ; puis pour i variant de 0 à len(descripteurs) moins 1 : si descripteurs[i] est dans ('temp', 'humidite', 'altitude') alors ligne_dict[descripteurs[i]] = float(valeurs[i]) sinon ligne_dict[descripteurs[i]] = valeurs[i] ; enfin table.append(ligne_dict). On peut aussi garder une compréhension et écrire une petite fonction convertir(nom_colonne, texte) appelée dedans, ce qui est plus lisible et se teste séparément.

d) La dernière ligne vaut la chaîne vide. Son découpage donne une liste d'un seul élément, la chaîne vide, alors que l'en-tête en compte cinq : la compréhension lève alors un IndexError sur i valant 1. La garde manquante est un test avant traitement : si ligne vaut la chaîne vide, on passe à la suivante, ce qui s'écrit if ligne == '': continue placé juste après le for. Cette garde est indispensable en pratique, presque tous les fichiers réels se terminant par un retour à la ligne.

e) La compréhension parcourt les indices 0 à 4 de descripteurs, mais valeurs n'en a que 4 : l'accès valeurs[4] lève un IndexError. Cela se produit AU CHARGEMENT, ce qui est une chance : l'erreur survient près de sa cause. Le problème est que le message ne dit ni quelle ligne ni quel fichier. Une vérification qui échoue tôt et clairement consiste à comparer les longueurs avant de construire le dictionnaire, et à lever une erreur explicite mentionnant le numéro de ligne et les deux longueurs. Une ligne de contrôle écrite au chargement économise des heures de recherche plus loin dans le programme.

a) On écrit froides = [l for l in table if l['temp'] < -6]. Les températures sont $-4{,}5$, $-9{,}2$, $-7{,}8$, $-3{,}1$ et $-6{,}4$. Sont strictement inférieures à $-6$ : $-9{,}2$, $-7{,}8$ et $-6{,}4$, donc les stations S02, S03 et S05. Attention au sens de l'inégalité sur les nombres négatifs : $-9{,}2$ est bien PLUS PETIT que $-6$, alors qu'une lecture rapide de la valeur absolue conclut l'inverse.

b) On écrit projetee = [{'ville': l['ville'], 'temp': l['temp']} for l in table]. On peut aussi écrire une version générique, [{c: l[c] for c in ('ville', 'temp')} for l in table], qui a l'avantage de se paramétrer par la liste des colonnes voulues et donc de servir pour n'importe quelle projection.

c) On écrit [{'ville': l['ville'], 'temp': l['temp']} for l in table if l['temp'] < -6]. L'ordre ne change pas le RÉSULTAT tant que la colonne du filtre survit à la projection : filtrer puis projeter, ou projeter puis filtrer, donne les mêmes lignes. Il change en revanche le COÛT, car projeter d'abord construit un dictionnaire pour chaque ligne, y compris celles que le filtre va jeter. Sur une table de un million de lignes dont dix survivent, filtrer d'abord évite 999 990 constructions inutiles. Et si la projection supprime la colonne du filtre, alors l'ordre devient obligatoire et non plus préférable.

d) On écrit [l['ville'] for l in table if l['altitude'] > 50 and l['humidite'] > 75]. Vérifions ligne par ligne. Montréal : altitude 36, éliminée. Québec : altitude 98 et humidité 81, retenue. Sherbrooke : altitude 241 mais humidité 69, éliminée. Gatineau : altitude 61 et humidité 77, retenue. Rimouski : altitude 12, éliminée. Le résultat est ['Québec', 'Gatineau'].

e) Une compréhension produit exactement un élément par ligne parcourue : elle ne peut pas décider de n'en produire qu'un pour plusieurs lignes identiques. Deux façons d'obtenir le résultat. La première utilise un ENSEMBLE, qui par définition ne conserve pas les doublons : on écrit set(l['ville'] for l in table), quitte à reconvertir en liste ; l'ordre est alors perdu. La seconde construit la liste à la main, en n'ajoutant une ville que si elle n'y figure pas déjà, ce qui préserve l'ordre de première apparition mais coûte un parcours à chaque ajout. Le choix dépend de ce à quoi on tient, l'ordre ou le coût.

a) On écrit sorted(table, key=lambda l: l['temp']). Les températures dans l'ordre croissant sont $-9{,}2$, $-7{,}8$, $-6{,}4$, $-4{,}5$ et $-3{,}1$, ce qui donne l'ordre S02, S03, S05, S01, S04. Le paramètre key attend une FONCTION qui, appliquée à un élément, renvoie la valeur sur laquelle comparer.

b) Première façon, sorted(table, key=lambda l: l['temp'], reverse=True). Seconde façon, sorted(table, key=lambda l: -l['temp']), qui inverse le signe de la clé. Les deux donnent l'ordre S04, S01, S05, S03, S02. La première est préférable : elle fonctionne quelle que soit la nature de la clé, y compris pour du texte, alors que la seconde ne s'applique qu'aux nombres.

c) Oui. Avant le tri, l'ordre des éléments commençant par B était B2, B1, B3 ; après le tri sur la seule lettre, ils apparaissent dans le même ordre B2, B1, B3, et non réarrangés. Cette propriété s'appelle la STABILITÉ. Elle est utile parce qu'elle rend le tri prévisible, et surtout parce qu'elle permet de construire un tri à plusieurs critères par une suite de tris à un seul critère, ce qui est exactement l'objet de la question suivante.

d) Il faut effectuer d'abord le tri sur la clé la MOINS prioritaire, ici la température décroissante, puis le tri sur la clé la plus prioritaire, ici la ville croissante. Le second tri étant stable, deux lignes de même ville conserveront l'ordre que le premier leur avait donné, c'est-à-dire l'ordre par température décroissante. On écrit donc t = sorted(table, key=lambda l: l['temp'], reverse=True) puis t = sorted(t, key=lambda l: l['ville']). L'ordre inverse ne marcherait pas : le tri par température écraserait le regroupement par ville.

e) La ligne correcte est table.sort(key=lambda l: l['temp']). L'erreur de fond est de confondre une VALEUR et une FONCTION. Le paramètre key ne reçoit pas la valeur d'une clé, il reçoit la fonction que le tri appliquera à chaque élément pour obtenir sa clé de comparaison. Écrire l['temp'] hors de toute boucle n'a d'ailleurs aucun sens, puisque la variable l n'existe pas à cet endroit : Python signalera un NameError, ce qui masque la vraie erreur conceptuelle.

a) Nombre de lignes : len(table), soit 6. Total des relevés : sum(l['releves'] for l in table), soit $1\ 200 + 800 + 1\ 500 + 500 + 2\ 000 + 1\ 000 = 7\ 000$. Total des défauts : sum(l['defauts'] for l in table), soit $36 + 16 + 60 + 5 + 40 + 45 = 202$.

b) La fonction s'écrit ainsi. On part d'un dictionnaire vide groupes. Pour chaque ligne l de la table, on prend v = l[cle] ; si v n'est pas déjà une clé de groupes, on écrit groupes[v] = [] ; puis on ajoute la ligne par groupes[v].append(l). On renvoie groupes à la fin. Pour la colonne region, les clés sont 'Est', 'Ouest' et 'Centre'. Le point délicat est l'initialisation de la liste vide : l'oublier provoque un KeyError sur la première ligne de chaque groupe.

c) Est : $(36 + 16) / (1\ 200 + 800) = 52 / 2\ 000 = 0{,}026$, soit $2{,}60$ pour cent. Ouest : $(60 + 5) / (1\ 500 + 500) = 65 / 2\ 000 = 0{,}0325$, soit $3{,}25$ pour cent. Centre : $(40 + 45) / (2\ 000 + 1\ 000) = 85 / 3\ 000 \approx 0{,}028333$, soit $2{,}83$ pour cent.

d) Moyenne des trois taux : $(2{,}60 + 3{,}25 + 2{,}83) / 3 \approx 2{,}89$ pour cent. Total sur total : $202 / 7\ 000 \approx 0{,}028857$, soit $2{,}89$ pour cent également au centième près, mais les deux nombres ne sont pas égaux : $2{,}8944$ contre $2{,}8857$. Le correct est le SECOND. Le premier donne le même poids aux trois régions, alors que le Centre porte 3 000 relevés et les deux autres 2 000 chacune. Ici l'écart est faible parce que les effectifs sont voisins ; il devient considérable dès que les groupes sont déséquilibrés, et c'est toujours le rapport des sommes qu'il faut écrire.

e) La fonction s'écrit en deux temps. D'abord on appelle groupes = grouper(table, cle). Ensuite, pour chaque clé v de groupes, on calcule d = sum(l['defauts'] for l in groupes[v]) et r = sum(l['releves'] for l in groupes[v]), puis on range taux[v] = d / r. On renvoie taux. Le coût est LINÉAIRE en le nombre de lignes : le regroupement parcourt la table une fois, et les sommes parcourent au total exactement les mêmes lignes une seconde fois, chaque ligne appartenant à un seul groupe. Le nombre de groupes n'intervient pas dans le coût, contrairement à ce qu'une lecture rapide de la double boucle laisse croire.

a) La fonction parcourt chaque ligne g de la table de gauche, et pour chacune parcourt toute la table de droite. Dès qu'une ligne d porte la même valeur de clé, elle construit une nouvelle ligne. dict(g) est essentiel : il crée une COPIE du dictionnaire de gauche, si bien que les colonnes de droite ajoutées ensuite n'écrasent pas la table d'origine. Écrire ligne = g à la place produirait exactement le bug de l'exercice 2 : la table de gauche se retrouverait enrichie des colonnes de droite, ce que personne n'a demandé. La boucle suivante recopie chaque colonne de d dans la ligne, puis la ligne complète est ajoutée au résultat.

b) Si une clé de gauche n'apparaît nulle part à droite, la boucle intérieure ne trouve rien et la ligne est simplement ABSENTE du résultat : c'est une jointure dite interne, qui ne garde que les correspondances. Si la clé apparaît dans deux lignes de droite, la ligne de gauche est appariée DEUX fois et figure deux fois dans le résultat : c'est un doublon de clé, et c'est l'accident le plus dangereux, parce que le programme ne signale rien et que tous les totaux calculés ensuite sont gonflés.

c) Le coût est le produit des tailles, c'est-à-dire $n \times m$ comparaisons, soit un coût QUADRATIQUE quand les deux tables grandissent ensemble. Pour $n = 4\ 000$ et $m = 3\ 900$ : $4\ 000 \times 3\ 900 = 15\ 600\ 000$ comparaisons, soit plus de quinze millions pour une opération que l'on croit anodine.

d) On construit d'abord index = {} puis, pour chaque ligne d de droite, index[d[cle]] = d. Ensuite, pour chaque ligne g de gauche, on regarde si g[cle] est dans index, et si oui on fabrique la ligne fusionnée. Le coût devient $m$ pour construire l'index, plus $n$ recherches à coût constant, soit $n + m$ opérations, c'est-à-dire un coût LINÉAIRE. Pour les mêmes tailles : $4\ 000 + 3\ 900 = 7\ 900$ opérations. Le facteur de gain vaut $15\ 600\ 000 / 7\ 900 \approx 1\ 975$, soit près de deux mille fois plus rapide. C'est exactement l'argument de l'exercice 1 : la recherche dans un dictionnaire ne parcourt rien.

e) La vérification consiste à comparer, pour chaque table, le nombre de lignes au nombre de valeurs DISTINCTES de la clé, ce qui s'écrit len(table) == len(set(l[cle] for l in table)). Elle détecte deux accidents. D'abord les DOUBLONS de clé, qui feraient exploser le nombre de lignes du résultat et fausseraient les agrégats. Ensuite, en comparant le nombre de clés communes au nombre attendu, les clés qui NE SE CORRESPONDENT PAS, presque toujours à cause d'espaces en trop, de majuscules ou d'un zéro initial perdu lors d'un passage par un tableur. Ces deux contrôles tiennent en trois lignes et évitent la classe entière des résultats faux mais plausibles.

1) FAUX. L'affectation ne construit aucun objet : elle donne un second nom au même objet. Après b = a, toute modification faite par l'un se voit par l'autre, et b.append(4) allonge la liste que a désigne aussi. Énoncé correct : b = a crée un alias ; pour obtenir une copie il faut écrire b = list(a), b = a[:] ou b = a.copy().

2) FAUX. list(table) duplique la LISTE mais pas les dictionnaires qu'elle contient : copie[0] et table[0] désignent le même dictionnaire. Énoncé correct : list(table) est une copie de surface ; pour protéger les lignes il faut une copie profonde, par exemple [dict(l) for l in table].

3) FAUX. La méthode split découpe du texte et rien d'autre : toutes les valeurs sont des chaînes, y compris '42' et '-7.8'. Énoncé correct : un chargement de CSV doit convertir explicitement les colonnes numériques avec int ou float ; sans conversion, une addition provoque un TypeError et une comparaison donne un ordre alphabétique, donc faux.

4) FAUX. Une recherche dans un dictionnaire ne parcourt pas les entrées : la clé est transformée en empreinte, et l'empreinte désigne directement l'emplacement à consulter. Le coût est constant, indépendant du nombre d'entrées. Énoncé correct : c'est la recherche dans une LISTE qui coûte proportionnellement au nombre d'éléments, et c'est précisément ce qui justifie d'indexer une table par dictionnaire avant une fusion.

5) FAUX. Dans un tri stable à deux passes, c'est le DERNIER tri effectué qui devient le critère principal. Trier par ville puis par température donne un résultat ordonné d'abord par température ; l'inverse donne un résultat ordonné d'abord par ville. Énoncé correct : pour trier par ville puis, à ville égale, par température, il faut trier d'abord par température, puis par ville.

a) La droite correspond au FILTRE : on regarde chaque ligne une fois, donc le coût est proportionnel à $n$. La courbe intermédiaire correspond au TRI : les bons algorithmes de tri par comparaison coûtent de l'ordre de $n \log_{2} n$, et l'on ne peut pas faire mieux dans ce modèle. La courbe la plus raide correspond à la FUSION NAÏVE, qui compare chaque ligne de gauche à chaque ligne de droite, soit $n^{2}$ comparaisons quand les deux tables ont la même taille.

b) Pour $n = 40$ : le filtre coûte 40 ; le tri coûte $40 \times \log_{2}(40) \approx 40 \times 5{,}32 \approx 213$ ; la fusion naïve coûte $40^{2} = 1\ 600$. Le rapport entre la plus grande et la plus petite vaut $1\ 600 / 40 = 40$. À cette échelle, la différence est réelle mais pas dramatique : une machine absorbe les trois sans qu'on s'en aperçoive.

c) Pour $n = 10^{6}$ : le filtre coûte $10^{6}$ ; le tri coûte $10^{6} \times \log_{2}(10^{6}) \approx 10^{6} \times 19{,}93 \approx 1{,}99 \times 10^{7}$ ; la fusion naïve coûte $10^{12}$. Le rapport entre la plus grande et la plus petite vaut $10^{12} / 10^{6} = 10^{6}$, soit un million au lieu de 40. Conclusion : un graphique de coût lu sur de petites valeurs est trompeur, car il écrase précisément ce qui fait toute la différence. Ce qui compte n'est pas la hauteur des courbes à gauche, c'est leur FORME, et la forme ne se voit qu'en poussant $n$.

d) À $10^{8}$ opérations par seconde : le filtre prend $10^{6} / 10^{8} = 0{,}01$ s, soit un centième de seconde. Le tri prend $1{,}99 \times 10^{7} / 10^{8} \approx 0{,}20$ s, soit un cinquième de seconde. La fusion naïve prend $10^{12} / 10^{8} = 10^{4}$ s, soit $10^{4} / 3\ 600 \approx 2{,}78$ heures. C'est la différence entre une page web qui s'affiche et un traitement qu'il faut lancer le soir pour le retrouver le lendemain.

e) Doubler la vitesse de la machine double le nombre d'opérations réalisables dans le même temps. Pour un coût LINÉAIRE, la taille traitable est donc multipliée par 2. Pour un coût en $n \log n$, elle est multipliée par un peu moins de 2, environ $1{,}9$ sur ces ordres de grandeur, l'écart venant du logarithme. Pour un coût QUADRATIQUE, il faut résoudre $(kn)^{2} = 2 n^{2}$, donc $k = \sqrt{2} \approx 1{,}41$ : la taille traitable n'augmente que de 41 pour cent. Autrement dit, dix ans de progrès du matériel offriraient un facteur mille sur la vitesse et seulement un facteur $\sqrt{1\ 000} \approx 31{,}6$ sur la taille, alors que remplacer la fusion naïve par la fusion indexée offre immédiatement un facteur de plusieurs milliers. On ne rattrape jamais un mauvais algorithme avec du matériel.

a) La structure reste identique à celle de l'exercice 3. Trois changements. La signature devient charger(nom, numeriques), où numeriques est la liste des colonnes à convertir. La garde du fichier vide est ajoutée : si la ligne est vide, on passe à la suivante. Enfin, la construction du dictionnaire ne se fait plus par une compréhension unique mais colonne par colonne : pour chaque indice i, on écrit float(valeurs[i]) si descripteurs[i] appartient à numeriques, et valeurs[i] sinon. On peut aussi contrôler à ce moment que len(valeurs) vaut len(descripteurs), et lever une erreur explicite mentionnant le numéro de ligne, comme l'exercice 3 le recommandait.

b) On indexe d'abord la table des résultats : index = {} puis, pour chaque ligne r de resultats, index[r['dossard']] = r. Ensuite, pour chaque ligne a de athletes, si a['dossard'] est dans index, on construit ligne = dict(a), on y recopie les colonnes de index[a['dossard']], et on ajoute ligne au résultat. Le coût est linéaire, $n + m$ opérations, contre $n \times m$ pour la version à deux boucles imbriquées. La copie par dict(a) est indispensable pour ne pas polluer la table des athlètes.

c) On écrit avec_total = [dict(l, temps_corrige=l['temps'] + l['penalite']) for l in fusion]. La forme dict(l, cle=valeur) construit un NOUVEAU dictionnaire à partir de l en y ajoutant la clé demandée, si bien que la table d'origine reste intacte. Écrire à la place une boucle qui ferait l['temps_corrige'] = ... modifierait les lignes de la table fusionnée, ce qui est acceptable si elle appartient à l'appelant, et dangereux sinon.

d) L'algorithme. Un, grouper les lignes par pays dans un dictionnaire, comme à l'exercice 6. Deux, pour chaque pays, calculer len du groupe, min des temps corrigés et sum divisé par len. Trois, renvoyer un dictionnaire de dictionnaires. Application. Canada : 3 athlètes, temps $141{,}2$, $135{,}9$ et $152{,}6$ ; meilleur $135{,}9$ ; moyenne $(141{,}2 + 135{,}9 + 152{,}6) / 3 = 429{,}7 / 3 \approx 143{,}23$. France : 2 athlètes, $138{,}7$ et $133{,}4$ ; meilleur $133{,}4$ ; moyenne $272{,}1 / 2 = 136{,}05$. Suisse : 1 athlète, $144{,}0$ ; meilleur $144{,}0$ ; moyenne $144{,}0$.

e) Les meilleurs temps sont France $133{,}4$, Canada $135{,}9$, Suisse $144{,}0$ : aucun n'est à égalité, donc le classement est France, Canada, Suisse. Pour l'écrire en deux tris successifs, on trie d'abord sur le critère le MOINS prioritaire, le nombre d'athlètes décroissant, puis sur le critère le plus prioritaire, le meilleur temps croissant : la stabilité du second tri conserve alors, entre pays de même meilleur temps, l'ordre par nombre d'athlètes décroissant. On peut aussi écrire le tri en une passe, avec une clé composée renvoyant le couple formé du meilleur temps et de l'opposé du nombre d'athlètes : les tuples se comparant terme à terme, l'effet est exactement le même et le code est plus court.

a) Le premier mot, le, n'est pas encore une clé : il est ajouté avec la valeur 1. Chaque nouvelle rencontre augmente son compteur. On obtient {'le': 4, 'chat': 2, 'voit': 2, 'chien': 2, 'et': 1}. Depuis Python 3.7, un dictionnaire conserve l'ordre d'insertion des clés : les mots apparaissent dans l'ordre de leur première rencontre.

b) len(occ) vaut 5 : c'est le nombre de mots DISTINCTS. sum(occ.values()) vaut 11 : c'est le nombre total de mots de la phrase, chaque occurrence ayant été comptée une fois. Vérifier que la somme des compteurs redonne la longueur de la liste est un contrôle simple et efficace.

c) On part de meilleur = None et maxi = 0 ; pour chaque couple (mot, n) de occ.items(), si n > maxi, on met à jour maxi = n et meilleur = mot. On obtient le mot le, avec 4 occurrences. En une ligne, max(occ, key=occ.get) donne le même mot : max parcourt les clés et compare leurs valeurs.

d) Au premier mot, occ['le'] n'existe pas encore : la lecture occ[m] lève une KeyError et le programme s'arrête. On lit une clé absente avec get et une valeur par défaut : occ[m] = occ.get(m, 0) + 1. La méthode get renvoie 0 si la clé manque, sans erreur.

e) [m for m, n in occ.items() if n == 2], qui donne ['chat', 'voit', 'chien'], dans l'ordre d'insertion. Le parcours de items fournit à chaque tour un tuple (clé, valeur), dépaqueté dans les deux variables m et n.

a) r vaut (1, 9), de type tuple : écrire deux valeurs séparées par une virgule après return construit un tuple, les parenthèses étant facultatives. On dépaquette avec mini, maxi = min_max([4, 9, 1, 7]), qui donne mini = 1 et maxi = 9.

b) a vaut 8 et b vaut 3. Le membre de droite b, a est entièrement évalué AVANT l'affectation : on construit le tuple (8, 3), puis on le dépaquette. Avec a = b puis b = a, la première ligne écrase la valeur 3 : a et b valent tous deux 8, et l'ancienne valeur de a est perdue.

c) ('Ada', 15) < ('Ada', 16) vaut True : premiers termes égaux, on compare les seconds. ('Bob', 2) < ('Ada', 20) vaut False : les premiers termes diffèrent, 'Bob' vient après 'Ada', et le second terme n'est même pas regardé. (2, 'z') < (10, 'a') vaut True : 2 < 10 décide seul. La comparaison s'arrête au premier terme qui diffère.

d) La clé associe à chaque élève le tuple (opposé de la note, nom). On obtient [('Ada', 17), ('Eve', 17), ('Bob', 14), ('Lin', 14)] : par note DÉCROISSANTE grâce au signe moins, puis par nom croissant à note égale. Un seul tri avec une clé tuple remplace les deux tris successifs d'un tri stable.

e) (5) est de type int : les parenthèses ne font que grouper une expression, comme dans (2 + 3) * 4. (5,) est un tuple d'un seul élément : c'est la VIRGULE qui fabrique le tuple, pas les parenthèses. Oublier la virgule donne un entier, et une instruction comme len((5)) lève alors une TypeError.

a) ';'.join(['nom', 'note', 'rang']) vaut 'nom;note;rang'. Le séparateur est placé ENTRE les éléments, jamais à la fin : trois colonnes, deux points-virgules.

b) join n'accepte que des chaînes : l['note'] est un flottant et l['rang'] un entier, donc une TypeError est levée. On convertit chaque valeur : ';'.join([l['nom'], str(l['note']), str(l['rang'])]), ou en compréhension ';'.join(str(l[c]) for c in ['nom', 'note', 'rang']).

c) Pour un tableur réglé en français, le point n'est pas un séparateur décimal : 15.5 risque d'être lu comme du texte, voire comme une date. Il faut écrire 'Ada;15,5;2', en remplaçant le point par une virgule dans la note, par exemple avec str(l['note']).replace('.', ','). C'est d'ailleurs la raison du choix du point-virgule : la virgule est déjà prise par les nombres.

d) La ligne 'Dupont; Jean;12,0;3' contient trois points-virgules, donc le tableur lit 4 champs au lieu de 3, et toutes les colonnes suivantes sont décalées. La norme CSV entoure de guillemets droits tout champ qui contient le séparateur : le nom ainsi protégé n'est plus découpé, et la ligne se relit bien en trois champs. D'où l'intérêt d'utiliser le module csv de la bibliothèque standard, qui gère ces cas.

e) 'nom;note;rang\n' compte 13 caractères plus la fin de ligne, soit 14 octets. 'Ada;15,5;2\n' et 'Bob;17,0;1\n' comptent 11 octets chacune. Total : 14 + 11 + 11 = 36 octets, tous les caractères étant en ASCII.

a) ' Ada Lovelace '.strip().lower() vaut 'ada lovelace'. ' '.join('alan turing'.split()) vaut 'alan turing' : split sans argument coupe sur toute suite d'espaces, et join recolle avec un seul espace. strip ne retire que les espaces AUX BORDS : 'alan turing', avec deux espaces au milieu, resterait différent de 'alan turing'.

b) Avec strip puis lower, on obtient 'ada lovelace', 'alan turing', 'grace hopper' et 'alan turing' : 4 valeurs, car les deux Alan Turing diffèrent encore par l'espace double. Avec normaliser, qui fait lower, split et join, il n'en reste que 3.

c) On parcourt la liste en tenant un ensemble vus des noms déjà rencontrés ; on n'ajoute un nom au résultat que s'il n'est pas dans vus. Résultat : ['ada lovelace', 'alan turing', 'grace hopper']. L'ensemble sert au test rapide, la liste garde l'ordre, que l'ensemble seul perdrait.

d) Avec une liste, le k-ième nom est comparé aux noms déjà gardés, au pire k - 1 comparaisons : au total $0 + 1 + \dots + 9\ 999 = \frac{10\ 000 \times 9\ 999}{2} = 49\ 995\ 000$ comparaisons. Avec un ensemble, chaque test a un coût constant : de l'ordre de 10 000 opérations, cinq mille fois moins.

e) Deux personnes différentes peuvent porter le même nom : les fusionner supprime une inscription réelle, sans aucun message. Le nom n'est pas une CLÉ fiable. Il faut dédoublonner sur une donnée qui identifie vraiment la personne, par exemple le couple formé du nom normalisé et de la date de naissance, ou l'adresse électronique normalisée.

def sans_doublons(noms):
    vus = set()
    resultat = []
    for s in noms:
        k = normaliser(s)
        if k not in vus:          # test a cout constant
            vus.add(k)
            resultat.append(k)
    return resultat

# ['ada lovelace', 'alan turing', 'grace hopper']

a) livres['978-3'] est le dictionnaire du livre Les Robots, et son champ 'auteur' vaut 'Asimov' : on enchaîne les deux accès. livres['978-9'] lève une KeyError, la clé n'existant pas. livres.get('978-9') renvoie None sans erreur.

b) On part de nb = {} ; pour chaque couple (code, lecteur) de prets, on écrit nb[code] = nb.get(code, 0) + 1. On obtient {'978-2': 3, '978-1': 1, '978-3': 1}. Le code le plus emprunté est '978-2', et livres['978-2']['titre'] vaut 'Fondation'.

c) set(livres) - {code for code, lecteur in prets} : l'ensemble des clés du dictionnaire privé de l'ensemble des codes empruntés. On obtient {'978-4'}, soit le livre Hypérion. La différence d'ensembles exprime directement la question posée.

d) Les emprunts d'Asimov sont ceux des codes '978-2' et '978-3' : 3 + 1 = 4 emprunts. Les lecteurs sont Lina, Sam, Noé pour Fondation et Lina pour Les Robots : {lecteur for code, lecteur in prets if livres[code]['auteur'] == 'Asimov'} donne 3 lecteurs différents, Lina n'étant comptée qu'une fois.

e) Parcourir la liste prets coûte un temps proportionnel au nombre d'emprunts, à chaque question posée. Un ensemble de tuples répond en temps constant : ('978-2', 'Lina') in deja fait un seul calcul d'empreinte. Le tuple convient comme élément d'ensemble parce qu'il est immuable ; une liste [code, lecteur] serait refusée.