Cours de structures de données et algorithmes

Leçon 1 • Introduction à l'organisation des données

Couvre les types de données primitifs par rapport aux types composites et les concepts de disposition en mémoire. Établit le vocabulaire utilisé tout au long du cours.

Leçon 2 • Tableaux et chaînes de caractères

Examine le stockage en mémoire contiguë via des tableaux et des séquences de caractères. Relie les mécanismes d'indexation aux algorithmes de recherche et de tri ultérieurs.

Leçon 3 • Notions de base de l'analyse de complexité

Introduit les notations Grand-O, Grand-Thêta et Grand-Oméga pour évaluer l'efficacité. Permet aux étudiants de comparer quantitativement les opérations sur les structures de données.

Leçon 4 • Piles et files d'attente

Définit les modes d'accès LIFO et FIFO ainsi que leurs implémentations. Présente des cas d'utilisation concrets comme l'analyse d'expressions et l'ordonnancement.

Leçon 1 • Algorithmes récursifs classiques

Applique la récursivité aux fonctions factorielle, Fibonacci et puissance. Renforce la reconnaissance de formes pour la résolution de problèmes récursifs.

Leçon 2 • Principes fondamentaux de la pensée récursive

Établit les cas de base, les cas récursifs et le comportement de la pile d'appels. Développe l'intuition nécessaire avant d'aborder les algorithmes d'arbres et de graphes.

Leçon 3 • Stratégie diviser pour régner

Formalise la division des problèmes en moitiés indépendantes et la fusion des résultats. Prépare les étudiants au tri par fusion et au tri rapide dans le chapitre suivant.

Leçon 1 • Tris efficaces par comparaison

Implémente le tri par fusion et le tri rapide à l'aide de la méthode diviser pour régner. Analyse les différences de performance entre les deux en moyenne et dans le pire des cas.

Leçon 2 • Algorithmes de tri élémentaires

Couvre le tri à bulles, le tri par sélection et le tri par insertion avec des traces étape par étape. Établit des références de complexité de base pour la comparaison avec les tris avancés.

Leçon 3 • Méthodes de tri sans comparaison

Introduit le tri par comptage, le tri par base et le tri par seaux pour un tri en temps linéaire. Montre quand les données de type entier ou à plage bornée permettent des garanties sous-quadratiques.

Leçon 4 • Sélection d'un algorithme de tri

Guide la prise de décision en fonction de la taille des données, du type et des contraintes de mémoire. Synthétise le contenu du chapitre en un cadre de sélection pratique.

Leçon 1 • Parcours d'un arbre binaire

Implémente les parcours en ordre, préordre, postordre et en largeur. Relie le choix du parcours à des exigences de sortie spécifiques comme la sortie triée.

Leçon 2 • Arbres binaires de recherche

Couvre l'insertion, la suppression et la recherche dans un ABR avec analyse de complexité. Montre comment les invariants d'ordre permettent une consultation efficace.

Leçon 3 • Tas et files de priorité

Construit des tas-min et des tas-max à l'aide d'une représentation par tableau et d'opérations sur les tas. Relie la structure du tas au tri par tas et à l'ordonnancement basé sur les priorités.

Leçon 4 • ABR équilibrés et arbres AVL

Introduit l'équilibrage en hauteur via les rotations AVL pour maintenir les garanties O(log n). Prépare les étudiants aux arbres rouge-noir et aux arbres B dans les sujets avancés.

Leçon 1 • Opérations et analyse des tables de hachage

Implémente les opérations d'insertion, de suppression et de recherche avec une analyse de complexité amortie. Relie les garanties théoriques aux décisions pratiques d'implémentation.

Leçon 2 • Applications avancées du hachage

Explore le hachage cohérent, les filtres de Bloom et les cas d'utilisation du hachage cryptographique. Étend les connaissances sur les tables de hachage aux systèmes distribués et probabilistes.

Leçon 3 • Stratégies de résolution de collisions

Compare les techniques de chaînage et d'adressage ouvert pour gérer les collisions. Analyse l'impact du facteur de charge sur les performances de chaque stratégie.

Leçon 1 • Sujets avancés sur les graphes

Introduit le tri topologique, les composantes fortement connexes et les bases du flot réseau. Prépare les étudiants aux problèmes de conception d'algorithmes dans des contextes compétitifs et appliqués.

Leçon 2 • Représentation et terminologie des graphes

Définit les graphes orientés, non orientés, pondérés et cycliques avec des structures d'adjacence. Établit les choix de représentation qui affectent l'efficacité des algorithmes.

Leçon 3 • Arbres couvrants minimaux

Implémente les algorithmes de Kruskal et de Prim à l'aide de l'union-find et de files de priorité. Relie les concepts d'ACM à la conception de réseaux et aux applications de regroupement.

Leçon 4 • Algorithmes de parcours de graphes

Implémente BFS et DFS avec une gestion explicite des files d'attente et des piles. Applique les parcours à la détection de connectivité et à l'identification de cycles.

Leçon 1 • DP sur les arbres et les graphes

Étend la DP aux structures arborescentes et aux problèmes basés sur les DAG. Relie les connaissances sur le parcours de graphes aux formulations DP par espace d'états.

Leçon 2 • DP sur les séquences et les intervalles

Applique la DP à la plus longue sous-séquence croissante et aux problèmes d'ordonnancement par intervalles. Étend la reconnaissance de formes aux optimisations par deux pointeurs et recherche binaire.

Leçon 3 • Principes de la DP et mémorisation

Définit les sous-problèmes qui se chevauchent et la sous-structure optimale comme prérequis à la DP. Introduit la mémorisation descendante comme première stratégie d'implémentation.

Leçon 4 • Tabulation ascendante

Convertit les solutions mémorisées en approches itératives de remplissage de tableau. Démontre l'optimisation de l'espace en réduisant les dimensions du tableau.

Leçon 1 • Structures trie et suffixe

Implémente des arbres préfixes pour la recherche rapide de chaînes et l'auto-complétion. Introduit les tableaux de suffixes pour la reconnaissance de motifs dans de grands corpus de texte.

Leçon 2 • Arbres de segments et arbres de Fenwick

Construit des structures de requête de plage et de mise à jour ponctuelle pour des opérations d'intervalle efficaces. Compare les arbres de segments et les arbres de Fenwick selon la complexité d'implémentation et le cas d'utilisation.

Leçon 3 • Analyse amortie et sujets avancés

Applique les méthodes agrégée, comptable et du potentiel pour analyser les séquences de structures de données. Introduit les listes à sauts et les structures auto-ajustables comme alternatives avancées.

Leçon 4 • Union-find et ensembles disjoints

Implémente l'union par rang et la compression de chemin pour des opérations en temps quasi constant. Applique l'union-find à la connectivité dynamique et à l'ACM de Kruskal.