Algorithmique Avancée & Conception Optimale
Optimisation algorithmique, programmation dynamique poussée, flots maximaux et preuves de complexité.
- 5 modules
- 20 leçons
- 5 h de contenu
- Exercices Python exécutables
- Évaluation finale
Ce que vous allez apprendre
- Analyse fine de complexité & Analyse amortie
- Structures de données avancées & Auto-équilibrage
- Programmation dynamique experte & Mémoïsation matricielle
- Graphes avancés, Flots & Couplages
- Algorithmes probabilistes, Heuristiques & Décidabilité
Programme
5 modules · 20 leçons · 5 h de contenu
1Analyse fine de complexité & Analyse amortie4 leçons · 1 h
- 1.1Bornes asymptotiques et relations de récurrence (Théorème maître, Akra-Bazzi)
- 1.2Complexité spatiale, modèle RAM et compromis temps-mémoire
- 1.3Analyse amortie fondamentale (Agrégat, méthode comptable et potentiel)
- 1.4Invariants de boucle complexes, ordres bien fondés et terminaison
2Structures de données avancées & Auto-équilibrage4 leçons · 1 h
- 2.1Arbres équilibrés AVL et rotations simples/doubles
- 2.2Arbres bicolores (Red-Black Trees) et Arbres B pour bases de données
- 2.3Tas perfectionnés : tas binomiaux et tas de Fibonacci
- 2.4Tries compressés, Radix Trees et Union-Find avec inverse d'Ackermann
3Programmation dynamique experte & Mémoïsation matricielle4 leçons · 1 h
- 3.1Formulation formelle des états et sous-structures sur DAGs
- 3.2Optimisations spatiales et réduction de dimension par tableaux roulants
- 3.3Chaînes matricielles, triangulation minimale et BST optimal
- 3.4Optimisations avancées de DP : Knuth-Yao et Divide and Conquer
4Graphes avancés, Flots & Couplages4 leçons · 1 h
- 4.1Plus courts chemins tout-paires et algorithme de Johnson
- 4.2Flot maximal : théorème Max-Flow Min-Cut et méthode d'Edmonds-Karp
- 4.3Algorithme de Dinic, graphes de niveau et flots bloquants
- 4.4Couplages maximaux dans les graphes bipartis et algorithme de Hopcroft-Karp
5Algorithmes probabilistes, Heuristiques & Décidabilité4 leçons · 1 h
- 5.1Algorithmes randomisés (Monte Carlo, Las Vegas, filtres de Bloom)
- 5.2Classes P, NP, NP-complétude et réductions polynomiales (Cook-Levin)
- 5.3Algorithmes d'approximation et schémas PTAS (TSP métrique, Vertex Cover)
- 5.4Décidabilité, calculabilité, problème de l'arrêt et machines de Turing
Comment se déroule la formation
Des leçons courtes ; votre progression est enregistrée et vous reprenez là où vous vous êtes arrêté.
Des exemples de code Python à modifier et exécuter dans le navigateur, sans rien installer.
Une évaluation finale s'ouvre quand vous avez parcouru l'essentiel de la formation.
Dans le même domaine
- Excellence CPGE🎓 Fondamentaux & CPGE
Python : les fondamentaux
Syntaxe Python, structures conditionnelles, boucles, fonctions, POO et calcul numérique avec exercices interactifs.
▶ Exercices PythonVoir le programme Accès sur attribution - Excellence CPGE🔥 Spécial Épreuves Concours
Algorithmique & Graphes en Python
Structures de données (piles, files, arbres), parcours de graphes, programmation dynamique et sujets concours.
▶ Exercices PythonVoir le programme Accès sur attribution - Excellence CPGE💾 Modélisation & SQL Avancé
Bases de données relationnelles & SQL
Modélisation relationnelle, algèbre relationnelle, requêtes SQL complexes, jointures multiples et interfaçage SQLite Python.
▶ Exercices Python▶ Exercices SQLVoir le programme Accès sur attribution