Revision sheet: Introduction aux Structures et Algorithmes Essentiels

📋 Plan du Cours

1. Programmation orientée objet
2. Structures de données (listes, piles, files, dictionnaires)
3. Arbres binaires
4. Graphes et parcours
5. SQL et requêtes
6. Routage et protocoles
7. Systèmes sur puce et processus
8. Tri par insertion et sélection
9. Congruences et algorithmes d’Euclide

📖 1. Programmation orientée objet

🔑 Notions clés & Définitions

Interface
AUTEUR (date) : Définit les fonctionnalités d’une classe ou d’un module, sans implémentation spécifique. Elle sert de contrat pour garantir que certaines méthodes seront présentes dans une classe.

Implémentation
AUTEUR (date) : La réalisation concrète des fonctionnalités définies par une interface. Elle consiste à coder les méthodes qui respectent le contrat établi par l’interface.

Encapsulation
AUTEUR (date) : Principe de protection des données internes d’une classe en utilisant des attributs privés et des méthodes publiques pour y accéder. Elle limite l’accès direct aux données pour préserver leur intégrité.

Héritage
AUTEUR (date) : Permet à une classe de réutiliser et d’étendre les fonctionnalités d’une autre classe, facilitant la réutilisation du code et la spécialisation des objets.

Polymorphisme
AUTEUR (date) : Capacité à utiliser une interface unique pour différents types d’objets, par exemple via des méthodes redéfinies, permettant une flexibilité dans le traitement des objets.

📝 Points essentiels

Une classe définit un type d'objet en regroupant attributs et méthodes encapsulés.
L’encapsulation protège les données internes en utilisant des attributs privés et en fournissant des méthodes publiques pour y accéder, ce qui limite les risques de modification accidentelle ou non contrôlée.
L’héritage permet de créer des classes dérivées qui réutilisent et étendent les fonctionnalités d’une classe de base, favorisant la modularité et la réutilisation du code.
Le polymorphisme offre la possibilité d’utiliser une même interface pour différents types d’objets, notamment en redéfinissant des méthodes dans des classes dérivées, ce qui facilite la gestion de comportements variés via une interface commune.

💡 À retenir

La programmation orientée objet structure le code en combinant données et comportements, ce qui améliore la modularité et la réutilisabilité grâce à l’encapsulation, l’héritage et le polymorphisme.

📖 2. Structures de données (listes, piles, files, dictionnaires)

🔑 Notions clés & Définitions

Pile (LIFO) : Structure de données où le dernier élément inséré est le premier à être retiré. Elle suit le principe "dernier entré, premier sorti" (Last In, First Out). La pile est souvent représentée par une liste où l’on ajoute ou retire des éléments à la fin.

File (FIFO) : Structure de données où le premier élément inséré est le premier à être retiré. Elle respecte le principe "premier entré, premier sorti" (First In, First Out). La file peut être implémentée avec une liste où l’on ajoute à la fin et retire au début.

Liste : Structure linéaire dynamique permettant d’accéder, d’insérer ou de supprimer des éléments à n’importe quelle position. Elle est flexible et adaptée à divers usages.

Dictionnaire : Structure de données qui stocke des paires clé-valeur. Elle permet un accès rapide aux éléments via leurs clés, avec une complexité moyenne en temps constant O(1).

📝 Points essentiels

• La pile suit le principe dernier entré, premier sorti (LIFO). Par exemple, on ajoute des éléments avec append() et on retire avec pop() en fin de liste.
• La file suit le principe premier entré, premier sorti (FIFO). On ajoute avec append() à la fin et retire avec pop(0) au début.
• La liste est une structure linéaire dynamique permettant l’accès, l’insertion et la suppression à n’importe quelle position, ce qui la rend très flexible.
• Le dictionnaire stocke des paires clé-valeur. Son accès moyen en temps constant O(1) permet une recherche, une insertion ou une suppression rapides via la clé.

💡 À retenir

Maîtriser ces structures fondamentales permet d’organiser et d’accéder efficacement aux données selon les besoins d’ordre (LIFO, FIFO) ou de rapidité d’accès (dictionnaire).

📖 3. Arbres binaires

🔑 Notions clés & Définitions

Arbre binaire : Structure hiérarchique dans laquelle chaque nœud peut avoir au plus deux enfants, appelés généralement gauche et droit. Aucune définition spécifique d'auteur ou de date n'est fournie dans le contenu source.

