Lernzettel: Introduction à la Programmation et Structures de Données

📋 Plan du Cours

1. Programmation orientée objet
2. Piles, files et listes
3. Dictionnaires Python
4. Arbres binaires et ABR
5. Parcours et recherche de graphes
6. Modèle relationnel SQL
7. Routage RIP et OSPF
8. Récursivité
9. Diviser pour régner
10. Modularité en Python
11. Tri par insertion et sélection
12. Congruences et théorèmes arithmétiques

📖 1. Programmation orientée objet

🔑 Notions clés & Définitions

• Interface : Une interface décrit les fonctionnalités attendues d’une classe ou d’un module sans imposer l’implémentation exacte.
• Implémentation : L’implémentation est la réalisation concrète des fonctionnalités décrites par une interface.
• Encapsulation : L’encapsulation consiste à protéger les données internes d’une classe et à n’y donner accès que via des méthodes prévues.
• 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 différents types, grâce à des méthodes redéfinies.

📝 Points essentiels

• Une interface définit ce que fait une classe sans fournir les détails de comment elle le fait.
• L’encapsulation passe par des attributs internes protégés (ex. privés) et des méthodes accessibles depuis l’extérieur.
• L’héritage sert à réutiliser du code existant et à spécialiser un comportement.
• Le polymorphisme s’exprime quand plusieurs types répondent à la même méthode/interface mais avec des comportements différents.

📖 2. Piles, files et listes

🔑 Notions clés & Définitions

• Pile LIFO : Une pile est une structure où le dernier élément entré est le premier à sortir.
• File FIFO : Une file est une structure où le premier élément entré est le premier à sortir.
• Liste : Une liste est une structure linéaire dynamique permettant l’accès et la modification à des positions quelconques.

📝 Points essentiels

• En Python, une pile peut être modélisée par une liste et utilisée avec append pour entrer et pop pour sortir.
• En Python, pour une file modélisée par une liste, pop(0) retire l’élément le plus ancien.
• Le comportement LIFO/FIFO dépend uniquement de la façon dont on ajoute et retire les éléments de la structure.

📖 3. Dictionnaires Python

🔑 Notions clés & Définitions

• Dictionnaire : Un dictionnaire est une structure non ordonnée associant des paires clé-valeur.
• Clé-valeur : Une clé est utilisée pour accéder à la valeur associée dans un dictionnaire.
• Complexité moyenne O(1) : Dans un dictionnaire, la recherche, l’insertion et la suppression ont une complexité moyenne en temps O(1).

📝 Points essentiels

• On accède à une valeur avec la syntaxe dictionnaire[clé] et on peut créer/modifier une entrée avec dictionnaire[clé]=valeur.
• La suppression d’une entrée se fait avec del dictionnaire[clé].
• Pour parcourir un dictionnaire, for donne les clés, values donne les valeurs et items donne les paires clé-valeur.

📖 4. 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 sans enfant dans l’arbre.
• Arbre binaire : Un arbre binaire est un arbre où chaque nœud a au plus deux enfants.
• ABR : Un ABR est un arbre binaire de recherche où tout nœud gauche contient des valeurs inférieures et tout nœud droit des valeurs supérieures.
• Hauteur : La hauteur d’un arbre est le nombre d’arêtes entre la racine et le nœud le plus profond, et elle vaut -1 pour un arbre vide.

📝 Points essentiels

• Dans un ABR, la recherche suit les comparaisons: à gauche si la valeur cherchée est inférieure, sinon à droite.
• Le parcours infixe (gauche → racine → droite) d’un ABR produit les valeurs triées dans l’ordre croissant.
• La taille d’un arbre correspond au nombre total de nœuds.

📖 5. Parcours et recherche de graphes

🔑 Notions clés & Définitions

• Sommet : Un sommet est un nœud (point) du graphe contenant une information.
• Arête orientée : Une arête orientée relie deux sommets en indiquant un sens de parcours.
• Matrice d’adjacence : Une matrice d’adjacence code les arêtes dans un tableau à deux dimensions (poids ou présence entre i et j).
• Liste de successeurs : Une liste de successeurs regroupe, pour chaque sommet, les sommets accessibles directement depuis lui.
• DFS : DFS est un parcours en profondeur d’abord qui explore le plus loin possible avant de revenir en arrière.

📝 Points essentiels

• DFS et BFS ignorent les poids dans le contenu fourni et se basent sur le voisinage non visité pour ordonner la visite.
• BFS (parcours en largeur) explore d’abord tous les voisins d’un niveau avant de passer au suivant.
• Dans l’implémentation avec liste de successeurs, l’ordre de visite dépend de la liste des voisins fournie.
• La représentation par matrice permet de construire la liste des successeurs en lisant les colonnes j reliées au i.

