🧠

ROADMAP ULTIME
MAÎTRISER L'ALGORITHMIE
Du niveau zéro absolu à l'élite mondiale du Top 1%

─────────────────────────────────────────────────────

Guide Complet, Exhaustif & Scientifique

Fondements mathématiques • Structures de données • Algorithmes classiques

Algorithmie avancée • Optimisation • Compétition • Recherche

─────────────────────────────────────────────────────

Toutes les phases • Toutes les notions • Toutes les ressources

Ce que les 99% ne connaissent jamais

PRÉAMBULE — Comprendre ce Roadmap
Ce roadmap est le guide le plus complet, le plus structuré et le plus approfondi jamais conçu pour maîtriser
l'algorithmie dans sa totalité, depuis les toutes premières notions de logique élémentaire jusqu'aux techniques
réservées à l'élite mondiale des compétiteurs, chercheurs et ingénieurs de pointe. Il est conçu pour quelqu'un qui part
de zéro absolu — sans aucun prérequis — et qui souhaite atteindre le niveau que seul le top 1% des praticiens
mondiaux possède réellement.
L'algorithmie n'est pas simplement un ensemble de recettes ou de formules à mémoriser. C'est une discipline
intellectuelle profonde qui combine la rigueur mathématique, la pensée abstraite, la résolution créative de problèmes
et la maîtrise technique. Ce roadmap traite ces dimensions de manière intégrée, progressive et explicite.

Comment utiliser ce Roadmap

Ce guide est organisé en 10 phases progressives, chacune bâtie sur la précédente. Chaque phase contient des objectifs
clairs, des notions à maîtriser, des exercices recommandés et des ressources précises. Il ne faut pas sauter de phase : la
progression est délibérément conçue pour construire des fondations solides avant d'aborder la complexité.
⚡ Principe fondamental : La compréhension profonde prime toujours sur la mémorisation superficielle.
Comprendre POURQUOI un algorithme fonctionne vaut infiniment plus que de savoir le recopier.

Durée estimée par phase

La progression dépend entièrement de la régularité et de l'intensité de l'étude. À raison de 2 à 3 heures par jour, un
parcours complet jusqu'au niveau élite représente entre 18 mois et 4 ans de travail soutenu. Il n'existe pas de raccourci
vers l'excellence réelle.
• Phase 1 (Fondations) : 1 à 2 mois
• Phase 2 (Logique & Maths) : 2 à 3 mois
• Phase 3 (Structures de données fondamentales) : 2 mois
• Phase 4 (Algorithmes classiques) : 3 mois
• Phase 5 (Analyse de complexité avancée) : 2 mois
• Phase 6 (Structures de données avancées) : 3 mois
• Phase 7 (Algorithmie avancée) : 4 mois
• Phase 8 (Compétition & Problem Solving) : 6 mois à 1 an
• Phase 9 (Domaines spécialisés de pointe) : 1 à 2 ans
• Phase 10 (Recherche & Innovation) : Continu
 PHASE 1

FONDATIONS ABSOLUES
Les bases de la pensée algorithmique — Partir de zéro

1.1 — Qu'est-ce qu'un Algorithme ? Définition scientifique et intuitive

