Lernzettel: Introduction aux structures de données et algorithmes fondamentaux

📋 Plan du Cours

1. POO et structures de données
2. Piles, files et dictionnaires
3. Arbres binaires et AVL
4. Parcours et recherche dans les graphes
5. Modèle relationnel et SQL
6. Routage et protocoles réseau
7. Récursivité et diviser pour régner
8. Modules et importations Python
9. Tri par insertion et sélection
10. Congruences et théorèmes arithmétiques

📖 1. POO et structures de données

🔑 Notions clés & Définitions

• Interface : Une interface décrit les fonctionnalités attendues d’un type sans fournir l’implémentation concrète.
• Implémentation : Une implémentation correspond au code réel qui réalise les fonctionnalités annoncées par l’interface.
• Encapsulation : L’encapsulation protège les données internes en les rendant privées et en exposant des méthodes publiques d’accès.
• Héritage : L’héritage permet à une classe de réutiliser et d’étendre le comportement d’une classe parente.
• Polymorphisme : Le polymorphisme permet d’utiliser une même interface avec plusieurs types grâce à des méthodes redéfinies.

📝 Points essentiels

• Une classe en Python utilise un constructeur init pour initialiser les attributs via self.
• Une méthode d’instance agit sur l’état de l’objet car elle accède aux attributs portés par self.
• On peut modifier un attribut d’instance en méthode, par exemple pour mettre à jour un kilométrage.

💡 Astuce mémo

Interface = contrat, implémentation = exécution.

📖 2. Piles, files et dictionnaires

🔑 Notions clés & Définitions

• Pile : Une pile applique le principe LIFO, où le dernier élément ajouté est le premier retiré.
• File : Une file applique le principe FIFO, où le premier élément ajouté est le premier retiré.
• Liste : Une liste est une structure linéaire dynamique permettant d’insérer et de supprimer à des positions quelconques.
• Dictionnaire : Un dictionnaire est une structure non ordonnée basée sur des paires clé-valeur pour accéder rapidement aux éléments.

📝 Points essentiels

• En Python, pile.append(x) ajoute en haut et pile.pop() retire le dernier ajouté.
• En Python, file.append(x) ajoute en fin et file.pop(0) retire le premier ajouté.
• Les opérations d’un dictionnaire (recherche, insertion, suppression) ont une complexité moyenne en O(1).
• Pour parcourir un dictionnaire, on peut itérer sur les clés, ou utiliser values() pour les valeurs, ou items() pour les paires clé-valeur.

💡 Astuce mémo

Pile : LIFO, File : FIFO, Dico : clé→valeur.

📖 3. Arbres binaires et AVL

🔑 Notions clés & Définitions

• Racine : La racine est le nœud de départ d’un arbre, celui qui n’a pas de parent.
• Feuille : Une feuille est un nœud de l’arbre qui ne possède aucun enfant.
• ABR : Un arbre binaire de recherche impose que le sous-arbre gauche contienne des valeurs plus petites et que le sous-arbre droit contienne des valeurs plus grandes.
• Arbre AVL : Un arbre AVL est un ABR auto-équilibré qui garde une hauteur logarithmique pour des opérations efficaces.

📝 Points essentiels

• La taille d’un arbre correspond au nombre total de nœuds, ce qui peut se calculer par récursion sur gauche et droite.
• La hauteur est le nombre d’arêtes entre la racine et le nœud le plus profond, avec -1 pour un arbre vide dans l’exemple.
• Dans un ABR, la recherche compare la valeur puis choisit gauche si la cible est plus petite, sinon droite.
• La recherche dans un AVL est en O(log(n)), alors qu’un ABR non équilibré peut tomber à O(n) en pire cas.

💡 Astuce mémo

ABR : gauche < parent < droite ; AVL : équilibre pour rester en log(n).

📖 4. Parcours et recherche dans les graphes

🔑 Notions clés & Définitions

• Sommet : Un sommet est un point représentant une entité dans un graphe.
• Arête orientée : Une arête orientée relie deux sommets avec une direction de départ vers arrivée.
• Graphe pondéré : Un graphe pondéré associe à chaque arête un poids qui représente un coût.
• Connexité : Un graphe est connexe si toute paire de sommets peut être reliée par une chaîne d’arêtes.

📝 Points essentiels

• Une matrice d’adjacence place le poids (ou une valeur non nulle) dans la case [i][j] pour l’arête de i vers j.
• Une liste de successeurs donne, pour un sommet, les sommets accessibles depuis celui-ci.
• DFS explore en profondeur avant de revenir en arrière et ignore les poids.
• BFS explore par niveaux (voisins puis voisins des voisins) et trouve un plus court chemin si chaque arête vaut 1.