Arbre binaire de recherche (ABR) : Type particulier d’arbre binaire où, pour chaque nœud, les valeurs du sous-arbre gauche sont inférieures à la valeur du nœud, et celles du sous-arbre droit sont supérieures. Aucune référence externe n’est mentionnée.

Racine : Nœud de départ de l’arbre, qui n’a pas de parent. Aucune définition supplémentaire n’est fournie.

Feuille : Nœud sans enfant. Aucune définition supplémentaire n’est fournie.

Hauteur : Nombre d’arêtes du chemin le plus long allant de la racine à une feuille. Aucune référence ou auteur n’est mentionné.

Profondeur : Nombre d’arêtes du nœud racine jusqu’à un nœud donné. Aucune référence ou auteur n’est mentionné.

📝 Points essentiels

• Un arbre binaire a au plus deux enfants par nœud.
• Dans un ABR, les valeurs du sous-arbre gauche sont inférieures à celles du nœud, celles du sous-arbre droit sont supérieures.
• La taille de l’arbre correspond au nombre total de nœuds.
• La hauteur d’un arbre est le nombre d’arêtes du chemin le plus long de la racine à une feuille.
• La profondeur d’un nœud est le nombre d’arêtes entre la racine et ce nœud.
• Les parcours principaux sont : préfixe (racine, gauche, droit), infixe (gauche, racine, droit), suffixe (gauche, droit, racine), et largeur d’abord (niveau par niveau).

💡 À retenir

Les arbres binaires, notamment les arbres de recherche, sont des structures hiérarchiques permettant un accès organisé et efficace aux données, avec des parcours variés pour explorer leur contenu. Leur hauteur et leur taille influencent directement la performance des opérations de recherche et d’insertion.

📖 4. Graphes et parcours

🔑 Notions clés & Définitions

Sommet : Un point dans le graphe, aussi appelé nœud. Il représente une entité ou un élément du réseau.
Arête orientée : Une connexion entre deux sommets avec une direction spécifique, indiquée par une flèche. Elle va d’un sommet source vers un sommet cible.
Graphe pondéré : Un graphe dont les arêtes possèdent un poids ou coût associé, représentant la distance, le coût ou toute autre valeur quantitative.
Matrice d’adjacence : Représentation du graphe sous forme de tableau à deux dimensions où chaque case indique le poids de l’arête entre deux sommets. Si aucune arête n’existe, la case est généralement à 0 ou à une valeur indiquant l’absence de connexion.
Liste de successeurs : Liste des sommets accessibles directement depuis un sommet donné, c’est-à-dire ses voisins immédiats.
DFS (Depth-First Search) : Méthode d’exploration qui parcourt un graphe en profondeur, en allant aussi loin que possible dans une branche avant de revenir en arrière.

📝 Points essentiels

Un graphe est constitué de sommets reliés par des arêtes, qui peuvent être orientées ou non. La matrice d’adjacence représente ces connexions sous forme de tableau, où chaque élément indique le poids de l’arête entre deux sommets. La liste de successeurs d’un sommet liste tous les sommets accessibles directement depuis celui-ci. Le parcours DFS explore un graphe en profondeur, en allant aussi loin que possible dans chaque branche avant de revenir, ce qui permet de couvrir efficacement la structure du réseau. Le BFS, quant à lui, explore en largeur, niveau par niveau, en visitant tous les voisins d’un sommet avant de passer à ceux du niveau suivant. Ces deux parcours ignorent les poids des arêtes, se concentrant uniquement sur la structure de connexions.

💡 À retenir

Les graphes peuvent être explorés efficacement à l’aide des parcours DFS ou BFS, qui permettent d’appréhender leur structure sans tenir compte des poids, facilitant ainsi la modélisation de réseaux complexes.

📖 5. SQL et requêtes

🔑 Notions clés & Définitions

Relation : Une relation est une table dans une base de données, composée d’attributs (colonnes) et de tuples (lignes). Elle représente une entité ou un lien entre entités.
Attribut : Une colonne d’une table, correspondant à une propriété ou caractéristique des données stockées.
Clé primaire : Un attribut ou un ensemble d’attributs qui identifie de manière unique chaque ligne d’une table. Elle garantit l’unicité des enregistrements.
Clé étrangère : Un attribut dans une table qui établit un lien avec la clé primaire d’une autre table, permettant de relier les données entre elles.
Jointure (INNER JOIN) : Une opération qui associe deux tables selon une condition sur leurs clés, permettant de combiner des données liées.
Requête SELECT : Une instruction SQL permettant d’extraire, filtrer et trier des données dans une ou plusieurs tables.

