Fiche de révision : Introduction aux structures et concepts fondamentaux en informatique

📋 Plan du Cours

1. Programmation Orientée Objet
2. Structures de données
3. Arbres binaires
4. Graphes
5. SQL et bases de données
6. Routage réseaux
7. Recursion et Divide & Conquer
8. Systèmes sur puce
9. Modularité en programmation
10. Tri par insertion et sélection

📖 1. Programmation Orientée Objet

🔑 Notions clés & Définitions

• Interface : Définit les fonctionnalités d'une classe ou d'un module, sans implémentation spécifique. Elle sert de contrat pour les classes qui l'implémentent, garantissant la présence de méthodes spécifiques sans définir leur contenu.
• Implémentation : La réalisation concrète des fonctionnalités définies par une interface. Elle consiste à écrire le code qui exécute les actions promises par l'interface, permettant la modularité et la réutilisabilité.
• Encapsulation : Principe de protection des données internes d'une classe via l'utilisation d'attributs privés et de méthodes publiques pour y accéder ou les modifier. Elle limite l'accès direct aux données, assurant la cohérence et la sécurité des objets.
• Héritage : Permet à une classe de réutiliser et d'étendre les fonctionnalités d'une autre classe. La classe fille hérite des attributs et méthodes de la classe parent, facilitant la réutilisation du code et la spécialisation.
• Polymorphisme : Capacité à utiliser une interface unique pour des types différents, notamment via la redéfinition (surcharge) de méthodes dans des classes dérivées. Cela permet d'écrire du code flexible et extensible, capable de traiter des objets de différentes classes de manière uniforme.
• Classe et instance : La classe est une structure qui définit un type d'objet avec ses attributs et méthodes. Une instance est un objet concret créé à partir de cette classe, représentant une entité spécifique avec ses propres données.

📝 Points essentiels

