Lernzettel: Introduction aux réseaux, SQL et arbres

📋 Plan du Cours

1. Routage et tables de routage
2. Protocole RIP
3. Protocole OSPF
4. SQL relationnel
5. Clauses et requêtes SQL
6. Fonctions d'agrégation SQL
7. Graphes et représentations
8. Chemins, chaînes et connexité
9. Arbres binaires et parcours
10. Processus et PCB
11. Ordonnancement des processus
12. Ressources et interblocage

📖 1. Routage et tables de routage

🔑 Notions clés & Définitions

• Routage : Le routage est le mécanisme qui choisit un chemin dans un réseau pour acheminer les données de l’émetteur vers le(s) destinataire(s).
• Routeur : Un routeur est un équipement reliant plusieurs réseaux et assurant le routage des paquets entre eux en déterminant leur chemin.
• Table de routage : Une table de routage associe des destinations (réseaux/sous-réseaux) à une interface de sortie, une passerelle et une métrique.
• Route par défaut : La route par défaut indique quel prochain saut utiliser quand la destination ne correspond à aucune entrée de la table.

📝 Points essentiels

• Un routeur lit une ligne en vérifiant si (IP cible AND masque) correspond au réseau cible de la ligne, puis en sortant par l’interface indiquée vers la passerelle avec la métrique associée.
• Quand plusieurs routes correspondent à une destination, le routeur choisit la plus “courte” selon la métrique, donc une valeur plus petite signifie un chemin meilleur.
• Un réseau directement connecté a une métrique de 0, ce qui correspond au cas où la passerelle et l’interface se confondent.
• Une table de routage peut contenir des routes directement connectées, des routes statiques, des routes dynamiques et une route par défaut pour les destinations non couvertes.
• En l’absence de route par défaut, le routeur élimine le datagramme dont la destination n’apparaît dans aucune entrée de la table.

💡 Astuce mémo

Choisir la route = (IP cible AND masque) ⇒ destination; puis interface de sortie, passerelle, et métrique (plus petite = meilleur).

📖 2. Protocole RIP

🔑 Notions clés & Définitions

• RIP : RIP est un protocole de routage dynamique basé sur l’échange périodique d’informations entre routeurs adjacents pour mettre à jour les tables de routage.
• Vecteur de distance : Un protocole à vecteur de distance diffuse, pour chaque destination, une estimation de la “meilleure” route à partir des informations reçues des voisins.
• Nombre de sauts : La métrique de RIP mesure le nombre de routeurs traversés pour atteindre un réseau cible.
• Algorithme de Bellman-Ford : Bellman-Ford calcule des plus courts chemins dans un graphe et sert de base au calcul des routes de RIP.

📝 Points essentiels

• RIP commence avec une table ne contenant que les réseaux directement reliés au routeur.
• Toutes les 30 secondes, chaque routeur envoie à ses voisins un message contenant la liste des réseaux qu’il connaît.
• Après échanges, les routeurs mettent à jour leur table de routage avec les informations reçues.
• RIP élit la route selon le nombre de sauts, en s’appuyant sur l’algorithme de Bellman-Ford.
• RIP est limité à 15 sauts pour atteindre une destination, soit au maximum 15 routeurs traversés.
• RIP est rarement utilisé dans les grandes infrastructures car ses échanges périodiques génèrent beaucoup de trafic et son plafond de sauts limite les réseaux étendus.

📖 3. Protocole OSPF

🔑 Notions clés & Définitions

• OSPF : OSPF est un protocole de routage dynamique qui choisit les meilleures routes en s’appuyant sur l’état des liaisons et un calcul de plus courts chemins.
• SPF : SPF est l’algorithme utilisé par OSPF pour déterminer la meilleure route vers une destination à partir du graphe du réseau.
• Coût de liaison : Le coût de liaison est une valeur associée à chaque lien pour orienter le choix de route, en privilégiant les liaisons avec un coût faible.
• Coût de route : Le coût de route est la somme des coûts des liaisons traversées pour atteindre une destination.

📝 Points essentiels

