Lernzettel: Introduction aux Structures de Données et Algorithmes

📋 Plan du Cours

1. POO et structures linéaires
2. Dictionnaires Python
3. Arbres binaires et ABR
4. Parcours et équilibre des arbres
5. Graphes et parcours
6. Modèle relationnel SQL
7. Routage et protocoles
8. Récursivité et tri fusion
9. Modules Python et importation
10. Tri par insertion et sélection
11. Congruences et théorèmes

📖 1. POO et structures linéaires

🔑 Notions clés & Définitions

• Interface : Une interface est un ensemble de fonctionnalités spécifiées sans fournir l’implémentation concrète.
• Encapsulation : L’encapsulation consiste à protéger les données internes d’une classe via des attributs privés et 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 comportements différents selon le type réel.
• Pile : Une pile est une structure linéaire fonctionnant en LIFO, donc dernier entré premier sorti.

📝 Points essentiels

• En Python, une classe est construite avec init pour initialiser les attributs de l’instance à la création.
• Une pile se met à jour avec append puis se lit/retire avec pop, ce qui retire le dernier élément ajouté.
• Une file se gère avec append puis pop(0) pour retirer le premier élément inséré.
• Le polymorphisme s’appuie sur la même interface tout en laissant chaque type redéfinir ses méthodes.
• L’encapsulation est typiquement réalisée en gardant les attributs internes privés et en exposant des méthodes pour les modifier.

💡 Astuce mémo

LIFO = Last In First Out ; FIFO = First In First Out.

📖 2. Dictionnaires Python

🔑 Notions clés & Définitions

• Dictionnaire : Un dictionnaire Python associe des paires clé-valeur et permet d’accéder rapidement à une valeur via sa clé.
• Clé-valeur : Une entrée de dictionnaire associe une clé à une valeur pour retrouver ou modifier la valeur correspondante.
• Parcours des clés : Par défaut, parcourir un dictionnaire en boucle itère sur ses clés.
• Parcours des valeurs : L’itération via values() parcourt les valeurs stockées dans le dictionnaire.
• Parcours items : L’itération via items() parcourt les couples (clé, valeur) du dictionnaire.

📝 Points essentiels

• Les opérations moyennes de recherche, insertion et suppression dans un dictionnaire sont en complexité 𝑂(1).
• Pour lire une valeur, on utilise dictionnaire[cle] et on obtient directement la valeur associée à la clé.
• Pour ajouter/modifier, on affecte dictionnaire[nouvelle_cle] = valeur.
• Pour supprimer une entrée, on utilise del dictionnaire[cle].
• Pour lister les clés, une boucle for cle in dictionnaire parcourt les clés.

💡 Astuce mémo

Clé → Valeur : “tu tapes la clé, tu récupères la valeur”.

📖 3. Arbres binaires et ABR

🔑 Notions clés & Définitions

• Racine : La racine est le nœud de départ d’un arbre, qui n’a pas de parent.
• Feuille : Une feuille est un nœud qui ne possède aucun enfant.
• Sous-arbre : Un sous-arbre est constitué d’un nœud et de tous ses descendants.
• Arbre binaire : Un arbre binaire est un arbre où chaque nœud a au plus deux enfants, appelés gauche et droit.
• ABR : Un ABR est un arbre binaire de recherche où la valeur du sous-arbre gauche est inférieure à celle du nœud et celle du sous-arbre droit est supérieure.

📝 Points essentiels

• La taille d’un arbre correspond au nombre total de nœuds dans l’arbre.
• La hauteur correspond au nombre d’arêtes entre la racine et le nœud le plus profond, et vaut -1 si l’arbre est vide.
• Dans un ABR, pour rechercher ou insérer, on compare la valeur à la valeur du nœud pour choisir gauche ou droit.
• L’implémentation type d’un nœud utilise des champs valeur, gauche et droit.
• Un ABR peut être construit en créant les nœuds puis en reliant gauche et droit lors des appels à Noeud.

💡 Astuce mémo

ABR = Gauche < Parent < Droite.

📖 4. Parcours et équilibre des arbres

🔑 Notions clés & Définitions