💡 Astuce mémo

DFS = on descend, BFS = on élargit par niveaux.

📖 5. Modèle relationnel et SQL

🔑 Notions clés & Définitions

• Relation : Une relation correspond à une table dans une base de données.
• Clé primaire : Une clé primaire identifie de façon unique chaque ligne d’une table.
• Clé étrangère : Une clé étrangère est un attribut qui référence la clé primaire d’une autre table.
• Jointure interne : Une jointure interne relie deux tables en ne gardant que les lignes qui correspondent selon une condition.

📝 Points essentiels

• Une requête SELECT * FROM nom_table affiche toutes les colonnes d’une table.
• La clause WHERE filtre les lignes et ORDER BY trie, avec DESC pour l’ordre décroissant.
• DISTINCT supprime les doublons, par exemple pour obtenir les langues présentes dans AUTEURS.
• Pour compter des lignes satisfaisant un filtre, on utilise SELECT COUNT(*) FROM ... WHERE ... .
• Une jointure interne se fait avec INNER JOIN ... ON, puis on peut ajouter des conditions via WHERE.

💡 Astuce mémo

WHERE filtre, ORDER BY trie, DISTINCT dédoublonne, JOIN relie.

📖 6. Routage et protocoles réseau

🔑 Notions clés & Définitions

• Adresse IP : Une adresse IP identifie une machine dans un réseau, comme 192.168.1.10.
• Masque de sous-réseau : Le masque de sous-réseau sépare la partie réseau de la partie hôte dans une adresse IP.
• Adresse de broadcast : L’adresse de broadcast permet d’envoyer un message à toutes les machines d’un même sous-réseau.
• Table de routage : Une table de routage indique vers où envoyer un paquet selon la destination et l’interface.

📝 Points essentiels

• En CIDR, /n correspond au nombre de bits de la partie réseau et /24 équivaut à 255.255.255.0.
• Une route de la table associe une Destination à une Interface et éventuellement à une Passerelle.
• RIP échange périodiquement des tables et utilise une métrique en nombre de sauts.
• Dans RIP, une route inactif depuis 3 minutes devient de distance infinie avec la valeur 16.
• OSPF choisit le chemin optimal selon un coût de liaisons proportionnel au débit, pas seulement le plus court en sauts.

💡 Astuce mémo

RIP = sauts ; OSPF = coût des liaisons (débit).

📖 7. Récursivité et diviser pour régner

🔑 Notions clés & Définitions

• Récursion : La récursivité est le mécanisme où une fonction s’appelle elle-même pour résoudre un problème par étapes.
• Cas de base : Le cas de base est la condition qui arrête la récursion et garantit la terminaison.
• Diviser pour régner : Diviser pour régner consiste à découper un problème, résoudre chaque partie, puis combiner les résultats.
• Tri fusion : Le tri fusion est un algorithme diviser-pour-régner qui trie en fusionnant deux moitiés triées.

📝 Points essentiels

• Une fonction récursive doit avoir un cas de base qui termine l’enchaînement des appels.
• La factorielle calcule n! via un cas de base n==0 et un appel sur n-1.
• Dans l’exemple, Python autorise environ 1000 appels récursifs par défaut, ce qui peut limiter les récursions profondes.
• Pour le tri fusion, on divise par milieu len(liste)//2 puis on combine via fusion des deux listes triées.
• Le cas de base du tri fusion renvoie la liste si sa longueur est ≤ 1.

💡 Astuce mémo

Récursion = cas de base + réduction du problème ; Tri fusion = diviser puis fusionner.

📖 8. Modules et importations Python

🔑 Notions clés & Définitions

• dir : dir(module) liste les noms disponibles dans un module Python, y compris les attributs internes.
• Documentation intégrée : L’aide intégrée help(...) affiche une description directement exploitable des objets Python.
• Docstring : Une docstring est la documentation d’un objet, accessible par doc.
• Alias : Un alias permet de renommer un module ou une fonction lors de l’importation via as.

📝 Points essentiels

• import module permet d’appeler ses fonctions avec la notation module.fonction().
• from module import fonction donne accès directement à la fonction sans préfixe.
• from module import * importe tout, et c’est déconseillé pour éviter des conflits de noms.
• help(nom_du_module.élément) affiche l’aide de l’élément, comme pour math.sin.

💡 Astuce mémo

import module.f() ; from module import f() ; as = raccourci.

📖 9. Tri par insertion et sélection