• OSPF est un protocole ouvert (son fonctionnement peut être connu de tous) et il utilise l’algorithme SPF, aussi appelé Dijkstra, pour sélectionner la route.
• OSPF attribue un coût à chaque liaison afin de favoriser l’élection de certaines routes en fonction de la bande passante.
• Le coût d’un lien se calcule par coût = référence / bande passante du lien, avec une référence par défaut de 100 000 000 pour un réseau de 100 Mbps.
• Le coût d’une route s’obtient en additionnant les coûts de chaque lien traversé.
• Contrairement à RIP qui ne privilégie que le nombre de sauts, OSPF peut choisir une route différente quand les liens rapides et lents modifient le coût global.
• OSPF est décrit comme robuste et adapté aux grands réseaux, mais il peut consommer plus de calcul et de mémoire que RIP en cas de nombreuses routes ou de changements fréquents.

💡 Astuce mémo

Coût OSPF = 100 000 000 ÷ bande passante : lien rapide → coût faible → meilleure route.

📖 4. SQL relationnel

🔑 Notions clés & Définitions

• SQL : SQL est un langage de requêtes utilisé pour créer, modifier et interroger des données stockées dans des bases de données relationnelles.
• Types de données SQL : Les types INT, FLOAT, DATE, BOOL et pour les chaînes TEXT ou VARCHAR(M) précisent le format des valeurs dans les colonnes.
• Cláuse WHERE : La clause WHERE sélectionne les lignes d’une table en ne gardant que celles dont les colonnes vérifient des critères.
• Jointure interne : La jointure interne combine deux tables en ne gardant que les paires de lignes dont la correspondance donnée par ON est vraie.
• Fonctions d’agrégation : Les fonctions d’agrégation transforment plusieurs lignes en une seule valeur à partir d’un ensemble de valeurs d’une colonne.

📝 Points essentiels

• AUTO_INCREMENT incrémente automatiquement une clé primaire numérique de 1 à chaque ajout d’enregistrement (départ à 1 par défaut).
• Les opérateurs logiques de WHERE sont AND, OR et NOT, et IS NULL / IS NOT NULL testent respectivement l’absence et la présence de valeur.
• A BETWEEN B AND C renvoie TRUE quand A est compris entre B et C, et A IN (B1,...,Bn) renvoie TRUE si A est dans la liste.
• A LIKE expr utilise des jokers : %a (finit par a), a% (commence par a), %a% (contient a), a%b (commence par a et finit par b).
• SELECT DISTINCT supprime les doublons dans le résultat, et ORDER BY tri dans l’ordre croissant sauf si on ajoute DESC pour un ordre décroissant.
• COUNT(nomColonne) ne compte pas les valeurs vides quand nomColonne est spécifié, et COUNT(DISTINCT nomColonne) évite aussi le comptage de doublons.

💡 Astuce mémo

LIKE : % = “trou” au début et/ou à la fin (commence/contient/termine).

📖 5. Clauses et requêtes SQL

🔑 Notions clés & Définitions

• Clause ORDER BY : La clause ORDER BY trie les lignes selon une ou plusieurs colonnes, avec un ordre précisé comme ASC ou DESC.
• COUNT en comptage : La fonction COUNT renvoie un nombre d’enregistrements en fonction du paramètre choisi, généralement avec des règles de prise en compte des valeurs vides.
• COUNT DISTINCT : COUNT avec DISTINCT compte uniquement les valeurs distinctes, en ne comptant pas les valeurs vides pour la colonne concernée.

📝 Points essentiels

• Une requête peut combiner SELECT, WHERE (optionnel) et ORDER BY (optionnel) pour filtrer puis trier les résultats.
• COUNT(*) compte les enregistrements d’une table, tandis que COUNT(nomColonne) ne compte que les valeurs non vides de cette colonne.
• COUNT(DISTINCT nomColonne) compte les valeurs distinctes non vides de la colonne, ce qui évite de compter plusieurs fois un même doublon.
• Pour une jointure interne, INNER JOIN relie table1 et table2 via ON, puis WHERE et ORDER BY sont traités comme d’habitude.
• Si JOIN est utilisé seul, il est équivalent à INNER JOIN pour la jointure interne.
• Une syntaxe SQL ancienne accepte FROM table1, table2 puis un WHERE qui définit le lien entre les deux tables, mais elle est déconseillée.

💡 Astuce mémo

COUNT : * = lignes, colonne = non vides, DISTINCT = distincts non vides.