• Parcours préfixe : Un parcours préfixe visite la racine puis récursive gauche puis récursive droite.
• Parcours infixe : Un parcours infixe visite récursive gauche puis la racine puis récursive droite.
• Parcours suffixe : Un parcours suffixe visite récursive gauche puis récursive droite puis la racine.
• Parcours largeur : Un parcours en largeur visite les nœuds niveau par niveau, de gauche à droite.
• Arbre AVL : Un arbre AVL est un ABR auto-équilibré qui maintient une hauteur logarithmique pour garder de bonnes performances.

📝 Points essentiels

• En parcours préfixe, l’ordre commence toujours par la racine avant d’explorer les sous-arbres.
• En parcours infixe, l’ordre devient trié pour les valeurs d’un ABR, car gauche < nœud < droite.
• Le parcours suffixe termine toujours par la racine du sous-arbre courant.
• Le parcours en largeur utilise une file pour traiter d’abord les nœuds les plus proches.
• La recherche dans un AVL est en 𝑂(log(𝑛)), alors qu’un ABR non équilibré peut atteindre 𝑂(𝑛) au pire.

💡 Astuce mémo

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

📖 5. Graphes et parcours

🔑 Notions clés & Définitions

• Sommet : Un sommet est un nœud du graphe, c’est-à-dire un point représentant une entité.
• Arête orientée : Une arête orientée relie deux sommets avec une direction de départ vers une arrivée.
• Graphe pondéré : Un graphe pondéré associe à chaque arête un poids, représentant un coût ou une distance.
• Matrice d’adjacence : Une matrice d’adjacence stocke les arêtes sous forme de tableau i,j avec le poids en i→j.
• DFS : DFS est un parcours en profondeur d’abord qui explore un chemin au maximum avant de revenir en arrière.

📝 Points essentiels

• Un graphe est connexe si chaque paire de sommets peut être reliée par une chaîne d’arêtes.
• La liste des successeurs pour un sommet i regroupe les sommets j tels que la matrice(i,j) n’est pas nulle.
• DFS n’utilise pas les poids et explore le premier voisin non visité jusqu’à ce qu’il n’y en ait plus.
• BFS ignore aussi les poids et trouve un plus court chemin seulement si chaque arête vaut 1.
• Dans l’exemple, BFS depuis A produit l’ordre ['A','B','C','D','E','F','G','H'] tandis que DFS produit ['A','B','E','F','C','G','H','D'].

💡 Astuce mémo

DFS = “creuser” ; BFS = “élargir par niveaux”.

📖 6. Modèle relationnel SQL

🔑 Notions clés & Définitions

• Relation : Une relation SQL correspond à une table qui organise les données sous forme de lignes.
• Attribut : Un attribut est une colonne d’une table qui décrit une propriété des données.
• Clé primaire : Une clé primaire identifie de manière unique chaque ligne d’une table.
• Clé étrangère : Une clé étrangère crée un lien entre deux tables en référence à une clé primaire.
• Domaine : Un domaine est l’ensemble des valeurs admissibles pour un attribut.

📝 Points essentiels

• En notation du schéma, les attributs soulignés représentent des clés primaires.
• Dans le schéma, le # indique qu’un attribut est une clé étrangère.
• La table AUTEURS contient notamment id et langue_ecriture, et LIVRES relie à AUTEURS via id_auteur.
• Une clé étrangère relie une ligne de LIVRES au bon auteur grâce à la clé primaire de AUTEURS.
• Les attributs servent de champs manipulables dans les requêtes SELECT et WHERE.

💡 Astuce mémo

Primaire = “identité unique” ; étrangère = “lien vers une autre table”.

📖 7. Routage et protocoles

🔑 Notions clés & Définitions

• Adresse IP : Une adresse IP est un identifiant d’une machine dans un réseau.
• Masque de sous-réseau : Un masque de sous-réseau sépare la partie réseau de la partie hôte d’une adresse IP.
• Broadcast : L’adresse de broadcast permet d’envoyer un message à toutes les machines d’un même réseau.
• Table de routage : Une table de routage décrit pour chaque destination le choix de l’interface et de la passerelle.
• RIP : RIP est un protocole de routage basé sur l’échange périodique de tables entre routeurs avec la métrique du nombre de sauts.

📝 Points essentiels

