Revision sheet: P-uplets nommés et dictionnaires

📋 Plan du Cours

1. P-uplets nommés en Python
2. Lecture de tables CSV
3. Calculs sur des p-uplets
4. Dictionnaire : principe et opérations
5. Dictionnaires Python et complexité
6. Dépouillement avec un dictionnaire
7. Tables de hachage
8. Tri par dénombrement

📖 1. P-uplets nommés en Python

🔑 Notions clés & Définitions

• P-uplet nommé : Un p-uplet nommé est un p-uplet dont les composantes sont accessibles via un descripteur au lieu d’un indice.

📝 Points essentiels

★ À maîtriser

• L’utilisation de p-uplets nommés améliore la lisibilité du code et réduit les risques d’erreurs.

Compléments

📌 Python ne possède pas nativement le type p-uplet nommé, qui peut être représenté par le module collections.namedtuple ou, dans ce cours, par un dictionnaire.

• Le dictionnaire {"nom": "X", "prenom": "Monsieur", "age": 47} représente un p-uplet nommé dont la valeur du champ age est obtenue par monsieurX["age"].

💡 Astuce mémo

Descripteur plutôt qu’indice

📖 2. Lecture de tables CSV

📝 Points essentiels

★ À maîtriser

🔄 Processus — Pour lire une ligne de fichier CSV séparée par des points-virgules, il faut supprimer les espaces de fin avec strip(), puis séparer les champs avec split(";").

🔄 Processus — Si la première ligne contient les noms des colonnes, il faut la lire, la découper avec split(";"), puis utiliser chaque nom comme clé pour construire automatiquement les dictionnaires des lignes suivantes.

Compléments

🔄 Processus — Lorsque les quatre premières colonnes sont nom, DS1, DS2 et projet, chaque ligne peut être transformée en dictionnaire en associant ces clés aux éléments de données[0] à données[3].

• Après extraction, notes[0]["DS1"] renvoie la note du premier élève au devoir DS1.

💡 Astuce mémo

Lire, découper, associer

📖 3. Calculs sur des p-uplets

📝 Points essentiels

★ À maîtriser

📐 Formule — La moyenne calculée pour chaque élève est (DS1 + DS2 + 2 × projet) / 4.

🔄 Processus — Pour calculer cette moyenne, les valeurs des champs DS1, DS2 et projet sont converties en flottants avant l’application de la formule.

Compléments

🔄 Processus — La fonction extrait_données ouvre le fichier, construit un tableau de dictionnaires, ferme le fichier et renvoie ce tableau.

• La fonction notes_et_moyennes ajoute à chaque dictionnaire un champ nommé moyenne.

• Une amélioration proposée consiste à ajouter au fichier CSV une ligne indiquant le type de chaque colonne parmi DS, DM, projet et autre afin d’automatiser la sélection des colonnes, les conversions et les coefficients.

💡 Astuce mémo

Convertir puis calculer

📖 4. Dictionnaire : principe et opérations

🔑 Notions clés & Définitions

• Dictionnaire : Associe à une clé appartenant à un ensemble C une valeur appartenant à un ensemble V.

📝 Points essentiels

★ À maîtriser

🔄 Processus — Les opérations fondamentales d’un dictionnaire sont la création d’un dictionnaire vide, l’ajout ou la modification d’une association et la lecture de la valeur associée à une clé.

📌 La lecture d’une clé à laquelle aucune valeur n’est associée déclenche une erreur.

Compléments

• Un dictionnaire peut aussi permettre de supprimer une entrée, de tester la présence d’une clé et de renvoyer toutes ses clés.

📌 Un dictionnaire est surtout utile pour rechercher rapidement une clé précise, tandis qu’un tableau convient également pour parcourir toutes les données.

💡 Astuce mémo

Clé → valeur

📖 5. Dictionnaires Python et complexité

📝 Points essentiels

★ À maîtriser

🔄 Processus — En Python, on crée un dictionnaire vide avec d = {}, on associe v à c avec d[c] = v et on lit la valeur avec d[c].

🔄 Processus — En Python, c in d teste la présence d’une clé, del d[c] supprime son entrée et d.pop(c) la supprime en renvoyant la valeur supprimée.

• Les opérations de base d’un dictionnaire Python ont une complexité en gros en O(1), tandis que c in d.keys() peut avoir une complexité en O(n).

Compléments