📖 6. Fonctions d'agrégation SQL

📖 7. Graphes et représentations

🔑 Notions clés & Définitions

• Graphe connexe : Un graphe est connexe lorsqu’il existe au moins une chaîne entre deux sommets quelconques.
• Chaîne entre sommets : Une chaîne est un chemin reliant deux sommets d’un graphe, utilisé pour établir la connexité.
• Arbre binaire : Un arbre binaire est une structure récursive pouvant être vide ou formée d’une racine avec un fils gauche et un fils droit qui sont aussi des arbres binaires.
• Parcours en largeur : Un parcours en largeur visite les nœuds niveau par niveau, de la racine vers le bas, en stockant les nœuds à traiter.
• Parcours en profondeur : Un parcours en profondeur explore l’arbre en descendant le plus possible puis en remontant lorsque les feuilles sont traitées.

📝 Points essentiels

• Dans un arbre binaire, chaque nœud a au plus deux fils, et si un nœud n’a qu’un seul fils, gauche ou droite change la structure.
• Un arbre binaire dégénéré (filiforme) a chaque nœud avec au plus un fils et, pour une hauteur h, contient h+1 nœuds.
• Un arbre binaire complet a chaque nœud intérieur avec exactement deux fils et, pour une hauteur h, contient 2^h+1−1 nœuds.
• Pour tout arbre binaire de hauteur h et de taille t, on a ⌊log2 t⌋ ≤ h ≤ t−1.
• Un parcours en largeur utilise une file et visite tous les n nœuds en complexité O(n).
• Un parcours en profondeur (souvent récursif) visite tous les n nœuds en complexité O(n) et admet trois ordres : préfixé, infixé, postfixé.

💡 Astuce mémo

Dégénéré : h+1 nœuds ; complet : 2^h+1−1 nœuds ; et la hauteur vérifie ⌊log2 t⌋ ≤ h ≤ t−1.

📖 8. Chemins, chaînes et connexité

🔑 Notions clés & Définitions

• Chaîne père-fils : Une chaîne père-fils est une suite de nœuds reliés par la relation parent vers enfant dans un arbre.
• Ordre préfixe : L’ordre préfixe est un type de traitement d’arbre où le nœud courant est traité avant ses descendants.
• Ordre infixe : L’ordre infixe est un type de traitement d’arbre où le nœud courant est traité entre les descendants gauche et droit.
• Ordre postfixe : L’ordre postfixe est un type de traitement d’arbre où le nœud courant est traité après ses descendants.

📝 Points essentiels

• Le parcours en profondeur explore un nœud en allant vers ses feuilles, puis en remontant au plus haut nœud dont des feuilles n’ont pas encore été visitées.
• Le parcours en profondeur choisit systématiquement le fils gauche (et ses descendants) avant le fils droit (et ses descendants) quand on le fait « à main gauche ».
• Le traitement préfixe traite le nœud avant la branche gauche puis la branche droite.
• Le traitement infixe traite la branche gauche, puis le nœud, puis la branche droite.
• Le traitement postfixe traite la branche gauche, puis la branche droite, puis le nœud.
• Le parcours en profondeur a une complexité O(n) avec n le nombre de nœuds de l’arbre et on peut remplacer la récursivité par une pile pour éviter la récursivité.

💡 Astuce mémo

Préfixe = Avant, Infixe = Entre, Postfixe = Après (par rapport au nœud).

📖 9. Arbres binaires et parcours

📖 10. Processus et PCB

🔑 Notions clés & Définitions

• PCB : Le PCB est le bloc de contrôle du système qui mémorise le contexte d’un processus pour pouvoir le gérer et le reprendre.
• PPID : Le PPID est l’identifiant de processus parent qui, sous UNIX, vaut le PID du processus qui a créé le processus courant.
• Arbre de filiation des processus : L’arbre de filiation des processus est la structure reliant chaque processus à son parent, construite à chaque création de processus.
• État bloqué : L’état bloqué est l’état d’un processus dont l’exécution est momentanément suspendue en attendant sa reprise.

📝 Points essentiels

