Lernzettel: Introduction aux structures et algorithmes fondamentaux

📋 Plan du Cours

1. Structures de données
2. Récursivité et algorithmes récursifs
3. Bases de données relationnelles et SQL
4. Architecture matérielle et programmation objet

📖 1. Structures de données

🔑 Notions clés & Définitions

• Pile : Structure de données organisée en accès selon le principe dernier entré, premier sorti.
• File : Structure de données organisée en accès selon le principe premier entré, premier sorti.
• Arbre binaire de recherche : Structure d’arbre binaire où la disposition des nœuds respecte une règle de tri entre sous-arbres.

📝 Points essentiels

• Une pile suit un mode d’accès LIFO, ce qui détermine l’ordre des opérations push et pop.
• Une file suit un mode d’accès FIFO, ce qui détermine l’ordre des opérations d’enfilage et de défiler.
• Les structures vues incluent piles, files, arbres binaires, arbres binaires de recherche et graphes.
• Les graphes servent à modéliser des relations entre éléments, contrairement aux structures hiérarchiques comme les arbres.

📖 2. Récursivité et algorithmes récursifs

🔑 Notions clés & Définitions

• Récursivité : Technique de programmation où une fonction s’appelle elle-même pour résoudre un problème en sous-problèmes.
• Tri fusion : Algorithme de tri basé sur une stratégie récursive de division puis de fusion de listes triées.
• Parcours d’arbres : Méthode d’exploration systématique des nœuds d’un arbre, souvent implémentée avec une fonction récursive.

📝 Points essentiels

• Les algorithmes récursifs du programme incluent le tri fusion et des parcours d’arbres.
• La récursivité décompose généralement un problème en cas plus petits jusqu’à atteindre des cas de base.
• Le parcours d’arbres utilise l’exploration des sous-arbres pour traiter tous les nœuds de façon structurée.
• Le tri fusion repose sur l’idée de combiner deux parties triées en un résultat trié final.

📖 3. Bases de données relationnelles et SQL

🔑 Notions clés & Définitions

• Modèle relationnel : Approche de stockage des données qui représente l’information sous forme de relations (tables) reliées entre elles.
• Requête SQL : Instruction permettant d’interroger une base de données pour retrouver, filtrer ou construire un résultat.
• Jointure : Opération SQL qui combine des lignes de tables différentes selon une condition de correspondance.

📝 Points essentiels

• Le programme introduit le modèle relationnel et le langage SQL.
• Les requêtes SQL portent sur des opérations comme le filtrage et la construction d’un résultat à partir des tables.
• Les jointures sont un mécanisme central pour combiner des informations provenant de plusieurs tables.
• L’agrégation permet de produire des valeurs résumées à partir d’ensembles de lignes dans SQL.

📖 4. Architecture matérielle et programmation objet

🔑 Notions clés & Définitions

• Système sur puce : Architecture matérielle où plusieurs composants informatiques sont intégrés sur une même puce.
• Encapsulation : Principe de programmation objet qui regroupe l’état et le comportement d’une classe tout en contrôlant l’accès extérieur.
• Héritage : Mécanisme de programmation objet qui permet à une classe de reprendre et étendre les caractéristiques d’une autre.

📝 Points essentiels

• Le programme aborde l’architecture matérielle avec les systèmes sur puce.
• Des protocoles de routage sont étudiés dans le contexte des communications réseau.
• La sécurité des communications fait partie du thème d’architecture matérielle.
• La programmation orientée objet en Python couvre classes, héritage et encapsulation.

⚠️ Pièges & confusions fréquents

1. Confondre FIFO (file) et LIFO (pile) conduit à inverser l’ordre attendu des opérations de traitement.
2. Traiter un parcours d’arbre comme une simple boucle sans logique de sous-arbres peut empêcher une implémentation récursive correcte.
3. Croire que la récursivité remplace toujours la base récursive et négliger les cas de base rend l’algorithme non terminant.
4. Réunir des tables sans jointure en pensant obtenir automatiquement les correspondances donne souvent un résultat incomplet ou faux.
5. Confondre modèle relationnel et programmation objet fait perdre le lien entre tables, relations, requêtes et opérations SQL.
6. Penser que la sécurité des communications relève uniquement du code objet en oubliant l’aspect protocolaire abordé en architecture matérielle.

✅ Checklist Examen

1. Savoir distinguer pile et file et décrire l’ordre produit par leurs règles d’accès.
2. Connaître les structures de données au programme : piles, files, arbres binaires, arbres binaires de recherche et graphes.
3. Définir la récursivité et expliquer l’idée de décomposition en sous-problèmes.
4. Savoir nommer des algorithmes récursifs étudiés : tri fusion et parcours d’arbres.
5. Associer l’arbre binaire de recherche à la contrainte de rangement entre sous-arbres.
6. Décrire ce que représente le modèle relationnel pour une base de données.
7. Formuler l’objectif d’une requête SQL pour obtenir un résultat à partir de tables.
8. Expliquer à quoi sert une jointure et ce qu’elle combine entre tables.
9. Relier l’agrégation à la production de valeurs résumées à partir de lignes.
10. Citer les thèmes d’architecture matérielle vus : systèmes sur puce, protocoles de routage et sécurité des communications.
11. Savoir définir et distinguer les notions de programmation objet : classes, héritage et encapsulation en Python.