Scheda di revisione: Introduction aux Structures et Parcours en POO

📋 Plan du Cours

1. Interface, implémentation et encapsulation
2. Héritage et polymorphisme en POO
3. Pile et opérations LIFO en Python
4. File et opérations FIFO en Python
5. Dictionnaires et parcours clé valeur
6. Arbres binaires et ABR
7. Taille, hauteur et profondeur des arbres
8. Parcours d arbres préfixe infixe suffixe
9. Recherche et insertion dans un ABR
10. Arbres AVL et complexité logarithmique
11. Graphes : sommets, arêtes et connexité
12. DFS et BFS pour parcourir un graphe

📖 1. Interface, implémentation et encapsulation

🔑 Notions clés & Définitions

• Interface : Une interface décrit les fonctionnalités attendues d’un composant sans préciser comment elles sont réalisées.
• Implémentation : Une implémentation correspond au code concret qui réalise les fonctionnalités annoncées par une interface.
• Encapsulation : L’encapsulation protège les données internes d’une classe en les rendant privées et en n’autorisant l’accès que via des méthodes publiques.
• Héritage : L’héritage permet à une classe de réutiliser et d’étendre le comportement d’une autre classe.
• Polymorphisme : Le polymorphisme permet d’utiliser une même interface avec des types différents, chacun pouvant redéfinir ses méthodes.

📝 Points essentiels

• Une interface sert de contrat : elle impose des méthodes/behaviors à fournir, sans détails d’exécution.
• Une implémentation est la version concrète du contrat, donc elle peut varier selon le type ou le module.
• En encapsulation, les attributs internes sont typiquement privés, et l’accès passe par des méthodes publiques.
• Les méthodes publiques peuvent modifier l’état interne (ex. mise à jour d’un attribut) tout en contrôlant l’accès.
• L’héritage favorise la réutilisation : une classe enfant ajoute ou spécialise le comportement de la classe parent.
• Le polymorphisme s’exprime quand un même appel fonctionne sur des objets de classes différentes grâce à une interface commune.

💡 Astuce mémo

Interface = contrat (quoi), Implémentation = code (comment), Encapsulation = coffre (données privées), Héritage = réutiliser, Polymorphisme = même appel, comportements différents.

📖 2. Héritage et polymorphisme en POO

🔑 Notions clés & Définitions

• Héritage : L’héritage est un mécanisme de POO où une classe enfant réutilise et étend le comportement d’une classe parent.
• Polymorphisme : Le polymorphisme est la capacité d’utiliser une même interface pour exécuter des comportements différents selon le type réel de l’objet.
• Classe mère : Une classe mère est la classe de base dont les attributs et méthodes peuvent être hérités par d’autres classes.
• Classe fille : Une classe fille est une classe qui hérite d’une classe mère et peut ajouter ou redéfinir des comportements.

📝 Points essentiels

• Le polymorphisme s’exprime quand une méthode appelée sur une référence de type parent s’exécute avec la version adaptée au type réel de l’objet.
• L’héritage permet de factoriser du code commun dans la classe mère pour éviter la duplication dans les classes filles.
• Une classe fille peut étendre un comportement en ajoutant des méthodes ou en modifiant le comportement existant.
• Pour obtenir le bon comportement polymorphe, la méthode concernée doit être redéfinie dans la classe fille.
• Le polymorphisme repose sur la relation parent→enfant : un objet de classe fille est utilisable là où un objet de classe mère est attendu.
• Le couple héritage + polymorphisme rend le code plus extensible : on ajoute de nouvelles classes filles sans changer l’interface utilisée côté appelant.

💡 Astuce mémo

Héritage = réutiliser (parent→enfant) ; polymorphisme = choisir le bon comportement (même appel, exécution différente).

📖 3. Pile et opérations LIFO en Python

🔑 Notions clés & Définitions

• Pile : Structure de données où le dernier élément ajouté est le premier à être retiré, selon le principe LIFO.
• LIFO : Principe d’accès où l’élément traité en premier est celui qui a été inséré le plus récemment.
• Opération push : Ajout d’un élément au sommet de la pile, sans modifier l’ordre relatif des éléments déjà présents.
• Opération pop : Retrait de l’élément situé au sommet de la pile, c’est-à-dire le plus récent parmi ceux encore présents.

