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é.
Ce cours pose les bases de l'IA par apprentissage statistique : comment relier une sortie à des entrées à l'aide d'un modèle, en tenant compte d'une part d'erreur inhérente aux données, et distinguer prédiction / interprétation. Il présente les grandes familles (supervisé/non supervisé, régression/classification) et annonce des méthodes comme k-NN et k-means. Enfin, il aborde l'évaluation et la mise en pratique : fonctions de perte, surapprentissage, métriques (MSE, accuracy…), séparation train/test et normalisation.
Ce cours présente le principe du KNN (vote local des k plus proches voisins) en le reliant au classificateur de Bayes comme référence théorique. Il étudie l'influence de k (frontière, biais–variance, sur/sous-apprentissage) via l'analyse des erreurs d'entraînement et de test. Enfin, il détaille les mesures de distance/similarité (L1/L2/L∞, cosinus/TF-IDF, etc.) et propose des algorithmes/implémentations Python pour classification et régression.
TD de Denis DEFAUCHY (cpge-sii.com). Ce TD met en œuvre pas à pas un KNN pour reconnaître automatiquement des panneaux à partir d'une base d'images d'apprentissage prétraitées. On y construit la représentation des images (vecteurs RGB), on calcule les distances euclidiennes, on extrait les k plus proches voisins et on décide par vote majoritaire. Enfin, on évalue l'algorithme via une matrice de confusion et une étude de l'influence de k (de 1 à 5) sur la qualité de reconnaissance.
Ce TD (basé sur le sujet du concours CCINP-PSI 2023) applique l'algorithme KNN à un problème de reconnaissance de caractères. Il guide l'implémentation complète : lecture et structuration des données de référence, calcul des distances entre images, puis sélection efficace des K plus proches voisins sans trier toutes les distances. Enfin, il demande d'évaluer les performances via matrice de confusion et taux de réussite, et d'interpréter l'influence de la base d'apprentissage (base de référence vs base enrichie) sur la qualité de reconnaissance.
Aucune ressource ne correspond à votre recherche.