23 — Annexes : glossaire et cheat sheets

Ce chapitre est la référence rapide de la formation. Il contient un glossaire de plus de 200 termes (français/anglais), les cheat sheets Big-O complètes, des templates d'algorithmes prêts à adapter, les méthodes de résolution de récurrences et les complexités des opérations par structure de données.

---

Sommaire

1. Glossaire : A – D
2. Glossaire : E – I
3. Glossaire : J – M
4. Glossaire : N – R
5. Glossaire : S – Z
6. Big-O cheat sheet : structures
7. Big-O cheat sheet : tris
8. Big-O cheat sheet : fonctions de croissance
9. Templates d'algorithmes
10. Résolution de récurrences
11. Complexités des opérations par structure
12. Formules utiles

---

1. Glossaire : A – D

• Algorithme (algorithm) — suite finie et non ambiguë d'instructions transformant une entrée en sortie.
• Algorithme déterministe — algorithme dont la sortie est entièrement déterminée par l'entrée.
• Algorithme probabiliste — algorithme utilisant l'aléatoire (Monte Carlo, Las Vegas).
• Algorithme en ligne (online) — traite l'entrée au fur et à mesure, sans connaissance du futur.
• Algorithme hors ligne (offline) — connaît toute l'entrée avant de commencer.
• Amorti (amortized) — coût moyen d'une opération sur une séquence, borne supérieure sur tout préfixe.
• Anagramme — chaîne réarrangement exact d'une autre (mêmes caractères, mêmes fréquences).
• Analyse asymptotique — étude du comportement d'un algorithme quand la taille tend vers l'infini.
• Arbre (tree) — graphe connexe acyclique.
• Arbre AVL — ABR auto-équilibré : facteur d'équilibre |hauteur gauche − hauteur droite| ≤ 1.
• Arbre B (B-tree) — arbre équilibré multi-voies pour les stockages externes.
• Arbre binaire — arbre dont chaque nœud a au plus 2 enfants.
• Arbre binaire de recherche (ABR / BST) — clé gauche < clé nœud < clé droite.
• Arbre de recherche (search tree) — structure ordonnée par clés avec opérations de recherche.
• Arbre de suffixes (suffix tree) — arbre compressé représentant tous les suffixes d'une chaîne.
• Arbre équilibré — arbre dont la hauteur reste O(log n) après insertion/suppression.
• Arbre rouge-noir (red-black tree) — BST auto-équilibré avec nœuds colorés et 5 invariants.
• Arbre couvrant de poids minimum (MST) — sous-ensemble d'arêtes reliant tous les sommets de poids total minimal.
• Arbre trié / trie (prefix tree) — arbre dont les chemins représentent des préfixes de clés.
• Architecture von Neumann — machine à programme enregistré (données et instructions en mémoire).
• Backtracking — recherche exhaustive avec retour en arrière et élagage.
• Bellman-Ford — plus courts chemins depuis une source avec poids négatifs ; détecte les cycles négatifs.
• BFS (parcours en largeur) — exploration par niveaux, à l'aide d'une file FIFO.
• Bidon (bucket) — compartiment d'une table de hachage (chaînage).
• Bipartition / graphe biparti — graphe coloriable avec 2 couleurs.
• Bornes supérieure/inférieure (upper/lower bound) — limites O / Ω de la complexité.
• Branch and bound — optimisation par recherche avec bornes pour élaguer.
• Brute force — résolution par essai de toutes les possibilités.
• Bubble sort (tri à bulles) — tri par échanges successifs d'éléments adjacents.
• Cache — mémoire rapide temporaire pour accélérer les accès répétés.
• Cas limite (edge case) — entrée exceptionnelle (vide, taille 1, valeurs extrêmes).
• Chaînage (chaining) — gestion des collisions de hachage par listes.
• Chemin critique — chemin le plus long dans un graphe de dépendances.
• Clé (key) — valeur sur laquelle on compare/hache les éléments.
• Cluster — groupe de nœuds partageant une fonctionnalité (systèmes distribués).
• Code de Huffman — code préfixe optimal par fréquences (greedy).
• Codage préfixe (prefix code) — aucun mot de code n'est préfixe d'un autre.
• Coefficient binomial C(n,k) — nombre de façons de choisir k éléments parmi n.
• Collision (hash) — deux clés distinctes mappées vers le même index.
• Complexité spatiale — quantité de mémoire utilisée en fonction de la taille d'entrée.
• Complexité temporelle — temps d'exécution en fonction de la taille d'entrée.
• Composante connexe — sous-ensemble maximal de sommets mutuellement atteignables.
• Composante fortement connexe (SCC) — composante connexe dans un graphe orienté (atteignabilité mutuelle).
• Compression — réduction de la taille des données (sans perte / avec perte).
• Congruence — relation de divisibilité : a ≡ b (mod m) ⇔ m | (a−b).
• Connexe (graphe) — tout sommet atteignable depuis tout autre.
• Consistent hashing — hachage stable lors de l'ajout/retrait de nœuds (caches distribués).
• Convex hull (enveloppe convexe) — plus petit ensemble convexe contenant des points.
• Count sort (tri comptage) — tri par comptage des occurrences, clés en intervalle borné.
• Cycle — chemin dont le premier sommet est aussi le dernier (longueur ≥ 1).
• Cycle négatif — cycle dont la somme des poids est négative (Bellman-Ford le détecte).
• DAG — graphe orienté acyclique (support du tri topologique).
• Deque — file à double extrémité (insertion/suppression aux deux bouts).
• Déterminisme — propriété d'un algorithme de toujours produire la même sortie pour la même entrée.
• DFS (parcours en profondeur) — exploration récursive, à l'aide d'une pile (implicite ou explicite).
• Dijkstra — plus courts chemins depuis une source, poids non négatifs, file prioritaire.
• Diviser pour régner (divide & conquer) — diviser, résoudre récursivement, combiner.
• Doublon — valeur apparaissant plus d'une fois.
• DP (programmation dynamique) — résolution par combinaison de sous-problèmes avec mémorisation.
• DP bottom-up — remplissage itératif d'une table d'états.
• DP top-down — récursion avec cache (memoization).
• Dummy node (nœud factice) — sentinelle pour simplifier les opérations sur les listes.
• Dynamique (structure) — dont la taille peut changer pendant l'exécution.

