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 des structures de données et algorithmes 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 une logique algorithmique 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 défaillances dans les programmes complexes.

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

Couvre les entiers, flottants, chaînes, booléens et la conversion de type. 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 économe en mémoire de grands ensembles de données dans les problèmes de structures de données et algorithmes.

Leçon 2 • Listes et tuples en profondeur

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

Leçon 3 • Dictionnaires et ensembles

Couvre le stockage par hachage, les opérations clé-valeur et l'algèbre des ensembles. Prend directement en charge les implémentations de tables de hachage et de listes d'adjacence de graphes.

Leçon 4 • Comprehensions de listes et de dictionnaires

Enseigne la syntaxe concise des comprehensions pour filtrer et transformer les collections. Réduit le code redondant dans les implémentations 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 la nécessité d'une analyse formelle. Instaure l'état d'esprit analytique appliqué à chaque structure de données et algorithme à venir.

Leçon 2 • Grand O, Grand Oméga et Grand Thêta

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 d'arbre.

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 de l'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 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 sur les listes, y compris l'insertion, la suppression et le parcours. Introduit la réflexion 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 concrets. Démontre la sémantique LIFO utilisée dans la récursivité, l'analyse syntaxique et le retour sur trace.

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

Couvre les files FIFO, les deques double extrémité et les files de priorité basées sur un tas. Prépare les étudiants aux problèmes de parcours en largeur, 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 référence 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'entretien réels.

Leçon 3 • Fondamentaux de la récursivité

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

Leçon 4 • Tri 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

Implémente l'insertion, la recherche et la suppression dans un arbre binaire de recherche avec une analyse moyenne en 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 préfixes

Construit un trie pour l'insertion de chaînes, la recherche et la correspondance de préfixes. Permet des solutions efficaces de saisie semi-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 post-ordre. Établit le modèle de parcours récursif utilisé dans tous les algorithmes d'arbre.

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. Prend directement en charge 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 flot dans un réseau. Étend les compétences sur les 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 d'adjacence et matrices. É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 à l'aide de l'union-find et de 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-Queens et les sous-ensembles. Complète la boîte à outils de base pour la conception d'algorithmes.

Leçon 2 • Tabulation et DP ascendant

Construit des tables DP de manière itérative pour le problème du 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 de la DP. Compare la DP avec diviser pour régner pour clarifier quand appliquer chaque méthode.

Leçon 4 • Mémorisation et DP descendant

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.