Lernzettel: Introduction aux Structures de Données et Algorithmes

📋 Plan du Cours

1. Interface, implémentation et POO
2. Listes, piles, files et dictionnaires
3. Arbres et graphes
4. Modèle relationnel et SQL
5. Systèmes, routage et cryptographie
6. Récursivité et algorithmes

📖 1. Interface, implémentation et POO

🔑 Notions clés & Définitions

• Interface de structure : Une interface de structure décrit les opérations disponibles pour utiliser la structure de données sans préciser comment elles sont réalisées.
• Implémentation : Une implémentation est la réalisation concrète du comportement d’une structure de données, avec un codage précis et des choix techniques.
• Classe : Une classe est un modèle qui regroupe des attributs (données) et des méthodes (fonctions) pour créer des objets.

📝 Points essentiels

• Une interface reste la même même si l’implémentation change, ce qui facilite la maintenance du code.
• On peut écrire plusieurs implémentations pour une même structure, par exemple une file avec un tableau ou avec deux piles.
• En POO, on accède aux attributs et on appelle les méthodes via l’objet créé à partir de la classe.
• Les structures de données servent d’abord à formaliser une interface, puis à choisir une implémentation réalisable dans un langage donné.

💡 Astuce mémo

Interface = boutons, implémentation = machine intérieure.

📖 2. Listes, piles, files et dictionnaires

🔑 Notions clés & Définitions

• Pile LIFO : Une pile est une structure linéaire où l’on retire toujours le dernier élément ajouté (LIFO).
• File FIFO : Une file est une structure linéaire où l’on retire toujours le premier élément ajouté (FIFO).
• Liste : Une liste est une structure linéaire qui regroupe des éléments, accessible et manipulable par l’une ou l’autre de ses extrémités selon les opérations.

📝 Points essentiels

• Pile : empiler ajoute au sommet et dépiler retire l’élément au sommet, après quoi la pile peut devenir vide.
• File : enfiler ajoute à une extrémité et défiler retire à l’autre extrémité, ce qui impose le comportement FIFO.
• Recherche dans une liste se fait typiquement en parcourant les éléments, tandis que l’accès par clé dans un dictionnaire passe par l’index de clé.
• Dans un dictionnaire, la clé permet d’accéder, de modifier et de supprimer une valeur avec un index de type mon_dictionnaire[clé] et del mon_dictionnaire[clé].

💡 Astuce mémo

Pile = Assiettes empilées (dernier posé, premier retiré) ; File = File d’attente (premier arrivé, premier servi).

📖 3. Arbres et graphes

🔑 Notions clés & Définitions

• Arbre binaire de recherche : Arbre binaire de recherche : arbre binaire où les valeurs à gauche d’un nœud sont plus petites et celles à droite sont plus grandes que la valeur du nœud.
• Parcours en profondeur : Parcours en profondeur : exploration récursive d’un arbre qui visite d’abord une branche jusqu’au bout avant de revenir en arrière.
• Matrice d’adjacence : Matrice d’adjacence : tableau $n\times n$ où un $1$ en position $(i,j)$ indique que le sommet $i$ est adjacent au sommet $j$.

📝 Points essentiels

• La taille d’un arbre est le nombre total de nœuds, et sa hauteur est le nombre d’arêtes entre la racine et le nœud le plus profond.
• Dans un ABR, chercher une clé se fait en comparant à chaque nœud puis en allant à gauche si la clé est plus petite, ou à droite si elle est plus grande.
• Un ABR équilibré permet une recherche en $O(\log(n))$, alors qu’un arbre déséquilibré peut dégrader la recherche jusqu’à $O(n)$.
• Pour les graphes, la représentation par matrice d’adjacence permet de passer ensuite à une liste de successeurs (voisins atteignables via une arête sortante) ou de prédécesseurs (voisins qui pointent vers un sommet).

💡 Astuce mémo

ABR : Gauche plus petit, Droite plus grand ; DFS : on descend avant de remonter.

📖 4. Modèle relationnel et SQL

🔑 Notions clés & Définitions

• SQL : Langage de requêtes conçu pour interroger, insérer, modifier et supprimer des données dans des bases de données relationnelles.
• SQLite : Système de gestion de base de données relationnelle très répandu, utilisant le langage SQL (avec de petites variations possibles selon les SGBD).
• Jointure INNER JOIN : Opération SQL qui combine deux tables en fusionnant les lignes dont les clés liées vérifient la condition ON.

📝 Points essentiels

• Les requêtes d’interrogation utilisent SELECT et peuvent filtrer avec WHERE, trier avec ORDER BY (ASC ou DESC) et supprimer les doublons avec DISTINCT.
• Dans une jointure INNER JOIN, la condition ON relie une clé étrangère d’une table à la clé primaire de l’autre, par exemple LIVRES.id_auteur = AUTEURS.id.
• Pour insérer, on utilise INSERT INTO avec la liste d’attributs puis des VALUES dans le même ordre, et pour UPDATE/DELETE on ajoute presque toujours une clause WHERE pour cibler les lignes.
• Les jointures peuvent ensuite être restreintes avec une clause WHERE portant sur les colonnes de la jointure, comme WHERE LIVRES.ann_publi>1965.

💡 Astuce mémo

SELECT = choisir, WHERE = filtrer, ORDER BY = trier, DISTINCT = dédoublonner.

📖 5. Systèmes, routage et cryptographie

🔑 Notions clés & Définitions