• La destruction d’un processus survient soit à la fin normale (routine d’arrêt comme exit), soit après une erreur irrécouvrable (trappe levée), soit sur demande d’un autre processus via une routine comme kill sous UNIX.
• Lors de la destruction, le système démantèle le contexte du processus : les ressources allouées sont libérées et le bloc de contrôle est détruit.
• La suspension d’exécution arrête temporairement un processus et sauvegarde son contexte dans le PCB pour reprendre exactement au même endroit.
• Pendant la suspension, le processus passe dans l’état bloqué, puis à la reprise il traverse la transition de déblocage et revient à l’état prêt.
• Sous Linux/UNIX, l’appel système sleep(duree) suspend l’exécution d’un processus pendant exactement duraee secondes.

📖 11. Ordonnancement des processus

🔑 Notions clés & Définitions

• Traitement par lots : Un traitement par lots est l’exécution automatique en enchaînant des commandes sur un ordinateur sans intervention humaine, souvent avec des temps d’exécution estimés.
• Premier Arrivé, Premier Servi : La politique FIFO choisit le prochain processus selon son ordre d’arrivée en file des prêts, sans réquisition, et il exécute jusqu’à terminer ou se bloquer.
• Plus Court d’Abord : La politique SJF choisit d’ordonnancer d’abord le processus dont le temps d’exécution estimé est le plus court, sans réquisition.
• Politique du tourniquet : La politique round robin découpe le temps en quantums et exécute un processus au plus durant un quantum avant de le préempter s’il n’a pas fini.
• Extinction de priorité : L’extinction de priorité diminue progressivement la priorité d’un processus en le faisant passer vers une file de priorité inférieure après son quantum.

📝 Points essentiels

• Dans un système en temps partagé, l’objectif est de maximiser l’occupation du processeur tout en réduisant le temps de réponse des processus.
• Dans un système temps réel, l’objectif est de respecter les contraintes temporelles imposées aux processus.
• Avec Premier Arrivé, Premier Servi, les processus de petite durée peuvent être pénalisés si de longs processus les précèdent en file prête.
• Avec Plus Court d’Abord, l’optimalité annoncée concerne le temps de réponse moyen minimal, mais elle suppose une connaissance a priori des durées d’exécution estimées.
• Dans la politique du tourniquet, la valeur du quantum peut varier de 10 à 100 ms et elle influence fortement le nombre de commutations de contexte.
• Dans l’exemple, si quantum = 10 ms et temps de commutation = 3 ms, l’attente due aux commutations représente 45 %, alors qu’elle tombe à 30 % pour quantum = 20 ms.

💡 Astuce mémo

FIFO pénalise les petits derrière les gros ; SJF est optimal mais exige l’estimation ; Round Robin équilibre par quantum ; priorité faible risque la famine ; l’extinction fait “descendre” la priorité.

📖 12. Ressources et interblocage

🔑 Notions clés & Définitions

• Ressource : Une ressource est une entité dont un processus a besoin pour s’exécuter et qui peut être libre ou occupée.
• Ressource critique : Une ressource critique ne peut pas être utilisée simultanément par plusieurs processus, donc elle est allouée à un seul à la fois.
• Interblocage : Un interblocage est une situation où des processus attendent indéfiniment la libération de ressources détenues par d’autres processus.
• Conditions de Coffman : Les conditions de Coffman regroupent quatre exigences qui doivent toutes être réunies pour qu’un interblocage apparaisse.

📝 Points essentiels

• L’utilisation d’une ressource suit trois étapes : demander l’accès, utiliser la ressource, puis la libérer pour permettre l’accès aux autres.
• Quand un processus demande un accès exclusif à une ressource déjà allouée, le système le met en attente ou lui renvoie un message lui demandant de réessayer plus tard.
• Un interblocage apparaît quand chaque processus d’un ensemble attend une ressource que l’un des autres détient, si bien que personne ne peut progresser.
• Un interblocage nécessite les quatre conditions de Coffman : exclusion mutuelle, détention et attente, pas de préemption, attente circulaire.
• Exemple fichier et disque : si A tient le fichier toto.txt et attend le disque C, pendant que B tient le disque C et attend toto.txt, les deux restent bloqués indéfiniment.
• Exemple base de données : A verrouille R1 puis demande R2, tandis que B verrouille R2 puis demande R1, ce qui forme une attente circulaire menant à l’interblocage.