Un algorithme est une séquence finie, ordonnée et non ambiguë d'instructions permettant de résoudre un problème
donné ou de produire un résultat précis à partir d'entrées définies. Cette définition, héritée de l'œuvre du
mathématicien al-Khwarizmi (IXe siècle), a été formalisée au XXe siècle par Alan Turing, Alonzo Church et Kurt Gödel.
Un algorithme doit posséder cinq propriétés fondamentales : la finitude (il se termine en un nombre fini d'étapes), la
définitude (chaque étape est précisément définie), les entrées (zero ou plusieurs données initiales), les sorties (au
moins un résultat produit), et l'effectivité (chaque opération est faisable par un agent de calcul).
📌 À retenir : Un algorithme est une idée abstraite, indépendante du langage de programmation. On peut
décrire un algorithme en langage naturel, en pseudocode, en diagramme ou en code. La maîtrise de
l'algorithmie est indépendante de la syntaxe d'un langage.

1.2 — Pensée algorithmique et décomposition de problèmes

La pensée algorithmique est la capacité à analyser un problème complexe, à le décomposer en sous-problèmes plus
simples, à identifier des patterns, à abstraire les détails non essentiels et à concevoir une solution systématique et
généralisable. Cette compétence se développe de manière progressive et consciente.
Les quatre piliers de la pensée computationnelle (selon Jeannette Wing, 2006) sont : la décomposition (diviser un
problème en parties plus petites), la reconnaissance de motifs (identifier des similitudes entre problèmes), l'abstraction
(distinguer les informations essentielles des détails) et l'algorithmisation (construire des solutions étape par étape).

1.2.1 — Décomposition de problèmes

Toute résolution de problème algorithmique commence par une compréhension parfaite de l'énoncé. Il faut identifier :
quelles sont les entrées ? Quelles sont les sorties attendues ? Quelles sont les contraintes ? Existe-t-il des cas
particuliers (cas limites, edge cases) ? La décomposition consiste ensuite à identifier les grandes étapes logiques de la
solution, puis à affiner chaque étape jusqu'à ce qu'elle soit directement implémentable.

1.2.2 — Abstraction et modélisation

L'abstraction consiste à identifier et conserver uniquement les informations pertinentes pour résoudre le problème, en
ignorant les détails inutiles. Par exemple, pour modéliser un réseau routier, on n'a pas besoin de connaître la couleur
des routes — on a besoin de savoir quelles villes sont connectées et à quelle distance. Ce processus de modélisation est
fondamental pour tout algorithmicien de haut niveau.

1.3 — Pseudocode et représentation algorithmique

Le pseudocode est une notation informelle et lisible par l'être humain permettant de décrire un algorithme sans se
préoccuper de la syntaxe d'un langage de programmation particulier. Il est universel, portable et axé sur la logique.
Apprendre à écrire et lire le pseudocode est une compétence fondamentale pour tout algorithmicien.
Les constructions de base du pseudocode incluent : DÉBUT / FIN pour délimiter un algorithme, les affectations (variable
← valeur), les structures conditionnelles (SI / SINON / FIN SI), les boucles (POUR, TANT QUE, RÉPÉTER...JUSQU'À), les
entrées (LIRE) et sorties (ÉCRIRE), les sous-programmes (PROCÉDURE, FONCTION, RETOURNER).

1.4 — Diagrammes de flux (Flowcharts)

Les diagrammes de flux sont une représentation graphique d'un algorithme. Chaque forme géométrique a une
signification précise : le rectangle représente une action ou un traitement, le losange représente une décision
(condition avec deux branches : oui/non), le parallélogramme représente une entrée ou sortie, le cercle représente un
point de connexion, et les ovales représentent le début et la fin. La maîtrise de la lecture et de la construction de
flowcharts développe la pensée visuelle algorithmique.

1.5 — Notions de variable, type et mémoire

Une variable est un espace mémoire nommé qui stocke une valeur pouvant changer au cours de l'exécution de
l'algorithme. Chaque variable possède un type (entier, réel, caractère, booléen, chaîne de caractères) qui détermine la
nature des données qu'elle peut contenir et les opérations applicables. Comprendre la notion de type et d'allocation
mémoire est fondamental pour l'analyse de complexité spatiale ultérieure.
Les types de données primitifs fondamentaux sont : les entiers (integers, représentés en binaire avec des contraintes de
taille), les flottants (nombres réels approchés selon IEEE 754), les booléens (vrai ou faux, un bit), et les caractères
(encodés selon ASCII ou Unicode). Ces types primitifs constituent les briques élémentaires de toute structure de
données.

1.6 — Structures de contrôle fondamentales

Toute logique algorithmique repose sur trois structures de contrôle fondamentales, prouvées suffisantes pour exprimer
tout algorithme calculable (théorème de la structure de Böhm-Jacopini) :
• La séquence : les instructions s'exécutent dans l'ordre, l'une après l'autre, de haut en bas. C'est la structure la plus
simple et la plus naturelle.
• La sélection (ou branchement conditionnel) : une condition est évaluée, et selon son résultat (vrai ou faux), un
chemin ou un autre est emprunté. Les formes sont SI...ALORS, SI...ALORS...SINON, et SELON...CAS.
• La répétition (ou itération, boucle) : un bloc d'instructions est répété tant qu'une condition est vraie, ou un
nombre défini de fois. Les formes principales sont TANT QUE (pré-condition), RÉPÉTER...JUSQU'À (post-condition)
et POUR (compteur).

1.7 — Notion de fonction et de procédure

Une fonction est un sous-programme qui prend des paramètres en entrée, exécute un traitement et retourne une
valeur. Une procédure est similaire mais ne retourne pas de valeur — elle produit des effets de bord. La modularisation
du code via des fonctions est un principe fondamental du génie logiciel et de la pensée algorithmique : elle favorise la
réutilisabilité, la lisibilité et la testabilité.
Notions clés associées : paramètres formels vs paramètres effectifs (actuels), passage par valeur vs passage par
référence, portée des variables (locale vs globale), récursivité (une fonction qui s'appelle elle-même, avec un cas de
base et un cas récursif).

1.8 — Introduction à la récursivité

La récursivité est l'un des concepts les plus puissants et les plus élégants de l'algorithmie. Une fonction récursive est
une fonction qui se définit en termes d'elle-même. Tout algorithme récursif doit obligatoirement contenir : un cas de
base (condition d'arrêt, qui stoppe la récursion) et un ou plusieurs cas récursifs (qui appellent la fonction avec des
paramètres 'plus petits', se rapprochant du cas de base).
📚 Ressources Phase 1 : Livre : 'Introduction to Algorithms' (CLRS) Chapitre 1 — Cours : MIT OpenCourseWare
6.006 Introduction to Algorithms (Lecture 1-2) — Exercices : Hackerrank 'Problem Solving' (niveau Easy, section
Warmup) — Khan Academy : cours 'Algorithms' (section Intro)
 PHASE 2

FONDEMENTS MATHÉMATIQUES
Le langage secret de l'algorithmie de haut niveau

Les mathématiques sont le fondement irréductible de toute algorithmie avancée. Un algorithmicien sans bases
mathématiques solides est comme un architecte sans connaissance des matériaux. Cette phase est souvent négligée
par les praticiens ordinaires — et c'est précisément ce qui les plafonne définitivement. Le top 1% des algorithmiciens
mondiaux possède une maîtrise mathématique significativement supérieure à la moyenne.

2.1 — Logique mathématique et raisonnement formel

2.1.1 — Logique propositionnelle
La logique propositionnelle étudie les propositions (énoncés vrais ou faux) et les connecteurs logiques qui les relient.
Les connecteurs fondamentaux sont : la négation (NON, ¬), la conjonction (ET, ∧), la disjonction (OU, ∨), l'implication
(⇒, si...alors), et la double implication (⟺, si et seulement si). Les tables de vérité permettent d'évaluer
systématiquement la valeur de vérité d'une expression logique pour toutes les combinaisons de valeurs des variables.
Les lois de De Morgan, la distributivité, la commutativité et l'associativité des connecteurs logiques sont des outils
fondamentaux de simplification et de raisonnement. Ces lois s'appliquent directement dans la conception et
l'optimisation des conditions dans les algorithmes.

2.1.2 — Logique des prédicats (premier ordre)

La logique des prédicats étend la logique propositionnelle en introduisant les quantificateurs : le quantificateur
universel (∀, 'pour tout') et le quantificateur existentiel ( ∃, 'il existe'). Elle permet d'exprimer des propriétés sur des
ensembles d'objets. C'est le langage formel des démonstrations mathématiques et de la spécification d'algorithmes.

2.1.3 — Techniques de démonstration mathématique

Savoir démontrer rigoureusement une propriété algorithmique est une compétence distinguant les algorithmiciens
d'élite des praticiens ordinaires. Les techniques de démonstration fondamentales sont :
• La démonstration directe : on part des hypothèses et on dérive la conclusion par des étapes logiques successives.
• La démonstration par contraposée : pour prouver 'Si A alors B', on prouve l'équivalent 'Si non-B alors non-A'.
• La démonstration par contradiction (raisonnement par l'absurde) : on suppose le contraire de ce qu'on veut
prouver et on en dérive une contradiction. Exemple classique : preuve de l'irrationalité de √2.
• La démonstration par cas : on considère exhaustivement tous les cas possibles et on prouve la propriété dans
chacun.
• La démonstration par récurrence (induction mathématique) : on prouve une propriété P(n) pour tout entier n ≥ 0
en prouvant P(0) (cas de base) et en prouvant que P(k) implique P(k+1) (hérédité). C'est la technique
fondamentale pour prouver la correction des algorithmes récursifs et itératifs.

2.2 — Mathématiques discrètes

Les mathématiques discrètes sont le cœur mathématique de l'informatique algorithmique. Elles étudient des structures
discontinues (opposées aux structures continues de l'analyse), ce qui correspond parfaitement à la nature des données
informatiques.

2.2.1 — Théorie des ensembles

Un ensemble est une collection non ordonnée d'éléments distincts. Les opérations fondamentales sur les ensembles
sont : l'union (A ∪ B, éléments dans A ou dans B), l'intersection (A ∩ B, éléments dans les deux), la différence (A \ B,
éléments dans A mais pas dans B), le complément et le produit cartésien (A × B, toutes les paires (a,b)). La théorie des
ensembles est le langage universel des mathématiques modernes et fonde la théorie des graphes, la théorie des types,
les bases de données relationnelles et bien plus.
2.2.2 — Relations et fonctions
Une relation est un sous-ensemble du produit cartésien A × B, décrivant des associations entre éléments de deux
ensembles. Les propriétés importantes d'une relation sur un ensemble A sont : la réflexivité (tout élément est en
relation avec lui-même), la symétrie, l'antisymétrie, la transitivité. Une relation reflexive, symétrique et transitive est
une relation d'équivalence. Une relation réflexive, antisymétrique et transitive est un ordre partiel. Ces notions sont
fondamentales pour les structures de données ordonnées.

2.2.3 — Combinatoire et dénombrement

La combinatoire est l'art de compter des configurations. Elle est essentielle pour analyser la complexité algorithmique
et pour résoudre des problèmes de dénombrement. Les concepts fondamentaux sont :
• Le principe multiplicatif (règle du produit) : si une tâche peut se réaliser en n₁ × n₂ × ... façons, le nombre total de
possibilités est le produit.
• Le principe additif (règle de la somme) : si des événements disjoints peuvent se produire de n₁ ou n₂ façons, le
total est la somme.
• Les permutations : arrangement ordonné de k éléments parmi n, noté P(n,k) = n!/(n-k)!.
• Les combinaisons : sélection non ordonnée de k éléments parmi n, noté C(n,k) = n!/(k!(n-k)!). Le triangle de Pascal
et ses propriétés.
• Le principe des tiroirs (pigeonhole principle) : si n+1 objets sont rangés dans n tiroirs, au moins un tiroir contient
au moins 2 objets. Cet outil simple mais puissant est utilisé dans de nombreuses preuves algorithmiques.
• Les suites et les séries : progressions arithmétiques, géométriques, et leurs sommes — indispensables pour
l'analyse de complexité.

2.2.4 — Théorie des nombres

La théorie des nombres étudie les propriétés des entiers. Elle est fondamentale pour la cryptographie algorithmique et
de nombreux problèmes compétitifs. Les notions clés sont :
• Divisibilité, quotient et reste (division euclidienne). Théorème fondamental de l'arithmétique : tout entier > 1 se
décompose de manière unique en produit de nombres premiers.
• PGCD (Plus Grand Commun Diviseur) et PPCM (Plus Petit Commun Multiple). Algorithme d'Euclide pour calculer le
PGCD en O(log(min(a,b))).
• Nombres premiers : définition, tests de primalité (naïf en O(√n), crible d'Ératosthène en O(n log log n)),
répartition asymptotique (théorème des nombres premiers).
• Arithmétique modulaire : congruences, classes d'équivalence modulo n, propriétés (addition, multiplication,
puissance). Petit théorème de Fermat et théorème d'Euler.
• L'identité de Bézout et l'algorithme d'Euclide étendu : exprimer le PGCD comme combinaison linéaire, calculer les
inverses modulaires.
• Indicatrice d'Euler φ(n) : nombre d'entiers entre 1 et n copremiers avec n.

2.2.5 — Théorie des graphes — Introduction

Un graphe G = (V, E) est un couple composé d'un ensemble de sommets V (vertices) et d'un ensemble d'arêtes E (edges)
reliant des paires de sommets. Les graphes modélisent une immense variété de situations réelles : réseaux sociaux,
cartes routières, circuits électroniques, dépendances entre tâches, etc.
Types de graphes fondamentaux : graphe non-orienté (arêtes sans direction), graphe orienté ou digraphe (arcs avec
direction), graphe pondéré (arêtes avec des poids/coûts), graphe biparti (sommets partitionnés en deux ensembles,
arêtes uniquement entre les deux), graphe complet (toutes les paires de sommets sont reliées).
Notions de base : degré d'un sommet (nombre d'arêtes incidentes), chemin (séquence de sommets reliés), cycle
(chemin fermé), connexité (existence d'un chemin entre toute paire de sommets), arbre (graphe connexe sans cycle),
forêt (union d'arbres).

2.3 — Probabilités et statistiques pour l'algorithmie

Les probabilités sont indispensables pour l'analyse des algorithmes randomisés, pour l'estimation de complexités
moyennes et pour la compréhension des structures de données probabilistes. Les notions fondamentales nécessaires
sont :
 • Espace probabiliste, événements, probabilité d'un événement. Règles d'addition et de multiplication. Probabilité
conditionnelle P(A|B) = P(A∩B)/P(B). Théorème de Bayes.
• Variables aléatoires discrètes et continues. Distributions importantes : uniforme, Bernoulli, binomiale,
géométrique, Poisson, normale (gaussienne).
• Espérance mathématique E[X] et ses propriétés (linéarité). Variance et écart-type. Inégalités fondamentales :
inégalité de Markov (P(X≥a) ≤ E[X]/a pour X≥0), inégalité de Chebyshev, inégalité de Chernoff (concentration des
sommes de variables indépendantes, essentielle pour les algorithmes randomisés).
• Chaînes de Markov : processus stochastiques à mémoire finie. Utiles pour analyser des algorithmes comme le tri
par mélange aléatoire ou certaines structures de données probabilistes.

2.4 — Algèbre linéaire algorithmique

L'algèbre linéaire est fondamentale pour les algorithmes numériques, l'apprentissage automatique et certains
problèmes algorithmiques avancés comme la multiplication matricielle rapide. Notions nécessaires :
• Vecteurs et espaces vectoriels. Opérations vectorielles (addition, multiplication scalaire, produit scalaire, produit
vectoriel).
• Matrices : définition, opérations (addition, multiplication, transposée, inverse). La multiplication matricielle naïve
est en O(n³) ; l'algorithme de Strassen la réduit à O(n^2.81).
• Déterminant et rang d'une matrice. Systèmes d'équations linéaires. Élimination gaussienne (O(n³)).
• Valeurs propres et vecteurs propres. Décompositions matricielles (SVD, LU, QR) — essentielles pour les
algorithmes numériques avancés.
📚 Ressources Phase 2 : Livres : 'Concrete Mathematics' (Graham, Knuth, Patashnik) — 'Discrete Mathematics
and Its Applications' (Rosen) — 'Introduction to Probability' (Bertsekas & Tsitsiklis) — MIT OpenCourseWare
6.042J 'Mathematics for Computer Science' (cours complet en ligne, gratuit) — Khan Academy : sections
Combinatorics, Probability, Linear Algebra
 PHASE 3

STRUCTURES DE DONNÉES FONDAMENTALES

Les conteneurs qui organisent l'information

Une structure de données est une manière d'organiser, de stocker et de gérer les données en mémoire pour permettre
un accès et des modifications efficaces. Le choix de la bonne structure de données pour un problème donné est souvent
la décision la plus importante dans la conception d'un algorithme, bien avant le choix de l'algorithme lui-même.

3.1 — Complexité : Notations asymptotiques (introduction)

Avant d'étudier les structures de données, il est indispensable d'introduire les outils d'analyse de performance
algorithmique. La notation O (Big O) mesure la borne supérieure du temps d'exécution ou de l'espace mémoire d'un
algorithme en fonction de la taille de ses entrées, en ignorant les constantes et les termes de moindre degré.
Notations fondamentales : O(f(n)) — borne supérieure asymptotique (worst case), Ω(f(n)) — borne inférieure
asymptotique (best case), Θ(f(n)) — borne serrée (average/exact). Hiérarchie des complexités du plus rapide au plus
lent : O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!).

3.2 — Tableaux (Arrays)

Le tableau est la structure de données la plus fondamentale et la plus utilisée. C'est une séquence contiguë de cases
mémoire, chacune contenant un élément du même type, accessibles directement via un indice entier. L'accès à un
élément par indice est en O(1) — temps constant — grâce à l'adressage direct en mémoire (adresse = base + indice ×
taille_élément).
Types de tableaux : tableaux statiques (taille fixée à la compilation), tableaux dynamiques (taille pouvant croître,
comme ArrayList en Java ou vector en C++), tableaux multidimensionnels (matrices, tenseurs). Les tableaux dynamiques
utilisent une stratégie de doublement de capacité qui amortit le coût des insertions à O(1) amorti.
Opérations et complexités : accès par indice O(1), recherche linéaire O(n), insertion/suppression en tête ou milieu O(n)
(nécessite décalage), insertion/suppression en queue O(1) amorti pour les tableaux dynamiques.

3.3 — Listes chaînées (Linked Lists)

Une liste chaînée est une structure de données séquentielle où chaque élément (nœud) contient une valeur et un
pointeur vers le nœud suivant. Contrairement aux tableaux, les nœuds ne sont pas stockés de manière contiguë en
mémoire.
Types principaux : liste simplement chaînée (pointeur vers le successeur uniquement), liste doublement chaînée
(pointeurs vers le successeur et le prédécesseur), liste circulaire (le dernier nœud pointe vers le premier).
Opérations : insertion/suppression en tête O(1), insertion/suppression en position connue O(1), accès par indice O(n),
recherche O(n). La liste chaînée excelle pour les insertions/suppressions fréquentes en début de liste, mais souffre
d'une mauvaise localité mémoire (cache-unfriendly).
Algorithmes classiques sur les listes chaînées : renverser une liste, détecter un cycle (algorithme de Floyd, deux
pointeurs), trouver le milieu (pointeur lent/rapide), fusionner deux listes triées, trouver le k-ième élément depuis la fin.

3.4 — Piles (Stacks)

Une pile est une structure de données abstraite suivant le principe LIFO (Last In, First Out — Dernier Entré, Premier
Sorti). Les opérations fondamentales sont : push (empiler un élément), pop (dépiler et retourner l'élément au sommet),
peek/top (consulter l'élément au sommet sans le retirer), isEmpty (vérifier si la pile est vide). Toutes ces opérations sont
en O(1).
Implémentations : avec un tableau dynamique (l'index de sommet augmente et diminue) ou avec une liste chaînée (le
sommet est toujours la tête). La pile peut être implémentée dans les deux cas avec des opérations O(1).
Applications fondamentales : gestion des appels de fonctions (call stack), évaluation d'expressions (notation
postfixée/polonaise inverse), vérification de l'équilibrage des parenthèses/crochets/accolades, algorithmes de
backtracking itératif, histogramme (problème du plus grand rectangle).

3.5 — Files (Queues)

Une file est une structure de données abstraite suivant le principe FIFO (First In, First Out — Premier Entré, Premier
Sorti). Les opérations fondamentales sont : enqueue (ajouter à l'arrière), dequeue (retirer du devant), front (consulter
l'élément de devant), isEmpty. Toutes en O(1).
Variantes importantes : file circulaire (implémentation efficace avec un tableau), deque (double-ended queue, ajout et
retrait des deux côtés en O(1)), file de priorité (le prochain élément retiré est celui de priorité maximale —
implémentée avec un tas/heap).
Applications : BFS (Breadth-First Search) sur les graphes, simulation de files d'attente, planification de processus en
systèmes d'exploitation, fenêtre glissante (sliding window), niveau par niveau dans les arbres.

3.6 — Tables de hachage (Hash Tables)

Une table de hachage est une structure permettant un accès moyen en O(1) pour les opérations d'insertion,
suppression et recherche. Elle utilise une fonction de hachage qui transforme une clé (clé quelconque) en un indice
entier dans un tableau de buckets (seaux).
Fonction de hachage : une bonne fonction de hachage doit être déterministe (même clé → même hash), rapide à
calculer, et distribuée uniformément pour minimiser les collisions. Techniques courantes : méthode de division (h(k) = k
mod m), méthode de multiplication, hachage polynomial pour les chaînes.
Gestion des collisions (deux clés avec le même hash) : chaînage (chaque bucket contient une liste chaînée), adressage
ouvert (sondage linéaire, quadratique, double hachage). Le facteur de charge α = n/m (n éléments, m buckets)
influence les performances. Une table de hachage bien dimensionnée maintient α < 0.75.
Analyse amortie : en cas de collision excessive (α trop élevé), la table est redimensionnée (rehashing) — doublement de
la taille et réinsertion de tous les éléments. Ce processus, bien qu'en O(n), est amorti sur de nombreuses insertions,
conservant O(1) amorti par opération.

3.7 — Arbres binaires et arbres binaires de recherche (BST)

Un arbre est un graphe acyclique et connexe. Dans un arbre binaire, chaque nœud possède au plus deux enfants :
gauche et droite. Le nœud sans parent est la racine. Les nœuds sans enfants sont les feuilles. La hauteur d'un arbre est
la longueur du plus long chemin de la racine à une feuille.
Un arbre binaire de recherche (BST) est un arbre binaire où, pour chaque nœud n, tous les nœuds du sous-arbre gauche
ont des valeurs inférieures à n, et tous les nœuds du sous-arbre droit ont des valeurs supérieures. Cette propriété
permet une recherche en O(h) où h est la hauteur. Pour un arbre parfaitement équilibré, h = O(log n).
Opérations : insertion O(h), suppression O(h), recherche O(h). Parcours fondamentaux : in-ordre (gauche-racine-droite,
donne les éléments triés), pré-ordre (racine-gauche-droite), post-ordre (gauche-droite-racine), par niveaux (BFS).
Problème du BST dégénéré : si les éléments sont insérés dans un ordre trié, le BST devient une liste chaînée (h = n),
réduisant toutes les opérations à O(n). Les arbres équilibrés (AVL, Red-Black) résolvent ce problème.

3.8 — Tas (Heaps) et file de priorité

Un tas binaire est un arbre binaire presque complet (rempli de gauche à droite à chaque niveau) satisfaisant la
propriété de tas : dans un max-tas, chaque nœud est supérieur ou égal à ses enfants (le maximum est à la racine). Dans
un min-tas, chaque nœud est inférieur ou égal à ses enfants.
Implémentation dans un tableau : pour le nœud d'indice i (base 1), le père est à l'indice i//2, l'enfant gauche à 2i,
l'enfant droit à 2i+1. Cette représentation implicite est très efficace en pratique (pas de pointeurs, bonne localité
mémoire).
Opérations : insertion O(log n) (percolation vers le haut), extraction du minimum/maximum O(log n) (percolation vers le
bas), construction d'un tas depuis un tableau O(n) (procédure heapify — résultat non trivial, utilise la série
harmonique), accès au min/max O(1).
Applications : tri par tas (heapsort) en O(n log n) et O(1) espace supplémentaire, algorithme de Dijkstra, algorithme de
Prim, k-ième plus grand élément, fusion de k listes triées.
📚 Ressources Phase 3 : Livres : CLRS Chapitres 6 (Heapsort), 10 (Elementary Data Structures), 11 (Hash Tables),
12 (BST) — 'Data Structures and Algorithms in Python' (Goodrich, Tamassia) — [Link] : outil de
visualisation interactive de TOUTES les structures de données — LeetCode : problèmes Easy sur Arrays, Linked
Lists, Stacks, Queues, Hash Tables, Trees
 PHASE 4

ALGORITHMES CLASSIQUES FONDAMENTAUX

Les piliers de toute algorithmie

4.1 — Algorithmique de tri

Le tri est l'un des problèmes les plus étudiés en informatique. Comprendre en profondeur les algorithmes de tri — leurs
mécanismes, leurs complexités, leurs avantages et leurs inconvénients — est une étape fondamentale. Il ne s'agit pas
seulement de mémoriser les algorithmes, mais de comprendre les principes qui les gouvernent.

4.1.1 — Tris élémentaires O(n²)

Tri par sélection (Selection Sort) : à chaque étape, on trouve le minimum du tableau non trié et on le place à sa position
finale. Simple mais toujours O(n²) même pour un tableau déjà trié. Avantage : O(n) échanges (utile si les échanges sont
coûteux).
Tri par insertion (Insertion Sort) : on insère chaque élément à sa position correcte dans la partie déjà triée. Complexité
O(n²) au pire cas, mais O(n) si le tableau est presque trié (inversions faibles). Excellent en pratique pour les petits
tableaux et souvent utilisé comme complément aux tris récursifs.
Tri à bulles (Bubble Sort) : on compare et échange des éléments adjacents dans l'ordre. O(n²) et peu efficace en
pratique. Valeur pédagogique pour illustrer la notion d'invariant de boucle.

4.1.2 — Tris efficaces O(n log n)

Tri fusion (Merge Sort) : paradigme diviser-pour-régner. On divise le tableau en deux moitiés, on trie récursivement
chaque moitié, puis on fusionne les deux moitiés triées. Complexité : O(n log n) dans TOUS les cas (meilleur, moyen,
pire). Stable (préserve l'ordre des éléments égaux). Inconvénient : nécessite O(n) espace supplémentaire. Fondamental
pour le tri de fichiers externes.
Tri rapide (Quicksort) : paradigme diviser-pour-régner. On choisit un pivot, on partitionne le tableau autour du pivot
(éléments plus petits à gauche, plus grands à droite), puis on trie récursivement les deux partitions. Complexité : O(n
log n) en moyenne, O(n²) au pire cas (tableau déjà trié avec pivot mal choisi). Très efficace en pratique grâce aux
constantes cachées et à la localité mémoire. Choix du pivot : aléatoire, médiane de trois. Pas stable.
Tri par tas (Heapsort) : construit un max-tas depuis le tableau, puis extrait successivement le maximum. O(n log n) dans
tous les cas, O(1) espace supplémentaire. Moins efficace en pratique que Quicksort à cause de la mauvaise localité
mémoire. Pas stable.

4.1.3 — Tris linéaires (au-delà de la borne Ω(n log n))

La borne inférieure Ω(n log n) s'applique aux tris basés sur des comparaisons (proven via les arbres de décision). Des tris
non-comparatifs peuvent dépasser cette borne sous certaines conditions sur les données.
Tri par dénombrement (Counting Sort) : suppose que les clés sont des entiers dans un intervalle [0, k]. On compte les
occurrences de chaque valeur. O(n + k). Optimal si k = O(n). Stable et très rapide en pratique pour les petits entiers.
Tri par base (Radix Sort) : trie les entiers chiffre par chiffre (de la position la moins significative à la plus significative).
Utilise le tri par dénombrement comme sous-routine. O(d(n+k)) où d est le nombre de chiffres et k la base. Très efficace
pour les entiers de taille fixe.
Tri par compartiments (Bucket Sort) : distribue les éléments dans des compartiments (buckets), trie chaque
compartiment, puis les concatène. O(n) en moyenne si les données sont uniformément distribuées.

4.2 — Recherche
4.2.1 — Recherche linéaire (séquentielle)
Parcourt chaque élément du tableau jusqu'à trouver la cible. O(n) en pire cas, O(1) en meilleur cas. Applicable à tout
tableau, trié ou non. Incontournable pour des petits ensembles ou des structures non triées.
4.2.2 — Recherche dichotomique (Binary Search)
Applicable uniquement sur un tableau trié. À chaque étape, on compare l'élément recherché avec l'élément central. Si
égal, trouvé. Si plus petit, on cherche dans la moitié gauche. Si plus grand, dans la moitié droite. O(log n) — l'un des
algorithmes les plus efficaces et les plus sous-utilisés par les programmeurs ordinaires.
La recherche dichotomique est souvent utilisée non pas seulement pour rechercher une valeur, mais pour trouver une
frontière (premier élément satisfaisant une propriété monotone). Cette technique — 'binary search on the answer' —
est une stratégie avancée fondamentale en algorithmie compétitive.

4.3 — Récursivité et Diviser pour Régner

Le paradigme Diviser pour Régner (Divide and Conquer) décompose un problème en sous-problèmes indépendants de
taille réduite, les résout récursivement, puis combine les solutions. Son analyse utilise les récurrences.
Récurrence de Merge Sort : T(n) = 2T(n/2) + O(n). Résolution par le Master Theorem : T(n) = O(n log n). La résolution
des récurrences est une compétence mathématique fondamentale.
Master Theorem (Théorème maître) : pour T(n) = aT(n/b) + f(n) (a ≥ 1, b > 1), les trois cas donnent : si f(n) =
O(n^(log_b(a) - ε)) → T(n) = Θ(n^log_b(a)) ; si f(n) = Θ(n^log_b(a)) → T(n) = Θ(n^log_b(a) × log n) ; si f(n) = Ω(n^(log_b(a)
+ ε)) et condition de régularité → T(n) = Θ(f(n)).
Autres algorithmes diviser-pour-régner importants : recherche du maximum et minimum simultané (T(n) = 2T(n/2) +
O(1)), calcul de la puissance rapide (exponentiation rapide, O(log n)), multiplication de grands entiers (algorithme de
Karatsuba, O(n^1.585)), transformée de Fourier rapide (FFT, O(n log n)).

4.4 — Algorithmique sur les graphes — Fondements

4.4.1 — Représentations d'un graphe
Deux représentations principales : la matrice d'adjacence (tableau 2D de n×n bits/poids, O(n²) espace, accès en O(1)
pour vérifier une arête) et la liste d'adjacence (chaque sommet stocke la liste de ses voisins, O(n+m) espace, m =
nombre d'arêtes). Le choix dépend de la densité du graphe : matrice pour les graphes denses, liste pour les graphes
creux.

4.4.2 — BFS (Breadth-First Search)

Le parcours en largeur explore le graphe niveau par niveau depuis un sommet source s, en utilisant une file. Il visite
d'abord tous les voisins de s, puis les voisins des voisins, etc. BFS calcule les distances minimales (en nombre d'arêtes)
depuis s vers tous les autres sommets dans un graphe non pondéré. Complexité : O(V + E) où V = sommets et E = arêtes.
Applications : chemin le plus court dans un graphe non pondéré, test de bipartitude (un graphe est biparti si et
seulement si il est 2-colorable, BFS détecte les cycles de longueur impaire), composantes connexes, diffusion
(broadcasting).

4.4.3 — DFS (Depth-First Search)

Le parcours en profondeur explore le graphe en suivant un chemin aussi loin que possible avant de revenir en arrière
(backtracking). Il peut s'implémenter récursivement (call stack implicite) ou itérativement avec une pile explicite.
Complexité : O(V + E).
Notions importantes du DFS : timestamps de découverte et de finalisation, arêtes d'arbre, arêtes avant, arêtes arrière
(back edges — indiquent des cycles), arêtes croisées. Ces notions définissent la forêt DFS et sont fondamentales pour
les algorithmes avancés sur les graphes.
Applications : détection de cycles, tri topologique, composantes fortement connexes (algorithmes de Kosaraju et
Tarjan), recherche de ponts et points d'articulation, résolution de labyrinthes.

4.4.4 — Tri topologique

Le tri topologique ordonne linéairement les sommets d'un graphe orienté acyclique (DAG) tel que pour toute arête (u,
v), u apparaît avant v dans l'ordre. Deux algorithmes : via DFS (ordre décroissant de timestamps de finalisation) ou via
l'algorithme de Kahn (itératif, retire successivement les sommets de degré entrant nul avec une file). Applications :
ordonnancement de tâches avec dépendances, résolution de systèmes de dépendances (make, npm).