• En notation CIDR, /n indique le nombre de bits pour la partie réseau, par exemple /24 équivaut à 255.255.255.0.
• Une adresse réseau correspond à la partie réseau de l’IP, et la plage d’hôtes est du premier au dernier avant le broadcast.
• Dans une table de routage, on trouve Destination, Interface, et Passerelle pour choisir le prochain saut.
• RIP utilise une métrique en nombre de sauts et met une route à jour si une distance plus courte est trouvée.
• OSPF utilise un coût proportionnel à la bande passante et choisit le chemin de coût minimal, pas forcément celui de moins de sauts, comme l’illustre l’exemple avec un coût de 18 contre celui du chemin RIP.

💡 Astuce mémo

RIP = “sauts” ; OSPF = “coût des liaisons”.

📖 8. Récursivité et tri fusion

🔑 Notions clés & Définitions

• Récursivité : La récursivité est le fait qu’une fonction s’appelle elle-même pour résoudre un problème en sous-problèmes.
• Cas de base : Le cas de base est la condition qui stoppe la récursion et évite une suite d’appels infinie.
• Diviser pour régner : Diviser pour régner décompose le problème, résout les sous-problèmes, puis combine leurs résultats.
• Tri fusion : Le tri fusion est une méthode diviser pour régner qui trie en fusionnant deux moitiés déjà triées.

📝 Points essentiels

• Une fonction récursive progresse en réduisant le problème jusqu’au cas de base, puis remonte avec les résultats.
• En factorielle, le cas de base est n==0 et la formule récursive multiplie n par factorielle(n-1).
• Python limite par défaut la profondeur de récursion à environ 1000 appels, ce nombre pouvant varier selon la plateforme.
• Le tri fusion divise la liste au milieu, trie récursivement gauche et droite, puis fusionne les deux listes triées.
• Dans la fusion du tri fusion, on compare les premiers éléments des deux listes et on ajoute le plus petit au résultat.

💡 Astuce mémo

Récursivité = Cas de base + Réduction + Retour en arrière.

📖 9. Modules Python et importation

🔑 Notions clés & Définitions

• Module : Un module est une unité de code réutilisable et importable pour accéder à des fonctions et objets.
• dir() : La fonction dir() liste les noms disponibles dans un module ou un objet.
• help() : La fonction help() affiche la documentation d’un module ou d’une fonction.
• Docstring : Une docstring est une chaîne de documentation associée à une fonction ou un élément importable.
• Importation : L’importation en Python permet d’accéder au contenu d’un module via import ou from import.

📝 Points essentiels

• Pour lister le contenu d’un module, on utilise dir(nom_module).
• Pour afficher l’aide d’un élément, on utilise help(nom_module.élément).
• Les docstrings sont accessibles via élément.doc pour une fonction ou un objet.
• Avec import math, on appelle une fonction comme math.sin(x) ou math.sqrt(2).
• Avec from module import fonction, on appelle directement la fonction sans préfixe de module.
• Avec from module import *, l’import de tout est déconseillé car il peut provoquer des conflits de noms.

💡 Astuce mémo

import = préfixe ; from ... import = direct.

📖 10. Tri par insertion et sélection

🔑 Notions clés & Définitions

• Tri par insertion : Le tri par insertion construit progressivement une partie triée en insérant chaque nouvel élément à sa place.
• Tri par sélection : Le tri par sélection sélectionne le minimum à partir d’un index et l’échange avec l’élément courant.
• Complexité quadratique : Une complexité quadratique $O(n^2)$ indique que le temps augmente proportionnellement au carré de la taille n.

📝 Points essentiels

• Dans le tri par insertion, on parcourt i puis on décale vers la droite les éléments plus grands que la valeur à insérer.
• Le tri par insertion s’appuie sur la condition j>0 et valeur_insertion < tab[j-1] pour déplacer les éléments.
• Dans le tri par sélection, on cherche min_i sur la partie i+1..fin avec tab[min_i] > tab[j].
• Après avoir trouvé min_i, on échange tab[i] et tab[min_i].
• Le tri par insertion et le tri par sélection ont un coût $O(n^2)$ dans le pire cas, donc deviennent beaucoup plus lents quand n grandit.

💡 Astuce mémo

Insertion = “insérer dans la zone triée” ; Sélection = “choisir le minimum à chaque tour”.

📖 11. Congruences et théorèmes

🔑 Notions clés & Définitions