📖 6. Modèle relationnel SQL

🔑 Notions clés & Définitions

• Relation : Une relation correspond à une table d’une base de données.
• Attribut : Un attribut est une colonne d’une table représentant une propriété des données.
• Clé primaire : La clé primaire identifie de façon unique chaque ligne d’une table.
• Clé étrangère : Une clé étrangère relie un enregistrement à la clé primaire d’une autre table.
• Domaine : Le domaine est l’ensemble des valeurs admissibles pour un attribut.

📝 Points essentiels

• La recherche de données s’exprime avec SELECT et le filtrage avec WHERE.
• Le tri se fait avec ORDER BY et peut être croissant (par défaut) ou décroissant avec DESC.
• Les doublons peuvent être supprimés avec DISTINCT.
• Une jointure interne INNER JOIN relie deux tables via une condition (ex. LIVRES.id_auteur = AUTEURS.id).
• La suppression sans WHERE (DELETE FROM LIVRES) supprime toutes les données de la table.

📖 7. Routage RIP et OSPF

🔑 Notions clés & Définitions

• Adresse IP : Une adresse IP identifie une machine dans un réseau.
• Masque de sous-réseau : Le masque sépare la partie réseau et la partie hôte d’une adresse IP.
• CIDR : La notation CIDR /n indique le nombre de bits réservés à la partie réseau.
• RIP : RIP est un protocole de routage fondé sur l’échange périodique de tables et une métrique en nombre de sauts.
• OSPF : OSPF est un protocole qui utilise une vision globale du réseau et calcule un coût minimal des liaisons.

📝 Points essentiels

• RIP utilise la métrique du nombre de sauts et ignore une route plus longue que la meilleure connue.
• RIP rend une route de distance infinie après inactivité pendant 3 minutes, avec une valeur d’infini fixée à 16.
• OSPF choisit un chemin optimal basé sur un coût minimal des liaisons, proportionnel à la bande passante.
• Le coût OSPF présenté se calcule à partir du débit, avec une comparaison montrant que RIP peut conduire à un trajet différent.

📖 8. Récursivité

🔑 Notions clés & Définitions

• Fonction récursive : Une fonction récursive est une fonction qui s’appelle elle-même pendant son exécution.
• Cas de base : Le cas de base est la condition qui arrête la récursion et évite l’appel infini.
• Appel récursif : L’appel récursif réduit le problème à une version plus petite pour atteindre le cas de base.
• Factorielle : La factorielle de n est calculée via une récursion qui multiplie n par la factorielle de n-1 jusqu’au cas de base.

📝 Points essentiels

• Une bonne récursion nécessite un cas de base présent et atteignable, sinon l’appel ne s’arrête pas.
• La réduction du problème doit être correcte à chaque appel pour garantir le passage vers le cas de base.
• Par défaut, Python autorise environ 1000 appels récursifs avant une erreur liée à la profondeur maximale.

📖 9. Diviser pour régner

🔑 Notions clés & Définitions

• Diviser pour régner : Diviser pour régner est une stratégie où l’on découpe un problème, on résout les sous-problèmes puis on combine les résultats.
• Tri fusion : Le tri fusion est un algorithme diviser pour régner qui sépare la liste, trie chaque moitié puis fusionne.
• Fusion (merge) : La fusion est l’étape qui combine deux listes triées en une seule liste triée.

📝 Points essentiels

• Tri fusion a pour cas de base une liste de longueur au plus 1, qui est déjà triée.
• L’étape de division sépare la liste au milieu via len(liste)//2.
• La fusion compare en tête les deux listes et ajoute successivement le plus petit élément au résultat final.

📖 10. Modularité en Python

🔑 Notions clés & Définitions

• Modularité : La modularité consiste à découper un système complexe en modules qui gèrent chacun une fonctionnalité spécifique.
• Réutilisabilité : La réutilisabilité désigne la possibilité d’utiliser un module dans plusieurs projets différents.
• Maintenabilité : La maintenabilité mesure la facilité à localiser et corriger les erreurs quand le code est découpé en modules.
• Extensibilité : L’extensibilité correspond à la capacité d’ajouter ou modifier des fonctionnalités sans tout réécrire.
• Docstring : Une docstring est la documentation accessible via l’attribut doc d’un élément.

📝 Points essentiels

• En Python, dir(module) liste les éléments disponibles dans un module.
• help(nom_module.élément) affiche l’aide intégrée d’un élément et help(fonction) documente une fonction.
• import module permet d’appeler module.fonction, tandis que from module import fonction permet d’appeler directement fonction.
• from module import * importe tout, ce qui peut créer des conflits de noms.
• On peut créer un module en écrivant une fonction (par ex. addition) documentée par une docstring.

