Fiche de révision : Introduction aux structures et requêtes en informatique

📋 Plan du Cours

1. Localiser le moteur Python et comprendre l'intérêt d'intercepter les erreurs
2. Conseils pour concevoir des tests en Python
3. Identifier et construire des requêtes SQL : SELECT, FROM, WHERE, JOIN, UPDATE, INSERT, DELETE
4. Principes de jointure en bases de données relationnelles
5. Création et manipulation d'une classe en Python (exemple : classe rectangle
6. Représentation et construction d'arbres binaires en Python
7. Différences entre piles (LIFO) et files (FIFO) et spécification des structures de données par
8. Analyse et manipulation de graphes : degrés, cycles, sommets et arêtes
9. Représentation matricielle d'un graphe et implémentation en Python
10. Algorithmes de parcours de graphes : file d'attente, DFS, et documentation de fonctions
11. Protocoles de routage : principes et limites de RIP
12. Protocoles de routage avancés : caractéristiques et avantages d'OSPF

📖 1. Localiser le moteur Python et comprendre l'intérêt d'intercepter les erreurs

🔑 Notions clés & Définitions

• Train : Objet de type Train dont les méthodes sont décrites dans le contenu, avec des opérations pour savoir s’il est vide, compter ses wagons, vérifier s’il transporte un contenu, ajouter un wagon ou supprimer le premier wagon portant un contenu donné.
• A NOTER : Repère de rappel qui signale des informations officielles ou pratiques, notamment que les informations officielles sur Python se trouvent sous www.python.org et qu’une ressource francophone est disponible sur www.afpy.org.

📝 Points essentiels

• Un module Python bien fait intègre sa propre documentation, accessible notamment avec help(module) dans la console Python.
• La commande python -m pydoc -p 1234 lance un mini-serveur web pour consulter l’aide.
• La documentation du module math affiche la liste de toutes les fonctions disponibles avec une courte explication.
• La documentation web permet de consulter le module random et de l’exploiter pour écrire un petit script qui simule le tirage du loto.
• La documentation d’un module peut être lue dans des pages web après lancement du mini-serveur pydoc.
• Il faut aller la chercher dans le module math.

💡 À retenir

L’aide officielle d’un module peut être consultée immédiatement dans la console Python avec help(), ou via un mini-serveur web lancé par python -m pydoc -p 1234. Le contenu insiste aussi sur le fait qu’un module bien conçu fournit sa propre documentation.

📖 2. Conseils pour concevoir des tests en Python

🔑 Notions clés & Définitions

