Cours d'algorithmique et structures de données

Leçon 1 • Tables de hachage et bases du hachage

Présente le stockage clé-valeur via des fonctions de hachage et des tableaux de buckets. Prépare les étudiants à la gestion des collisions et à l'analyse des performances en moyenne.

Leçon 2 • Tableaux et tableaux dynamiques

Présente le stockage mémoire contigu et l'accès par index. Relie les tableaux statiques aux stratégies de redimensionnement dynamique utilisées dans les implémentations réelles.

Leçon 3 • Listes chaînées et chaînes de pointeurs

Enseigne le stockage basé sur les nœuds à l'aide de pointeurs ou de références. Compare les listes chaînées aux tableaux pour clarifier les compromis en insertion et en parcours.

Leçon 4 • Mémoire, variables et types de données

Couvre la façon dont les données sont stockées en mémoire et en quoi les types primitifs diffèrent. Établit le modèle mental nécessaire pour toute analyse ultérieure des structures.

Leçon 1 • Techniques de benchmark empiriques

Fait le pont entre l'analyse théorique et les expériences de temps d'exécution mesurées. Les étudiants conçoivent des benchmarks contrôlés pour valider ou contester les prédictions théoriques.

Leçon 2 • Complexité spatiale et compromis

Analyse l'utilisation de l'espace auxiliaire parallèlement aux coûts temporels. Met en évidence les compromis classiques temps-espace qui guident la sélection pratique des algorithmes.

Leçon 3 • Relations de récurrence

Présente les récurrences comme un outil d'analyse des algorithmes récursifs. Couvre le théorème maître et les méthodes de substitution pour les résoudre.

Leçon 4 • Big-O, Big-Theta et Big-Omega

Définit les notations asymptotiques et leur signification mathématique. Fournit le vocabulaire utilisé tout au long du cours pour comparer les performances des algorithmes.

Leçon 1 • Tris par comparaison élémentaires

Couvre le tri à bulles, le tri par sélection et le tri par insertion avec une analyse complète de la complexité. Établit une intuition de base avant d'introduire des approches plus efficaces.

Leçon 2 • Tris diviser-pour-régner

Enseigne le tri fusion et le tri rapide à l'aide de la décomposition récursive. Relie l'analyse de récurrence du chapitre 2 aux performances réelles de tri.

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

Synthétise toutes les connaissances sur le tri dans un cadre de décision. Les étudiants associent le choix de l'algorithme à la taille de l'entrée, à la distribution des données et aux contraintes de mémoire.

Leçon 4 • Algorithmes de tri en temps linéaire

Présente le tri par comptage, le tri par base et le tri par bucket comme des méthodes sans comparaison. Clarifie les conditions dans lesquelles un temps linéaire est réalisable.

Leçon 1 • Mémorisation et DP descendante

Étend la récursion avec la mise en cache des résultats pour éliminer les calculs redondants. Sert de pont vers le chapitre complet sur la programmation dynamique qui suit.

Leçon 2 • Recherche linéaire et binaire

Compare la recherche séquentielle et la recherche par division sur des données triées et non triées. Établit les préconditions et les garanties de complexité de chaque approche.

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

Formalise le paradigme diviser-régner-combiner au-delà du tri. Les étudiants l'appliquent à des problèmes comme le sous-tableau maximal et la paire de points la plus proche.

Leçon 4 • Techniques de retour sur trace (backtracking)

Introduit la recherche systématique avec élagage via le retour sur trace. Relie les arbres d'appels récursifs aux problèmes de satisfaction de contraintes et de combinatoire.

Leçon 1 • Fondamentaux de l'arbre binaire

Définit la terminologie des arbres, les relations entre nœuds et les propriétés structurelles. Ancre tous les algorithmes d'arbres ultérieurs dans un vocabulaire et un modèle mental partagés.

Leçon 2 • Arbres rouge-noir et arbres B