📝 Points essentiels

Une relation, en tant que table, est composée d’attributs et de tuples. La clé primaire est essentielle pour identifier de façon unique chaque ligne, ce qui facilite la manipulation et la référence des données. La clé étrangère sert à établir un lien entre deux tables, en faisant référence à la clé primaire d’une autre relation. Les requêtes SELECT permettent de sélectionner tous ou certains attributs, en utilisant la clause FROM pour spécifier la table. On peut ajouter des conditions avec WHERE pour filtrer les résultats, par exemple en ne conservant que les lignes où une valeur dépasse un seuil. Le tri des résultats s’effectue avec ORDER BY, en ordre croissant ou décroissant. Enfin, les jointures, notamment INNER JOIN, combinent des tables selon des conditions sur leurs clés, permettant d’obtenir des ensembles de données enrichis et cohérents.

💡 À retenir

Utiliser SQL pour manipuler et interroger efficacement des bases de données relationnelles repose sur la compréhension des clés et des jointures, qui permettent d’établir des liens entre tables et d’extraire des données pertinentes.

📖 6. Routage et protocoles

🔑 Notions clés & Définitions

• AUTEUR : voir section 1

Routeur : AUTEUR (date) : équipement réseau chargé d’acheminer les paquets de données entre différents réseaux. Il utilise des tables de routage pour déterminer le chemin optimal pour chaque paquet.

Protocole de routage : AUTEUR (date) : ensemble de règles permettant aux routeurs d’échanger des informations sur le réseau, afin de construire et maintenir leur table de routage. Exemples : RIP, OSPF.

Paquet : AUTEUR (date) : unité de transmission de données dans un réseau, contenant notamment une adresse IP source et destination pour permettre son acheminement.

Table de routage : AUTEUR (date) : document stocké dans un routeur, listant les destinations possibles, les interfaces à utiliser, et les passerelles pour acheminer les paquets vers leur destination.

📝 Points essentiels

Le routage consiste à acheminer les paquets de données entre réseaux. Pour cela, les routeurs jouent un rôle crucial en utilisant des tables de routage. Ces tables contiennent des informations essentielles telles que la destination (sous-réseau ou IP cible), l’interface par laquelle sortiront les données, et la passerelle si un autre routeur doit être traversé. Lorsqu’un paquet arrive, le routeur consulte sa table de routage pour déterminer le meilleur chemin à suivre.

Les protocoles de routage facilitent la communication entre routeurs en leur permettant d’échanger des informations sur le réseau. Par exemple, le protocole RIP fonctionne par échanges périodiques de tables, utilisant le nombre de sauts comme métrique pour choisir le chemin. En revanche, le protocole OSPF calcule le chemin le plus court en utilisant un coût attribué à chaque lien, ce qui permet d’optimiser la vitesse de transmission.

Chaque paquet contient une adresse IP source et une adresse IP destination, ce qui permet au routeur de savoir d’où il vient et où il doit aller, assurant ainsi un acheminement précis et efficace.

💡 À retenir

Le routage repose sur la collaboration entre équipements (routeurs) et protocoles pour échanger des informations, permettant de diriger efficacement le trafic de données à travers Internet ou d’autres réseaux.

📖 7. Systèmes sur puce et processus

🔑 Notions clés & Définitions

Système sur puce (SoC) : Un SoC intègre tous les composants nécessaires pour faire fonctionner un système informatique sur une seule puce, permettant une miniaturisation et une optimisation des performances.

Processus : Un processus est une instance d’un programme en cours d’exécution, comprenant l’ensemble des ressources et des données associées à cette exécution.

Ordonnancement : L’ordonnancement gère l’exécution concurrente des processus, en déterminant l’ordre dans lequel ils accèdent aux ressources processeur.

Mémoire partagée : La mémoire partagée facilite la communication entre processus en leur permettant d’accéder à un espace mémoire commun.

Interruption : Une interruption permet de gérer les événements asynchrones en suspendant temporairement l’exécution en cours pour traiter un événement spécifique.

📝 Points essentiels