🔄 Processus — La méthode keys permet de parcourir les clés avec une boucle for c in d.keys().

📌 Les dictionnaires Python sont modifiables, ce qui impose de tenir compte des effets des copies et des procédures qui les modifient.

💡 Astuce mémo

Présence rapide, accès direct

📖 6. Dépouillement avec un dictionnaire

📝 Points essentiels

★ À maîtriser

🔄 Processus — Pour dépouiller une urne en un seul parcours, un dictionnaire associe chaque nom de candidat à son nombre de voix.

🔄 Processus — La procédure incr_dico incrémente la valeur d’une clé déjà présente et initialise cette valeur à 1 lorsque la clé est absente.

🔄 Processus — La fonction dépouillement parcourt l’urne, met à jour le dictionnaire des voix, puis conserve le nom dont le nombre de voix est strictement supérieur au maximum courant.

Compléments

📌 La fonction dépouillement ne traite pas le cas de deux vainqueurs ex æquo.

💡 Astuce mémo

Compter puis comparer

📖 7. Tables de hachage

🔑 Notions clés & Définitions

• Fonction de hachage : Associe un nombre entier à tout objet persistant et son temps d’exécution est supposé en O(1).
• Table de hachage : Un tableau de tableaux contenant des couples clé-valeur, chaque couple étant rangé dans une case déterminée par hash(c) % d, où d est la longueur du tableau principal.

📝 Points essentiels

★ À maîtriser

🔄 Processus — Pour rechercher une clé dans une table de hachage, on calcule son hachage afin de déterminer la case dans laquelle se trouve sa valeur.

• Dans une table de hachage, l’insertion et la lecture ont une complexité moyenne en O(1), même si une case trop remplie peut ralentir la recherche.

Compléments

• Deux clés peuvent produire la même case et être stockées ensemble dans une liste de couples, phénomène appelé collision dans l’exemple de la table de longueur 3.

📌 Python agrandit automatiquement la table lorsque le rapport entre le nombre d’éléments et le nombre de cases devient supérieur à 2/3.

💡 Astuce mémo

Hacher pour ranger

📖 8. Tri par dénombrement

🔑 Notions clés & Définitions

• Tri par dénombrement : Trie un tableau d’entiers en comptant les occurrences de chaque valeur puis en reconstruisant un nouveau tableau dans l’ordre croissant.

📝 Points essentiels

★ À maîtriser

🔄 Processus — La fonction compte construit un dictionnaire associant chaque valeur du tableau à son nombre d’occurrences et détermine simultanément son minimum et son maximum.

🔄 Processus — La fonction tri_dénombrement parcourt toutes les valeurs de l’intervalle [mini, maxi], puis ajoute chaque valeur dans le tableau résultat autant de fois que l’indique le dictionnaire.

📐 Formule — Pour un tableau de n éléments, de minimum m et de maximum M, la complexité du tri par dénombrement est O(n + M − m).

Compléments

🔄 Processus — La méthode get(i, 0) renvoie la valeur associée à i ou 0 lorsque i n’est pas une clé du dictionnaire.

• Le tri par dénombrement est particulièrement efficace lorsque l’amplitude des nombres à trier n’est pas trop grande.

💡 Astuce mémo

Compter, parcourir, reconstruire

📊 Tableaux de synthèse

Opérations fondamentales des dictionnaires

Opération	Syntaxe Python	Effet
Création	d = {}	Crée un dictionnaire vide
Association	d[c] = v	Associe v à la clé c
Lecture	d[c]	Renvoie la valeur associée
Test	c in d	Teste la présence de c
Suppression	del d[c] ou d.pop(c)	Supprime l’entrée de c

⚠️ Pièges & confusions fréquents

1. Un p-uplet nommé se distingue d’un p-uplet classique par l’accès nommé et non indexé.
2. La première ligne est l’en-tête et ne doit pas être traitée comme une ligne d’élève.
3. Le projet possède ici un coefficient deux, contrairement à DS1 et DS2.
4. Un dictionnaire n’associe pas nécessairement une valeur à chaque élément possible de C.
5. del d[c] déclenche une erreur si c n’est pas présente.
6. Les clés d’un dictionnaire Python doivent être persistantes, donc non mutables.
7. Ce tri ne s’applique qu’aux tableaux d’entiers et n’est pas réalisé en place.
8. Un p-uplet est également appelé tuple en Python