📖 11. 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 choisit à chaque étape le minimum restant et l’échange avec la position courante.
• Coût quadratique : Un coût quadratique signifie que le temps augmente proportionnellement au carré de la taille du tableau.

📝 Points essentiels

• Le tri par insertion avance i de 1 à n-1 et décale vers la droite les éléments plus grands jusqu’à placer la valeur insérée.
• Le tri par sélection parcourt i puis cherche l’indice du minimum dans la partie à droite et échange avec tab[i].
• Tri par insertion et tri par sélection ont un coût en O(n^2) dans le pire cas.

📖 12. 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 garantit l’existence de coefficients x et y tels que ax+by soit égal au PGCD de a et b.
• Algorithme d’Euclide : L’algorithme d’Euclide calcule le PGCD en remplaçant (a,b) par (b, a mod b) jusqu’à b=0.
• Euclide étendu : L’algorithme d’Euclide étendu renvoie aussi des coefficients x et y pour écrire une combinaison de a et b égale au PGCD.
• Congruence : On a a≡b (mod n) si et seulement si n divise la différence a−b.
• Petit théorème de Fermat : Le petit théorème de Fermat relie un premier p et un entier a non divisible par p via ap-1 ≡ 1 (mod p).

📝 Points essentiels

• Avec l’Euclide, si b=0 alors le PGCD vaut a, et si b>0 on écrit a=qb+r puis on remplace par PGCD(b,r).
• Dans l’Euclide étendu, quand b=0 on obtient x=1 et y=0 pour satisfaire ax+by=d avec d=a.
• Les congruences vérifient la réflexivité, la symétrie, la transitivité, et sont compatibles avec l’addition, la soustraction, la multiplication et les puissances.
• Critère de divisibilité par 9: un entier est divisible par 9 exactement quand la somme de ses chiffres est divisible par 9.

📊 Tableaux de synthèse

RIP vs OSPF

⚠️ Pièges & confusions fréquents

1. Confondre pile et file: LIFO utilise pop sur le dernier, alors que FIFO se fait typiquement en retirant le premier élément (ex. pop(0) dans la liste).
2. Croire que DFS/BFS prennent en compte les poids: dans le contenu fourni, les parcours ignorent les poids des arêtes.
3. Se tromper sur la hauteur d’un arbre vide: elle vaut -1 dans l’implémentation donnée.
4. Oublier le cas de base en récursivité: sans condition d’arrêt atteignable, Python finit par provoquer une erreur de profondeur maximale.
5. Confondre congruence et égalité: a≡b (mod n) signifie un reste de différence divisible par n, pas forcément a=b.
6. Prendre une route sans WHERE en SQL: DELETE sans condition supprime toutes les lignes de la table.

✅ Checklist Examen

1. Savoir définir une interface, distinguer interface et implémentation, puis expliquer encap­sulation, héritage et polymorphisme.
2. Savoir caractériser pile LIFO et file FIFO, et relier cela aux opérations append/pop dans une liste Python.
3. Savoir décrire un dictionnaire comme ensemble clé-valeur non ordonné et donner la complexité moyenne O(1) pour recherche/insertion/suppression.
4. Savoir définir racine, feuille, arbre binaire et ABR, puis donner la règle ABR gauche < parent < droite.
5. Savoir comparer les parcours arbre: préfixe, infixe, suffixe et préciser l’idée de parcours en largeur niveau par niveau.
6. Savoir expliquer comment chercher et insérer dans un ABR à l’aide des comparaisons avec la valeur du nœud.
7. Savoir définir sommet et arête orientée, puis distinguer matrice d’adjacence et liste de successeurs.
8. Savoir décrire DFS (profondeur) et BFS (largeur) et donner l’idée d’ordre de visite illustrée.
9. Savoir donner les notions relation, attribut, domaine, clé primaire, clé étrangère.
10. Savoir écrire des requêtes SQL avec SELECT, WHERE, ORDER BY, DISTINCT et INNER JOIN, et citer COUNT(*) et les opérations INSERT/UPDATE/DELETE.
11. Savoir définir adresse IP, masque, adresse réseau, broadcast et CIDR, puis décrire les champs typiques d’une table de routage.
12. Savoir résumer RIP: métrique en sauts, règles d’update et inactivation après 3 minutes (distance infinie à 16).
13. Savoir résumer OSPF: coût minimal basé sur un coût lié au débit et notion de chemin optimal.
14. Savoir définir récursivité, cas de base, et décrire le rôle de la réduction jusqu’à une terminaison.