Cours Algorithmique en PDF (Avancé)

Algorithmique : Ce qu'il faut savoir. Discipline qui étudie la conception, l'analyse et la correction d'algorithmes pour résoudre des problèmes computationnels, en mesurant coûts en temps et en espace à l'aide de notations asymptotiques et d'outils formels (récurrences, théorèmes, preuves d'optimalité). Ce polycopié rassemble cours et travaux dirigés de l'ENS Lyon en un seul document pédagogique, utile pour l'apprentissage et la référence; il est disponible en PDF gratuit pour téléchargement et usage académique.

🎯 Ce que vous allez apprendre

• Résolution des récurrences et Master theorem — comment formaliser le coût des algorithmes récursifs à l'aide d'équations de récurrence et appliquer le Master theorem pour obtenir des bornes asymptotiques tight. Vous saurez manipuler récurrences homogènes et non homogènes et interpréter les solutions en termes de complexité pratique pour la conception d'algorithmes diviser‑pour‑régner.
• Algorithmes diviser‑pour‑régner (Strassen, produit de polynômes) — techniques de décomposition problématique pour réduire la complexité asymptotique, illustrées par l'algorithme de Strassen et le produit rapide de polynômes. L'étudiant saura dériver la relation de coût, analyser l'impact des constantes et choisir une méthode selon les caractéristiques du problème (taille, mémoire).
• Programmation dynamique (sac à dos, pièces, plus longue sous‑suite) — formulation d'états, transitions et tables de DP pour transformer des formulations exponentielles en solutions polynomiales. À l'issue, l'étudiant pourra écrire la relation de récurrence, optimiser l'espace (tableau 1D vs 2D) et implémenter des solutions exactes et des variantes FPTAS quand le PDF les propose comme exercices.
• Algorithmes sur graphes (Dijkstra, BFS, DFS, tri topologique) — structures de représentation (matrice d'adjacence, listes d'adjacence), parcours en largeur/profondeur, plus courts chemins dans le cadre de poids positifs et chemins algébriques sur semi‑anneaux. Vous maîtriserez l'analyse de Dijkstra, la détection de composantes fortement connexes, et l'usage du tri topologique pour la résolution de dépendances.
• Structures de données et tables de hachage — principes de hachage, collisions séparées, adressage ouvert et implications sur la complexité moyenne et pire cas. L'étudiant saura choisir et paramétrer une table de hachage, analyser le facteur de charge et comprendre les compromis entre temps d'accès et mémoire.
• Analyse amortie, NP‑complétude et algorithmes d'approximation — méthodes des acomptes et du potentiel pour obtenir des coûts amortis réalistes, définition de P/NP et réductions (3‑SAT, clique, vertex cover), et techniques d'approximation (2‑approx, FPTAS pour 2‑Partition). Vous serez capable d'argumenter sur la tractabilité, construire des réductions et appliquer une approximation quand un optimum polynomial est inaccessible.

📑 Sommaire du document

• Introduction : calcul de xn
• Diviser pour régner
• Programmation dynamique
• Algorithmes gloutons
• Tri
• Graphes
• Tables de hachage
• Analyse amortie

💡 Pourquoi choisir ce cours ?

Document issu de l'ENS Lyon rédigé par Anne Benoit, Benjamin Depardon, Christophe Mouilleron et Clément Resvoy, qui combine cours magistraux et séances de TD avec corrigés. L'approche pédagogique alterne démonstrations formelles, preuves de complexité et exercices guidés, favorisant la maîtrise tant théorique que pratique. La richesse des références bibliographiques et des exercices faits en TD distingue ce polycopié comme ressource d'entraînement rigoureuse pour la L3/masters préliminaires.

👤 À qui s'adresse ce cours ?

• Public cible : étudiants de licence avancée ou début de master en informatique, enseignants et ingénieurs cherchant à consolider les fondements d'algorithmique (analyse d'algorithmes, conception, preuves et application aux graphes et structures).
• Prérequis : notions de complexité (notations asymptotiques), logique et méthodes de preuve, familiarité avec structures de données de base (listes, piles, arbres), et expérience pratique d'un langage de programmation pour implémenter et tester les algorithmes.

❓ Foire Aux Questions (FAQ)

Comment appliquer le Master theorem à une récurrence non standard ? Réponse : on identifie d'abord les paramètres a, b et la fonction f(n) de la récurrence T(n)=aT(n/b)+f(n), puis on compare f(n) à n^{log_b a} pour choisir le cas du Master theorem; si f(n) ne cadre pas, il faut recourir à une substitution, à des bornes par majoration/minoration ou à la méthode de l'arbre de récursion.

Quelle méthode d'analyse amortie choisir entre acomptes et potentiel ? Réponse : la méthode des acomptes convient pour des preuves simples où l'on attribue crédits par opération, tandis que la fonction de potentiel offre une mesure globale d'état utile pour structures avec invariants complexes; le PDF illustre les deux sur les exemples de compteur et d'allocateur.