📝 Points essentiels

• LIFO signifie Last In, First Out : le dernier empilé est le premier dépilé.
• Une pile se modélise naturellement avec une structure de type liste, en manipulant l’extrémité correspondant au sommet.
• push ajoute au sommet, tandis que pop retire depuis le sommet.
• Si la pile est vide, une opération pop n’a pas d’élément à retirer et doit être gérée (selon l’implémentation).
• Le sommet de la pile est l’unique zone d’accès : on ne retire pas un élément “au milieu” sans le dépiler d’abord.
• Comparaison : LIFO (pile) traite le plus récent en premier, alors que FIFO (file) traite le plus ancien en premier.

💡 Astuce mémo

LIFO = “dernier entré, premier sorti” : sommet = dernier arrivé.

📖 4. File et opérations FIFO en Python

🔑 Notions clés & Définitions

• File (queue) : Une file est une structure de données où le premier élément ajouté est le premier à être retiré (principe FIFO).
• Opération pop(0) : L’opération pop(0) retire et renvoie l’élément situé au début de la liste, ce qui simule une file FIFO.
• Parcours en largeur : Le parcours en largeur explore un arbre ou un graphe niveau par niveau en utilisant une file FIFO.
• FIFO : FIFO signifie First In, First Out : l’ordre de sortie suit l’ordre d’entrée.

📝 Points essentiels

• Dans une file FIFO, l’élément le plus ancien est toujours celui qui sort en premier.
• En Python, une file peut être simulée avec une liste, en retirant le premier élément via file.pop(0).
• Le parcours en largeur initialise la file avec la racine puis répète : retirer le premier nœud, ajouter ses enfants à la fin de la file.
• L’ordre produit par le parcours en largeur correspond à l’exploration par niveaux (du haut vers le bas).
• Dans l’exemple, le parcours préfixe donne [40, 20, 10, 30, 60, 50, 70] tandis que le parcours largeur donne [40, 20, 60, 10, 30, 50, 70].
• Le parcours en largeur renvoie une liste résultat construite en ajoutant la valeur de chaque nœud extrait de la file.

💡 Astuce mémo

FIFO = « premier entré, premier sorti » ; parcours largeur = « niveaux d’abord » (file = queue).

📖 5. Dictionnaires et parcours clé valeur

🔑 Notions clés & Définitions

• Sommet : Un sommet est un nœud du graphe, c’est-à-dire une entité représentée comme un point.
• Arête : Une arête relie deux sommets et modélise une relation entre eux dans le graphe.
• Graphe pondéré : Un graphe pondéré associe à chaque arête un poids, interprété comme coût ou distance.
• Matrice d’adjacence : Une matrice d’adjacence est un tableau $n\times n$ où l’entrée $(i,j)$ décrit l’arête de $i$ vers $j$.
• Liste de successeurs : Une liste de successeurs regroupe, pour un sommet donné, tous les sommets accessibles depuis lui.

📝 Points essentiels

• Sommet = nœud du graphe, tandis qu’une arête est la connexion entre deux sommets.
• Arête orientée : elle a une direction, donc l’accès de $i$ vers $j$ peut différer de $j$ vers $i$.
• Arête non-orientée : elle n’a pas de direction, donc la connexion est symétrique entre les deux sommets.
• Connexité : un graphe est connexe si toute paire de sommets peut être reliée par une chaîne d’arêtes.
• Matrice d’adjacence : on inscrit le poids en ligne $i$ et colonne $j$ pour l’arête de rang $i$ vers $j$.
• Liste de successeurs : elle correspond aux sommets $j$ tels que l’entrée $(i,j)$ indique une arête depuis $i$.

💡 Astuce mémo

Sommet=point, Arête=liaison, Matrice=table $(i,j)$, Successeurs=sorties depuis $i$.

📖 6. Arbres binaires et ABR

🔑 Notions clés & Définitions

