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.
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).
L'objectif de ce TD est de mettre en oeuvre l'algorithme de Dijkstra en utilisant les tas comme structure de données.
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).
Exercice sur les notions de schéma relationnel, clés primaires et étrangère.
Cette base « Streaming musical » modélise une plateforme d'écoute. Les entités principales sont utilisateurs, artistes, albums et pistes.
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.
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 étrangères, cardinalités en notation Merise, multiplicités en notation UML, auto-association et table de liaison (décomposition *-*).
TD basé sur (PT-INFO-MOD-2025)
TD basé sur (CCINP-PSI-INFO-2025)
TD basé sur (CCINP-PSI-INFO-2024)
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.
Quelques rappels sur les dictionnaires en Python et leur utilisation.
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 %).
TD de Denis DEFAUCHY (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.
TD de Denis DEFAUCHY (cpge-sii.com). Exercices sur la manipulation des dictionnaires (inversion, comptage, chemin).
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.
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.
Nous allons introduire dans ce cours une nouvelle méthode de programmation : la programmation dynamique. C'est une technique particulièrement puissante, car elle conduit souvent à des solutions efficaces. Ici, nous allons étudier un algorithme faisant partie des « grands classiques » afin d'apprendre le fonctionnement de cette méthode.
Notre deuxième étude de cas concerne le problème de partitionnement d'un tableau d'entiers positifs. Nous allons construire la solution du problème par programmation dynamique.
Mise en pratique de la partition équilibrée d'un tableau d'entiers positifs.
Notre troisième étude de cas concerne le problème du sac à dos. Nous allons construire la solution du problème par programmation dynamique.
Mise en pratique du problème du sac à dos (énoncé + scripts Python + correction).
Étude de la plus longue sous-suite commune et de sa résolution par programmation dynamique.
Mise en pratique de la plus longue sous-suite commune (énoncé + scripts Python + correction).
Étude de la distance de levenshtein et de sa résolution par programmation dynamique.
Mise en pratique de la distance de Levenshtein (énoncé + scripts Python + correction).
Présentation de l'algorithme de Bellman-Ford pour le calcul des plus courts chemins avec poids négatifs.
Mise en pratique de l'algorithme de Bellman-Ford (énoncé + scripts Python + correction).
Présentation de l'algorithme de Floyd-Warshall pour le calcul des plus courts chemins entre toutes les paires de sommets.
Mise en pratique de l'algorithme de Floyd-Warshall (énoncé + scripts Python + correction).
Ce TD, basé sur le sujet de concours "Jeu de Rockse" (X/ENS 2025), présente la modélisation du problème, l'évaluation de chemins et la comparaison d'approches gloutonnes. Il aboutit à une solution optimale par programmation dynamique, en tenant compte de bonus qui modifient l'ensemble des sauts disponibles, avec jeux de tests progressifs et analyse de complexité.
Aucune ressource ne correspond à votre recherche.