Cours de structures de données et algorithmes

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

Couvre les types de données primitifs et composites ainsi que 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 contigu en mémoire via les tableaux et les séquences de caractères. Relie les mécanismes d'indexation aux futurs algorithmes de recherche et de tri.

Leçon 3 • Bases de l'analyse de complexité

Présente 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. Démontre des cas d'usage réels tels que 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 motifs pour la résolution de problèmes récursifs.

Leçon 2 • 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 sur les arbres et les 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 pour le tri fusion et le tri rapide dans le chapitre suivant.

Leçon 1 • Tris efficaces par comparaison

Implémente le tri fusion et le tri rapide en utilisant la stratégie 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 les tris à bulles, par sélection et par insertion avec des traces pas à pas. É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

Présente le tri par comptage, le tri par base et le tri par compartiments pour un tri en temps linéaire. Montre quand des données entières ou à plage bornée permettent des garanties sous-quadratiques.

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

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

Leçon 1 • Parcours d'arbres binaires

Implémente les parcours en ordre infixe, préfixe, postfixe et en largeur d'abord. Relie le choix du parcours à des besoins de sortie spécifiques tels que 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é. Démontre comment les invariants d'ordre permettent une recherche efficace.

Leçon 3 • Tas et files de priorité

Construit des tas minimaux et maximaux en utilisant une représentation par tableau et des opérations de 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

Présente l'équilibrage en hauteur via les rotations AVL pour maintenir les garanties O(log n). Prépare les étudiants pour les arbres rouge-noir et les 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'usage 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

Présente le tri topologique, les composantes fortement connexes et les bases du flot de réseau. Prépare les étudiants pour les 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 en utilisant l'union-find et les files de priorité. Relie les concepts d'ACM à la conception de réseaux et aux applications de clustering.

Leçon 4 • Algorithmes de parcours de graphes

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

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

Étend la PD aux structures arborescentes et aux problèmes basés sur les DAG. Relie la connaissance du parcours de graphes aux formulations de PD sur les espaces d'états.

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

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

Leçon 3 • Principes de la PD et mémoïsation

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

Leçon 4 • Tabulation ascendante

Convertit les solutions mémoïsées en approches de remplissage de tableaux itératives. Démontre l'optimisation de l'espace en réduisant les dimensions des tableaux.

Leçon 1 • Trie et structures de suffixes

Implémente des arbres préfixes pour la recherche rapide de chaînes de caractères et l'autocomplétion. Introduit les tableaux de suffixes pour la recherche 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 en termes de complexité d'implémentation et de cas d'usage.

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

Applique les méthodes globale, comptable et potentielle pour analyser des 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 à temps quasi constant. Applique l'union-find à la connectivité dynamique et à l'ACM de Kruskal.