Formation Python DSA

Leçon 1 • Fonctions et Portée

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

Leçon 2 • Aperçu 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 de construire des structures personnalisées.

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 type compétitif. Prépare les étudiants à des flux de travail structurés de résolution de problèmes.

Leçon 1 • Big-O, Big-Thêta et Big-Oméga

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

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 est supérieure au seul benchmarking. Établit l'état d'esprit analytique pour chaque chapitre qui suit.

Leçon 3 • Analyse des Boucles et de la Récursion

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

Leçon 1 • Double Pointeur et Fenêtre Glissante

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

Leçon 2 • Tables de Hachage et Gestion des Collisions

Explique la conception de la fonction de hachage, la résolution des collisions et le fonctionnement interne des dictionnaires 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 en place, les sommes de préfixes et les tableaux de différence 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 files doublement terminées (deques) et des files de priorité basées sur des tas. Prépare les étudiants aux problèmes d'algorithmes BFS et d'ordonnancement.

Leçon 2 • Listes Chaînées Simples et Doubles

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 de Pile et Applications

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

Leçon 1 • Fondamentaux de la Récursion

Définit les cas de base, les appels récursifs et le comportement de la pile d'appels avec un traçage visuel. La conception correcte de la récursion 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 par 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 sur les Arbres

Couvre les problèmes de somme de chemins, de plus bas ancêtre commun et de diamètre en utilisant la récursion. 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 gérer 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 • Fondamentaux 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 la base 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 les problèmes de connectivité réseau et de clustering.

Leçon 3 • Algorithmes de Plus Court Chemin

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

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 sur les graphes de ce chapitre.

Leçon 1 • Motifs Classiques de Problèmes de Programmation Dynamique

Résout les problèmes du sac à dos, de la plus longue sous-séquence et du rendu de monnaie comme modèles canoniques de programmation dynamique. Maîtriser ces modèles accélère la résolution de nouveaux problèmes de programmation dynamique.

Leçon 2 • Fondements de la Programmation Dynamique et Mémorisation

Définit les sous-problèmes qui se chevauchent et la sous-structure optimale comme prérequis de la programmation dynamique. La mémorisation descendante convertit les solutions récursives en solutions efficaces de programmation dynamique.

Leçon 3 • Tabulation et Optimisation Spatiale

Construit des tables de programmation dynamique ascendantes et réduit l'espace à l'aide de tableaux glissants. La programmation dynamique optimisée en espace est cruciale pour les contraintes de grandes entrées dans les problèmes de compétition.

Leçon 4 • Programmation Dynamique sur Intervalles et Grilles

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