• Exemple : 4 + 5 * 3 est une expression algébrique.
• Path : 9) 3 A faire vous même 2. S’il est bien fait, un module python intègre sa propre documentation.
• Dans la console python testez ces lignes : import math help(math)
• Vous avez la liste de toutes les fonctions disponibles dans ce module avec une courte explication
• Cherchez comment récupérer une valeur approchée du nombre réel pi
• Testez la fonction sinus
• Testez une autre fonction de votre choix A faire vous même 3. L’aide peut être récupérée et lue via des pages web. Dans un shell linux tapez : $ python -m pydoc -p 1234 Vous venez de lancer un mini-serveur web
• Consultez la documentation et testez le module random
• Écrivez un petit script qui simule le tirage du loto A faire vous même 4.
• Pour le plus rapides et/ou les plus motivés, voici une liste de modules intéressants : ◦ time, datetime, calendar : gestion de l’heure et de la date ◦ sys : adaptation de Python au système hôte. Un peu « fourre tout » ◦ os : se substitue à certaines commandes linux ◦ os.path : manipulation de chemin de fichiers ◦ stat : informations sur les fichiers (sécurité, dates, UID, ...) ◦ tempfile : fichiers et répertoires temporaires ◦ glob, fnmatch : recherche et correspondance des fichiers avec patterns Unix (« *.py? », ...) ◦ shutil, filecmp : déplacement, copie, comparaison de fichiers et répertoires A faire vous même 5.
• Explorez plus en détail le module : os.path : manipulation de chemin
• Bouche bornée :
  • Complétez la fonction factorielClassique en utilisant une bouche bornée : def factorielClassique(n) : """ >>> factorielClassique( P) ?

📝 Points essentiels

• Les jeux de tests servent à valider le comportement attendu d’une fonction.
• La docstring peut contenir un exemple de test exécutable.
• Les tests doivent être vérifiés dans la console Python.
• La fonction factorielClassique doit être complétée avec une bouche bornée.

💡 À retenir

La docstring peut contenir un exemple de test exécutable.

📖 3. Identifier et construire des requêtes SQL : SELECT, FROM, WHERE, JOIN, UPDATE, INSERT, DELETE

🔑 Notions clés & Définitions

• Saisissez et testez la requête SQL suivante : Consigne d’exercice consistant à écrire puis exécuter la requête SQL proposée.
• WHERE : Clause SQL utilisée pour ajouter une condition de filtrage sur les lignes.

📝 Points essentiels

• SELECT sert à sélectionner les attributs qui devront être affichés.
• FROM indique la table qui doit être utilisée comme table source de la requête.
• WHERE ajoute une condition de filtrage sur les lignes.
• UPDATE modifie des valeurs existantes dans une table.
• On est donc souvent amené à regrouper des données dans une nouvelle table.

💡 À retenir

Les requêtes SQL de base servent à choisir des colonnes, utiliser une table source, filtrer des lignes et relier plusieurs tables. Les commandes UPDATE, INSERT et DELETE permettent ensuite de modifier ou gérer les données dans une table.

📖 4. Principes de jointure en bases de données relationnelles

🔑 Notions clés & Définitions

• Clé primaire : Attribut qui identifie de façon unique une ligne dans une table.
• Un attribut : Couple formé d’un nom et d’un domaine, où le nom représente un titre de colonne et prend ses valeurs dans ce domaine.
• Clé étrangère : grâce à cette précision, sqlite sera capable de détecter les anomalies au niveau de clé étrangère : essayez par exemple d'ajouter un livre à la table LIVRES avec l'attribut id_auteur égal à 11 !

📝 Points essentiels

• La jointure est introduite pour relier deux tables à partir d’un lien entre elles, souvent une clé étrangère et une clé primaire.
• La table LIVRES peut être déclarée avec FOREIGN KEY (id_auteur) REFERENCES AUTEURS(id) pour que sqlite détecte les anomalies de clé étrangère.
• • clé étrangère: C’ est un attribut qui correspond à une clé primaire d’ une autre table/relation • contrainte d’ intégrité : C’ est une règle qui définit la cohérence d’ une donnée ou d’ un ensemble de données d’ une base de données A faire vous même 6.
• Cet attribut x est appelé clef étrangère (l' attribut correspond à la clé primaire d'une autre table, d'où le nom).

💡 À retenir

La jointure est introduite pour relier deux tables à partir d’un lien entre elles, souvent une clé étrangère et une clé primaire.

📖 5. Création et manipulation d'une classe en Python (exemple : classe rectangle

🔑 Notions clés & Définitions

• Exemple : Def maFonction(a, b): """ Rôle : calcule a/b Paramètres : a le dividende b le diviseur non nul Retourne : le quotient a/b """ return(a/b) Il est enfin recommandé de pratiquer la programmation défensive que nous verrons plus loin dans ce cours.

📝 Points essentiels

• Une classe regroupe des données et des comportements pour décrire des objets.
• Les méthodes définissent les actions possibles sur l’objet, comme démarrer ou rouler.
• Objectifs 1. Spécifier une structure de données par son interface 2. Écrire la définition d’une classe 3. Accéder aux attributs et méthodes d’une classe Cette séquence s’appuie sur :
  • https://www.lecluse.fr/nsi/NSI_T/langages/paradigmes/
  • https://pixees.fr/informatiquelycee/n_site/nsi_term_paraProg_poo.html
  • https://isn-icn-ljm.pagesperso-orange.fr/NSI-TLE/res/res_les_classes.pdf
  • https://e-nsi.gitlab.io/pratique/N2/700-poo_train/sujet/ 1 Introduction La programmation orientée objet repose, comme son nom l'indique, sur le concept d'objet. Un objet dans la vie de tous les jours vous connaissez, mais en informatique, c'est un nouveau concept. Imaginez un objet, par exemple un moteur de voiture : il est évident qu'en regardant cet objet, on est frappé par sa complexité. Imaginez que l'on enferme cet objet dans une caisse et que l'utilisateur n'ait pas besoin d'en connaître son principe de fonctionnement interne pour pouvoir l'utiliser. L'utilisateur a, à sa disposition, des boutons, des manettes et des écrans de contrôle pour faire fonctionner l'objet, ce qui rend son utilisation relativement simple. La mise au point de l'objet (par des ingénieurs) a été très complexe, en revanche son utilisation est relativement simple. Programmer de manière orientée objet, c'est un peu reprendre cette idée : utiliser des objets sans se soucier de leur complexité interne. Un des nombreux
• 3 Les attributs de classe Un objet a une apparence, des caractéristiques qui lui sont propres : rouge, bleu, en plastique, 15 cm de hauteur, … Ces caractéristiques sont des attributs.

💡 À retenir

Une classe regroupe des données et des comportements pour décrire des objets.

📖 6. Représentation et construction d'arbres binaires en Python

🔑 Notions clés & Définitions

• Un arbre binaire est :

  • soit l’arbre vide, noté Δ ;

📝 Points essentiels

• La racine est le nœud de départ de l’arbre.
• Chaque nœud peut avoir un fils gauche et un fils droit.
• L’arbre vide n’est pas localement complet.

💡 À retenir

Un arbre binaire est une structure hiérarchique de données organisée autour d’une racine. Il se reconnaît par ses fils gauche et droit, et sa complétude locale exige que chaque nœud interne ait exactement deux fils, ce qui exclut l’arbre vide.

📖 7. Différences entre piles (LIFO) et files (FIFO) et spécification des structures de données par

🔑 Notions clés & Définitions

• Ajout : valeur décimale. On lit un à un les caractères de l’expression postfixée 1 … 2 … + … 4 … * … 5 … + pour l’évaluer.

• Les opérateurs sont les éléments + et *.

• Les opérandes sont les éléments 1, 2, 4 et 5.

• Le premier opérateur + permet de dépiler les deux opérandes 1 et 2, et d’empiler le résultat de l’opération 1 + 2. A faire vous même 4. Une calculatrice virtuelle en NPI Installez le paquet : grpn Lancez ce programme et effectuez les deux calculs suivants :

• 3+4

• ((1+2)×3)4 A faire vous même 5.

• P. 108 ex 11 4 Les files (ou queue) Comme les piles, les files ont des points communs avec les listes. Différences majeures : dans une file on ajoute des éléments à une extrémité de la file et on supprime des éléments à l'autre extrémité. On prend souvent l'analogie de la file d'attente devant un magasin pour décrire une file de données. Les files sont basées sur le principe FIFO (First In First Out : le premier qui est rentré sera le premier à sortir. Ici aussi, on retrouve souvent ce principe FIFO en informatique. Voici les opérations que l'on peut réaliser sur une file, on peut :

• Savoir si une file est vide (file_vide)

• Ajouter un nouvel élément à la file (ajout)

• Récupérer l'élément situé en bout de file tout en le supprimant (retire)

• Accéder à l'élément situé en bout de file sans le supprimer de la file (premier)

• Connaître le nombre d'éléments présents dans la file

📝 Points essentiels

• Le sommet désigne l’extrémité d’accès d’une pile.
• La tête désigne l’extrémité de sortie d’une file.
• La spécification d’une structure de données décrit ses opérations d’accès et de modification.
• Files 3. Choisir une structure de données adaptée à la situation à modéliser. 4. Distinguer la recherche d’une valeur dans une liste et dans un dictionnaire. 5. Spécifier une structure de données par son interface. 6. Distinguer interface et implémentation. 7. Écrire plusieurs implémentations d’une même structure de données. Cette séquence s’appuie sur :
  • https://pixees.fr/informatiquelycee/n_site/nsi_term_structDo_liste.html
  • https://www.maxicours.com/se/cours/utiliser-une-pile-pour-evaluer-une-notation-en-polonais-inverse/ 1 Types abstraits De nombreux algorithmes "classiques" manipulent des structures de données plus complexes que des simples nombres. Indépendamment de tous langages de programmation, chaque type abstrait de structure de données est défini par son interface. L’ interface décrit de quelle manière on peut manipuler ces données (création, destruction, modification, …). C’ est une approche théorique. L’implémentation, c’est-à-dire la transposition dans tel ou tel langage de programmation, ne doit pas être pris en compte. Cela est fait après dans une approche pratique. Nous allons ici voir quelques-unes de ces structures de données : les listes, les piles et les files. Ces trois types abstraits de structures sont qualifiés de linéaires. Lire livre P. 94 2 Les listes Une liste est une structure de données permettant de regrouper des données. Une liste L est
• Une liste L est piles, il est uniquement possible de manipuler le dernier élément introduit dans la pile.

💡 À retenir

Une pile et une file organisent l’accès aux éléments selon deux ordres opposés : LIFO pour la pile et FIFO pour la file. La spécification d’une structure de données se fait par ses opérations d’accès et de modification.

📖 8. Analyse et manipulation de graphes : degrés, cycles, sommets et arêtes

🔑 Notions clés & Définitions

• Graphe : Structure composée de sommets reliés par des arêtes.

📝 Points essentiels

• La somme des degrés des sommets est paire.
• F). Aucun sommet n’est isolé. Ce graphe n’est pas complet. Sommet (ici, ami) sommets adjacents (ici, … est amis avec…) Degré du sommet A B, C et D 3 B A et D 2 C A, E et D 3 D A, B, C, E et F 5 E C, D et F 3 F E et D 2 Les sommets B et F ne sont pas adjacents. 3 Différents types de graphes Un graphe peut être orienté ou non-orienté :
  • Dans un graphe non-orienté, chaque arête peut-être parcourue dans les deux sens .
  • Dans un graphe orienté, chaque arête ne peut-être parcourue que dans un seul sens indiqué par une flèche. Un graphe (orienté ou non-orienté) peut contenir des boucles c'est-à-dire une arête dont l'origine et l'extrémité correspondent au même sommet (on a par exemple une boucle B sur la représentation ci-dessous). Propriété : Le nombre d'arêtes est égal à la moitié de la somme des degrés des sommets Ce résultat s'explique assez facilement: en ajoutant les degrés de chaque sommet (c'est à dire le nombre d'arêtes issues de ce sommet), on comptabilise deux fois chaque arête (une fois avec le sommet d'une extrémité et une seconde fois avec le sommet de l'autre extrémité de l'arête). Une boucle est donc comptabilisée deux fois (exemple1 : dans un sens R-T-V-S-U-R et l’autre sens R-U-S-V-T-R, soit 5 arêtes et une somme des degrés égale à

💡 À retenir

Un graphe se lit comme un ensemble de sommets reliés par des arêtes, ce qui permet d’en déduire ses propriétés structurelles. Les notions de degré, de chaîne et de cycle servent à analyser cette structure.

📖 9. Représentation matricielle d'un graphe et implémentation en Python

🔑 Notions clés & Définitions

• Matrice : Symétrique suivant une diagonale.

📝 Points essentiels

• Les cases d’un labyrinthe sont numérotées pour construire la représentation.
• Deux cases sont voisines si elles ont un côté commun.
• La représentation choisie influence le coût d’accès aux informations du graphe.
• Pour les rapides (bfs1.py) Au chapitre précédent, vous avez vu que tout graphe est caractérisé par sa matrice d'adjacence composée de 1 et de 0 selon que deux sommets sont ou ne sont pas reliés par une arête et qu’une façon d'encoder un graphe sous Python est d'utiliser un dictionnaire qui est la représentation de sa matrice d'adjacence.
• Cela dépend :
  • de la structure du graphe : Plus un graphe est "dense", c'est-à-dire plus il y a d'arêtes pour un nombre donnés de sommets, plus le choix de la matrice d'adjacence est pertinente.

💡 À retenir

Les cases d’un labyrinthe sont numérotées pour construire la représentation.

📖 10. Algorithmes de parcours de graphes : file d'attente, DFS, et documentation de fonctions

🔑 Notions clés & Définitions

• chemin : suite de sommets reliant un sommet à un autre dans un graphe.
• DIVISER : première étape du paradigme « diviser pour régner » ; le problème d’origine est séparé en un certain nombre de sous-problèmes.
• Rappel : structure de données de type file, organisée selon le principe du premier entré, premier sorti, comme une file d’attente à un guichet.
• sommets_fermés : sommets déjà traités dans un parcours, marqués pour éviter de les explorer de nouveau.
• file d'attente : structure FIFO dans laquelle les nouveaux éléments se placent à la fin et où l’élément servi est celui qui est arrivé en premier.

📝 Points essentiels

• Le parcours en largeur utilise une file d’attente, c’est-à-dire une structure FIFO qui permet de traiter en premier les sommets découverts en premier.
• Le parcours en largeur visite les sommets niveau par niveau : il commence par les sommets à distance 1 du sommet de départ, puis ceux à distance 2, puis ceux à distance 3, et ainsi de suite.
• Le parcours en profondeur repose sur une exploration récursive ou équivalente, et il s’écrit naturellement de manière récursive.
• Le parcours en profondeur explore une branche complètement avant de passer à la suivante, donc il va d’abord le plus profond possible.
• La fonction de parcours doit être documentée par une docstring claire, afin d’indiquer précisément son rôle.

💡 À retenir

Comparer ces deux stratégies revient à opposer une visite par niveaux, fondée sur une file d’attente, à une visite en profondeur, fondée sur une exploration récursive. Leur implémentation doit rester lisible et clairement documentée pour expliciter le rôle de la fonction de parcours.

📖 11. Protocoles de routage : principes et limites de RIP

🔑 Notions clés & Définitions

• Métrique : grandeur utilisée pour définir la distance entre une source et une destination dans RIP ; ici, elle est simplement le nombre de sauts.

• Rôle : fonctionnement totalement réparti dans lequel aucun routeur n’a de rôle prépondérant dans le système autonome, à part le fait que certains puissent être en liaison avec l’extérieur.

• Soit le réseau suivant : réseau d’exemple servant à illustrer le calcul des chemins et l’enrichissement progressif des tables de routage par échanges entre routeurs voisins.

• table de routage : tableau qui contient toutes les destinations possibles et les instructions pour les rejoindre ; il indique, pour chaque réseau destination, l’adresse du réseau et son masque, la sortie du routeur de départ, la passerelle ou gateway, ainsi que le nombre de sauts.

• nombre de sauts : nombre d’étapes franchies par un paquet pour atteindre une destination ; dans RIP, chaque routeur qui reçoit une route ajoute 1 à la métrique pour tenir compte du saut supplémentaire vers lui.

📝 Points essentiels

• RIP s’appuie sur le nombre de sauts pour choisir un chemin : la route retenue est celle dont la métrique est la plus basse.
• La table de routage indique destination, passerelle, interface et nombre de sauts : elle doit être actualisée et précise pour permettre l’acheminement correct des paquets.
• Chaque échange de routage ajoute un saut aux routes apprises : lorsqu’un routeur reçoit une nouvelle route d’un voisin, il ajoute 1 à la métrique avant de l’intégrer ou de la comparer.
• RIP devient vite long à détailler quand les tables s’enrichissent : les tables évoluent au gré des échanges et leur contenu devient rapidement trop long à énumérer en détail.
• RIP montre ses limites quand le réseau et les échanges se multiplient : il ne permet pas de gérer des systèmes autonomes avec des routeurs situés à plus de 15 sauts l’un de l’autre, et il met du temps à se mettre en place car la connaissance des nouvelles routes progresse de proche en proche, un nouveau saut toutes les 30 s.

💡 À retenir

RIP est un protocole simple de routage par propagation de tables : chaque routeur apprend les routes de ses voisins, ajoute un saut, puis conserve la meilleure passerelle selon la métrique. Cette simplicité le rend facile à comprendre, mais elle montre vite ses limites dès que le réseau grandit ou que les échanges se multiplient.

📖 12. Protocoles de routage avancés : caractéristiques et avantages d'OSPF

🔑 Notions clés & Définitions

• Graph : Représentation du réseau sous forme de sommets et de liens, utilisée pour appliquer visuellement l’algorithme de Djikstra et chercher le plus court chemin.
• Taille : Caractéristique d’un réseau que le système de zones d’OSPF permet de découper en zones semi-autonomes reliées à une zone centrale appelée Backbone, ce qui permet d’atteindre des systèmes avec plus de 1000 routeurs.

📝 Points essentiels

• OSPF vise à calculer des chemins plus efficaces que les approches par nombre de sauts en s’appuyant sur le débit des liaisons.
• OSPF est présenté comme plus adapté aux réseaux complexes et permet, grâce au système de zones et au Backbone, d’atteindre des systèmes avec plus de 1000 routeurs.
• Soit le réseau suivant : En vous basant sur le protocole OSPF (métrique: somme des coûts), déterminez la table de routage du routeur A On donne les débits suivants :
  • liaison routeur A - routeur B : 1 Mbps
  • liaison routeur A - routeur C : 10 Mbps
  • liaison routeur C - routeur B : 10 Mbps RA RB RC Quel est, d'après la table de routage construite ci-dessus, le chemin qui sera emprunté par un paquet pour aller d'une machine ayant pour adresse IP 172.18.1.1/16 à une machine ayant pour adresse IP 172.16.5.3/16 ?

💡 À retenir

OSPF vise à calculer des chemins plus efficaces que les approches par nombre de sauts en s’appuyant sur le débit des liaisons.

🧩 Compléments de couverture

1. La requête SQL peut sélectionner seulement certaines lignes et certaines colonnes grâce à une notation dédiée.
2. Dans une jointure, la ligne A et la ligne B sont associées lorsque l’attribut id_auteur de A vaut 1 et que l’attribut id de B vaut 1.
3. La jointure INNER JOIN peut être écrite en sélectionnant explicitement seulement certains attributs comme nom, prenom et titre.
4. Quand un même nom d’attribut existe dans deux tables, il faut préfixer le nom de la table pour les distinguer.
5. La fonction récursive de parcours de graphe utilise une file d’attente et marque les sommets déjà traités avec un tableau de drapeaux initialisé à -1.
6. Dans le parcours en largeur, un sommet déjà découvert mais pas encore traité est repéré par la valeur -1 dans le tableau drapeaux.
7. La représentation d’un labyrinthe par dictionnaire d’adjacence repose sur le numérotage préalable des cases.
8. Un graphe peut contenir une chaîne fermée sans être un cycle si une arête y est parcourue deux fois.
9. Un graphe connexe est défini par le fait que deux sommets quelconques sont toujours reliés par une chaîne.
10. Dans un arbre binaire de recherche, le parcours infixe donne les valeurs dans l’ordre croissant.
11. Les bases de données relationnelles ont été mises au point en 1970 par Edgar Franck Codd, informaticien britannique (1923-2003).
12. 7 Labyrinthe représenté à l'aide d'un graphe Le but des questions suivantes est de compléter le programme https://ninoo.
13. 2 Les bases du routage Voir vidéo : https://www.
14. 270 ex 5 5 CONCLUSION : Voir vidéo : https://www.
15. Avec ce kit, reproduisez les instructions du A faire vous-même 1 ACTIVITE AUTOUR DU JEU LES TOURS DE HANOI : http://championmath.
16. 0 Calculatrice réseau en ligne : https://www.
17. 2 Routage dynamique Voir vidéo : https://www.
18. 1 Un protocole à vecteurs de distance : RIP Voir vidéo : https://www.

📅 Repères chronologiques

📊 Tableaux de Synthèse

SQL de base

Structures de données et parcours

⚠️ Pièges & Confusions Fréquentes

1. Confondre SELECT avec FROM : SELECT choisit les attributs, FROM désigne la table source.
2. Confondre clé primaire et clé étrangère : la clé primaire identifie une ligne, la clé étrangère renvoie à la clé primaire d’une autre table.
3. Oublier qu’une file est FIFO alors qu’une pile est LIFO.
4. Confondre sommet, arête et degré dans un graphe.
5. Prendre la matrice d’adjacence pour une liste d’adjacence : ici la représentation est matricielle ou via dictionnaire d’adjacence.
6. Croire qu’un arbre binaire peut avoir un nœud interne avec un seul fils : le contenu insiste sur fils gauche et fils droit.
7. Confondre parcours en largeur et DFS : le parcours en largeur utilise une file d’attente.

✅ Checklist Examen

1. Savoir lancer l’aide d’un module avec help(module).
2. Savoir lancer python -m pydoc -p 1234 pour consulter la documentation web.
3. Retenir qu’un module bien conçu intègre sa propre documentation.
4. Identifier le rôle de SELECT, FROM et WHERE dans une requête SQL.
5. Connaître le rôle de UPDATE, INSERT et DELETE pour modifier ou gérer les données.
6. Expliquer le lien entre clé primaire, clé étrangère et jointure.
7. Décrire une classe rectangle comme exemple de création et manipulation de classe en Python.
8. Définir un arbre binaire par sa racine et ses fils gauche et droit.
9. Distinguer pile LIFO et file FIFO.
10. Relier un graphe à ses sommets, arêtes, degrés et cycles.
11. Expliquer la représentation matricielle d’un graphe et le rôle du numérotage des cases.
12. Associer le parcours en largeur à une file d’attente et à la notion de sommets déjà traités.