---

2. Glossaire : E – I

• Editorial — solution officielle expliquée d'un problème de compétition.
• Efficacité — mesure de la qualité d'un algorithme (temps/mémoire).
• Élagage (pruning) — élimination de branches ne pouvant pas mener à une solution.
• Enfant / parent / feuille / racine — vocabulaire des arbres.
• Entrée (input) — données fournies à un algorithme.
• Équivalence asymptotique Θ — croissance identique à une fonction donnée.
• Équilibrage (balancing) — maintenance de la hauteur d'un arbre.
• Euclide (algorithme d') — calcul du PGCD par modulos successifs.
• Exponentiation rapide (fast exponentiation) — a^b en O(log b) par carrés successifs.
• Factorielle — produit de 1 à n ; sert aux dénombrements.
• Facteur d'équilibre — différence de hauteurs des sous-arbres (AVL : |f| ≤ 1).
• Facteur de charge (load factor) — nombre de clés / taille de la table de hachage.
• File (queue / FIFO) — structure premier entré, premier sorti.
• File prioritaire (priority queue) — file dont l'élément prioritaire sort en premier (tas).
• Fenwick tree (BIT) — structure en arbre binaire indexé pour sommes de préfixes.
• Fermeture transitive — ensemble de toutes les paires atteignables.
• Fermat (petit théorème de) — p premier et a non multiple de p ⇒ a^(p−1) ≡ 1 (mod p).
• Floyd-Warshall — tous les plus courts chemins, O(V³).
• Force brute — voir Brute force.
• Fréquence — nombre d'occurrences d'une valeur dans un ensemble.
• Fusion (merge) — combinaison de deux séquences triées.
• Générativité (greedy) — voir Greedy.
• Graphe — ensemble de sommets (V) et d'arêtes (E).
• Graphe dense / creux (sparse) — dense : E ≈ V² ; creux : E ≈ V.
• Graphe non orienté / orienté — arêtes sans direction / avec direction (arcs).
• Greedy (glouton) — choix optimal local à chaque étape.
• Grille (grid) — matrice de cellules, cas particulier de graphe.
• Hamiltonien (cycle) — cycle visitant chaque sommet exactement une fois (NP-difficile).
• Hachage (hashing) — fonction mappant des clés vers des indices.
• Hash map / hash table — structure clé → valeur via fonction de hachage.
• Hash set — ensemble d'éléments sans doublon, via hachage.
• Hash roulant (rolling hash) — hash recalculé en O(1) quand la fenêtre glisse.
• Hauteur (d'un arbre) — longueur du plus long chemin racine → feuille.
• Heapsort (tri par tas) — tri via un tas binaire, O(n log n) en place.
• Heuristique — règle approximative, non garantie optimale.
• Huffman — voir Code de Huffman.
• In-order (parcours infixe) — gauche, racine, droite (donne un tri pour un BST).
• In-place (en place) — n'utilisant qu'une mémoire additionnelle constante.
• Insertion sort (tri par insertion) — tri par insertion d'éléments dans la partie triée.
• Invariant — propriété maintenue vraie pendant l'exécution (preuve de correction).
• Inverse modulaire — entier a⁻¹ tel que a·a⁻¹ ≡ 1 (mod m).
• Inversion (paire) — paire (i < j) avec arr[i] > arr[j].
• Irrédondance — absence de calcul inutile ; complexité minimale.

---

3. Glossaire : J – M

• Job scheduling — ordonnancement de tâches avec échéances et profits.
• Kadane (algorithme de) — sous-tableau de somme maximale en O(n).
• Kahn (algorithme de) — tri topologique par file des nœuds de degré 0.
• KMP (Knuth-Morris-Pratt) — recherche de motif en O(n + m) via prefix-function.
• Kruskal — MST par tri des arêtes + union-find.
• LCS — plus longue sous-séquence commune.
• Levenshtein (distance d') — distance d'édition (insertions/suppressions/substitutions).
• Liste chaînée (linked list) — séquence de nœuds pointés, accès séquentiel.
• Liste doublement chaînée — nœuds avec pointeurs précédent et suivant.
• Liste simplement chaînée — nœuds avec pointeur suivant uniquement.
• LIS — plus longue sous-séquence strictement croissante.
• LIFO / FIFO — last-in first-out / first-in first-out.
• Local search (recherche locale) — optimisation par voisinage itératif.
• Logarithme — fonction inverse de l'exponentielle ; base 2 par défaut en algorithmique.
• LRU (least recently used) — politique d'éviction de cache.
• LSB (bit de poids faible) — le bit le moins significatif.
• Maintenance d'ordre (order statistics) — k-ième plus petit élément.
• Manacher (algorithme de) — plus long palindrome en O(n).
• Matrice d'adjacence — représentation de graphe par table V×V.
• Max-flow — flot maximum d'une source vers un puits (Ford-Fulkerson).
• Master theorem — résolution des récurrences T(n) = a·T(n/b) + f(n).
• Médiane — valeur du milieu d'un ensemble trié.
• Mémoire cache — hiérarchie de mémoire ; localité des accès.
• Memoization (mémorisation) — cache des résultats de sous-problèmes.
• Merge sort (tri fusion) — tri stable récursif O(n log n).
• Milieu (slow/fast pointer) — deux pointeurs pour trouver le milieu d'une liste.
• Modulo — reste de la division entière.
• Monte Carlo — algorithme probabiliste dont le résultat peut être faux avec faible probabilité.
• MST — voir Arbre couvrant de poids minimum.
• Multiset / multiset — ensemble avec multiplicité.

---

4. Glossaire : N – R

• N-Queens — placer n reines sans attaque mutuelle (backtracking).
• Naturel (nombre) — entier non négatif ; domaine des indices.
• NP — classe des problèmes vérifiables en temps polynomial.
• NP-complet — plus difficile problème de NP ; pas de solution polynomiale connue.
• NP-difficile — au moins aussi difficile que les problèmes NP-complets.
• Nœud (node) — élément de base d'un arbre, d'un graphe ou d'une liste.
• Notation asymptotique — O, Ω, Θ (bornes supérieure, inférieure, exacte).
• Off-by-one — erreur d'indexation d'une unité (très fréquente).
• Optimisation — recherche de la meilleure solution selon un critère.
• Ordre de tri (sorted order) — séquence selon la relation d'ordre définie.
• Palindrome — chaîne identique à son renversement.
• Parcours (traversal) — visite de tous les éléments d'une structure.
• Parcours préfixe/suffixe — visite racine d'abord / racine en dernier.
• Partition — division d'un ensemble en sous-ensembles.
• Path compression — optimisation d'union-find : rattacher directement à la racine.
• Permutation — arrangement ordonné des éléments.
• PGCD / PPCM — plus grand commun diviseur / plus petit commun multiple.
• Pile (stack / LIFO) — structure dernier entré, premier sorti.
• Pivot — élément de partitionnement du quicksort.
• Plus court chemin — chemin de coût minimal entre deux sommets.
• Point fixe — valeur f(x) = x ; base des méthodes itératives.
• Polynomial (temps) — O(n^k) ; efficace en théorie.
• Portée / fenêtre (window) — sous-tableau contigu délimité par deux pointeurs.
• Postfixe (parcours) — gauche, droite, racine.
• Prefix sum (somme de préfixes) — tableau cumulatif pour sommes de plage O(1).
• Prefix-function (KMP) — plus longue bordure propre de chaque préfixe.
• Prim (algorithme de) — MST par croissance d'un seul arbre.
• Primalité (test de) — déterminer si un nombre est premier.
• Priority queue — voir File prioritaire.
• Probabilité d'anniversaire — collisions probables dès ~√n éléments.
• Programme dynamique — voir DP.
• Quicksort (tri rapide) — tri par partitionnement récursif, pivot aléatoire en moyenne O(n log n).
• Queue — voir File.
• Radix sort — tri par positions successives des chiffres (clés de longueur bornée).
• Randomisation — usage de l'aléatoire dans l'algorithme.
• Rabin-Karp — recherche de motif par hash roulant.
• Recherche binaire — recherche en O(log n) dans un tableau trié.
• Recherche linéaire / séquentielle — parcours complet, O(n).
• Récursion (récursivité) — fonction qui s'appelle elle-même.
• Récurrence — équation définissant T(n) en fonction de T(n/b).
• Red-black tree — voir Arbre rouge-noir.
• Réduction — transformation d'un problème en un autre (NP-complétude).
• Relaxation — mise à jour d'une distance candidate (Dijkstra/Bellman-Ford).
• Restes chinois (théorème des) — résolution de systèmes de congruences.
• Rotation (arbre) — opération d'équilibrage d'un BST (LL, RR, LR, RL).

---

5. Glossaire : S – Z

• SCC — voir Composante fortement connexe.
• Segment tree (arbre de segments) — arbre pour requêtes de plage + mises à jour en O(log n).
• Sentinelle — valeur factice simplifiant les conditions aux limites.
• Shellsort — tri par insertion sur des sous-suites à pas décroissants.
• Shuffle (Fisher-Yates) — permutation aléatoire uniforme en O(n).
• Skip list — liste à niveaux probabilistes, recherche O(log n) en moyenne.
• Sliding window (fenêtre glissante) — technique des deux pointeurs sur sous-tableaux contigus.
• Sommet (vertex) — élément d'un graphe.
• Stabilité (tri) — préservation de l'ordre relatif des clés égales.
• Stable matching — appariement sans blocage (problème des mariages stables, Gale-Shapley).
• STAR — Situation, Task, Action, Result (méthode d'entretien).
• Streaming algorithm — traitement des données en un seul passage.
• Strassen (algorithme de) — multiplication matricielle en O(n^2.807).
• Substitution (méthode de) — résolution de récurrences par induction.
• Substructure optimale — propriété : la solution optimale contient des solutions optimales des sous-problèmes.
• Suffix array — tableau trié des suffixes ; recherche de sous-chaîne en O(m log n).
• Tas binaire (heap) — arbre binaire presque complet avec propriété min/max.
• Tas de min / max — racine = minimum / maximum.
• Temps constant O(1) — coût indépendant de la taille d'entrée.
• Temps exponentiel O(2^n) — croissance explosive, à éviter.
• Thêta Θ — croissance asymptotique exacte.
• Token bucket — algorithme de limitation de débit (rate limiter).
• Topologique (tri) — ordre linéaire respectant les dépendances d'un DAG.
• Tortue et lièvre (Floyd) — détection de cycle par deux vitesses.
• Traversée — voir Parcours.
• Tri (sorting) — réorganisation selon un ordre défini.
• Tri à bulles / comptage / fusion / insertion / par sélection / rapide / par tas — famille des tris.
• Trie — voir Arbre trié.
• TSP (voyageur de commerce) — cycle hamiltonien de coût minimal (NP-difficile).
• Two Sum — problème classique : deux éléments de somme cible.
• Union-Find (ensembles disjoints) — gestion de partitions, O(α(n)) amorti.
• Upper bound — borne supérieure (O).
• Validation — vérification qu'une solution satisfait les contraintes.
• Variable d'état — paramètre définissant un état de DP.
• Voisinage — ensemble de solutions proches (recherche locale).
• Weighted graph (graphe pondéré) — graphe avec coûts sur les arêtes.

---

6. Big-O cheat sheet : structures

---

7. Big-O cheat sheet : tris

---

8. Big-O cheat sheet : fonctions de croissance

---

9. Templates d'algorithmes

T1 — Deux pointeurs (tableau trié)

def two_pointers(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return left, right
        elif s < target:
            left += 1
        else:
            right -= 1
    return -1, -1

T2 — Fenêtre glissante (sous-tableau contigu)

def sliding_window(arr, k):
    window_sum = sum(arr[:k])
    best = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        best = max(best, window_sum)
    return best

T3 — BFS (graphe)

from collections import deque

def bfs(adj, start):
    seen = {start}
    q = deque([start])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            if v not in seen:
                seen.add(v)
                q.append(v)
    return order

T4 — DFS récursif (graphe)

def dfs(adj, u, seen):
    seen.add(u)
    for v in adj[u]:
        if v not in seen:
            dfs(adj, v, seen)

T5 — Dijkstra

import heapq

def dijkstra(n, adj, src):
    dist = [float("inf")] * n
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

T6 — Topological sort (Kahn)

from collections import deque

def topo_sort(n, adj):
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None

T7 — Union-Find

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1

T8 — DP sur une dimension (Fibonacci)

def fib_dp(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1

T9 — Backtracking (template général)

def backtrack(choice, path, solutions):
    if is_solution(choice):
        solutions.append(path[:])
        return
    for candidate in candidates(choice):
        if valid(candidate):
            path.append(candidate)
            backtrack(candidate, path, solutions)
            path.pop()

T10 — Binary search

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

T11 — Segment tree (somme de plage)

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self._build(data, 1, 0, self.n - 1)

    def _build(self, data, node, l, r):
        if l == r:
            self.tree[node] = data[l]
            return
        mid = (l + r) // 2
        self._build(data, 2 * node, l, mid)
        self._build(data, 2 * node + 1, mid + 1, r)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def query(self, node, l, r, ql, qr):
        if ql > r or qr < l:
            return 0
        if ql <= l and r <= qr:
            return self.tree[node]
        mid = (l + r) // 2
        return self.query(2 * node, l, mid, ql, qr) + \
               self.query(2 * node + 1, mid + 1, r, ql, qr)

    def update(self, node, l, r, idx, val):
        if l == r:
            self.tree[node] = val
            return
        mid = (l + r) // 2
        if idx <= mid:
            self.update(2 * node, l, mid, idx, val)
        else:
            self.update(2 * node + 1, mid + 1, r, idx, val)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

T12 — Exponentiation modulaire

def mod_pow(a, b, m):
    result = 1
    a %= m
    while b:
        if b & 1:
            result = result * a % m
        a = a * a % m
        b >>= 1
    return result

---

10. Résolution de récurrences

Méthode de substitution

1. Deviner la forme de la solution (à partir des exemples).
2. Prouver par induction.
3. Ajuster les constantes si nécessaire.

Exemple : T(n) = 2T(n/2) + n. Devinette : T(n) = O(n log n). Preuve : T(n) ≤ 2·c·(n/2)log(n/2) + n = cn log n − cn + n ≤ cn log n pour c ≥ 1. ✔

Arbre de récurrence

Décomposer T(n) en niveaux : nombre de nœuds par niveau × coût par nœud. Somme sur la hauteur.

Exemple : T(n) = T(n/3) + T(2n/3) + n → hauteur ≈ log_{3/2}(n), coût par niveau O(n) → T(n) = O(n log n).

Master theorem

Pour T(n) = a·T(n/b) + f(n), avec a ≥ 1, b > 1 :

---

11. Complexités des opérations par structure

Cas d'usage rapide

Algorithmes de référence (complexités)

---

12. Formules utiles

• Somme 1 + 2 + … + n = n(n+1)/2.
• Somme 1 + 2 + 4 + … + 2^(k−1) = 2^k − 1.
• Somme 1² + 2² + … + n² = n(n+1)(2n+1)/6.
• Nombre de paires d'un tableau de n : n(n−1)/2.
• Nombre de sous-ensembles de n éléments : 2^n.
• Nombre de permutations de n éléments : n!.
• log₂(10^k) ≈ 3.32·k (pour estimer le nombre de bits).
• Zéros terminaux de n! : Σ ⌊n/5^i⌋.
• √(n) ≈ nombre de diviseurs à tester pour la primalité.
• Nombre de nœuds d'un arbre binaire complet de hauteur h : 2^(h+1) − 1.
• Espace du tri fusion : O(n) ; du quicksort : O(log n) (pile de récursion).

Prochaine étape : les tendances et algorithmes modernes du chapitre 24.