4.5 — Algorithmes de chemin le plus court

4.5.1 — Algorithme de Dijkstra
Dijkstra calcule les distances minimales depuis un sommet source vers tous les autres sommets dans un graphe
pondéré avec des poids positifs. Il utilise une file de priorité (min-heap). À chaque étape, le sommet non-visité avec la
distance minimale est extrait, ses voisins sont mis à jour (relaxation). Complexité : O((V + E) log V) avec un tas binaire,
O(E + V log V) avec un tas de Fibonacci.

4.5.2 — Algorithme de Bellman-Ford

Bellman-Ford calcule les distances minimales depuis une source dans un graphe pondéré pouvant contenir des arêtes
de poids négatif (mais pas de cycles négatifs accessibles depuis la source). Il effectue V-1 itérations de relaxation de
toutes les arêtes. Complexité : O(VE). Il détecte aussi les cycles négatifs. Moins efficace que Dijkstra pour les graphes
sans arêtes négatives.

4.5.3 — Algorithme de Floyd-Warshall

Floyd-Warshall calcule les plus courts chemins entre toutes les paires de sommets (all-pairs shortest paths) dans un
graphe pondéré (avec poids potentiellement négatifs, sans cycles négatifs). Il utilise la programmation dynamique sur
une matrice de distances. Complexité : O(V³). Applications : fermeture transitive, détection de cycles négatifs.

