Lernzettel: Introduction aux structures de données et algorithmes

📋 Plan du Cours

1. Structures de données et graphes
2. Algorithmique et programmation dynamique
3. Bases de données et requêtes SQL
4. Réseaux, systèmes et cryptographie

📖 1. Structures de données et graphes

🔑 Notions clés & Définitions

• Listes : Structure de données séquentielle qui stocke des éléments dans un ordre et permet des accès et mises à jour selon la position.
• Piles : Structure de données LIFO où le dernier élément ajouté est le premier à être retiré.
• Files : Structure de données FIFO où le premier élément ajouté est le premier à être retiré.
• Arbres binaires de recherche : Arbre binaire organisé pour que, pour chaque nœud, les valeurs à gauche soient plus petites et celles à droite plus grandes.

📝 Points essentiels

• Une pile suit un ordre LIFO, donc l’opération de retrait correspond au dernier ajout.
• Une file suit un ordre FIFO, donc l’opération de retrait correspond au premier ajout.
• Un arbre binaire de recherche impose une contrainte d’ordre entre sous-arbres et nœud pour guider la recherche.
• Les graphes peuvent être représentés puis parcourus avec BFS ou DFS pour explorer des sommets.
• Les dictionnaires reposent sur une table de hachage pour retrouver rapidement une valeur à partir d’une clé.

💡 Astuce mémo

LIFO = Last In, First Out ; FIFO = First In, First Out.

📖 2. Algorithmique et programmation dynamique

🔑 Notions clés & Définitions

• Tri par fusion : Algorithme de tri qui combine des sous-tableaux déjà triés pour produire un tableau trié.
• Tri rapide : Algorithme de tri qui partitionne un tableau autour d’un pivot puis trie récursivement les parties obtenues.
• Diviser pour régner : Technique algorithmique qui décompose un problème en sous-problèmes, les résout, puis combine les résultats.
• Programmation dynamique : Approche qui résout un problème en réutilisant des sous-problèmes stockés pour éviter des recalculs.

📝 Points essentiels

• La recherche dichotomique exploite un ordre pour réduire l’espace de recherche à chaque étape.
• Le tri par fusion s’appuie sur une stratégie de décomposition puis fusion des résultats.
• Le tri rapide s’appuie sur une partition autour d’un pivot avant de traiter récursivement les sous-parties.
• La programmation dynamique vise à capitaliser sur des sous-résultats pour accélérer des calculs répétitifs.
• Diviser pour régner est un schéma général qui s’applique à des problèmes où une combinaison finale est possible.

💡 Astuce mémo

Dichotomie = on coupe en deux ; Diviser pour régner = couper → résoudre → recoller.

📖 3. Bases de données et requêtes SQL

🔑 Notions clés & Définitions

• Modèle relationnel : Modèle qui organise les données en relations (tables) et décrit les opérations possibles sur ces relations.
• Algèbre relationnelle : Ensemble d’opérations formelles permettant de construire des requêtes à partir de relations.
• Requêtes SQL : Langage permettant d’exprimer des demandes sur une base de données via des clauses comme SELECT et JOIN.
• Intégrité et contraintes : Ensemble de règles qui limitent les valeurs et relations autorisées dans la base pour préserver la cohérence.

📝 Points essentiels

• Le modèle relationnel structure les données en tables et relations entre elles.
• L’algèbre relationnelle fournit un cadre formel pour raisonner sur les requêtes.
• Une requête SQL peut utiliser SELECT pour choisir des colonnes, JOIN pour combiner des tables, et GROUP BY pour regrouper des lignes.
• Les sous-requêtes permettent d’imbriquer une requête dans une autre pour filtrer ou calculer des résultats.
• Les contraintes et règles d’intégrité empêchent des incohérences en limitant ce qui peut être stocké ou relié.

💡 Astuce mémo

SELECT = choisir ; JOIN = assembler ; GROUP BY = regrouper.

📖 4. Réseaux, systèmes et cryptographie

🔑 Notions clés & Définitions

• TCP/IP : Suite de protocoles qui organise la communication réseau en couches pour acheminer des données.
• DNS : Système qui traduit des noms de domaine en informations nécessaires pour localiser des ressources réseau.
• Chiffrement asymétrique : Chiffrement utilisant une paire de clés, où une clé sert au chiffrement et l’autre au déchiffrement.
• HTTPS : Version sécurisée d’HTTP qui s’appuie sur des certificats pour établir une connexion chiffrée.

📝 Points essentiels

• HTTP est un protocole utilisé pour échanger des requêtes et réponses web.
• DNS sert à résoudre des noms de domaine vers des informations de localisation réseau.
• Le chiffrement symétrique et le chiffrement asymétrique sont deux familles de méthodes cryptographiques, dont RSA fait partie pour l’asymétrique.
• HTTPS s’appuie sur des certificats pour sécuriser l’échange et établir la confiance.
• Les systèmes incluent des mécanismes comme la gestion des processus, l’ordonnancement et les systèmes de fichiers pour organiser l’exécution et le stockage.

💡 Astuce mémo

DNS = annuaire ; HTTPS = HTTP + confiance via certificats.

📊 Tableaux de synthèse

Parcours de graphes BFS vs DFS

Méthode	Ordre d’exploration	Idée clé
BFS	Par couches	Explore d’abord les voisins proches
DFS	En profondeur	Explore un chemin au maximum avant de revenir

⚠️ Pièges & confusions fréquents

1. Confondre LIFO et FIFO quand on passe d’une pile à une file.
2. Croire qu’un arbre binaire de recherche est un simple arbre binaire sans contrainte d’ordre.
3. Mélanger BFS et DFS : BFS explore par couches, DFS explore en profondeur.
4. Oublier que GROUP BY sert au regroupement avant des calculs agrégés, pas seulement à filtrer.
5. Confondre chiffrement symétrique et asymétrique, ou croire que RSA est le seul mécanisme asymétrique mentionné.

✅ Checklist Examen

1. Savoir distinguer listes, piles (LIFO) et files (FIFO) et décrire leur comportement de base.
2. Savoir expliquer ce qu’est un arbre binaire de recherche et comment l’ordre guide la recherche.
3. Savoir représenter un graphe et choisir BFS ou DFS pour explorer des sommets.
4. Savoir décrire l’objectif des dictionnaires et le rôle d’une table de hachage pour retrouver par clé.
5. Savoir reconnaître et expliquer les schémas de tri fusion, tri rapide et diviser pour régner.
6. Savoir expliquer la recherche dichotomique comme réduction de l’espace de recherche.
7. Savoir expliquer la programmation dynamique comme réutilisation de sous-résultats.
8. Savoir décrire le modèle relationnel et l’algèbre relationnelle comme cadres de requêtes.
9. Savoir associer SELECT, JOIN, GROUP BY et sous-requêtes à leurs rôles dans une requête SQL.
10. Savoir expliquer le rôle de l’intégrité et des contraintes pour préserver la cohérence des données.
11. Savoir relier TCP/IP, HTTP et DNS à leurs fonctions réseau.
12. Savoir distinguer chiffrement symétrique et asymétrique et situer RSA dans l’asymétrique.
13. Savoir expliquer ce que HTTPS apporte via les certificats.
14. Savoir citer des éléments systèmes : gestion des processus, ordonnancement et systèmes de fichiers, ainsi que la gestion des exceptions et la récursivité dans le développement logiciel.