Université de Genève · CUI BSc · Algorithmique & Structures de données

Fondamentaux Python II : POO et structures de données

Séminaire 3

1 / 14

Ordre du jour

Structures de données — choisir list / tuple / dict / set
Fonctions — paramètres obligatoires vs optionnels (bases d'abord)
POO depuis les bases — classe, constructeur (__init__), self
Variables de classe + les quatre piliers de la POO

2 / 14

Collections intégrées en un coup d'œil

Type	Ordonné	Modifiable	Unique	Utilisation
list	✓	✓	✗	Séquences, piles
tuple	✓	✗	✗	Enregistrements fixes, clés
dict	✓ (3.7+)	✓	Clés uniquement	Mapping clé→valeur
set	✗	✓	✓	Tests d'appartenance, déduplication

3 / 14

Choisir la bonne structure

Besoin d'une séquence ordonnée que vous allez modifier ? → list
Enregistrement fixe ou clé de dictionnaire ? → tuple (immuable = utilisable comme clé)
Recherche rapide par clé, comptage, cache ? → dict — O(1) average
Test d'appartenance, déduplication ? → set — O(1) average
Règle générale : commencez par la structure la plus simple qui convient
Un mauvais choix ≠ une mauvaise réponse, mais ça peut signifier O(n) vs O(1)

4 / 14

Fonctions — Concepts clés

Une fonction est un bloc nommé et réutilisable de calcul
Types de paramètres clés pour aujourd'hui : positionnels + valeurs par défaut
Bonus pour plus tard : *args / **kwargs lorsque les API ont besoin de flexibilité
Valeurs de retour : toute fonction renvoie quelque chose (None si implicite)
Portée (première approche) : les variables locales existent uniquement à l'intérieur de la fonction
Les annotations de type documentent l'intention et permettent l'analyse statique
def add(a: int, b: int) -> int

5 / 14

Qu'est-ce que la POO ?

Procédural : des fonctions opèrent sur des données séparées
Orienté objet : regrouper données et comportements dans des objets
Idée centrale — modéliser le monde :
Classe = plan (quels attributs et méthodes existent)
Objet = instance (une chose concrète construite à partir du plan)
Pourquoi la POO dans ce cours ?
Les structures de données (pile, file, arbre) sont naturellement des objets
L'encapsulation protège les invariants (ex. solde ≥ 0)

6 / 14

Classe vs Objet

Classe = modèle définissant attributs et méthodes
Objet = instance concrète avec son propre état
Plusieurs objets à partir d'une même classe, chacun indépendant
alice.grade = 87, bob.grade = 42

7 / 14

Les classes en Python — Anatomie

Une classe définit données et comportement. Concentrez-vous sur le constructeur et self :

class Student:
    def __init__(self, name, grade):   # constructor
        # __init__ runs automatically on Student(...)
        self.name = name               # saved on THIS object
        self.grade = grade

    def is_passing(self):             # instance method
        return self.grade >= 50

8 / 14

Constructeur (init) et self

Lorsque vous appelez Student('Alice', 87), Python crée un nouvel objet.

Ensuite Python appelle __init__(self, ...) pour initialiser cet objet.

self signifie : l'instance courante en cours d'initialisation ou d'utilisation.

alice = Student('Alice', 87)
bob = Student('Bob', 42)

print(alice.name, alice.grade)   # Alice 87
print(bob.name, bob.grade)       # Bob 42

9 / 14

Variables de classe vs attributs d'instance

Variable de classe = partagée par tous les objets de la classe.

Attribut d'instance = stocké séparément dans chaque objet.

class Student:
    school = 'UNIGE'              # class variable (shared)

    def __init__(self, name):
        self.name = name          # instance attribute (per object)

    def label(self):
        return f"{self.name} @ {self.__class__.school}"

print(Student.school)             # access via class
print(Student('Alice').label())   # access via method/self

10 / 14

POO — Les quatre piliers

Encapsulation — regrouper données et méthodes ; cacher les détails internes
Convention : _préfixe pour attributs privés (self._balance)
Abstraction — exposer une interface propre, cacher la complexité
Les utilisateurs appellent account.deposit(100), pas account._update_ledger()
Héritage — class Dog(Animal): — réutiliser et spécialiser
La sous-classe hérite de tous les attributs/méthodes, peut les redéfinir
Polymorphisme — même interface, comportements différents selon la classe
Exemple : dog.speak() -> 'Woof', cat.speak() -> 'Meow'

11 / 14

Exercices d'aujourd'hui

Exercice principal 1 — Mise en train sur les compréhensions : uniques triés, dict par longueur, mots répétés
Exercice principal 2 — Compteur de fréquence de caractères utilisant un dict
Exercice principal 3 — Supprimer les doublons sans utiliser set() — conserver l'ordre
Exercice principal 4 — Fusionner deux dicts (boucle et .update())
Exercice principal 5 — Classe Student : __init__, add_grade, average, is_passing
Bonus — best_subject, report(), et améliorations supplémentaires

12 / 14

Points clés

Choisissez votre structure de données délibérément — elle façonne la complexité
Commencez par les bases des fonctions ; les signatures avancées sont un bonus aujourd'hui
POO = données + comportement au même endroit ; classe = modèle, objet = instance
__init__ est le constructeur ; self fait référence à l'objet courant
Les variables de classe sont partagées ; les attributs d'instance appartiennent à chaque objet
Quatre piliers : encapsulation, abstraction, héritage, polymorphisme
La semaine prochaine : appliquer ces structures à de vrais algorithmes

13 / 14