4.6 — Algorithmes sur les arbres

Arbre couvrant minimum (MST — Minimum Spanning Tree) : un MST d'un graphe pondéré connexe non-orienté est un
arbre reliant tous les sommets avec le poids total minimal. Deux algorithmes gloutons : Algorithme de Kruskal (trier
toutes les arêtes par poids, ajouter chaque arête si elle ne crée pas de cycle — utilise l'union-find, O(E log E)) et
Algorithme de Prim (construire le MST en ajoutant à chaque étape l'arête de poids minimal reliant un sommet déjà
dans le MST à un sommet extérieur, O(E log V) avec un tas).
📚 Ressources Phase 4 : CLRS Chapitres 2 (Sorting), 4 (Divide and Conquer), 22 (Graph Representations), 23
(BFS/DFS), 24 (Shortest Paths — Dijkstra, Bellman-Ford), 25 (Floyd-Warshall), 21 (MST) — Stanford Algorithms
Coursera (Tim Roughgarden) — LeetCode : Medium sur Sorting, Binary Search, Graph BFS/DFS
 PHASE 5

ANALYSE DE COMPLEXITÉ APPROFONDIE

Mesurer et prédire les performances avec précision

5.1 — Analyse asymptotique avancée

Au-delà de la simple notation Big O, une analyse rigoureuse exige de distinguer le pire cas (worst case), le meilleur cas
(best case) et le cas moyen (average case). Ces trois mesures peuvent différer considérablement, comme pour
Quicksort (O(n²) au pire cas vs O(n log n) en moyenne).
L'analyse de cas moyen nécessite de définir une distribution de probabilité sur les entrées, ce qui la rend plus délicate
mais aussi plus réaliste. Pour Quicksort avec pivot aléatoire, l'analyse du cas moyen utilise des espérances et des
récurrences probabilistes.

5.2 — Analyse amortie

L'analyse amortie étudie le coût moyen par opération sur une séquence de n opérations, même si certaines opérations
individuelles sont coûteuses. Trois méthodes d'analyse amortie :
• Méthode de l'agrégat : calculer le coût total de n opérations et diviser par n.
• Méthode de la comptabilité (accounting method) : attribuer un crédit virtuel à chaque opération, les opérations
'bon marché' accumulent des crédits pour 'payer' les opérations coûteuses futures.
• Méthode du potentiel : définir une fonction de potentiel Φ sur l'état de la structure de données, le coût amorti =
coût réel + ΔΦ. Si Φ ne diminue jamais sous sa valeur initiale, la somme des coûts amortis est une borne
supérieure de la somme des coûts réels.
Exemples classiques : tableaux dynamiques (doublement de capacité — O(1) amorti par insertion), compteur binaire
(O(1) amorti par incrémentation), splay trees (O(log n) amorti par opération).

5.3 — Complexité spatiale

La complexité spatiale mesure la quantité de mémoire utilisée par un algorithme en fonction de la taille de l'entrée. On
distingue l'espace auxiliaire (mémoire supplémentaire utilisée au-delà des entrées) et l'espace total. Un algorithme in-
place n'utilise que O(1) espace auxiliaire (ex: Heapsort, tri par sélection).

5.4 — Borne inférieure et optimalité

Certains problèmes ont des bornes inférieures prouvables : il est mathématiquement impossible de les résoudre plus
rapidement. La borne Ω(n log n) pour le tri par comparaisons est prouvée via les arbres de décision (un arbre de
décision pour trier n éléments doit avoir n! feuilles, donc une hauteur ≥ log₂(n!) = Θ(n log n) par la formule de Stirling).
Un algorithme est dit optimal s'il atteint la borne inférieure de son problème. Merge Sort et Heapsort sont optimaux
pour le tri par comparaisons. La compréhension des bornes inférieures est une compétence distinguant le chercheur de
l'ingénieur ordinaire.

5.5 — Complexité en pratique : analyse cache et modèles de mémoire

Dans les systèmes réels, l'analyse asymptotique seule est insuffisante. Les constantes cachées par la notation Big O
peuvent faire varier les performances d'un facteur 10x à 100x. La hiérarchie mémoire (registres → cache L1 → L2 → L3
→ RAM → disque) influence considérablement les performances pratiques.
La localité de référence (spatiale : accès à des adresses proches ; temporelle : réutilisation des mêmes adresses) est
cruciale pour l'efficacité du cache. Les tableaux ont une excellente localité spatiale ; les listes chaînées, les arbres et les
tables de hachage souffrent de nombreux cache misses. Cette réalité explique pourquoi Quicksort surpasse Heapsort en
pratique malgré une complexité identique.
Le modèle de cache-oblivious (Frigo, Leiserson, Prokop, Ramachandran) conçoit des algorithmes efficaces pour
n'importe quel niveau de cache sans connaître ses paramètres. La recherche en algorithmie externe (external memory
algorithms) traite les algorithmes optimaux lorsque les données ne tiennent pas en RAM.

5.6 — Récurrences et leur résolution

Les récurrences sont des équations définissant T(n) en fonction de T sur de plus petites valeurs. Méthodes de résolution
:
• Substitution : deviner une solution et la prouver par récurrence.
• Arbre de récurrence (Recursion tree) : développer l'arbre des appels récursifs et sommer les coûts à chaque
niveau.
• Master Theorem (cas standard et extensions de Akra-Bazzi).
• Fonction génératrice : transformer la récurrence en une équation sur des séries formelles.
📚 Ressources Phase 5 : CLRS Chapitres 3 (Asymptotic Notation), 4 (Divide and Conquer — Master Theorem), 17
(Amortized Analysis) — 'Algorithm Design' (Kleinberg & Tardos) Chapitres 2-3 — Cours Stanford CS161
(Roughgarden) — Article 'Cache-Oblivious Algorithms' (Frigo et al., 1999)
 PHASE 6

STRUCTURES DE DONNÉES AVANCÉES

Les outils que les 99% ne maîtrisent pas

6.1 — Arbres équilibrés