🔑 Notions clés & Définitions

• Tri par insertion : Le tri par insertion construit progressivement un tableau trié en insérant chaque nouvel élément à la bonne position.
• Tri par sélection : Le tri par sélection parcourt le tableau et choisit à chaque étape l’élément minimal restant à placer.

📝 Points essentiels

• Dans tri_insertion, on échange vers la gauche tant que la valeur courante est strictement plus petite que l’élément précédent.
• Dans tri_selection, on recherche min_i dans la partie non triée puis on échange tab[i] avec tab[min_i].
• Pour les deux tris, le coût au pire est quadratique, en O(n²), et dépend de la taille du tableau n.
• Le tri par insertion et le tri par sélection réalisent des boucles imbriquées, ce qui explique la croissance en n².

💡 Astuce mémo

Insertion = on décale, Sélection = on trouve le minimum puis on échange.

📖 10. Congruences et théorèmes arithmétiques

🔑 Notions clés & Définitions

• Théorème de Bézout : Le théorème de Bézout affirme l’existence d’entiers x et y tels que ax + by égale le PGCD(a,b).
• Algorithme d’Euclide : L’algorithme d’Euclide calcule le PGCD en remplaçant (a,b) par (b, r) avec r le reste de la division euclidienne.
• Congruence : On écrit a≡b (mod n) quand n divise la différence a−b.
• Petit théorème de Fermat : Le petit théorème de Fermat donne une congruence pour a^{p-1} modulo un nombre premier p.

📝 Points essentiels

• Dans l’algorithme d’Euclide, si b==0 alors le PGCD vaut a, sinon on pose a=qb+r et on recommence sur (b,r).
• L’Euclide étendu renvoie aussi des coefficients x et y tels que ax+by=PGCD(a,b).
• Les congruences sont stables par addition, soustraction et multiplication, comme a+c≡b+d (mod n).
• Pour tout entier k, si a≡b (mod n) alors a^k≡b^k (mod n).
• Si p est premier et a non divisible par p, alors a^{p-1}≡1 (mod p).
• Un nombre est divisible par 9 si et seulement si la somme de ses chiffres est divisible par 9.

💡 Astuce mémo

Bézout = combinaisons vers le PGCD ; Congruence = même reste modulo n.

⚠️ Pièges & confusions fréquents

1. Confondre pile et file : une pile retire le dernier ajouté (LIFO) tandis qu’une file retire le premier ajouté (FIFO).
2. Mélanger ABR et AVL : un ABR ne garantit pas l’équilibre, alors qu’un AVL maintient une hauteur logarithmique.
3. Se tromper sur la hauteur : l’exemple définit la hauteur comme un nombre d’arêtes depuis la racine, avec -1 pour l’arbre vide.
4. Croire que BFS utilise les poids : dans le cours, BFS/DFS ignorent les poids et supposent un coût unitaire pour parler de plus court chemin.
5. Oublier que DELETE sans WHERE supprime toutes les données, alors que WHERE restreint la suppression aux lignes ciblées.
6. Croire que la congruence est une égalité : a≡b (mod n) signifie seulement que a−b est divisible par n.
7. Penser que la récursion termine automatiquement : sans cas de base, elle peut dépasser la limite d’environ 1000 appels en Python.

✅ Checklist Examen

1. Savoir définir et distinguer interface et implémentation en POO.
2. Savoir expliquer l’encapsulation via attributs privés et méthodes publiques.
3. Savoir définir héritage et polymorphisme et donner le rôle des méthodes redéfinies.
4. Savoir donner la règle LIFO pour une pile et FIFO pour une file.
5. Savoir décrire les opérations Python montrées : append et pop (pile) et pop(0) (file).
6. Savoir définir un dictionnaire clé-valeur et la complexité moyenne O(1) des opérations.
7. Savoir définir racine, feuille et sous-arbre, et reconnaître la structure hiérarchique d’un arbre.
8. Savoir formuler la propriété d’un ABR sur le sous-arbre gauche et le sous-arbre droit.
9. Savoir citer les formules de taille et de hauteur telles qu’utilisées et interpréter l’exemple de hauteur.
10. Savoir comparer les parcours préfixe, infixe, suffixe et largeur d’abord.
11. Savoir décrire la recherche dans un ABR et l’insertion par récursion.
12. Savoir définir un AVL et annoncer la complexité O(log(n)) de la recherche dans le cours.
13. Savoir définir sommet, arête (orientée ou non) et graphe pondéré.
14. Savoir distinguer connexité et représentation par matrice d’adjacence ou listes de successeurs.