Structures de données avancées

Description du cours

Vous vous êtes déjà demandé.e comment fonctionnent les listes en python, les tableaux associatifs en php ? Dans ce cours, nous allons étudier les mécanismes à l’oeuvre dans les structures apparaissant dans vos langages de programmation préférés. Plus précisément, vous allez étudier et coder, en commençant de zéro,

• les tableaux dynamiques,
• les tables de hachages,
• les files de priorité,
• et d’autres structures un peu moins connues, comme l’Union Find ! En comprenant le fonctionnement de ces structures de données, vous serez en mesure de sélectionner la plus appropriée selon la situation, devenant ainsi une codeuse ou un codeur plus aguerri. Notamment, nous allons voir que des problèmes algorithmiques se résolvent de manière plus ou moins efficaces selon la structure choisie. En TD, nous essaierons de comprendre d’un point de vue théorique pourquoi les structures vues en cours sont efficaces. (La notion clé derrière s’appelle la complexité amortie.) De plus, nous nous demanderons comment choisir la structure de données la plus approprié selon un problème algorithmique donné. En TP, nous allons coder, en C, chacune des structures du cours.

Modalités d'évaluation

Session 1 :

• Contrôle terminal (CT1) : documents non autorisées. La moitié du CT portera sur les problèmes vus en TD (comprendre les notions du cours, trouver la bonne structure pour un problème algorithmique donnée). L’autre moitié consistera à réécrire ce que vous avez fait en TP.
• Note finale : celle du CT1.

Session 2 :

• Contrôle terminal (CT2) : pareil que CT1.
• Note finale : celle du CT2.