Cours d'algorithmes et structures de données en Python

Leçon 1 • Fonctions et portée

Définit des fonctions réutilisables avec paramètres, valeurs de retour et règles de portée. Prépare les étudiants à encapsuler la logique DSA dans des unités de test propres.

Leçon 2 • Contrôle de flux et itération

Enseigne les branchements if/elif/else, les boucles for et while, et les instructions de contrôle de boucle. Permet aux étudiants d'exprimer des logiques algorithmiques en Python.

Leçon 3 • Gestion des erreurs et débogage

Présente les exceptions, les blocs try/except et les outils de débogage. Équipe les étudiants pour écrire du code robuste et diagnostiquer les échecs dans des programmes complexes.

Leçon 4 • Types de données de base et variables

Couvre les entiers, les flottants, les chaînes, les booléens et le transtypage. Fournit les primitives de données utilisées dans toutes les implémentations d'algorithmes à venir.

Leçon 1 • Itérateurs, générateurs et évaluation paresseuse

Explique le protocole d'itérateur, les fonctions génératrices et yield. Permet un parcours efficace en mémoire de grands ensembles de données dans les problèmes DSA.

Leçon 2 • Listes et tuples en profondeur

Explore l'indexation, le tranchage, la mutation et l'immutabilité des tuples. Ces types de séquences sous-tendent les structures de données basées sur des tableaux abordées plus tard.

Leçon 3 • Dictionnaires et ensembles

Couvre le stockage basé sur les tables de hachage, les opérations clé-valeur et l'algèbre des ensembles. Soutient directement les implémentations de tables de hachage et de graphes d'adjacence.

Leçon 4 • Compréhensions de listes et de dictionnaires

Enseigne la syntaxe concise de compréhension pour filtrer et transformer les collections. Réduit le code standard dans les implémentations d'algorithmes tout au long du cours.

Leçon 1 • Introduction à l'analyse d'algorithmes

Définit l'exactitude, l'efficacité et le besoin d'analyse formelle des algorithmes. Établit l'état d'esprit analytique appliqué à chaque structure de données et algorithme à venir.

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

Formalise la notation asymptotique et les classes de complexité courantes. Fournit le vocabulaire utilisé pour décrire chaque algorithme dans les chapitres suivants.

Leçon 3 • Analyse des boucles et des appels récursifs

Enseigne le comptage d'étapes pour les boucles et les relations de récurrence pour la récursivité. Prépare directement les étudiants à analyser les algorithmes de tri et les arbres.

Leçon 4 • Profilage du code Python

Utilise timeit, cProfile et memory_profiler pour mesurer le rendement réel. Relie la complexité théorique au comportement d'exécution Python mesurable.

Leçon 1 • Comparaison de complexité des structures linéaires

Compare la complexité temporelle et spatiale de toutes les structures linéaires étudiées. Permet une sélection éclairée des structures pour les problèmes de conception d'algorithmes.

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

Construit des classes Node et des opérations de liste incluant insertion, suppression et parcours. Introduit la pensée basée sur les pointeurs essentielle pour les arbres et les graphes.

Leçon 3 • Piles : implémentation et applications

Implémente des piles à l'aide de listes et de listes chaînées, puis les applique à des problèmes réels. Démontre la sémantique LIFO utilisée en récursivité, analyse syntaxique et retour sur trace.

Leçon 4 • Files d'attente, deques et files de priorité

Couvre les files FIFO, les deques doublement terminées et les files de priorité basées sur des tas. Prépare les étudiants aux problèmes BFS, d'ordonnancement et d'algorithmes gloutons.

Leçon 1 • Algorithmes de tri quadratiques

Implémente les tris à bulles, par sélection et par insertion avec une analyse étape par étape. Fournit la base O(n²) par rapport à laquelle les tris plus rapides sont mesurés.

Leçon 2 • Algorithmes de recherche

Implémente la recherche linéaire et la recherche binaire avec des preuves de complexité. Relie la recherche aux données triées et aux problèmes d'entrevue réels.

Leçon 3 • Notions fondamentales sur la récursivité

Définit les cas de base, les cas récursifs et la pile d'appels. Construit le modèle mental requis pour le parcours d'arbres et les algorithmes diviser-pour-régner.

Leçon 4 • Tri en temps linéaire et hybride

Couvre le tri par comptage, le tri par base et le Timsort utilisé dans la fonction de tri intégrée de Python. Élargit la boîte à outils des étudiants au-delà du tri par comparaison.

Leçon 1 • Arbres binaires de recherche

Implémente l'insertion, la recherche et la suppression dans un ABR avec une analyse moyenne O(log n). Démontre le stockage et la récupération de données ordonnées à l'aide d'une structure arborescente.

Leçon 2 • Tries et arbres de préfixes

Construit un trie pour l'insertion de chaînes, la recherche et la correspondance de préfixes. Permet des solutions efficaces de correction automatique et de recherche dans un dictionnaire.

Leçon 3 • Arbres binaires et parcours

Définit la terminologie des arbres et implémente les parcours en ordre, préordre et postordre. Établit le modèle de parcours récursif utilisé dans tous les algorithmes d'arbres.

Leçon 4 • Tas et opérations sur les tas

Construit un tas-max et un tas-min, implémente l'entassement et le tri par tas. Soutient directement les implémentations de files de priorité et d'algorithmes gloutons.

Leçon 1 • Problèmes avancés sur les graphes

Couvre les composantes fortement connexes, la vérification de bipartition et les bases du flux réseau. Étend les compétences en graphes à des catégories de problèmes complexes du monde réel.

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

Définit les graphes orientés, non orientés, pondérés et cycliques avec des représentations par listes et matrices d'adjacence. Établit la base de toutes les implémentations d'algorithmes de graphes.

Leçon 3 • Algorithmes de plus court chemin

Implémente les algorithmes de Dijkstra et Bellman-Ford pour les graphes pondérés. Équipe les étudiants pour résoudre des problèmes de routage et de minimisation de coûts.

Leçon 4 • Arbres couvrants minimaux

Implémente les algorithmes de Kruskal et Prim en utilisant l'union-find et les files de priorité. Résout les problèmes de conception de réseau nécessitant une connectivité à coût minimal.

Leçon 1 • Algorithmes gloutons et retour sur trace

Implémente des stratégies gloutonnes pour l'ordonnancement d'intervalles et le codage de Huffman, ainsi que le retour sur trace pour les N-Reines et les sous-ensembles. Complète la boîte à outils de base de conception d'algorithmes.

Leçon 2 • Tabulation et DP ascendante

Construit des tables DP de manière itérative pour le rendu de monnaie, la montée d'escaliers et les chemins dans une grille. Élimine la surcharge de la récursivité et clarifie la logique de transition d'état.

Leçon 3 • Introduction à la programmation dynamique

Définit les sous-problèmes qui se chevauchent et la sous-structure optimale comme prérequis à la DP. Compare la DP au diviser-pour-régner pour clarifier quand chacun s'applique.

Leçon 4 • Mémorisation et DP descendante

Convertit la récursivité naïve en solutions mémorisées à l'aide de dictionnaires et de functools.lru_cache. Démontre une réduction spectaculaire de la complexité sur Fibonacci et des problèmes similaires.