• Adresse de passerelle : L’adresse de passerelle est l’IP du routeur à utiliser pour joindre un réseau non directement connecté à l’émetteur.
• Table de routage statique : Une table de routage statique est une table construite manuellement quand le réseau est petit et peu évolutif.
• RIP : RIP est un protocole de routage dynamique qui met à jour les tables en échangeant périodiquement des informations de distance.

📝 Points essentiels

• Les réseaux directement accessibles au routeur n’exigent pas d’adresse passerelle, alors qu’un réseau distant passe par le routeur choisi dans la table de routage avec son IP de passerelle.
• RIP échange les tables toutes les 30 secondes et utilise une métrique en nombre de sauts où la distance augmente de 1 à chaque routeur intermédiaire.
• RIP considère comme distance infinie la valeur 16 et limite donc la validité aux réseaux de petite taille.
• Dans OSPF, la valeur de coût d’une liaison est inversement proportionnelle au débit, via la formule coût = 108 / d, et le plus rapide n’est pas forcément le plus court en nombre de sauts.

💡 Astuce mémo

RIP = Répète toutes les 30 s + distance en sauts (jusqu’à 16) ; OSPF = coût inverse au débit (coût = 108/d) puis Dijkstra en fond.

📖 6. Récursivité et algorithmes

🔑 Notions clés & Définitions

• Récursivité : La récursivité est une technique où une fonction se définit en s’appelant elle-même sur un cas plus petit jusqu’à atteindre un cas de base.
• Correction d’un algorithme récursif : La correction d’un algorithme récursif garantit que, s’il termine, il renvoie bien le résultat attendu en s’appuyant sur la validité des appels internes.
• Terminaison d’un algorithme récursif : La terminaison d’un algorithme récursif signifie que l’appel récursif atteint forcément un cas de base au bout d’un nombre fini d’étapes.

📝 Points essentiels

• Pour $sum\_recursif(5)$, la fonction est exécutée 6 fois et les valeurs de l’argument $n$ sont 5, 4, 3, 2, 1 et 0.
• Pour $sum\_recursif(5)$, les valeurs renvoyées par les appels successifs sont 0, 1, 3, 6, 10 et 15.
• Un algorithme récursif correct vérifie deux propriétés : la correction (cas de base puis conservation) et la terminaison (atteinte du cas de base).
• Avec $somme t ext{ }it\_iteratif$ vs $somme\_recursif$ pour $n=100$ sur 100 exécutions, l’itératif est plus rapide (environ 0.001 s contre 0.005 s).

💡 Astuce mémo

Correction = Base + Conservation ; Terminaison = n décroît jusqu’à 0.

📅 Repères chronologiques

📊 Tableaux de synthèse

Piles vs files (logique FIFO/LIFO)

Interface vs implémentation

⚠️ Pièges & confusions fréquents

1. Confondre interface et implémentation : l’interface ne change pas quand on remplace la façon de réaliser la structure.
2. Croire que dans une file (FIFO) on retire le dernier élément : en réalité on défiler à l’autre extrémité (premier arrivé, premier servi).
3. Mélanger clé de dictionnaire et index de liste : une clé est associée à une valeur via mon_dictionnaire[clé], un index via ma_liste[i].
4. En ABR, oublier la règle de parcours : à chaque nœud, aller à gauche si la clé est plus petite, à droite si elle est plus grande.
5. Erreur SQL classique : omettre WHERE dans UPDATE/DELETE, ce qui cible toutes les lignes de la table.
6. Récursivité : croire qu’il suffit que la fonction s’appelle elle-même ; il faut aussi un cas de base (correction) et une décroissance vers ce cas (terminaison).
7. Boyer-Moore : confondre le sens du ‘regard’ (comparaison droite-gauche) ou le décalage quand le caractère n’est pas dans la table.

✅ Checklist Examen

1. Spécifie une structure par son interface (opérations) et explique la différence avec son implémentation (réalisation concrète).
2. Définis une classe (attributs + méthodes), puis montres comment accéder aux attributs et appeler les méthodes via un objet.
3. Distingue pile LIFO et file FIFO en utilisant les opérations (empiler/dépiler, enfiler/défiler) et la logique de retrait.
4. Décris le rôle des listes pour accéder/manipuler via extrémités et compare la recherche linéaire d’une liste à l’accès par clé d’un dictionnaire (mon_dictionnaire[clé], del).
5. Calcule/emploie les métriques d’arbres (taille = nb de nœuds, hauteur = nb d’arêtes) et identifie la recherche dans un ABR (gauche <, droite >).
6. Reconnais les parcours d’arbres (préfixe/infixe/suffixe) et le BFS/DFS en suivant l’ordre de visite demandé.
7. Construis des requêtes SQL avec SELECT/WHERE/ORDER BY/DISTINCT et une INNER JOIN via ON reliant clé étrangère et clé primaire.
8. Réalise en SQL : INSERT INTO (respect de l’ordre des VALUES), UPDATE/DELETE avec WHERE, et comprendre l’intérêt d’une clause WHERE après une jointure.
9. Exploite les notions réseau : différence réseau directement accessible vs distant via adresse de passerelle, et appliquer RIP (métrique en sauts jusqu’à 16) vs OSPF (coût = 108/d).
10. Vérifie une fonction récursive : correction (cas de base + conservation) et terminaison (atteinte du cas de base en nb fini d’étapes).
11. Décris la modularité (modules, fonctions/classes, bibliothèques) et utiliser l’aide/documentation Python (dir, help, docstrings).
12. Modélise un graphe et relie représentation et traitement : matrice d’adjacence ↔ listes successeurs/prédécesseurs, puis DFS/BFS, et savoir situer Dijkstra, diviser pour régner, programmation dynamique, et Boyer-Moore (avec prétraitement du motif).