6.1.1 — Arbres AVL
L'arbre AVL (Adelson-Velsky et Landis, 1962) est le premier arbre binaire de recherche auto-équilibré. La propriété
d'équilibre AVL stipule que pour chaque nœud, les hauteurs de ses sous-arbres gauche et droit diffèrent d'au plus 1. Le
facteur d'équilibre bf(n) = h(droite) - h(gauche) ∈ {-1, 0, 1}.
Après chaque insertion ou suppression, si la propriété est violée, des rotations sont effectuées pour rétablir l'équilibre.
Les quatre types de rotation sont : rotation simple droite (LL), rotation simple gauche (RR), rotation double gauche-
droite (LR), rotation double droite-gauche (RL). Toutes les opérations (insertion, suppression, recherche) sont garanties
O(log n) car la hauteur est maintenue ≤ 1.44 log₂(n).

6.1.2 — Arbres Rouge-Noir (Red-Black Trees)

Les arbres Rouge-Noir (Bayer 1972, améliorés par Guibas et Sedgewick 1978) sont des BST où chaque nœud est coloré
rouge ou noir selon cinq règles : tout nœud est rouge ou noir ; la racine est noire ; toutes les feuilles (NIL) sont noires ;
si un nœud est rouge, ses deux enfants sont noirs (pas de rouge consécutif) ; pour tout nœud, tous les chemins vers les
feuilles descendantes ont le même nombre de nœuds noirs (hauteur noire constante).
La hauteur est au plus 2 log₂(n+1). Toutes les opérations sont O(log n). Les arbres Rouge-Noir sont utilisés en pratique
dans la bibliothèque standard de C++ (std::map, std::set), Java (TreeMap, TreeSet), les systèmes de fichiers Linux
(rbtree dans le noyau), et les planificateurs de processus.

6.1.3 — B-Trees et B+-Trees

Les B-Trees (Bayer et McCreight, 1972) sont des arbres de recherche généralisés où chaque nœud peut contenir de t-1
à 2t-1 clés (t est l'ordre minimum). Tous les nœuds feuilles sont au même niveau. Les B-Trees sont optimisés pour les
systèmes de stockage à accès lent (disques durs, SSD) car ils minimisent le nombre d'accès disque. Toutes les opérations
sont O(log_t n) = O(log n). Les B+-Trees (nœuds internes n'ont que des clés, les données réelles sont dans les feuilles
liées entre elles) sont la structure fondamentale des systèmes de gestion de bases de données (SGBD) : MySQL InnoDB,
PostgreSQL.

6.1.4 — Arbres de segments et arbres de Fenwick (Binary Indexed Trees)

L'arbre de segments (Segment Tree) est une structure permettant de répondre à des requêtes d'intervalles (somme,
minimum, maximum sur un sous-tableau) et de mettre à jour des éléments en O(log n) pour les deux opérations. C'est
une structure essentielle en algorithmie compétitive. Construction en O(n), requête en O(log n), mise à jour en O(log n).
Extensions : lazy propagation (mise à jour paresseuse d'un intervalle en O(log n)), arbres de segments persistants.
L'arbre de Fenwick (Binary Indexed Tree ou BIT), conçu par Peter Fenwick en 1994, permet de calculer des sommes
préfixes et de mettre à jour des éléments en O(log n) avec une implémentation beaucoup plus simple et un facteur
constant inférieur à l'arbre de segments. Il exploite la représentation binaire des indices.

6.2 — Union-Find (Disjoint Set Union — DSU)

L'union-find est une structure de données gérant des partitions d'éléments en sous-ensembles disjoints, supportant
deux opérations : Find (trouver le représentant/racine du sous-ensemble d'un élément) et Union (fusionner les sous-
ensembles de deux éléments).
Deux optimisations fondamentales : la compression de chemin (path compression — lors d'un Find, tous les nœuds sur
le chemin pointent directement vers la racine) et l'union par rang/taille (lors de l'union, la racine avec le rang inférieur
est attachée à celle avec le rang supérieur). Avec ces deux optimisations combinées, la complexité amortie par
opération est quasiment O(1) — précisément O(α(n)) où α est la fonction inverse d'Ackermann, une fonction qui croit si
lentement qu'elle est ≤ 4 pour toute valeur pratique de n.
Applications : algorithme de Kruskal (détection de cycles), composantes connexes en graphes dynamiques, problèmes
de connectivité, percolation, réseaux dynamiques.

6.3 — Tries (Arbres de préfixes)

Un Trie (Retrieval tree, aussi appelé Prefix Tree) est un arbre où chaque nœud représente un préfixe d'une chaîne de
caractères. La racine représente la chaîne vide. Chaque chemin de la racine vers un nœud marqué représente un mot.
Insertion, recherche et suppression en O(L) où L est la longueur de la chaîne — indépendant du nombre de chaînes
stockées.
Variantes : Compressed Trie (PATRICIA Tree) — les chaînes de nœuds à un seul enfant sont fusionnées pour économiser
de l'espace ; Ternary Search Tree — compromis espace/vitesse ; Suffix Tree et Suffix Array — structures fondamentales
pour la recherche de motifs en temps linéaire (algorithme de Ukkonen).

6.4 — Tables de hachage avancées

Hachage parfait : pour un ensemble statique de n clés, on peut construire une table de hachage sans collision avec O(n)
espace et O(1) accès pire cas (FKS hashing — Fredman, Komlós, Szemerédi). Hachage universel : choisir aléatoirement
une fonction de hachage dans une famille universelle garantit peu de collisions en espérance. Hachage coucou (cuckoo
hashing) : chaque élément a deux positions candidates dans deux tables différentes ; si les deux sont occupées, l'un est
déplacé (cuckoo). O(1) accès en pire cas. Utilisé dans les tables de routage réseau.

6.5 — Skip Lists

Une skip list est une structure de données probabiliste composée de plusieurs niveaux de listes chaînées. Au niveau le
plus bas, tous les éléments sont présents. À chaque niveau supérieur, chaque élément est présent avec une probabilité
1/2. Les opérations de recherche, insertion et suppression ont une complexité O(log n) en espérance. Simple à
implémenter et concurrent (utile dans les systèmes multi-threads).

6.6 — Structures de données avancées pour les graphes

Link-Cut Trees (Sleator & Tarjan) : gèrent dynamiquement des forêts de chemins, permettant des requêtes et
modifications en O(log n) amorti. Fondamentaux pour les algorithmes de flot maximal et les arbres couvrants
dynamiques. Euler Tour Trees : représentent un arbre par son tour d'Euler stocké dans une structure de données
d'arbres équilibrés, permettant des requêtes sur les sous-arbres en O(log n).

6.7 — Structures de données géométriques

K-d Trees : arbres binaires qui partitionnent un espace à k dimensions. Permettent des recherches par région et de plus
proche voisin efficaces dans des espaces multidimensionnels. Arbres R (R-Trees) : généralisent les B-Trees aux objets
géométriques (rectangles, polygones). Utilisés dans PostGIS et les bases de données spatiales. Quadtrees et Octrees :
partitionnent récursivement un espace 2D (quadtree) ou 3D (octree) en régions. Convex Hull : l'enveloppe convexe d'un
ensemble de points — algorithme de Graham scan en O(n log n).
📚 Ressources Phase 6 : CLRS Chapitres 13 (Red-Black Trees), 18 (B-Trees), 21 (Union-Find) — 'Algorithms'
(Sedgewick & Wayne) : sections sur les arbres équilibrés — Competitive Programmer's Handbook (Laaksonen,
gratuit en ligne) chapitres sur les structures avancées — Codeforces : EDU section (Segment Tree, DSU) — CP-
[Link] : référence exhaustive
 PHASE 7

ALGORITHMIE AVANCÉE
Les paradigmes et techniques de l'élite

7.1 — Programmation Dynamique (Dynamic Programming)

La programmation dynamique (Bellman, 1957) est l'une des techniques algorithmiques les plus puissantes et les plus
importantes. Elle s'applique aux problèmes ayant deux propriétés fondamentales : la sous-structure optimale (la
solution optimale du problème global contient les solutions optimales de ses sous-problèmes) et les sous-problèmes qui
se chevauchent (les mêmes sous-problèmes sont résolus plusieurs fois lors d'une approche naïve récursive).

7.1.1 — Deux approches de la DP

Top-down avec mémoïsation (memoization) : implémentation récursive naturelle, avec une table de mémoïsation
(tableau ou dictionnaire) pour stocker les résultats déjà calculés. Chaque sous-problème n'est calculé qu'une seule fois.
Intuitif mais avec un overhead de récursion.
Bottom-up (tabulation) : remplir itérativement un tableau DP dans l'ordre croissant des sous-problèmes, garantissant
que les dépendances sont calculées avant d'être utilisées. Plus efficace en pratique (pas de récursion, meilleure localité
mémoire).

7.1.2 — Problèmes classiques de DP à maîtriser

Fibonacci (introduction) : calcul naïf O(2ⁿ), avec mémoïsation O(n). Plus grand sous-tableau croissant (LIS — Longest
Increasing Subsequence) : O(n²) naïf avec DP, O(n log n) avec patience sorting. Plus longue sous-séquence commune
(LCS — Longest Common Subsequence) : O(mn) — fondamental pour diff, alignement de séquences biologiques.
Distance d'édition (Edit Distance / Levenshtein) : O(mn) — correcteurs orthographiques, comparaison de chaînes ADN.
Problème du sac à dos (0/1 Knapsack) : O(nW) — optimisation combinatoire, allocation de ressources. Problème de la
monnaie (Coin Change) : O(nk) — nombre minimal de pièces pour une somme. Multiplication de matrices (Matrix
Chain) : O(n³) — ordre optimal de multiplication pour minimiser les opérations. Décodage de chaînes, partition de
tableaux, calcul de chemins dans des grilles.

7.1.3 — Techniques avancées de DP

DP sur les intervalles : état DP[i][j] représente la solution optimale pour l'intervalle [i, j]. Exemples : multiplication de
chaînes de matrices, optimal BST, palindrome partitioning.
DP sur les arbres : calculer des propriétés globales d'un arbre par des DP depuis les feuilles vers la racine. Problème de
la couverture indépendante maximale, centroïde, DP sur le diamètre.
DP sur les sous-ensembles (bitmask DP) : l'état DP[mask] représente une propriété pour le sous-ensemble encodé par le
masque binaire 'mask'. Complexité O(2ⁿ × n). Problème du voyageur de commerce (TSP) : O(2ⁿ × n²). Comptage de
couvertures de sommet.
DP avec optimisation de diviser-pour-régner : optimisation d'une DP à deux dimensions lorsque l'indice optimal du
dernier état satisfait une propriété de monotonie. Réduit O(n²) à O(n log n). Knuth's optimization : O(n²) → O(n²) avec
une constante réduite. Convex Hull Trick (CHT) : optimise les DP avec des transitions de type min(ax+b) en utilisant une
enveloppe convexe. Réduit O(n²) à O(n log n) ou O(n) si les pentes sont monotones.
Alien trick (Lambda optimization) : technique permettant de résoudre des DP avec contrainte de cardinalité
(exactement k groupes, k opérations) en transformant la contrainte en une pénalité λ et en effectuant une recherche
binaire sur λ. Réduit la dimension d'état.

