Lernzettel: Introduction aux Structures et Algorithmes Essentiels

📋 Plan du Cours

1. POO et structures de données
2. Arbres binaires et recherche
3. Parcours et arbres équilibrés
4. Graphes et parcours
5. Modèle relationnel et SQL
6. Routage et protocoles
7. Récursivité et tri fusion
8. Modularité et fonctions
9. Tri par insertion et sélection
10. Congruences et arithmétique

📖 1. POO et structures de données

🔑 Notions clés & Définitions

• Interface : Une interface décrit les fonctionnalités attendues d’une classe ou d’un module sans donner l’implémentation concrète.
• Encapsulation : L’encapsulation protège les données internes d’une classe en utilisant des attributs privés accessibles 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, en utilisant des méthodes redéfinies.
• Pile : Une pile est une structure LIFO où le dernier élément ajouté est le premier élément retiré.

📝 Points essentiels

• Une implémentation est la réalisation concrète des fonctionnalités annoncées par l’interface.
• En POO, l’interface fixe le “quoi” et l’implémentation fournit le “comment” pour exécuter les fonctionnalités.
• Dans une pile, le retrait avec pop correspond au dernier élément entré, et dans une file pop(0) retire le premier élément entré.
• Pour un dictionnaire, les opérations de recherche, insertion et suppression ont une complexité moyenne de 𝑂(1).
• Un dictionnaire permet d’accéder à une valeur uniquement à partir de sa clé, et on peut ajouter ou supprimer une clé avec une syntaxe dédiée.

💡 Astuce mémo

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

📖 2. Arbres binaires et recherche

🔑 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.
• Arbre binaire : Un arbre binaire est un arbre où chaque nœud a au plus deux enfants.
• Arbre binaire de recherche : Un ABR est un arbre binaire où le sous-arbre gauche contient des valeurs plus petites et le sous-arbre droit des valeurs plus grandes que le nœud.
• Taille d’un arbre : La taille d’un arbre est le nombre total de nœuds dans l’arbre.

📝 Points essentiels

• Dans un ABR, pour rechercher une valeur, on compare à la valeur du nœud puis on descend à gauche si la valeur cherchée est plus petite, sinon à droite.
• L’insertion dans un ABR suit les mêmes comparaisons : chaque valeur est envoyée dans le sous-arbre gauche ou droit jusqu’à trouver une position de nœud vide.
• La hauteur est comptée en nombre d’arêtes entre la racine et le nœud le plus profond, et vaut −1 si l’arbre est vide dans l’exemple donné.
• La taille se calcule récursivement comme 1 + taille(gauche) + taille(droit), et renvoie 0 si le nœud est None.
• Dans le code de recherche, si le nœud est None la fonction renvoie False, ce qui correspond à l’absence de la valeur.

💡 Astuce mémo

ABR = gauche plus petit, droit plus grand, donc comparaison à chaque nœud.

📖 3. Parcours et arbres équilibrés

🔑 Notions clés & Définitions

• Parcours préfixe : Un parcours préfixe visite d’abord la racine, puis le sous-arbre gauche, puis le sous-arbre droit.
• Parcours infixe : Un parcours infixe visite d’abord le sous-arbre gauche, puis la racine, puis le sous-arbre droit.
• Parcours suffixe : Un parcours suffixe visite d’abord le sous-arbre gauche, puis le sous-arbre droit, puis la racine.
• Parcours en 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 des opérations efficaces.

📝 Points essentiels

• Pour un parcours infixe d’un ABR, l’ordre des valeurs obtenues est croissant car tout gauche est inférieur et tout droit est supérieur au parent.
• Le parcours en largeur utilise une file et ajoute d’abord les voisins gauche puis droit du nœud courant pour respecter l’ordre par niveaux.
• La recherche dans un arbre AVL a une complexité en 𝑂(log(𝑛)), alors qu’un ABR très déséquilibré peut dégrader la recherche à 𝑂(𝑛).
• La hauteur d’un arbre AVL reste contrôlée grâce à son mécanisme d’auto-équilibrage, ce qui évite la structure “en ligne droite”.
• Dans l’exemple, le parcours en largeur donne [40, 20, 60, 10, 30, 50, 70], illustrant la visite par niveaux.

💡 Astuce mémo

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