Couvre les règles de coloration rouge-noir et la structure des arbres B multi-voies. Relie ces structures à l'indexation de bases de données et aux cas d'usage de systèmes de fichiers.

Leçon 3 • Arbres AVL et rotations

Présente les arbres AVL équilibrés en hauteur et les quatre cas de rotation. Les étudiants implémentent un auto-équilibrage pour garantir des opérations en O(log n).

Leçon 4 • Algorithmes de parcours d'arbres

Couvre les parcours en ordre, préordre, postordre et en largeur. Relie le choix du parcours à des exigences de sortie spécifiques et aux algorithmes en aval.

Leçon 1 • Parcours en profondeur (DFS)

Implémente DFS de manière récursive et itérative avec les temps de découverte et de fin. Relie DFS à la détection de cycles, au tri topologique et aux composantes connexes.

Leçon 2 • Tri topologique

Obtient un ordre topologique à partir des temps de fin de DFS et de l'algorithme de Kahn. Applique l'ordre à la résolution de dépendances et aux problèmes d'ordonnancement de tâches.

Leçon 3 • Terminologie et représentations des graphes

Définit les sommets, les arêtes, les graphes orientés vs. non orientés et pondérés. Compare les représentations par matrice d'adjacence et par liste d'adjacence en termes de coût d'espace et d'accès.

Leçon 4 • Parcours en largeur (BFS)

Implémente BFS à l'aide d'une file et analyse sa complexité O(V+E). Applique BFS à la recherche du plus court chemin dans les graphes non pondérés.

Leçon 1 • Arbres couvrants minimum : Kruskal

Construit des arbres couvrants minimum en ajoutant gloutonnement les arêtes de poids minimum à l'aide de l'union-find. Analyse la justesse via la propriété de coupe et la propriété de cycle des arbres couvrants minimum.

Leçon 2 • Algorithme du plus court chemin de Dijkstra

Implémente Dijkstra à l'aide d'une file de priorité par tas-min avec une complexité O((V+E) log V). Couvre la preuve de justesse via l'invariant de relâchement glouton.

Leçon 3 • Plus courts chemins entre toutes les paires

Résout les plus courts chemins entre chaque paire de sommets à l'aide de Floyd-Warshall. Analyse la formulation par programmation dynamique en O(V³) et la reconstruction du chemin.

Leçon 4 • Arbres couvrants minimum : Prim

Fait croître un arbre couvrant minimum à partir d'un sommet semence à l'aide d'une file de priorité dans l'algorithme de Prim. Compare Prim à Kruskal en fonction de la densité du graphe et de la complexité d'implémentation.

Leçon 1 • Problèmes DP 1D classiques

Résout Fibonacci, la montée d'escaliers et le rendu de monnaie à l'aide de tables DP 1D. Développe l'intuition du remplissage de table avant de passer aux formulations 2D.

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

Applique la DP aux structures arborescentes et aux DAG pour des problèmes d'optimisation avancés. Couvre la DP sur arbre pour le diamètre, les ensembles indépendants et la DP sur les chemins d'un DAG.

Leçon 3 • Problèmes de sac à dos et de sous-ensemble

Résout le sac à dos 0/1, le sac à dos illimité et la somme de sous-ensemble avec des tables DP. Relie ces problèmes à l'allocation de ressources et aux problèmes de décision de faisabilité.

Leçon 4 • Problèmes DP 2D classiques

Étend la DP aux tables bidimensionnelles pour les problèmes de chaînes et de grilles. Couvre la distance d'édition, la plus longue sous-séquence commune et le comptage de chemins dans une grille avec des dérivations complètes de récurrence.

Leçon 5 • Optimisation de l'espace en DP

Réduit l'espace de la table DP de O(n²) à O(n) ou O(1) à l'aide de tableaux roulants. Applique l'optimisation de l'espace au sac à dos, à la plus longue sous-séquence commune et à la distance d'édition.