Formation Python DSA

Leçon 1 • Fonctions et portée

Définit les fonctions réutilisables, les arguments par défaut et les règles de portée des variables. Les fonctions sont l'unité principale d'implémentation d'algorithmes dans ce cours.

Leçon 2 • Présentation des collections intégrées

Passe en revue les listes, les tuples, les dictionnaires et les ensembles avec leurs complexités temporelles. Fournit les connaissances pratiques sur les conteneurs nécessaires avant que les structures personnalisées ne soient construites.

Leçon 3 • Modules, bibliothèques et entrées/sorties

Présente l'importation de modules, l'utilisation de la bibliothèque standard et la lecture d'entrées pour des problèmes de style compétitif. Prépare les étudiants aux flux de travail structurés de résolution de problèmes.

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

Définit les trois notations asymptotiques et leur signification mathématique. Les étudiants appliquent chaque notation pour classifier précisément le comportement des algorithmes.

Leçon 2 • Mesure de la performance des algorithmes

Présente les concepts de mesure du temps d'exécution et pourquoi l'analyse théorique surpasse le simple benchmarking. Établit l'état d'esprit analytique pour chaque chapitre suivant.

Leçon 3 • Analyse des boucles et de la récursivité

Enseigne l'analyse systématique des boucles imbriquées et des appels récursifs. Directement applicable à chaque algorithme de tri et de recherche des chapitres suivants.

Leçon 1 • Pointeur double et fenêtre glissante

Présente les motifs de pointeur double et de fenêtre glissante pour des solutions O(n) sur des données triées ou séquentielles. Réduit considérablement les approches O(n²) par force brute.

Leçon 2 • Tables de hachage et gestion des collisions

Explique la conception de fonctions de hachage, la résolution de collisions et les mécanismes internes du dictionnaire Python. Les étudiants implémentent des tables de hachage personnalisées et résolvent des problèmes de recherche en O(1).

Leçon 3 • Techniques de manipulation de tableaux

Couvre les opérations sur place, les sommes préfixes et les tableaux de différences pour les requêtes de plage. Ces motifs apparaissent dans la majorité des problèmes de type entretien.

Leçon 1 • File, deque et file de priorité

Implémente des files FIFO, des deques à double extrémité et des files de priorité basées sur un tas. Prépare les étudiants aux problèmes d'algorithme BFS et d'ordonnancement.

Leçon 2 • Listes chaînées simples et doublement chaînées

Construit des classes de listes chaînées basées sur des nœuds avec insertion, suppression et parcours. Établit les compétences de manipulation de pointeurs utilisées plus tard dans les arbres et les graphes.

Leçon 3 • Implémentation et applications de la pile

Implémente des piles en utilisant des listes et des listes chaînées, puis les applique à des problèmes d'analyse et d'évaluation. Les piles sous-tendent la simulation de récursivité et le backtracking.

Leçon 1 • Notions fondamentales de la récursivité

Définit les cas de base, les appels récursifs et le comportement de la pile d'appels avec traçage visuel. Une conception correcte de la récursivité est un prérequis pour le diviser pour régner et le backtracking.

Leçon 2 • Tri par diviser pour régner

Implémente le tri fusion et le tri rapide avec une analyse complète des récurrences. Les étudiants comprennent les stratégies de partition et les compromis de stabilité.

Leçon 3 • Algorithmes de recherche

Implémente la recherche binaire et ses variantes sur des tableaux triés et des espaces de réponses. La recherche binaire sur la réponse est un motif clé pour les problèmes d'optimisation.

Leçon 1 • Motifs de problèmes d'arbres

Couvre les problèmes de somme de chemin, d'ancêtre commun le plus bas et de diamètre en utilisant la récursivité. Ces motifs apparaissent fréquemment dans les entretiens techniques et la conception de systèmes.

Leçon 2 • Tries et arbres de segments

Construit des tries de préfixes pour la recherche de chaînes et des arbres de segments pour les requêtes de plage. Ces arbres spécialisés résolvent des problèmes que les BST et les tas ne peuvent pas traiter efficacement.

Leçon 3 • Arbres équilibrés et tas

Présente les concepts d'équilibrage des arbres AVL et rouge-noir, ainsi que la structure du tas. Les étudiants comprennent quand les arbres auto-équilibrés sont nécessaires pour des garanties de performance.

Leçon 4 • Notions fondamentales des arbres binaires

Définit la terminologie des arbres, la structure des nœuds et les ordres de parcours récursifs. Les motifs de parcours sont le fondement de tous les algorithmes basés sur les arbres.

Leçon 1 • Tri topologique et détection de cycle

Applique l'algorithme de Kahn et le tri topologique basé sur DFS aux DAG. La détection de cycle et l'ordonnancement sont essentiels pour les problèmes de résolution de dépendances.

Leçon 2 • Arbres couvrants minimaux et Union-Find

Implémente les algorithmes de Kruskal et de Prim avec la structure Union-Find. Ces outils résolvent efficacement des problèmes de connectivité réseau et de clustering.

Leçon 3 • Algorithmes de plus court chemin

Implémente Dijkstra, Bellman-Ford et Floyd-Warshall pour les graphes pondérés. Les étudiants sélectionnent le bon algorithme en fonction des propriétés et contraintes du graphe.

Leçon 4 • Parcours BFS et DFS

Implémente le BFS itératif et le DFS récursif avec suivi des visites. Ces deux parcours sous-tendent presque tous les algorithmes de graphes de ce chapitre.

Leçon 1 • Motifs classiques de problèmes de DP

Résout les problèmes de sac à dos, de plus longue sous-séquence et de rendu de monnaie comme gabarits canoniques de DP. La maîtrise de ces gabarits accélère la résolution de nouveaux problèmes de DP.

Leçon 2 • Fondements de la DP et mémoïsation

Définit les sous-problèmes qui se chevauchent et la sous-structure optimale comme prérequis de la DP. La mémoïsation descendante convertit des solutions récursives en solutions DP efficaces.

Leçon 3 • Tabulation et optimisation spatiale

Construit des tables DP ascendantes et réduit l'espace en utilisant des tableaux roulants. La DP optimisée en espace est essentielle pour les contraintes de grandes entrées dans les problèmes compétitifs.

Leçon 4 • DP d'intervalle et de grille

Applique la DP à la fusion d'intervalles et aux problèmes de chemin dans une grille avec des espaces d'état 2D. Ces motifs étendent les compétences en DP aux types de problèmes matriciels et basés sur des plages.