7.2 — Algorithmes gloutons (Greedy)

Un algorithme glouton fait à chaque étape le choix localement optimal, espérant que cela mène à une solution
globalement optimale. Contrairement à la DP, il ne reconsidère jamais ses choix. La difficulté réside dans la preuve que
la stratégie gloutonne est correcte, ce qui nécessite généralement de prouver soit la propriété de choix glouton (le
choix glouton est toujours compatible avec une solution optimale), soit l'optimalité par échange (greedy stays ahead /
exchange argument).
Exemples canoniques : algorithme de Kruskal et Prim (MST), algorithme de Dijkstra, problème de sélection d'activités
(Activity Selection), codage de Huffman (compression optimale sans perte), fractional knapsack (sac à dos
fractionnable). Matroïdes : cadre général permettant de prouver qu'un algorithme glouton est optimal pour une classe
de problèmes.

7.3 — Théorie des flots (Network Flow)

Le problème du flot maximum (Max-Flow) consiste à trouver le flot maximal pouvant transiter d'une source s à un puits
t dans un réseau orienté avec des capacités sur les arêtes. La dualité fondamentale est le théorème Max-Flow Min-Cut
(Ford & Fulkerson, 1956) : le flot maximum est égal à la capacité minimale d'une coupe séparant s de t.
Algorithmes : Ford-Fulkerson (augmentation de chemins, O(E × maxflow) — peut ne pas terminer pour des capacités
irrationnelles), Edmonds-Karp (Ford-Fulkerson avec BFS pour trouver le chemin augmentant le plus court, O(VE²)), Dinic
(utilise des réseaux de niveaux et des flots bloquants, O(V²E), O(E√V) pour les graphes unitaires), Push-Relabel (O(V²E)
ou O(V³)).
Applications et réductions : couplage maximum biparti (se réduit en flot max), problème de transport, flot de coût
minimum (min-cost max-flow), circulation avec demandes, problème d'affectation (algorithme hongrois O(n³)).

7.4 — Théorie des cordes et hachage de Rabin-Karp

Les algorithmes sur les chaînes de caractères sont fondamentaux en bioinformatique, en traitement de texte et en
compétition. Les algorithmes fondamentaux à maîtriser sont :
• Algorithme de Knuth-Morris-Pratt (KMP) : recherche de motif en O(n + m) grâce à la fonction de préfixe (failure
function). Élimine les recomparisons inutiles.
• Algorithme de Boyer-Moore : recherche en temps sous-linéaire en pratique grâce aux règles du mauvais caractère
et du bon suffixe. Très efficace pour les grands alphabets.
• Algorithme de Rabin-Karp : hachage glissant (rolling hash) pour rechercher plusieurs motifs simultanément. O(n +
m) en espérance.
• Z-algorithm : calcule le tableau Z[i] = longueur du plus long préfixe de s qui commence à la position i. O(n), utile
pour de nombreux problèmes de chaînes.
• Automates finis (finite automata) pour la recherche de motifs.
• Suffix Arrays et Suffix Trees : permettent de répondre en O(m log n) ou O(m) à des requêtes de recherche sur un
texte de longueur n. Fondamentaux pour la bioinformatique (alignement de génomes).
• Algorithme d'Aho-Corasick : généralisation de KMP pour rechercher simultanément plusieurs motifs dans un texte
en O(n + m + k) où k est le nombre de correspondances. Construit un automate sur un trie.

7.5 — Transformée de Fourier rapide (FFT)

La FFT (Fast Fourier Transform, Cooley-Tukey 1965) calcule la transformée de Fourier discrète (DFT) en O(n log n) au
lieu de O(n²). C'est l'un des algorithmes les plus importants du XXe siècle. Applications algorithmiques : multiplication
de polynômes en O(n log n) (alors que la multiplication naïve est O(n²)), multiplication de grands entiers en O(n log n log
log n), convolution de signaux.
La DFT transforme une séquence de n nombres complexes en n fréquences complexes. La FFT divise récursivement le
calcul en deux DFT de taille n/2 (séparation pairs/impairs), d'où la récurrence T(n) = 2T(n/2) + O(n) → O(n log n). La
transformée de Fourier modulaire (NTT — Number Theoretic Transform) effectue la FFT dans un corps fini Z/pZ — évite
les erreurs d'arrondi des flottants et est utilisée en compétition et en cryptographie.

7.6 — Algorithmes randomisés

Les algorithmes randomisés utilisent des choix aléatoires pour obtenir de meilleures performances en espérance ou en
probabilité. Deux types : Las Vegas (toujours correct, temps aléatoire — ex: Quicksort avec pivot aléatoire) et Monte
Carlo (temps déterministe, résultat correct avec haute probabilité — ex: test de Miller-Rabin pour la primalité, hachage
de Rabin-Karp).
Techniques fondamentales : randomisation (mélanger les données pour éviter le pire cas), amplification (répéter un
algorithme Monte Carlo pour augmenter la probabilité de succès), hachage universel, min-cut de Karger (O(n² log n)
pour le coupe minimum en probabilité).

7.7 — Géométrie algorithmique

La géométrie algorithmique traite des problèmes sur des objets géométriques (points, segments, polygones). Notions
fondamentales : produit vectoriel (détermine l'orientation de trois points — anti-horaire, horaire, colinéaire),
intersection de segments (test algorithmique via le produit vectoriel et les intervalles), balayage de ligne (sweep line —
technique fondamentale consistant à balayer le plan avec une ligne verticale).
Algorithmes fondamentaux : enveloppe convexe (Graham Scan O(n log n), Jarvis March O(nh)), plus proche paire de
points (divide and conquer O(n log n)), triangulation de Delaunay et diagramme de Voronoï (duale l'un de l'autre, O(n
log n)), algorithme de Shamos-Hoey (détection d'intersections O(n log n)), algorithme de Bentley-Ottmann
(énumération de toutes les intersections O((n+k) log n)).
📚 Ressources Phase 7 : CLRS Chapitres 15 (Dynamic Programming), 16 (Greedy), 26 (Max Flow) — 'Algorithm
Design' (Kleinberg & Tardos) — 'Competitive Programming 3' (Steven Halim) — [Link] (DP, String
Algorithms, Geometry, FFT) — Codeforces : résoudre des problèmes Div2 C/D — KACTL (KTH Algorithm
Competition Template Library) pour référence
 PHASE 8

COMPÉTITION & PROBLEM SOLVING D'ÉLITE

L'art de résoudre l'impossible sous pression

8.1 — Mindset et méthodologie du compétiteur d'élite

La compétition algorithmique (ICPC, IOI, Codeforces, Leetcode) est un sport intellectuel exigeant bien plus que la simple
connaissance des algorithmes. Les grands compétiteurs comme Tourist (Gennady Korotkevich), Petr Mitrichev ou
Um_nik possèdent des compétences qui transcendent la maîtrise technique.
La méthodologie du problem solving compétitif : lire et analyser l'énoncé avec précision extrême (identifier entrées,
sorties, contraintes, exemples), reformuler le problème en langage mathématique formel, identifier la catégorie du
problème (graphe ? DP ? greedy ? géométrie ?), générer des hypothèses sur la solution et les tester contre les exemples
et des cas limites, implémenter proprement et rapidement, tester exhaustivement (cas limite, n=1, n=max, réponse=0).

8.2 — Techniques avancées de Problem Solving

8.2.1 — Réductions et équivalences
Réduire un problème inconnu à un problème connu est une compétence fondamentale. Si le problème A se réduit à B,
alors un algorithme pour B résout A. Exemples courants : problèmes de chemin → graphe + BFS/Dijkstra, problèmes
d'ordonnancement → tri topologique ou glouton, problèmes de comptage → DP, problèmes de matching → flot max
ou couplage biparti.

8.2.2 — Techniques de deux pointeurs et fenêtre glissante

La technique des deux pointeurs utilise deux indices se déplaçant sur un tableau pour résoudre des problèmes en O(n)
au lieu de O(n²). La fenêtre glissante maintient un sous-tableau de taille fixe ou variable satisfaisant une condition,
glissant de gauche à droite. Applications : sous-tableau de somme maximale, paire de somme dans un tableau trié, plus
long sous-tableau sans répétition.

8.2.3 — Bit manipulation

Les opérations bit à bit (AND &, OR |, XOR ^, NOT ~, décalage gauche <<, décalage droit >>) permettent des algorithmes
ultra-rapides sur les entiers. Applications : vérifier si un bit est actif, activer/désactiver/inverser un bit, compter les bits
actifs (popcount), isoler le bit le plus bas (n & -n), itérer sur tous les sous-ensembles d'un masque (for mask = S; mask >
0; mask = (mask-1) & S). L'itération sur tous les sous-ensembles de taille k est fondamentale pour la bitmask DP.

8.2.4 — Techniques de requêtes hors ligne

Certains problèmes de requêtes sur des intervalles se résolvent plus efficacement en traitant les requêtes dans un ordre
différent de celui donné (hors ligne). Techniques : algorithme de Mo (square root decomposition — traitement des
requêtes dans un ordre optimisé pour minimiser les déplacements des pointeurs, O((n + q)√n)), algorithme de Mo avec
arbre (pour requêtes sur des chemins dans un arbre), traitement par ordre croissant de la borne droite.

8.2.5 — Décomposition racine carrée (Sqrt Decomposition)

La décomposition racine carrée est une technique universelle permettant d'obtenir des performances O(√n) par
requête en découpant un tableau en blocs de taille √n. Simple à implémenter et très robuste. Utilisée quand aucune
structure de données avancée n'est connue pour un problème.

8.3 — Théorie des jeux algorithmique

La théorie des jeux combinatoires étudie les jeux à deux joueurs à information parfaite et sans hasard. Notions
fondamentales : position gagnante (le joueur à jouer peut forcer une victoire), position perdante (tout mouvement
mène à une position gagnante pour l'adversaire), jeu de Nim (prendre des objets sur des piles — la stratégie optimale
est basée sur le XOR des tailles de piles), valeur de Grundy/nimber (une position de jeu équivaut à un jeu de Nim d'une
certaine valeur), théorème de Sprague-Grundy (tout jeu impartiel est équivalent à un jeu de Nim par sa valeur de
Grundy).

8.4 — Algorithmes sur les arbres avancés

Ancêtre commun le plus bas (LCA — Lowest Common Ancestor) : étant donné deux nœuds u et v, trouver leur ancêtre
commun le plus profond. Algorithme naïf O(n) par requête, algorithme de Tarjan offline O(n + q) avec union-find, binary
lifting O(n log n) preprocessing + O(log n) par requête, Sparse Table sur l'Euler Tour O(n log n) preprocessing + O(1) par
requête (optimal).
Heavy-Light Decomposition (HLD) : décompose un arbre en chaînes de façon à ce que tout chemin racine-nœud
traverse O(log n) chaînes. Combinée avec un arbre de segments sur chaque chaîne, permet des requêtes et mises à jour
sur des chemins d'arbre en O(log² n). Fondamentale pour les problèmes de graphes pondérés sur les arbres.
Centroid Decomposition : décompose un arbre en centroïdes (nœud dont la suppression laisse des sous-arbres de taille
≤ n/2). La hauteur de la décomposition est O(log n). Permet de résoudre des problèmes sur les chemins en O(n log n) ou
O(n log² n).