• Parcours en largeur BFS : Parcours en largeur qui explore d’abord tous les voisins d’un nœud avant de passer au niveau suivant.
• Parcours en profondeur DFS : Parcours en profondeur qui explore un chemin aussi loin que possible avant de revenir en arrière.
• Plus court chemin en BFS : Propriété de BFS sur un graphe non pondéré où le plus court chemin en nombre d’arêtes est trouvé en supposant un poids 1 pour chaque arête.

📝 Points essentiels

• BFS utilise une file (FIFO) : on retire le premier nœud ajouté avec pop(0) puis on ajoute ses successeurs en fin de liste.
• BFS ignore les poids des arêtes et traite chaque arête comme ayant le même coût, ce qui permet de minimiser le nombre d’arêtes.
• DFS utilise une structure de type pile/traitement en profondeur via pop(0) dans le code fourni, ce qui produit un ordre de visite différent de BFS.
• DFS explore d’abord un voisin puis continue sur ce chemin avant d’explorer les autres voisins, ce qui peut retarder la découverte de nœuds proches.
• Sur le graphe donné en exemple, BFS depuis A visite dans l’ordre A, B, C, D, E, F, G, H.
• Sur le graphe donné en exemple, DFS depuis A visite dans l’ordre A, B, E, F, C, G, H, D.

💡 Astuce mémo

BFS = « même niveau d’abord » (file) ; DFS = « chemin d’abord » (profondeur).

📖 7. Taille, hauteur et profondeur des arbres

🔑 Notions clés & Définitions

• Adresse IP : Une adresse IP est un identifiant unique d’une machine dans un réseau, permettant de la repérer pour l’envoi de données.
• Masque de sous-réseau : Un masque de sous-réseau découpe une adresse IP en partie réseau et partie hôte pour déterminer l’appartenance au réseau.
• Adresse réseau : L’adresse réseau est la valeur qui identifie le réseau auquel appartient une machine, obtenue à partir de son IP et du masque.
• Adresse de broadcast : L’adresse de broadcast est l’adresse qui permet d’envoyer un message à toutes les machines d’un même sous-réseau.
• Notation CIDR : La notation CIDR, notée /n, indique le nombre de bits réservés à la partie réseau dans le masque de sous-réseau.

📝 Points essentiels

• Une IP du type 192.168.1.10/24 correspond à un réseau 192.168.1.0, avec un masque 255.255.255.0.
• Pour 192.168.1.10/24, l’adresse de broadcast est 192.168.1.255 et les hôtes utilisables vont de 192.168.1.1 à 192.168.1.254.
• Une table de routage sert à choisir le chemin d’un paquet à partir d’une destination et de la sortie réseau à utiliser.
• Les champs typiques d’une table de routage sont Destination, Interface et Passerelle pour indiquer où envoyer ensuite.
• Si aucune route spécifique ne correspond, une route par défaut peut être utilisée pour acheminer le paquet.
• RIP échange périodiquement des informations entre routeurs pour mettre à jour ses routes connues, en s’appuyant sur une métrique.

💡 Astuce mémo

CIDR = « /n » → n bits pour le réseau ; broadcast = « tout à 1 » dans la partie hôte.

📖 8. Parcours d arbres préfixe infixe suffixe

🔑 Notions clés & Définitions

• Parcours préfixe : Parcours préfixe : on visite d’abord la racine, puis on parcourt récursivement les sous-arbres gauche et droit.
• Parcours infixe : Parcours infixe : on visite d’abord le sous-arbre gauche, puis la racine, puis le sous-arbre droit.
• Parcours suffixe : Parcours suffixe : on parcourt d’abord les sous-arbres gauche et droit, puis on visite la racine en dernier.
• Arbre binaire : Arbre binaire : structure où chaque nœud a au plus deux enfants, souvent notés gauche et droit.

📝 Points essentiels

• Préfixe donne l’ordre racine→gauche→droite, ce qui met la racine en premier dans la liste produite.
• Infixe donne l’ordre gauche→racine→droite, ce qui place la racine entre les deux sous-listes.
• Suffixe donne l’ordre gauche→droite→racine, ce qui met la racine en dernier dans la liste produite.
• Pour un arbre vide, aucun nœud n’est visité ; pour un nœud seul, les trois parcours renvoient la même valeur.
• Les trois parcours s’obtiennent naturellement avec une logique récursive : traiter la racine à un moment différent puis parcourir gauche et droite.