• Congruence modulo n : On dit que a est congru à b modulo n si la différence a-b est divisible par n.
• Théorème de Bézout : Le théorème de Bézout assure l’existence d’entiers x,y tels que ax+by égale le PGCD de a et b.
• Algorithme d’Euclide : L’algorithme d’Euclide calcule le PGCD de deux entiers en remplaçant (a,b) par (b, a mod b) jusqu’à b==0.
• Euclide étendu : L’algorithme d’Euclide étendu fournit en plus des coefficients x,y vérifiant ax+by = PGCD(a,b).
• Théorème de Gauss : Le théorème de Gauss relie la divisibilité de bc à celle de c sous une condition de coprimalité entre a et b.

📝 Points essentiels

• La congruence s’écrit $a\equiv b\ (\mathrm{mod}\ n)$ ou $a\equiv b[n]$ et signifie que n divise a-b.
• Les propriétés de congruence incluent réflexivité, symétrie, transitivité et la conservation par addition, soustraction et multiplication.
• Si $a\equiv b[n]$ alors pour tout entier k, on a $a^k\equiv b^k[n]$.
• Le PGCD via Euclide utilise la décomposition a = qb + r et le remplacement par PGCD(b,r).
• Le petit théorème de Fermat affirme : si p est premier et a n’est pas divisible par p, alors $a^{p-1}\equiv 1[p]$.
• Critère de divisibilité par 9 : N est divisible par 9 si et seulement si la somme de ses chiffres est divisible par 9.

💡 Astuce mémo

Mod n : “on ne garde que le reste”, et pour 9 on regarde la somme des chiffres.

⚠️ Pièges & confusions fréquents

1. Confondre LIFO et FIFO fait inverser les appels: pop() de pile retire le dernier, alors que pop(0) retire le premier d’une file.
2. Pour l’infixe d’un ABR, croire que ce n’est pas trié: en fait, l’infixe produit les valeurs dans l’ordre croissant.
3. En parcours en largeur, oublier que l’ordre dépend du niveau (file) et non d’un simple choix gauche/droite comme en DFS.
4. Dans RIP, croire qu’il choisit le chemin le plus court en nombre d’arêtes: il minimiserait le nombre de sauts, alors que l’exemple oppose coût et RIP.
5. Pour SQL, oublier un WHERE lors d’un DELETE conduit à supprimer toutes les lignes de la table.
6. En congruences, écrire une phrase sans condition de divisibilité: la définition clé est “n divise a-b” pour $a\equiv b[n]$.

✅ Checklist Examen

1. Identifier et distinguer interface, implémentation, encapsulation, héritage et polymorphisme dans un exemple de classe Python.
2. Choisir la bonne opération pour simuler une pile (LIFO) et une file (FIFO) avec les méthodes append et pop.
3. Expliquer comment parcourir un dictionnaire via clés, values(), et items() et reconnaître les accès dictionnaire[cle].
4. Calculer la taille et la hauteur d’un arbre à partir des définitions de nombre de nœuds et nombre d’arêtes.
5. Donner l’ordre produit par un parcours préfixe, infixe, suffixe et largeur d’abord sur un arbre donné.
6. Utiliser les règles d’un ABR pour justifier le choix gauche/droit en recherche ou insertion.
7. Décrire les définitions sommet, arête orientée/non orientée et graphe pondéré, puis donner le rôle de la matrice d’adjacence.
8. Décrire DFS et BFS et préciser l’hypothèse liée à la longueur la plus courte (poids=1 par arête).
9. Citer les rôles clé primaire et clé étrangère, et interpréter le schéma relationnel avec le symbole #.
10. Écrire le sens des commandes SQL : SELECT (avec attributs et WHERE), ORDER BY (ASC/DESC), DISTINCT, INNER JOIN, COUNT, INSERT, UPDATE, DELETE.
11. Résoudre une question de routage : CIDR, adresse réseau/broadcast, et interpréter une table de routage Destination/Interface/Passerelle.
12. Comparer RIP et OSPF sur leur métrique et reconnaître que l’exemple oppose sauts et coût minimal.
13. Vérifier une récursion : existence d’un cas de base et réduction correcte, et reconnaître la limite d’environ 1000 appels.
14. Appliquer les étapes de tri fusion : diviser, trier récursivement, puis fusionner en comparant les premiers éléments.