💡 Astuce mémo

EDPA : Exclusion mutuelle, Détention et attente, Pas de préemption, Attente circulaire.

📊 Tableaux de synthèse

RIP vs OSPF

⚠️ Pièges & confusions fréquents

1. Confondre route sélectionnée : dans la table, on compare (IPCible AND masque) à IPReseauCible, et en cas de plusieurs lignes on prend la métrique la plus petite (chemin “le plus court”).
2. Croire que la route par défaut est “en priorité” : elle s’applique seulement si aucune autre route n’est sélectionnée (masque 0.0.0.0 ⇒ 0.0.0.0).
3. Penser que RIP privilégie la bande passante : il élit la route uniquement selon le nombre de sauts (hops), alors que l’idée de bande passante/liaison vient d’OSPF.
4. Se tromper dans la formule OSPF : coût = référence / bande passante, donc bande passante plus grande ⇒ coût plus faible ⇒ meilleure route.
5. Erreur sur COUNT en SQL : COUNT(nomColonne) ignore les valeurs vides, alors que COUNT(*) compte toutes les lignes.
6. LIKE mal interprété : %a signifie “se termine par a”, a% signifie “commence par a”, %a% “contient”, et a%b “commence par a et finit par b”.
7. Mélanger états/processus et opérations : un processus passe prêt→élu (élection), élu→bloqué (blocage), bloqué→prêt (déblocage), et ne se termine pas depuis l’état prêt (sauf anomalie).

✅ Checklist Examen

1. Expliquer ce que fait le routage et décrire les rôles de routeur et table de routage (destination, interface, passerelle, métrique, route par défaut).
2. Savoir le test de sélection d’une ligne : vérifier (IPcible AND masque) = IPReseauCible, parcourir les lignes et choisir la route correspondant au “meilleur” critère (métrique plus petite).
3. Donner les types de routes d’une table de routage (directement connectées, statiques, dynamiques, route par défaut) et dire ce qui se passe s’il n’y a pas de route par défaut.
4. Décrire RIP : tables initiales, envoi périodique toutes les 30 secondes aux voisins, métrique = nombre de sauts, appui sur Bellman-Ford, limite à 15 sauts, et raison de la rareté en grandes infrastructures.
5. Décrire OSPF : protocole ouvert, SPF (Dijkstra), coût de lien = référence / bande passante (référence 100 000 000 pour 100 Mbps), coût de route = somme des coûts, meilleure route selon coût.
6. En SQL, savoir utiliser WHERE avec opérateurs logiques (AND, OR, NOT, IS NULL, IS NOT NULL) et de comparaison (BETWEEN, IN, LIKE avec %).
7. Maîtriser SELECT : DISTINCT pour supprimer les doublons, ORDER BY avec ASC/DESC, et COUNT : COUNT(*) vs COUNT(nomColonne) vs COUNT(DISTINCT nomColonne) en ignorant les valeurs vides selon le cours.
8. Savoir écrire une jointure interne SQL : SELECT ... FROM table1 INNER JOIN table2 ON ... avec WHERE/ORDER BY optionnels, et connaître que JOIN seul = INNER JOIN et que la syntaxe ancienne est déconseillée.
9. Côté graphes, savoir donner la définition de graphe connexe via une chaîne entre deux sommets quelconques et distinguer graphe orienté vs non orienté (adjacence symétrique vs non).
10. Pour les arbres binaires, savoir les propriétés demandées : dégénéré = chaque nœud a au plus un fils (t = h+1), complet = chaque nœud intérieur a exactement deux fils (t = 2^h+1−1) et la borne ⌊log2 t⌋ ≤ h ≤ t−1, puis reconnaître les parcours (largeur niveau par niveau avec file, profondeur préfixé/infixé/postfixé).
11. Pour processus, savoir relier états et opérations (prêt/élu/bloqué, élection, blocage, déblocage, préemption) et décrire PCB (PID, états, contextes processeur et mémoire).
12. Pour ordonnancement et ressources, savoir comparer au moins FIFO/FCFS, SJF (sans réquisition), tourniquet (quantum préemption + fin de quantum réinsertion en fin de file), extinction de priorité, puis définir interblocage et rappeler les 4 conditions de Coffman (EDPA).