1. Quelques rappels de première année (et nouvelles notions) sur les tris, les structures et les graphes
| 1. Cours - Algorithmes de tri et structures de données | Ce cours a pour objectif de réviser les structures et algorithmes de recherche étudiés en première année et d’introduire de nouvelles structures de données qui jouent un rôle essentiel dans le fonctionnement interne des bases de données. | |
| 2. Cours - Algorithme de Dijkstra avec les tas | L’objectif de ce cours est d’introduire l’algorithme de Dijkstra en utilisant les tas comme
structure de données. Cela permettra d’accélérer le temps d’exécution de l’algorithme puisque les tas sont une structure de données possédant une opération de recherche du minimum s’exécutant en O(log n), alors que la recherche d’un minimum avec les listes ou les dictionnaires se fait en O(n). |
|
| 3. TD - Algorithme de Dijkstra avec les tas | L’objectif de ce TD est de mettre en oeuvre l’algorithme de Dijkstra en utilisant les tas comme structure de données. |
2. Bases de données
| 1. Cours - Bases de données relationnelles et langage SQL | Cours sur les bases de données : modèle relationnel, langage SQL, modèle de données et SQL (cardinalités - mutliplicités, décomposition). | Logiciel : https://sqlitebrowser.org/ Bases de données (format .db) utilisées dans le cours : festival.db et playlists.db |
| 2. Exercice - Modélisation relationnelle | Exercice sur les notions de schéma relationnel, clés primaires et étrangère. | |
| 3. TD_Musique - Commandes SQL | Cette base « Streaming musical » modélise une plateforme d’écoute. Les entités principales sont utilisateurs, artistes, albums et pistes. | |
| 4. TD_RPG - Commandes SQL | La base modélise un MMORPG (jeu de rôle en ligne) : des joueurs réalisent des quêtes données par des PNJ , les quêtes se déroulent dans des zones avec un niveau requis, les joueurs peuvent appartenir à une guilde. Chaque participation à une quête est enregistrée avec le succès/échec, la durée et les dates. | |
| 5. Exercice - Modélisation relationnelle et cardinalité | On s’intéresse dans cet exercice à une plateforme de covoiturage où certains utilisateurs publient des trajets comme conducteurs. Thèmes : schéma relationnel, clés primaires et étangères, cardinalités en notaiton Merise, multiplicités en notation UML, auto-association et table de liaison (décomposition *-*). |
Correction |
| 6. TD_Concours - CCMP2025 | TD basé sur (CCMP-MP-PC-PSI-2025) |
|
| 7. TD_Concours - CCINP2025 | TD basé sur (CCINP-MP-2025) | |
| 8. TD_Concours - PT_INFOMOD2025 | TD basé sur (PT-INFO-MOD-2025) |
|
| 9. TD_Concours - CCINP-PSI-INFO | TD basé sur (CCINP-PSI-INFO-2025) | |
| 10. TD_Concours - CCINPT-PSI-INFO | TD basé sur (CCINP-PSI-INFO-2024) | |
| 11. TD SQL1 | TD de Bernard SALAMITO (commandes de base sans jointure) | world.db |
| 12. TD SQL2 | TD de Bernard SALAMITO (jointures, group-by, having, ...) | world.db |
| 13. TD SQL3 | TD de Bernard SALAMITO (cas de base, jointures, group-by, having, ...) |
mondial.db |
3. Dictionnaires et hachage
| 1. Cours - Tables et fonctions de hachage | Dans ce chapitre, nous allons étudier les tables de hachage, des structures pensées pour des recherches ultra-rapides sur un ensemble qui évolue, avec trois opérations phares : la recherche, l’insertion et la suppression. Nous verrons également comment les dictionnaires Python implémentent les tables de hachage. |
|
| 2. TD1 - Hachage polynomial | Dans ce TD, vous allez concevoir vos propres tables de hachage afin de comprendre concrètement comment un hachage polynomial répartit des chaînes de caractères et pourquoi de « mauvais » choix de paramètres (base, taille de table paire ou puissance de 2) peuvent cibler des régularités dans les données et des emplacements vides. Vous implémenterez la stratégie par chaînage en instrumentant chaque opération (insertion, recherche, suppression). Vous mettrez également en oeuvre une politique de redimensionnement automatique (seuil 70 %). |
Fichiers à décompresser : TD1_sources.rar Correction : TD1_correction.rar |
| 3. TD2 - Hachage | TD de Denis DEFAUCHY (https://www.cpge-sii.com/) et Bernard SALAMITO dont le thème est d'implémenter une table de hachage séparée avec chainage linéaire. | Correction |
| 4. TD3 - Dictionnaires | TD de Denis DEFAUCHY (https://www.cpge-sii.com/). Exercices sur la manipulation des dictionnaires (inversion, comptage, chemin) | Fichier ressource : Dictionnaires - Dico.py |
| 5. TD_Concours - Hachage ADN | TD basé sur (CCINP-TSI-Info 2020) Le thème traité est la recherche d'un motif dans une molécule d'ADN fondée sur l’utilisation d’une fonction de hachage, comme dans l’algorithme de Karp–Rabin. |
Correction |
| 6. TD_Concours - Rush Hour | TD basé sur (Centrale-Supélec MPI 2025) Le jeu Rush Hour est un casse-tête où l’on doit faire sortir une voiture d’un parking encombré. On modélise le problème par un graphe dynamique dont chaque sommet est un état du plateau, mémorisé dans une table de hachage, puis on le résout d’abord avec un BFS dynamique (coût 1 par coup), puis avec Dijkstra dynamique quand les déplacements ont des coûts différents. |
Fichiers à décompresser : TD6_sources.rar Correction Python : TD6_correction Correction questions du TD : Correction |
(alexandre-antoi.bourrieau@ac-creteil.fr)