💡 Astuce mémo

Préfixe = Racine d’abord ; Infixe = Racine au milieu ; Suffixe = Racine à la fin.

📖 9. Recherche et insertion dans un ABR

🔑 Notions clés & Définitions

• ABR : Un ABR est un arbre binaire de recherche où, pour chaque nœud, les valeurs à gauche sont plus petites et celles à droite plus grandes.
• Recherche dans un ABR : La recherche dans un ABR consiste à parcourir l’arbre en comparant la clé cherchée à chaque nœud pour choisir la branche gauche ou droite.
• Insertion dans un ABR : L’insertion dans un ABR place une nouvelle clé à la position feuille qui respecte l’ordre des valeurs du nœud courant.
• Tri fusion : Le tri fusion est un algorithme diviser-pour-régner qui trie en séparant la liste, en triant récursivement, puis en fusionnant deux sous-listes triées.

📝 Points essentiels

• Dans un ABR, la comparaison clé < nœud mène à la branche gauche et la comparaison clé > nœud mène à la branche droite.
• La recherche dans un ABR s’arrête quand la clé est trouvée ou quand on atteint un pointeur vide (absence de la clé).
• L’insertion dans un ABR se fait en descendant l’arbre jusqu’à une position vide, puis en créant un nouveau nœud à cet endroit.
• Le schéma diviser-pour-régner du tri fusion suit : diviser, résoudre récursivement, puis combiner par fusion.
• Le cas de base du tri fusion est une liste de taille ≤ 1, qui est déjà triée.

💡 Astuce mémo

ABR = « Gauche plus petit, Droite plus grand » ; tri fusion = « Diviser → Régner → Fusionner ».

📖 10. Arbres AVL et complexité logarithmique

🔑 Notions clés & Définitions

• Arbre AVL : Arbre binaire de recherche auto-équilibré qui maintient une contrainte de hauteur pour limiter la dégradation des performances.
• Hauteur d’un nœud : Mesure de la profondeur maximale d’un nœud dans l’arbre, utilisée pour calculer les déséquilibres dans un AVL.
• Facteur d’équilibre : Valeur dérivée des hauteurs des sous-arbres gauche et droit, qui indique si un nœud est trop déséquilibré.
• Rotation AVL : Opération locale qui réorganise quelques nœuds pour rétablir la propriété d’équilibre sans casser l’ordre de recherche.

📝 Points essentiels

• Un arbre AVL garantit une hauteur $h$ en $O(\log n)$, ce qui rend les opérations de recherche/insertion/suppression logarithmiques en nombre de nœuds $n$.
• Le facteur d’équilibre d’un nœud est calculé à partir des hauteurs des deux sous-arbres, et un déséquilibre trop grand déclenche une rotation.
• Les rotations corrigent localement le déséquilibre tout en conservant la propriété d’arbre binaire de recherche (ordre des clés).
• Quand l’insertion ou la suppression modifie une hauteur, l’équilibre doit être vérifié en remontant vers la racine jusqu’à ce que l’équilibre soit rétabli.
• Comparaison : un arbre binaire de recherche non équilibré peut atteindre une hauteur $O(n)$ (cas dégénéré), alors qu’un AVL reste à $O(\log n)$ grâce aux rotations.

💡 Astuce mémo

AVL = Anti-Verticale : il empêche l’arbre de devenir trop “haut”, donc $\log n$.

📖 11. Graphes : sommets, arêtes et connexité

📖 12. DFS et BFS pour parcourir un graphe

🔑 Notions clés & Définitions

• Parcours en profondeur DFS : Un parcours de graphe qui explore d’abord aussi loin que possible un chemin avant de revenir en arrière.
• Parcours en largeur BFS : Un parcours de graphe qui explore d’abord tous les sommets à distance $1$, puis $2$, puis $3$, etc.
• Graphe : Un ensemble de sommets reliés par des arêtes, utilisé pour modéliser des relations entre objets.
• Pile : Structure de données de type LIFO utilisée naturellement pour implémenter un parcours DFS.
• File : Structure de données de type FIFO utilisée naturellement pour implémenter un parcours BFS.

