Cours Python et Algorithmique

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 propres et testables.

Leçon 2 • Flux de contrôle 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 la logique algorithmique en Python.

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

Introduit 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, flottants, chaînes, booléens et le transtypage. Fournit les primitives de données utilisées dans chaque mise en œuvre d'algorithme à 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 économe 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'immuabilité des tuples. Ces types de séquences sous-tendent les structures de données basées sur des tableaux couvertes plus tard.

Leçon 3 • Dictionnaires et ensembles

Couvre le stockage basé sur le hachage, les opérations clé-valeur et l'algèbre d'ensembles. Soutient directement les mises en œuvre de tables de hachage et de listes d'adjacence de graphes.

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

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

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

Définit la correction, l'efficacité d'un algorithme et le besoin d'une analyse formelle. Instaure 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écursion. Prépare directement les étudiants à analyser les algorithmes de tri et d'arborescence.

Leçon 4 • Profilage du code Python

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

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 de la structure pour les problèmes de conception d'algorithmes.

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

Construit des classes de nœuds et des opérations de liste incluant l'insertion, la suppression et le parcours. Introduit la pensée basée sur les pointeurs essentielle pour les arbres et les graphes.

Leçon 3 • Piles : mise en œuvre et applications

Met en œuvre 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 dans la récursion, l'analyse syntaxique et le retour sur trace.

Leçon 4 • Files d'attente, deques et files d'attente prioritaires

Couvre les files FIFO, les deques double extrémité et les files d'attente prioritaires basées sur des tas. Prépare les étudiants pour le BFS, l'ordonnancement et les problèmes d'algorithmes gloutons.

Leçon 1 • Algorithmes de tri quadratiques

Met en œuvre le tri à bulles, le tri par sélection et le tri par insertion avec une analyse étape par étape. Fournit la référence O(n²) par rapport à laquelle les tris plus rapides sont mesurés.

Leçon 2 • Algorithmes de recherche

Met en œuvre la recherche linéaire et la recherche binaire avec des preuves de complexité. Relie la recherche aux exigences de données triées et aux problèmes d'entretien réels.

Leçon 3 • Fondamentaux de la récursion

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 Timsort utilisé dans le tri intégré de Python. Élargit la boîte à outils des étudiants au-delà du tri par comparaison.

Leçon 1 • Arbres binaires de recherche

Met en œuvre l'insertion, la recherche et la suppression BST 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 d'autocomplétion et de recherche dans un dictionnaire.

Leçon 3 • Arbres binaires et parcours

Définit la terminologie des arbres et met en œuvre les parcours en ordre, pré-ordre et post-ordre. É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 max-tas et un min-tas, met en œuvre heapify et le tri par tas. Soutient directement les mises en œuvre de files d'attente prioritaires et d'algorithmes gloutons.

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

Couvre les composants 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 du monde réel complexes.

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 liste d'adjacence et matrice. Établit la base pour toutes les mises en œuvre d'algorithmes de graphes.

Leçon 3 • Algorithmes de plus court chemin

Met en œuvre 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

Met en œuvre les algorithmes de Kruskal et Prim en utilisant union-find et files d'attente prioritaires. Résout des problèmes de conception de réseau nécessitant une connectivité à coût minimal.

Leçon 1 • Algorithmes gloutons et retour sur trace (backtracking)

Met en œuvre 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 conception d'algorithmes de base.

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 récursion 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 DP. Compare la DP avec diviser pour régner pour clarifier quand chacun s'applique.

Leçon 4 • Mémorisation et DP descendante

Convertit la récursion 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.