8.5 — Algorithmes avancés sur les graphes

Composantes fortement connexes (SCC) : algorithme de Kosaraju (deux DFS, O(V+E)) et algorithme de Tarjan (un DFS,
O(V+E)) basé sur les low-link values. Applications : condensation d'un graphe, 2-SAT.
2-SAT (2-Satisfiabilité) : problème de satisfiabilité booléenne où chaque clause a exactement deux littéraux. Réductible
aux SCC sur un graphe d'implications en O(n + m) — soluble en temps polynomial (contrairement au 3-SAT qui est NP-
complet). Très fréquent en compétition.
Points d'articulation et ponts : un point d'articulation est un sommet dont la suppression déconnecte le graphe. Un
pont est une arête dont la suppression déconnecte le graphe. Algorithme de Tarjan en O(V+E). Applications : fiabilité
des réseaux, décomposition en composantes 2-connexes.
📚 Ressources Phase 8 : Codeforces : résoudre quotidiennement des problèmes (Div1 A/B/C ciblés) — USACO
(USA Computing Olympiad) : tous les problèmes de Gold et Platinum — AtCoder : ABC/ARC régulièrement —
'Competitive Programming 3' (Halim) — KACTL — [Link] — livres : 'Guide to Competitive
Programming' (Laaksonen)
 PHASE 9

DOMAINES SPÉCIALISÉS DE L'ÉLITE MONDIALE

Ce que le Top 1% maîtrise exclusivement

9.1 — Théorie de la complexité computationnelle

La théorie de la complexité classe les problèmes selon les ressources (temps, espace) nécessaires pour les résoudre.
C'est la théorie fondamentale qui distingue les problèmes 'faciles' des problèmes 'difficiles'.
Classes de complexité fondamentales : P (problèmes décidables en temps polynomial par une machine de Turing
déterministe), NP (problèmes dont les solutions peuvent être vérifiées en temps polynomial — Non-deterministic
Polynomial), co-NP (compléments des problèmes NP), PSPACE (résolubles en espace polynomial), EXPTIME (résolubles
en temps exponentiel).
La question P ≠ NP : le problème ouvert le plus important de l'informatique théorique. Si P = NP, tous les problèmes
dont on peut vérifier une solution rapidement pourraient aussi être résolus rapidement — ce qui briserait la
cryptographie moderne. Consensus très fort des chercheurs : P ≠ NP, mais non prouvé.
NP-complétude : un problème est NP-complet s'il est dans NP ET tout problème NP s'y réduit en temps polynomial. Les
problèmes NP-complets canoniques : SAT (Cook-Levin, 1971), 3-SAT, 3-COLORING, CLIQUE, VERTEX COVER,
HAMILTONIAN CIRCUIT, TSP de décision, SUBSET SUM. Pour prouver qu'un nouveau problème est NP-complet, on le
réduit depuis un problème NP-complet connu.
Au-delà de P et NP : classes #P (comptage des solutions NP), BPP (problèmes résolubles par algorithmes randomisés en
temps polynomial avec erreur < 1/3), ZPP, RP, la hiérarchie polynomiale PH, FPT (Fixed-Parameter Tractability —
résolution efficace si certains paramètres sont fixés).

9.2 — Algorithmique d'approximation

Pour les problèmes NP-difficiles (d'optimisation), on cherche des algorithmes d'approximation — des algorithmes
polynomiaux qui produisent des solutions garanties à un facteur constant de l'optimum. Un algorithme est ρ-
approximant si la solution produite est toujours dans un facteur ρ de l'optimal.
Exemples et techniques : algorithme 2-approximant pour Vertex Cover (matching maximal), algorithme (1-1/e)-
approximant pour Coverage Maximum (greedy glouton, optimal pour les fonctions submodulaires), schéma
d'approximation polynomial (PTAS) et FPTAS (fully polynomial), algorithme de Christofides pour TSP métrique (3/2-
approximation — record longtemps inégalé), hardness of approximation (prouver qu'on ne peut pas approximer mieux
que ρ sauf si P=NP, via le PCP theorem).

9.3 — Algorithmique en ligne et compétitive

Les algorithmes en ligne reçoivent les données une à une sans connaître le futur. La performance se mesure par le ratio
de compétitivité (competitive ratio) — rapport entre le coût de l'algorithme en ligne et le coût optimal hors ligne
(oracle). Algorithme k-compétitif : coût ≤ k × OPT pour toute entrée.
Problèmes et résultats canoniques : problème du ski (ski rental/rent-or-buy), problème du secrétaire (optimal stopping
— algorithme 1/e), paging et algorithmes de cache (LRU est k-compétitif pour un cache de taille k), algorithme de la
liste de Lykos.

9.4 — Cryptographie algorithmique

La cryptographie moderne est entièrement fondée sur l'algorithmique et la théorie de la complexité. Notions
fondamentales : chiffrement symétrique (AES — Advanced Encryption Standard), chiffrement asymétrique (RSA basé
sur la difficulté de factoriser de grands entiers, courbes elliptiques ECC), protocoles d'échange de clés (Diffie-Hellman),
fonctions de hachage cryptographiques (SHA-256, SHA-3).
Fondements algorithmiques de RSA : génération de nombres premiers (test de Miller-Rabin randomisé), exponentiation
modulaire rapide, algorithme d'Euclide étendu (calcul de l'inverse modulaire), théorème de Fermat et d'Euler.
Algorithmes de factorisation : crible quadratique O(exp(√(log n log log n))), GNFS (General Number Field Sieve — le plus
rapide connu, O(exp((log n)^(1/3) (log log n)^(2/3))))).
Cryptographie post-quantique : résistance aux ordinateurs quantiques. Algorithmes candidats NIST : CRYSTALS-Kyber
(KEM basé sur LWE), CRYSTALS-Dilithium (signatures), NTRU (lattice-based). Algorithme de Shor (quantique) : factorise
en O((log n)³) — rendrait RSA obsolète.

9.5 — Algorithmique des flux de données (Streaming)

Les algorithmes de streaming traitent des données en un seul passage (ou quelques passages) avec une mémoire sous-
linéaire O(polylog(n)). Fondamentaux pour les big data, la surveillance réseau, les bases de données. Techniques :
sampling (échantillonnage aléatoire), sketching (compression linéaire des données), structures de données
probabilistes.
Algorithmes canoniques : comptage d'éléments distincts (Flajolet-Martin, HyperLogLog — utilisé par Facebook et
Google), éléments fréquents (Count-Min Sketch, misra-gries), moments de fréquence (algorithme d'AMS), détection de
seuil (majority vote — Boyer-Moore).

9.6 — Algorithmique parallèle et distribuée

Les algorithmes parallèles exploitent plusieurs processeurs ou cœurs simultanément. Modèles : PRAM (Parallel RAM —
partage de mémoire parfait, idéalisation), BSP (Bulk Synchronous Parallel), MPI (Message Passing Interface), GPU (SIMD
massif). Mesures de performance : travail total W(n) et profondeur D(n) (critical path — longueur du chemin le plus
long). Un algorithme parallèle optimal satisfait W(n) = O(travail séquentiel optimal) et D(n) = O(polylog(n)).
Algorithmes parallèles fondamentaux : somme préfixe parallèle (parallel prefix/scan) en O(log n) profondeur — brique
de base de nombreux algorithmes parallèles, tri bitonique (bitonic sort) en O(log² n) profondeur, recherche de
composantes connexes en O(log² n), flot parallèle. MapReduce et ses algorithmes (Google, 2004) : modèle distribué
pour le big data.

9.7 — Algorithmique quantique

L'informatique quantique exploite les principes de la mécanique quantique (superposition, intrication) pour calculer.
Les qubits existent dans une superposition de 0 et 1 ; la mesure collapse l'état. Un ordinateur quantique de n qubits
explore simultanément 2ⁿ états.
Algorithmes quantiques fondamentaux : algorithme de Grover (recherche non structurée en O(√N) au lieu de O(N) —
speedup quadratique), algorithme de Shor (factorisation en O((log n)³) — speedup exponentiel pour RSA), algorithme
de Deutsch-Jozsa, QFT (Quantum Fourier Transform), simulation quantique (application primaire des ordinateurs
quantiques). Complexité quantique : classes BQP (problèmes résolubles en temps polynomial quantique), QMA.

9.8 — Apprentissage automatique algorithmique

L'intersection entre l'algorithmique et le machine learning est un domaine de recherche actif. Fondements
algorithmiques : gradient descent (descente de gradient) et ses variantes (SGD, Adam, AdaGrad), algorithmes
d'optimisation convexe, apprentissage PAC (Probably Approximately Correct — cadre théorique de Valiant), théorie VC
(Vapnik-Chervonenkis dimension — mesure de la complexité d'un modèle), algorithmes de noyau (SVM), forêts
aléatoires (random forests), boosting (AdaBoost — algorithme de boosting PAC-optimal de Schapire).

9.9 — Algorithmique dans les bases de données

Les bases de données relationnelles reposent sur l'algorithmique avancée. Optimisation de requêtes SQL : le
planificateur de requêtes (query planner) choisit le plan d'exécution optimal (ordre des jointures, utilisation d'index).
Algorithmes de jointure : nested loop join O(nm), hash join O(n+m), sort-merge join O((n+m) log(n+m)). Index : B+-
Trees pour les recherches par plage, hash index pour l'égalité, index bitmap, index inversé (TF-IDF pour la recherche
plein-texte). OLAP et data warehousing : star schema, cube de données, algorithmes de rollup.
📚 Ressources Phase 9 : Livres : 'Introduction to the Theory of Computation' (Sipser) — 'Approximation
Algorithms' (Vazirani) — 'Quantum Computation and Quantum Information' (Nielsen & Chuang) —
'Randomized Algorithms' (Motwani & Raghavan) — Cours : MIT 6.854 Advanced Algorithms — MIT 18.404J
Theory of Computation — [Link] pour les dernières recherches
 PHASE 10

RECHERCHE & INNOVATION — LE SOMMET

Créer la connaissance, pas seulement la consommer

10.1 — Lecture et compréhension de la littérature scientifique

Les meilleurs algorithmiciens du monde ne se contentent pas de consommer des connaissances existantes — ils créent
de nouvelles connaissances. La première étape est de savoir lire et comprendre des articles de recherche en
algorithmique. Les conférences de référence sont : STOC (Symposium on Theory of Computing), FOCS (Foundations of
Computer Science), SODA (Symposium on Discrete Algorithms), ESA (European Symposium on Algorithms), ICALP, CCC
(Computational Complexity Conference).
Méthode de lecture d'un article scientifique : lire d'abord le titre, l'abstract et la conclusion pour comprendre la
contribution ; lire ensuite l'introduction pour les motivations, la comparaison avec l'état de l'art et les idées clés ; lire les
théorèmes principaux et leurs preuves en détail ; implémenter les algorithmes décrits pour vérifier la compréhension.