📖 4. Graphes et parcours

🔑 Notions clés & Définitions

• Sommet : Un sommet est un point du graphe, aussi appelé nœud.
• Arête orientée : Une arête orientée relie deux sommets avec une direction.
• Graphe pondéré : Un graphe pondéré associe un coût ou un poids à chaque arête.
• Connexité : Un graphe est connexe si chaque paire de sommets peut être reliée par une chaîne d’arêtes.
• Matrice d’adjacence : Une matrice d’adjacence stocke les liens entre sommets sous forme de tableau à deux dimensions, avec le poids dans la case (i, j).

📝 Points essentiels

• En BFS et en DFS, les poids d’arêtes ne sont pas utilisés, car l’exploration dépend uniquement des voisins visités.
• La recherche du plus court chemin entre deux nœuds via BFS est garantie si on considère un modèle où chaque arête vaut 1 en coût.
• Une matrice d’adjacence permet de construire une liste des successeurs en parcourant chaque case (i, j) et en ajoutant j si la valeur indique l’existence d’une arête.
• La liste des successeurs respecte l’orientation si le graphe est orienté, car l’accessibilité dépend du sens des arêtes.
• Dans l’exemple, l’ordre de visite DFS partant de A est ['A','B','E','F','C','G','H','D'] tandis que BFS donne ['A','B','C','D','E','F','G','H'].

💡 Astuce mémo

DFS va “au fond”, BFS va “par couches”.

📖 5. Modèle relationnel et SQL

🔑 Notions clés & Définitions

• Relation : Une relation correspond à une table dans une base de données.
• Attribut : Un attribut est une colonne d’une table qui décrit une propriété des données.
• Domaine : Un domaine est l’ensemble des valeurs admissibles pour un attribut.
• Clé primaire : Une clé primaire identifie de manière unique une ligne dans une table.
• Clé étrangère : Une clé étrangère est un attribut qui référence la clé primaire d’une autre table.

📝 Points essentiels

• Les requêtes de sélection utilisent SELECT, et SELECT * FROM renvoie tous les attributs d’une table.
• WHERE filtre les lignes avant l’affichage, par exemple en gardant uniquement celles dont note > 9.
• ORDER BY trie les résultats et DESC inverse l’ordre, comme dans ORDER BY ann_publi DESC.
• DISTINCT supprime les doublons pour un ensemble de valeurs, par exemple SELECT DISTINCT langue_ecriture FROM AUTEURS.
• La jointure interne associe LIVRES et AUTEURS via LIVRES.id_auteur = AUTEURS.id puis peut être filtrée avec WHERE.
• INSERT ajoute une ligne, UPDATE modifie des lignes ciblées par WHERE, et DELETE supprime des lignes ciblées par WHERE.

💡 Astuce mémo

SELECT trie avec ORDER BY, filtre avec WHERE, dédoublonne avec DISTINCT.

📖 6. Routage et protocoles

🔑 Notions clés & Définitions

• Adresse IP : Une adresse IP identifie une machine sur un réseau.
• Masque de sous-réseau : Le masque sépare la partie réseau de la partie hôte dans une adresse IP.
• Adresse réseau : L’adresse réseau correspond à la partie réseau de l’IP, identifiant le réseau d’appartenance.
• Adresse de broadcast : L’adresse de broadcast permet d’envoyer un message à toutes les machines d’un sous-réseau.
• Notation CIDR : La notation CIDR /n indique le nombre de bits réservés à la partie réseau dans l’adresse.

📝 Points essentiels

• Pour 192.168.1.10/24, l’adresse réseau est 192.168.1.0, le masque est 255.255.255.0 et l’adresse de broadcast est 192.168.1.255.
• Une table de routage fournit une Destination, une Interface de sortie et une Passerelle (prochain routeur) selon la destination.
• RIP ajoute une route si elle est inconnue, et remplace une route si une distance plus courte est trouvée.
• RIP ignore une route plus longue, et si un routeur est inactif pendant 3 minutes la distance devient infinie (16).
• Dans RIP, la métrique est le nombre de sauts, tandis que dans OSPF le coût dépend du débit des liaisons (coût proportionnel à la bande passante).
• Dans l’exemple OSPF, le coût total pour R1-R2-R4 vaut 18 et bat le chemin R1-R3 qui serait choisi par RIP avec une logique “sauts”.