Un SoC intègre plusieurs composants informatiques sur une seule puce, ce qui optimise l’espace et la performance des systèmes embarqués. Un processus représente une instance active d’un programme, pouvant contenir plusieurs threads pour exécuter simultanément différentes tâches dans le même espace mémoire. L’ordonnancement est crucial pour gérer cette exécution concurrente, en attribuant le temps processeur aux processus selon une stratégie définie, afin d’assurer une utilisation efficace des ressources. Les interruptions jouent un rôle clé en permettant au système de réagir rapidement aux événements asynchrones, comme une entrée utilisateur ou un signal matériel. La mémoire partagée, quant à elle, simplifie la communication entre processus en leur fournissant un espace mémoire commun, évitant ainsi la duplication de données et facilitant la synchronisation.

💡 À retenir

L’intégration matérielle d’un SoC et la gestion logicielle des processus, notamment par l’ordonnancement, les interruptions et la mémoire partagée, sont essentielles pour optimiser la performance et la réactivité des systèmes embarqués.

📖 8. Tri par insertion et sélection

🔑 Notions clés & Définitions

Tri par insertion : Méthode de tri où chaque élément du tableau est inséré à sa place dans une sous-liste déjà triée. À chaque étape, l’élément suivant est comparé et inséré à la position correcte, permettant de construire progressivement une liste triée.

Tri par sélection : Technique consistant à sélectionner à chaque étape le plus petit élément du tableau non trié, puis à l’échanger avec l’élément en début de cette partie non triée. La partie triée s’agrandit à chaque étape.

Complexité temporelle : Mesure du temps d’exécution d’un algorithme en fonction de la taille du problème. Pour ces algorithmes, la complexité moyenne est en O(n²).

Permutation : Échange de deux éléments dans un tableau, utilisé notamment dans le tri par sélection pour placer le plus petit élément à sa position finale.

Tableau : Structure de données linéaire contenant une collection d’éléments accessibles par leur position (indice).

📝 Points essentiels

Le tri par insertion insère chaque élément à sa place dans une sous-liste triée, ce qui permet de construire progressivement une liste ordonnée. Le tri par sélection, quant à lui, sélectionne à chaque étape le plus petit élément du tableau non trié pour le placer en début de cette partie, en effectuant une permutation avec l’élément en position.

Ces deux algorithmes ont une complexité moyenne en O(n²), ce qui signifie que leur temps d’exécution augmente de façon quadratique avec la taille du tableau. Ils sont simples à implémenter mais peu efficaces pour de grandes quantités de données, car leur performance se dégrade rapidement lorsque n devient grand.

💡 À retenir

Les algorithmes de tri par insertion et par sélection sont des méthodes simples pour classer des données, mais leur inefficacité pour de grands ensembles limite leur usage aux petits tableaux ou à l’apprentissage des bases du tri. Leur compréhension permet de saisir les mécanismes fondamentaux des algorithmes de classement et leurs limites en termes de complexité.

📖 9. Congruences et algorithmes d’Euclide

🔑 Notions clés & Définitions

Congruence modulo : La congruence modulo exprime l'égalité des restes de division. Deux entiers a et b sont congrus modulo n, noté a≡b (mod n) ou a≡b[n], si n divise la différence a−b. Autrement dit, n | (a−b).

Classe d'équivalence : Ensemble d'entiers partageant la même congruence modulo n. Chaque classe regroupe tous les entiers qui ont le même reste lorsqu'ils sont divisés par n.

Algorithme d'Euclide : Méthode récursive ou itérative permettant de calculer efficacement le PGCD de deux entiers a et b. Il repose sur la division euclidienne répétée jusqu'à ce que le reste soit nul.

PGCD (Plus Grand Commun Diviseur) : Plus grand entier qui divise deux nombres sans reste. Il est calculé via l'algorithme d'Euclide ou l'algorithme étendu de Bézout.

Division euclidienne : Décomposition d’un entier a en un quotient q et un reste r, tels que a = q×b + r, avec 0 ≤ r < |b|. Elle sert de base à la définition de la congruence et à l’algorithme d’Euclide.

📝 Points essentiels

La congruence modulo exprime l'égalité des restes de division : si a≡b (mod n), alors a et b ont le même reste lorsqu'ils sont divisés par n. Cette relation est une classe d'équivalence, regroupant tous les entiers partageant ce même reste.