10.2 — Problèmes ouverts importants en algorithmique

S'exposer aux grands problèmes ouverts développe la vision scientifique. Quelques problèmes ouverts fondamentaux :
P vs NP (le plus grand), la complexité exacte du tri (peut-on trier avec moins de n log₂ n comparaisons en pire cas ?), la
multiplication matricielle optimale (O(n^ω) avec ω → 2 ou ω = 2 est-il atteignable ?), les lower bounds de l'arbre
couvrant minimum (peut-on faire mieux que O(m α(n)) ?), la complexité de l'édition d'un graphe, conjecture 3-SUM
(base de nombreux lower bounds de géométrie computationnelle).

10.3 — Contribution à la communauté

Les algorithmiciens d'élite mondiale participent activement à leur communauté : contribuer à des bibliothèques open
source (LEMON graph library, CGAL pour la géométrie), écrire des tutoriels et articles de vulgarisation (Codeforces
blogs, [Link]), créer des problèmes de compétition de haut niveau, encadrer des jeunes compétiteurs,
participer à des conférences et ateliers, soumettre des articles de recherche.

10.4 — Outils de l'algorithmicien de haut niveau

Un algorithmicien expert maîtrise un écosystème d'outils : langage C++ pour la compétition (STL, optimisations,
pragmas), Python pour le prototypage rapide (NumPy, SciPy, NetworkX), Jupyter Notebooks pour l'exploration,
Mathematica/Sage pour les calculs symboliques, CPLEX/Gurobi pour l'optimisation linéaire/entière, Coq/Lean/Isabelle
pour la vérification formelle de preuves.

10.5 — Développer l'intuition algorithmique

L'intuition algorithmique — cette capacité à sentir quel paradigme ou quelle structure convient à un problème avant
même d'avoir analysé formellement — se développe uniquement par une exposition massive et variée à des
problèmes. Cela nécessite des années de pratique intense, une réflexion méta sur ses propres erreurs, la lecture des
solutions des meilleurs compétiteurs, et la résolution de problèmes dans des domaines variés.
Le top 1% mondial se distingue par : la rapidité d'identification du paradigme correct (souvent en quelques minutes), la
capacité à combiner plusieurs techniques (DP + graphe + géométrie), la robustesse face aux problèmes jamais vus, et
surtout la capacité à innover — à trouver de nouvelles réductions ou structures adaptées à un problème nouveau.
📚 Ressources Phase 10 : [Link] ([Link], [Link], [Link]) — ECCC (Electronic Colloquium on Computational
Complexity) — Theory of Computing Journal — Compte Twitter/X : @CompScienceNews, @arXiv_cs_DS —
Séminaires en ligne : Simons Institute (Berkeley), DIMACS — Rejoindre : SIGACT (ACM Special Interest Group on
Algorithms and Computation Theory)
ANNEXE A — Bibliothèque de Ressources Complète

Livres fondamentaux (classés par niveau)

Débutant → Intermédiaire
• 'Introduction to Algorithms' (CLRS — Cormen, Leiserson, Rivest, Stein) — La bible absolue. Couvre tout de façon
rigoureuse. 4e édition (2022). À lire entièrement.
• 'Algorithm Design' (Kleinberg & Tardos) — Excellent pour les paradigmes (DP, greedy, graphes). Approche
pédagogique exemplaire. Chapitres très bien structurés.
• 'Algorithms' (Sedgewick & Wayne) — Avec des implémentations Java. Très bon pour les structures de données et les
graphes. Site web compagnon avec des visualisations.
• 'Grokking Algorithms' (Bhargava) — Introduction très visuelle et accessible pour les débutants absolus. Pas rigoureux
mais excellent pour l'intuition initiale.
• 'Concrete Mathematics' (Graham, Knuth, Patashnik) — Les mathématiques discrètes pour informaticiens. Rigoureux
et élégant. Indispensable pour l'analyse d'algorithmes.

Intermédiaire → Avancé
• 'The Art of Computer Programming' (Knuth, 4 volumes) — L'œuvre magistrale de Donald Knuth. Traité
encyclopédique sur les algorithmes. Volume 1 (Fundamental Algorithms), Volume 2 (Seminumerical Algorithms),
Volume 3 (Sorting and Searching). Le niveau de rigueur mathématique est exceptionnel.
• 'Competitive Programming 3' (Steven Halim & Felix Halim) — Le référentiel de l'algorithmie compétitive. Couvre tous
les topics de compétition avec des problèmes UVa associés.
• 'Guide to Competitive Programming' (Antti Laaksonen) — Plus accessible que CP3. Disponible partiellement gratuit.
Basé sur le CSES problem set.
• 'Randomized Algorithms' (Motwani & Raghavan) — La référence sur les algorithmes randomisés. Rigoureux et
complet.

Avancé → Expert
• 'Approximation Algorithms' (Vazirani) — La référence sur les algorithmes d'approximation. Prouve les garanties
d'approximation rigoureusement.
• 'Introduction to the Theory of Computation' (Sipser) — La meilleure introduction à la théorie de la complexité.
Pédagogie remarquable.
• 'Computational Geometry: Algorithms and Applications' (de Berg et al.) — La référence en géométrie algorithmique.
• 'Data Structures and Network Algorithms' (Tarjan) — Structures de données avancées par leur créateur. Dense et
révélateur.

Plateformes d'entraînement (classées par usage)

• LeetCode ([Link]) : indispensable pour les entretiens FAANG. Focus sur les problèmes pratiques. Niveau
Easy/Medium/Hard bien calibré.
• Codeforces ([Link]) : la plateforme numéro 1 pour la compétition algorithmique. Contests réguliers (Div1 à
Div4), section EDU, Gym. Le meilleur endroit pour progresser rapidement.
• AtCoder ([Link]) : problèmes de très haute qualité, souvent mathématiquement profonds. ABC/ARC/AGC
hebdomadaires.
• USACO ([Link]) : olympiade informatique américaine. Progresser de Bronze à Platinum. Excellente progression
pédagogique.
• CSES Problem Set ([Link]/problemset) : 300 problèmes couvrant systématiquement tous les topics algorithmiques.
Indispensable.
• Kattis ([Link]) : large collection de problèmes d'ICPC.
• Hackerrank ([Link]) : bon pour les débutants, focus entretiens.
• Project Euler ([Link]) : problèmes mathématico-algorithmiques. Excellent pour la théorie des nombres.

Cours en ligne recommandés

• MIT OpenCourseWare 6.006 'Introduction to Algorithms' (gratuit) — Les vidéos des meilleures leçons de MIT.
Exercices corrigés inclus.
• MIT OpenCourseWare 6.046J 'Design and Analysis of Algorithms' (gratuit) — Niveau avancé. Complément de 6.006.
• MIT 6.042J 'Mathematics for Computer Science' (gratuit) — Mathématiques discrètes complètes.
• Stanford Algorithms Specialization (Tim Roughgarden, Coursera) — 4 cours couvrant tout de Divide & Conquer à NP-
Completeness.
• Princeton Algorithms I & II (Sedgewick, Coursera) — Excellent niveau intermédiaire avec visualisations.
• [Link] — La référence la plus complète de l'algorithmie compétitive en anglais. Couvre tout avec des
explications et du code.
• KACTL ([Link]/kth-competitive-programming/kactl) — Template de code KTH pour la compétition. La référence
implémentation pour ICPC.

Sites de référence et communautés

• [Link] : tutoriels détaillés sur tous les algorithmes importants.
• [Link] : visualisation interactive de structures de données et algorithmes.
• [Link] : tableau de référence des complexités.
• [Link] : apprentissage interactif des mathématiques et de l'informatique.
• r/algorithms et r/cscareerquestions (Reddit) : communautés actives.
• Codeforces Blogs : les meilleurs algorithmiciens du monde y partagent des tutoriels.
ANNEXE B — Tableau Synthétique de Complexités
Référence rapide des complexités des algorithmes et structures de données les plus importants :
Structure / Algorithme Meilleur Moyen Pire

Tableau — Accès O(1) O(1) O(1)

Tableau — Recherche O(1) O(n) O(n)
Liste chaînée — Accès O(1) O(n) O(n)
Table de hachage O(1) O(1) O(n)
BST — Recherche O(log n) O(log n) O(n)
AVL/RB-Tree O(log n) O(log n) O(log n)
Tas (Heap) — Accès max O(1) O(1) O(1)
Tri par sélection O(n²) O(n²) O(n²)
Tri par insertion O(n) O(n²) O(n²)
Tri fusion O(n log n) O(n log n) O(n log n)
Tri rapide O(n log n) O(n log n) O(n²)
Tri par tas O(n log n) O(n log n) O(n log n)
Recherche binaire O(1) O(log n) O(log n)
BFS / DFS O(V+E) O(V+E) O(V+E)
Dijkstra (tas binaire) — O((V+E)log V) O((V+E)log V)
Bellman-Ford O(VE) O(VE) O(VE)
Floyd-Warshall O(V³) O(V³) O(V³)
FFT O(n log n) O(n log n) O(n log n)

ANNEXE C — Feuille de Route Condensée

Phase 1 : Pensée algorithmique, pseudocode, variables, contrôle, récursivité (1-2 mois)
Phase 2 : Logique, démonstrations, combinatoire, théorie des nombres, graphes intro, probabilités (2-3 mois)
Phase 3 : Arrays, listes, piles, files, hash tables, BST, heaps, notation Big O (2 mois)
Phase 4 : Tris (O(n²) → O(n) → O(n log n)), BFS/DFS, Dijkstra, Bellman-Ford, Floyd, MST (3 mois)
Phase 5 : Amortized analysis, complexité spatiale, borne inférieure, cache, récurrences (2 mois)
Phase 6 : AVL, Red-Black, B-Trees, Segment Trees, Fenwick, Union-Find, Tries, Skip Lists (3 mois)
Phase 7 : DP (toutes variantes), Greedy, Max Flow, String Algorithms, FFT, Randomized (4 mois)
Phase 8 : Compétition, 2-SAT, SCC, LCA, HLD, Centroid, Bitmask, Sqrt Decomp, Mo's (6-12 mois)
Phase 9 : Théorie de la complexité, Approximation, Streaming, Quantique, Crypto, Parallèle (1-2 ans)
Phase 10 : Recherche, articles, problèmes ouverts, contribution, innovation (continu)

────────────────────────────────────────────────────────
 « Un expert est une personne qui a fait toutes les erreurs

qui peuvent être faites dans un domaine très étroit. »

— Niels Bohr

────────────────────────────────────────────────────────

La maîtrise de l'algorithmie est un voyage de toute une vie.

Commencez aujourd'hui. Soyez constant. Devenez l'exception.