• L'interface sert de contrat pour garantir que certaines méthodes seront présentes dans une classe, facilitant la modularité et l'interopérabilité.
• La réalisation concrète dans l'implémentation permet de donner vie aux fonctionnalités définies par l'interface, en écrivant le code spécifique dans la classe.
• L'encapsulation est essentielle pour protéger l'intégrité des données internes, en utilisant des attributs privés (souvent précédés de double underscore en Python) et des méthodes publiques pour y accéder ou les modifier.
• L'héritage favorise la réutilisation du code, en permettant à une classe fille d'hériter des attributs et méthodes d'une classe mère, tout en pouvant ajouter ou redéfinir des fonctionnalités.
• Le polymorphisme permet d'utiliser une même interface pour des objets de classes différentes, en redéfinissant des méthodes pour adapter leur comportement selon le type d'objet.
• La distinction entre classe (structure définissant un type d'objet) et instance (objet spécifique créé à partir de cette classe) est fondamentale pour comprendre la programmation orientée objet.

💡 À retenir

La programmation orientée objet repose sur la définition de classes et d'interfaces pour structurer le code, en utilisant l'encapsulation, l'héritage et le polymorphisme pour favoriser la modularité, la réutilisabilité et la flexibilité.

📖 2. Structures de données

🔑 Notions clés & Définitions

• Pile (LIFO) : Structure de données où le dernier élément ajouté est le premier à être retiré (Last In, First Out).
• File (FIFO) : Structure de données où le premier élément ajouté est le premier à être retiré (First In, First Out).
• Liste : Structure de données linéaire dynamique permettant l'accès, l'insertion et la suppression à n'importe quelle position.
• Dictionnaire : Structure non ordonnée basée sur des paires clé-valeur, avec une complexité moyenne d'opération de O(1), permettant un accès rapide via la clé.

📝 Points essentiels

• La pile fonctionne selon le principe LIFO, idéale pour gérer des tâches ou des états temporaires (ex : pile d'appels).
• La file suit le principe FIFO, utilisée pour gérer des files d'attente ou des processus en ordre d'arrivée.
• La liste en Python est une structure flexible permettant d’accéder et de modifier ses éléments à n’importe quelle position, ce qui la rend très utile pour diverses opérations.
• Le dictionnaire est une structure clé pour optimiser la recherche d’éléments, grâce à sa complexité moyenne de O(1). Elle est essentielle pour associer rapidement des clés à des valeurs, notamment dans la gestion de données structurées.

💡 À retenir

Les piles et files sont des structures linéaires fondamentales pour gérer l’ordre d’accès aux données, tandis que les listes et dictionnaires offrent une flexibilité et une rapidité d’accès accrues pour manipuler efficacement de grandes quantités d’informations.

📖 3. Arbres binaires

🔑 Notions clés & Définitions

• Arbre : Structure hiérarchique composée de nœuds reliés par des arêtes, où chaque nœud peut avoir zéro, un ou deux enfants. La relation entre parent et enfant modélise des relations de type hiérarchique ou de dépendance.
• Racine : Nœud de départ de l’arbre, qui ne possède pas de parent. C’est le point d’origine de la hiérarchie.
• Feuille : Nœud sans enfant, représentant la terminaison d’un chemin dans l’arbre.
• Arbre binaire : Arbre dans lequel chaque nœud possède au plus deux enfants, appelés généralement gauche et droit.
• Taille : Nombre total de nœuds dans l’arbre. (voir aussi métriques)
• Hauteur : Nombre d’arêtes sur le chemin le plus long de la racine à une feuille. Elle mesure la profondeur maximale de l’arbre. (voir aussi métriques)
• Profondeur d’un nœud : Nombre d’arêtes entre la racine et ce nœud, indiquant sa distance hiérarchique par rapport à la racine. (voir aussi métriques)

💡 Point à retenir

Les arbres binaires, notamment les arbres de recherche, permettent une organisation hiérarchique efficace pour la recherche, l’insertion et la suppression d’éléments, tout en étant caractérisés par leur taille, hauteur et profondeur.

📖 4. Graphes

🔑 Notions clés & Définitions

• Sommet : Point ou nœud dans un graphe, représentant un élément ou une entité.
• Arête : Connexion ou lien entre deux sommets, pouvant être orientée (direction définie) ou non (sans direction).
• Graphe pondéré : Graphe dont chaque arête possède un poids ou coût associé, utilisé pour modéliser des distances ou des coûts.
• Matice d'adjacence : Représentation matricielle d'un graphe où chaque case indique la présence et le poids de l'arête entre deux sommets, selon AUTEUR (date).
• Liste de successeurs : Liste des sommets accessibles directement depuis un sommet donné, permettant une navigation efficace dans un graphe orienté.
• Liste de prédécesseurs : Liste des sommets qui pointent vers un sommet donné, utile pour analyser les dépendances ou flux entrants.

📝 Points essentiels

• La matrice d'adjacence est une représentation compacte pour les graphes denses, où chaque élément (i, j) indique la présence ou le poids d'une arête entre le sommet i et le sommet j.
• La liste de successeurs facilite l'exploration en profondeur ou en largeur, en listant directement les voisins accessibles.
• La liste de prédécesseurs est essentielle pour analyser la structure inverse ou pour certains algorithmes de parcours et de flux.
• La distinction entre graphes orientés et non-orientés influence la symétrie de la matrice ou des listes.
• La représentation par matrice ou liste dépend du contexte : la matrice est plus adaptée aux graphes denses, la liste aux graphes clairsemés.
• La connexion dans un graphe peut être vérifiée via la matrice ou les listes, et détermine si le graphe est connexe (voir section 3).

💡 À retenir

Les graphes sont des structures essentielles pour modéliser des réseaux complexes, où la représentation (matrice ou liste) doit être choisie en fonction de la densité et des besoins en exploration.

📖 5. SQL et bases de données

🔑 Notions clés & Définitions

• Relation : Une table dans une base de données, qui organise les données sous forme de lignes et de colonnes.
• Attribut : Une colonne d'une table, représentant une propriété ou caractéristique des enregistrements.
• Clé primaire : Un attribut ou un ensemble d'attributs permettant d'identifier de manière unique chaque ligne d'une table.
• Clé étrangère : Un attribut dans une table qui établit un lien avec la clé primaire d'une autre table, permettant d'associer des données entre elles.
• Requêtes SQL : Des commandes permettant d'interroger ou manipuler les données dans une base, telles que SELECT, WHERE, ORDER BY, DISTINCT, et INNER JOIN (jointure interne).

📝 Points essentiels

• La relation correspond à une table dans le modèle relationnel, chaque ligne étant un enregistrement et chaque colonne un attribut.
• La clé primaire doit garantir l'unicité de chaque ligne, facilitant l'identification et la recherche rapide.
• La clé étrangère permet de relier deux tables, assurant l'intégrité référentielle.
• La commande SELECT sert à extraire des données, avec la syntaxe SELECT * FROM nom_table pour toutes les colonnes ou SELECT colonne1, colonne2 FROM nom_table pour des colonnes spécifiques.
• La clause WHERE filtre les résultats selon une condition, par exemple WHERE note > 9.
• ORDER BY trie les résultats selon un ou plusieurs attributs, en ordre croissant (par défaut) ou décroissant (avec DESC).
• DISTINCT élimine les doublons dans les résultats, par exemple SELECT DISTINCT langue_ecriture.
• La jointure interne (INNER JOIN) combine deux tables en associant les lignes où la clé étrangère correspond à la clé primaire, par exemple :

  SELECT LIVRES.titre, AUTEURS.nom
  FROM LIVRES
  INNER JOIN AUTEURS ON LIVRES.id_auteur = AUTEURS.id;
  

• Les opérations INSERT, UPDATE et DELETE permettent respectivement d'ajouter, modifier ou supprimer des données.

💡 À retenir

Les requêtes SQL exploitent le modèle relationnel pour manipuler efficacement les données en utilisant des tables reliées par des clés, avec des commandes permettant de sélectionner, filtrer, trier et associer les informations.

📖 6. Routage réseaux

🔑 Notions clés & Définitions

• Adresse IP : Identifiant unique d'une machine dans un réseau, permettant son identification sur Internet ou un réseau local (ex. 192.168.1.10).

• Masque de sous-réseau : Sépare la partie réseau et la partie hôte d'une adresse IP, en utilisant une série de bits (ex. 255.255.255.0). Selon AUTEUR (date), il permet de définir la taille du sous-réseau et d'isoler des segments du réseau.

• Adresse réseau : Représente le réseau auquel appartient une machine, obtenue en effectuant une opération ET entre l'adresse IP et le masque de sous-réseau (ex. pour 192.168.1.10/24, l'adresse réseau est 192.168.1.0).

• Adresse de broadcast : Adresse permettant d'envoyer un message à toutes les machines du réseau, généralement la dernière adresse du sous-réseau (ex. 192.168.1.255 pour 192.168.1.0/24).

• Notation CIDR (/n) : Indique le nombre de bits utilisés pour la partie réseau dans le masque, facilitant la notation compacte des sous-réseaux (ex. /24 équivaut à 255.255.255.0). Selon AUTEUR (date), cette notation optimise la gestion des adresses IP.

• Table de routage : Ensemble d'informations contenues dans un routeur, permettant de déterminer le chemin optimal pour acheminer les paquets vers leur destination, en utilisant des critères comme la destination, l'interface et la passerelle.

📝 Points essentiels

• L'adresse IP, combinée au masque de sous-réseau, permet d'identifier précisément le réseau et la machine dans ce réseau. La conversion en notation CIDR (/n) simplifie la gestion des sous-réseaux (voir AUTEUR (date)).

• L'adresse réseau est calculée par une opération ET entre l'adresse IP et le masque de sous-réseau, ce qui permet de distinguer la partie réseau de la partie hôte.

• L'adresse de broadcast est utilisée pour la diffusion de messages à toutes les machines du sous-réseau, facilitant la communication globale.

• La table de routage contient des routes spécifiques pour atteindre différents sous-réseaux ou adresses IP, avec des informations sur l'interface de sortie et la passerelle. En absence de route spécifique, une route par défaut est utilisée.

• Les protocoles RIP et OSPF permettent la mise à jour dynamique des tables de routage, RIP utilisant le nombre de sauts comme métrique, tandis qu'OSPF privilégie le coût basé sur la bande passante (voir AUTEUR (date)).

💡 À retenir

Le routage repose sur la compréhension des adresses IP, du masque de sous-réseau et des tables de routage, qui permettent d'acheminer efficacement les paquets entre réseaux. La notation CIDR simplifie la gestion des sous-réseaux et optimise l'utilisation des adresses IP.

📖 7. Recursion et Divide & Conquer

🔑 Notions clés & Définitions

• Récursion : Fonction qui s'appelle elle-même pour résoudre un problème en le décomposant en sous-problèmes plus simples, jusqu'à atteindre un cas de base.
  Source : factorielle (exemple dans le contenu source).

• Cas de base : Condition qui arrête la récursion, évitant une boucle infinie.
  Exemple : if n == 0: return 1 dans la fonction factorielle.

• Appel récursif : Réduction du problème en appelant la fonction elle-même avec une version simplifiée du problème.
  Exemple : return n * factorielle(n - 1).

• Divide & Conquer : Méthode algorithmique qui divise un problème en sous-problèmes plus petits, les résout indépendamment, puis combine leurs solutions pour obtenir la résultat final.
  Source : Tri fusion (Merge Sort).

• Fusion : Étape de la méthode Divide & Conquer qui consiste à combiner les solutions des sous-problèmes pour former la solution du problème initial.
  Exemple : Fonction fusion(gauche, droite) dans le tri fusion.

📝 Points essentiels

• La récursion repose sur deux éléments fondamentaux : le cas de base qui arrête la récursion, et l'appel récursif qui réduit le problème à chaque étape.
• La fonction factorielle illustre la récursion : elle se calcule en multipliant n par la factorielle de n-1, jusqu'à atteindre le cas n == 0.
• La diviser pour régner consiste à fractionner le problème en sous-problèmes plus petits, à les résoudre récursivement, puis à fusionner leurs résultats pour obtenir la solution globale.
• Exemple de tri fusion : la liste est divisée en deux parties, triée séparément, puis fusionnées pour obtenir la liste triée finale.
• La récursion nécessite de vérifier l’existence d’un cas de base pour éviter une récursion infinie, et la réduction du problème doit être correcte à chaque étape pour garantir la convergence.
• La méthode Divide & Conquer est efficace pour des algorithmes comme le tri fusion, qui exploitent la division en sous-problèmes pour optimiser la complexité.

💡 À retenir

La récursion permet de simplifier la résolution de problèmes complexes en les décomposant en sous-problèmes plus simples, tandis que la méthode Divide & Conquer structure cette décomposition pour optimiser la résolution et la fusion des résultats.

📖 8. Systèmes sur puce

🔑 Notions clés & Définitions

• Système sur puce (SoC) : Circuit intégré unique regroupant tous les composants nécessaires au fonctionnement d’un système informatique, permettant une intégration compacte et performante.
• Composants typiques : Ensemble de modules intégrés dans un SoC, tels que processeur, mémoire, interfaces d'entrée/sortie.
• Avantages : La compacité, la faible consommation d’énergie et la performance accrue qu’offre cette intégration.
• Utilisations : Smartphones, objets connectés, systèmes embarqués.
• Loi de Moore : Énoncé selon lequel la densité des transistors double environ tous les 18 à 24 mois, augmentant performances et réduisant les coûts (source implicite).

📝 Points essentiels

• Le Système sur puce (SoC) permet d’intégrer tous les composants essentiels d’un système informatique sur une seule puce, ce qui favorise la miniaturisation et la performance.
• La Loi de Moore explique la croissance exponentielle des capacités des transistors dans les SoC, bien que ses limites physiques actuelles soient atteintes, notamment en raison des dimensions atomiques et des problématiques de dissipation thermique.
• Les composants typiques d’un SoC incluent un processeur, la mémoire, et des interfaces d’entrée/sortie, permettant une gestion efficace de l’ensemble du système.
• Les exemples courants de SoC : Apple A15 Bionic (iPhone) et Snapdragon 8 Gen 1 (smartphones Android haut de gamme).
• La conception de SoC favorise la réduction de la consommation énergétique tout en maintenant ou améliorant la performance, ce qui est crucial pour les appareils mobiles et objets connectés.

💡 À retenir

Le SoC est une solution intégrée qui optimise la compacité, la performance et la consommation d’énergie, répondant aux besoins croissants de miniaturisation et d’efficacité dans les technologies modernes.

📖 9. Modularité en programmation

🔑 Notions clés & Définitions

• Modularité : Approche de conception consistant à diviser un système complexe en modules indépendants, chacun gérant une fonctionnalité spécifique, afin de faciliter la maintenance, la réutilisation et l'extensibilité.

• Interface d'un module : Ensemble des fonctionnalités, méthodes ou fonctions exposées par un module, permettant à d'autres modules ou programmes d'interagir avec lui sans connaître son implémentation interne.

• Implémentation : Code interne d’un module, c’est-à-dire la réalisation concrète des fonctionnalités définies par l’interface, généralement cachée pour préserver l’encapsulation.

• Avantages : La modularité permet la réutilisabilité des modules dans différents projets, facilite la maintenance en localisant rapidement les erreurs, favorise l’extensibilité en ajoutant ou modifiant des fonctionnalités, et améliore la compréhensibilité du système global.

💡 À retenir

La modularité consiste à structurer un programme en modules indépendants avec des interfaces clairement définies, ce qui optimise la réutilisation, la maintenance et la compréhension du code.

📖 10. Tri par insertion et sélection

🔑 Notions clés & Définitions

• Tri par insertion : Algorithme de tri qui parcourt le tableau en insérant chaque nouvel élément à sa place dans la partie déjà triée, en décalant les autres éléments si nécessaire.
• Tri par sélection : Algorithme de tri qui, à chaque étape, sélectionne le plus petit élément du sous-tableau non trié et l’échange avec l’élément en début de sous-tableau.
• Complexité moyenne : O(n²), ce qui indique que le temps d’exécution augmente quadratiquement avec la taille du tableau, adapté aux petites données.
• Fonctionnement étape par étape : Les algorithmes s’exécutent en parcourant le tableau, insérant ou sélectionnant les éléments dans l’ordre, avec des exemples concrets pour illustrer chaque étape.

📝 Points essentiels

• Tri par insertion : Pour chaque élément à partir du deuxième, on le compare avec ceux précédents et on le déplace vers sa position correcte dans la partie triée, en décalant les autres éléments vers la droite si nécessaire.
• Tri par sélection : Pour chaque position, on cherche le minimum dans le reste du tableau, puis on échange cet élément avec celui en cours. La partie triée s’agrandit à chaque étape.
• Complexité : Les deux algorithmes ont une complexité O(n²) dans le pire cas, car ils nécessitent deux boucles imbriquées pour parcourir tous les éléments.
• Adaptation : Ces algorithmes sont simples à implémenter et efficaces pour de petites quantités de données, mais peu performants pour de grands tableaux.

💡 À retenir

Les tris par insertion et sélection sont des algorithmes simples, avec une complexité quadratique, adaptés aux petites tailles de tableau, en suivant un processus étape par étape d’insertion ou de sélection du minimum.

📊 Tableaux de Synthèse

⚠️ Pièges & Confusions Fréquentes

1. Confondre interface et classe abstraite : une interface ne contient que des méthodes sans implémentation, alors qu’une classe abstraite peut contenir du code partiel.
2. Assimiler la récursivité uniquement à la division en sous-problèmes : elle peut aussi servir à parcourir des structures hiérarchiques comme les arbres.
3. Confusion entre pile et file : la pile suit LIFO, la file FIFO, mais leur utilisation pratique est souvent inversée.
4. Mauvaise compréhension des arbres binaires : ne pas distinguer la hauteur de la taille, ou confondre arbre binaire de recherche et arbre binaire complet.
5. Oublier que la matrice d’adjacence est inefficace pour graphes clairsemés : privilégier la liste d’adjacence.
6. Confusion entre polymorphisme paramétrique (générique) et ad hoc : le polymorphisme en POO concerne la redéfinition de méthodes, pas la généralisation de types.
7. Mauvaise maîtrise des jointures en SQL : oublier de préciser le type de jointure (INNER, LEFT, RIGHT, FULL).

✅ Checklist Examen

1. Connaître la définition d’une interface en programmation orientée objet et son rôle dans la modularité (Connaître la conception par Alan Kay).
2. Savoir différencier encapsulation, héritage et polymorphisme avec leurs exemples pratiques.
3. Maîtriser les opérations fondamentales sur une pile (LIFO) et une file (FIFO), et leur utilisation concrète.
4. Identifier les caractéristiques d’une liste en Python et leur intérêt pour la manipulation de données.
5. Définir un arbre binaire, ses composants (racine, feuille, nœud) et ses métriques (hauteur, profondeur).
6. Expliquer la différence entre arbre binaire de recherche et arbre binaire complet.
7. Connaître la représentation d’un graphe par matrice d’adjacence et liste de successeurs, et leurs cas d’usage.
8. Définir un graphe pondéré et ses applications en optimisation.
9. Savoir décrire une relation dans une base de données relationnelle, avec la notion de clé primaire.
10. Comprendre le principe des jointures en SQL et leur impact sur la récupération de données.
11. Connaître la différence entre parcours en largeur (BFS) et en profondeur (DFS) dans un graphe.
12. Maîtriser la notion de normalisation en bases de données pour éviter la redondance.

Dernier item de la checklist :
Connaître la définition et le rôle de l’héritage en programmation orientée objet.