L’algorithme d’Euclide calcule efficacement le PGCD de deux entiers a et b en utilisant la division euclidienne : si b = 0, alors PGCD(a, b) = a ; sinon, on remplace a par b et b par le reste de la division de a par b, et on répète jusqu’à ce que b soit nul.

Le PGCD est la plus grande valeur divisant deux nombres sans reste. Il est essentiel pour simplifier des fractions, résoudre des équations diophantiennes, ou encore pour déterminer des propriétés arithmétiques.

La division euclidienne décompose un entier en quotient et reste, permettant d’établir la relation de congruence et de simplifier les calculs dans l’arithmétique modulaire.

💡 À retenir

La congruence modulo exprime l’égalité des restes de division, et l’algorithme d’Euclide permet de calculer efficacement le PGCD, outil fondamental pour résoudre des problèmes arithmétiques et d’optimisation.

📊 Tableaux de Synthèse

Structure / Concept	Définition / Fonctionnement	Méthodes clés / Parcours	Auteur / Référence
Interface	Contrat définissant les fonctionnalités d’une classe sans implémentation spécifique.	N/A	N/A
Implémentation	Réalisation concrète des fonctionnalités d’une interface.	N/A	N/A
Encapsulation	Protection des données internes via attributs privés et méthodes publiques.	N/A	N/A
Héritage	Réutilisation et extension des classes par dérivation.	N/A	N/A
Polymorphisme	Utilisation d’une même interface pour différents types d’objets, redéfinition de méthodes.	N/A	N/A
Pile (LIFO)	Structure où le dernier élément inséré est le premier retiré.	append(), pop()	N/A
File (FIFO)	Structure où le premier élément inséré est le premier retiré.	append(), pop(0)	N/A
Liste	Structure linéaire dynamique, accès/insère/supprime à n’importe quelle position.	insert(), delete(), accès par index	N/A
Dictionnaire	Paires clé-valeur, accès rapide en O(1).	dict[key], update(), pop()	N/A
Arbre binaire	Structure hiérarchique avec au plus deux enfants par nœud.	Parcours préfixe, infixe, suffixe, niveau par niveau	N/A
Arbre binaire de recherche	Ordre : sous-arbre gauche < nœud < sous-arbre droit.	Recherche, insertion, suppression	N/A
Graphe	Ensemble de sommets reliés par des arêtes (orientées ou non).	DFS, BFS	N/A

⚠️ Pièges & Confusions Fréquentes

1. Confondre pile (LIFO) et file (FIFO) lors de leur implémentation.
2. Oublier que la complexité moyenne d’un dictionnaire est en O(1), mais peut varier selon la gestion des collisions.
3. Confusion entre hauteur et profondeur dans un arbre binaire.
4. Croire que tous les parcours d’un arbre binaire sont équivalents ou interchangeables.
5. Confondre matrice d’adjacence et liste de successeurs dans la représentation d’un graphe.
6. Négliger l’importance de l’ordre dans les parcours DFS et BFS pour explorer un graphe.
7. Confondre interface et implémentation en programmation orientée objet.

✅ Checklist Examen

1. Connaître la définition d’une interface selon l’auteur (sans référence précise dans le contenu fourni).
2. Savoir ce qu’est l’implémentation en programmation orientée objet.
3. Expliquer le principe d’encapsulation et ses avantages.
4. Définir l’héritage et ses bénéfices pour la réutilisation du code.
5. Comprendre le polymorphisme et comment il permet la flexibilité dans le traitement des objets.
6. Décrire le fonctionnement d’une pile (LIFO) et ses méthodes principales (append(), pop()).
7. Décrire le fonctionnement d’une file (FIFO) et ses méthodes principales (append(), pop(0)).
8. Connaître les caractéristiques d’une liste et ses opérations fondamentales.
9. Savoir ce qu’est un dictionnaire, ses avantages, et comment y accéder rapidement.
10. Définir un arbre binaire, ses nœuds, racine, feuille, hauteur, profondeur.
11. Expliquer les parcours principaux d’un arbre binaire : préfixe, infixe, suffixe, niveau par niveau.
12. Comprendre la différence entre arbre binaire de recherche et arbre binaire simple.
13. Définir un graphe, sommet, arête orientée/non orientée, poids.
14. Connaître la représentation matricielle (matrice d’adjacence) et la liste de successeurs.
15. Expliquer les principes des parcours DFS et BFS dans un graphe.
16. Maîtriser la différence entre parcours en profondeur (DFS) et en largeur (BFS).