💡 Astuce mémo

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

📖 7. Récursivité et tri fusion

🔑 Notions clés & Définitions

• Récursivité : La récursivité est un mécanisme où une fonction s’appelle elle-même pour résoudre un problème décomposé.
• Cas de base : Le cas de base est la condition qui stoppe la récursion en empêchant les appels de continuer indéfiniment.
• Diviser pour régner : Diviser pour régner consiste à découper un problème, résoudre chaque morceau récursivement, puis combiner les solutions.
• Tri fusion : Le tri fusion (merge sort) divise la liste en deux moitiés, trie récursivement, puis fusionne les deux listes triées.

📝 Points essentiels

• Une fonction récursive doit avoir un cas de base qui termine la suite d’appels, sinon on risque une récursion infinie.
• À chaque appel récursif, la taille du problème doit diminuer de façon correcte pour atteindre le cas de base.
• En Python, le nombre d’appels récursifs autorisé est d’environ 1000 (variable selon la plateforme).
• Dans le tri fusion, si la longueur de la liste est ≤ 1, la fonction renvoie la liste directement comme cas de base.
• La fusion compare les premières valeurs des deux listes et construit une sortie triée en répétant le choix du plus petit élément.
• L’exemple de tri fusion renvoie [1, 2, 3, 4, 5, 7, 8] pour la liste de départ [4, 3, 8, 2, 7, 1, 5].

💡 Astuce mémo

Diviser → Régner → Combiner : coupe, trie, puis fusionne.

📖 8. Modularité et fonctions

🔑 Notions clés & Définitions

• Modularité : La modularité consiste à découper un système en modules qui gèrent chacun une fonctionnalité précise.
• Module Python : Un module Python est un regroupement de fonctions et/ou variables utilisables via une importation.
• Docstring : Une docstring est une documentation intégrée à une fonction ou à un élément Python accessible via doc.
• Importation avec alias : Un alias permet de renommer un module ou une fonction lors de l’importation grâce à as.

📝 Points essentiels

• Décomposer en modules augmente la réutilisabilité, facilite la maintenance, et améliore l’extensibilité et la compréhension du code.
• Pour lister les éléments d’un module, dir(nom_du_module) affiche ses noms définis.
• Pour afficher l’aide d’un élément, help(nom_du_module.élément) ou help(addition) renvoie sa description.
• La documentation d’un objet est disponible via élément.doc, par exemple math.sin.doc.
• En Python, import module impose l’usage module.fonction(), tandis que from module import fonction permet d’appeler directement fonction().
• from module import * importe tout, et c’est déconseillé car cela peut créer des conflits de noms.

💡 Astuce mémo

import module = module. ; from module import = direct ; alias = as.

📖 9. Tri par insertion et sélection

🔑 Notions clés & Définitions

• Tri par insertion : Le tri par insertion insère à chaque étape un élément dans la partie déjà triée en le décalant vers sa place.
• Tri par sélection : Le tri par sélection choisit à chaque position l’élément minimal restant et l’échange avec l’élément courant.
• Insertion triée : La partie “déjà triée” du tri par insertion correspond aux éléments examinés avant i.
• Minimum restant : Dans le tri par sélection, le minimum restant est l’élément le plus petit parmi la portion non triée.

📝 Points essentiels

• Le tri par insertion parcourt i de 1 à n−1 et décale vers la droite tant que valeur_insertion < tab[j−1] pour insérer au bon endroit.
• Le tri par sélection parcourt i puis cherche min_i parmi j de i+1 à fin, et échange tab[i] avec tab[min_i].
• Dans les deux algorithmes (insertion et sélection), le coût en pire cas est quadratique et s’exprime par 𝑂(𝑛²) sur un tableau de taille 𝑛.
• Le double parcours du tri par sélection explique le grand nombre de comparaisons en pire cas.
• Sur l’exemple [4, 3, 5, 1], le tri par insertion donne [1, 3, 4, 5], et sur [12, 11, 13, 5, 6] le tri par sélection donne [5, 6, 11, 12, 13].

💡 Astuce mémo

Insertion = décale pour placer, Sélection = cherche le min puis échange.

📖 10. Congruences et arithmétique

🔑 Notions clés & Définitions