📝 Points essentiels

• DFS utilise une exploration « en profondeur » et revient quand un sommet n’a plus de voisins à visiter.
• BFS explore par couches : la distance en nombre d’arêtes depuis la source augmente progressivement.
• Avec une file, BFS garantit que le premier moment où l’on atteint un sommet correspond à un chemin de longueur minimale (en arêtes).
• Avec une pile, DFS ne garantit pas la distance minimale : il dépend de l’ordre d’exploration des voisins.
• Pour éviter les boucles, on maintient un ensemble de sommets déjà visités pendant le parcours.
• Le choix pile vs file correspond directement à la logique profondeur vs couches de BFS/DFS.

💡 Astuce mémo

DFS = Deep First (pile/LIFO) ; BFS = Breadth First (couches/file/FIFO).

📊 Tableaux de synthèse

Pile vs file (LIFO vs FIFO)

Parcours BFS vs DFS

⚠️ Pièges & confusions fréquents

1. Confondre interface (contrat sans détails) et implémentation (code concret) : on décrit alors des détails d’exécution dans le contrat.
2. Croire que l’encapsulation autorise l’accès direct aux attributs : en réalité, l’accès passe par des méthodes publiques (attributs privés).
3. Penser que le polymorphisme dépend uniquement de l’héritage : en pratique, il faut redéfinir la méthode pour obtenir le bon comportement.
4. Mélanger LIFO et FIFO : utiliser pop(0) comme pour une pile, ou pop() comme pour une file, inverse l’ordre des éléments.
5. Oublier que BFS ignore les poids et minimise le nombre d’arêtes : on peut alors croire qu’il trouve le plus “coût” minimal sur un graphe pondéré.
6. Confondre préfixe/infixe/suffixe : placer la racine au mauvais moment (début, milieu, fin) donne un ordre de parcours faux.
7. Se tromper sur la hauteur : la hauteur est le nombre d’arêtes de la racine au nœud le plus profond (et non le nombre de nœuds).

✅ Checklist Examen

1. Définir interface, implémentation et encapsulation, puis expliquer comment l’accès aux données internes est contrôlé via méthodes publiques.
2. Expliquer héritage et polymorphisme, et préciser le rôle de la redéfinition de méthode pour obtenir le bon comportement.
3. Reconnaître une pile (LIFO) et décrire push/pop ; donner l’ordre de sortie attendu après empilements.
4. Reconnaître une file (FIFO) et décrire l’effet de pop(0) et l’ajout en fin de liste.
5. Décrire un dictionnaire comme structure clé-valeur non ordonnée et rappeler la complexité moyenne O(1) des opérations via clé.
6. Pour un arbre binaire, donner les définitions : racine, nœud, feuille, arête, sous-arbre, puis distinguer taille et hauteur (en arêtes).
7. Donner les ordres exacts des parcours préfixe, infixe, suffixe et vérifier les listes obtenues sur l’exemple du cours.
8. Décrire le parcours en largeur (BFS) : file, retrait du premier, ajout des enfants, et l’ordre produit sur l’exemple.
9. Pour un ABR, expliquer la règle de comparaison (gauche < nœud < droite) et décrire recherche puis insertion jusqu’à une position feuille.
10. Comparer ABR et AVL : rappeler l’objectif d’équilibre d’un AVL et la conséquence sur la complexité (hauteur en O(log n)).
11. Pour les graphes, définir sommet, arête (orientée/non-orientée), graphe pondéré, connexité, matrice d’adjacence et liste de successeurs.
12. Expliquer DFS vs BFS sur un graphe : structure utilisée, ordre de visite, et la propriété de plus court chemin en nombre d’arêtes pour BFS.
13. Pour les congruences, donner la définition a≡b (mod n) et énoncer au moins les propriétés de réflexivité, symétrie, transitivité et compatibilités (addition/soustraction/multiplication).
14. Expliquer le théorème de Bézout et l’algorithme d’Euclide (PGCD), puis l’Euclide étendu (coefficients de Bézout).