• Congruence modulaire : On dit que a est congru à b modulo n si n divise la différence a − b.
• Théorème de Bézout : Le théorème de Bézout garantit l’existence de coefficients x et y tels que ax + by égale le PGCD de a et b.
• Algorithme d’Euclide : L’algorithme d’Euclide calcule le PGCD en remplaçant (a, b) par (b, r) où r est le reste de a divisé par b.
• Euclide étendu : L’Euclide étendu calcule le PGCD et fournit aussi des coefficients x et y vérifiant l’égalité de Bézout.
• Théorème de Gauss : Le théorème de Gauss relie une divisibilité sur un produit à une divisibilité sur un facteur quand deux entiers sont premiers entre eux.

📝 Points essentiels

• La congruence s’écrit a≡b (mod n), et revient à dire que n divise a−b.
• Dans l’algorithme d’Euclide, si b = 0 alors le PGCD vaut a, et sinon on calcule r = a mod b puis on recommence avec (b, r).
• L’Euclide étendu renvoie une triple (pgcd, x, y) vérifiant ax + by = pgcd.
• Le petit théorème de Fermat affirme que pour p premier et p∤a, on a a^{p-1} ≡ 1 (mod p).
• Le critère de divisibilité par 9 est basé sur 10 ≡ 1 (mod 9), ce qui rend N congru à la somme des chiffres modulo 9.

💡 Astuce mémo

Euclide réduit par restes, Bézout reconstruit ax+by = PGCD, Fermat donne a^{p-1} ≡ 1 (mod p).

📊 Tableaux de synthèse

DFS vs BFS

⚠️ Pièges & confusions fréquents

1. Confondre LIFO et FIFO conduit à inverser l’ordre des retraits quand on utilise pop et pop(0) sur une liste.
2. Croire que BFS/DFS utilisent les poids : dans le cours, ils ignorent les poids et BFS sert pour le plus court chemin seulement en supposant coût 1.
3. Se tromper sur la hauteur : elle compte des arêtes de la racine au nœud le plus profond, et l’arbre vide donne −1 dans l’exemple.
4. Mélanger les ordres de parcours : préfixe (Racine→Gauche→Droite), infixe (Gauche→Racine→Droite), suffixe (Gauche→Droite→Racine).
5. Penser qu’un ABR permet n’importe quelle insertion : l’insertion doit respecter la règle gauche plus petit, droit plus grand.
6. Oublier le cas de base en récursivité provoque une récursion qui ne se termine pas.
7. En congruences, confondre a≡b (mod n) avec une égalité stricte sans condition “n divise a−b”.

✅ Checklist Examen

1. Définir et distinguer interface et implémentation en POO.
2. Expliquer l’encapsulation (privé/public) et dire quel est le but en termes de protection des données.
3. Définir héritage et polymorphisme, et relier polymorphisme à des méthodes redéfinies via une même interface.
4. Donner la différence entre pile LIFO et file FIFO, et identifier quel retrait correspond à pop et pop(0).
5. Définir dictionnaire et préciser la complexité moyenne annoncée pour recherche/insertion/suppression (𝑂(1)).
6. Définir racine, feuille, arbre binaire et ABR, puis énoncer la règle gauche plus petit et droit plus grand.
7. Décrire la recherche dans un ABR (comparaison puis descente gauche/droite) et dire ce que renvoie la recherche si le nœud est None.
8. Calculer ou expliquer taille et hauteur à partir des définitions (taille = nombre de nœuds, hauteur = arêtes jusqu’au plus profond).
9. Produire l’ordre obtenu par un parcours : préfixe, infixe, suffixe, et en largeur (par niveaux).
10. Rappeler que BFS ignore les poids et donne le plus court chemin quand chaque arête a un coût égal à 1.
11. Construire une idée de matrice d’adjacence et rappeler ce que contiennent les cases (i, j) via le poids.
12. En SQL, écrire une requête avec SELECT * ou SELECT de colonnes, ajouter WHERE, et trier avec ORDER BY (avec ASC implicite et DESC).
13. Utiliser DISTINCT pour supprimer les doublons et décrire le rôle de INNER JOIN avec la condition ON.
14. En SQL, décrire l’effet d’INSERT, UPDATE et DELETE, et rappeler le rôle crucial de WHERE (sinon tout).