24 — Tendances : les algorithmes du futur

Ce chapitre ouvre la formation vers les domaines en pleine expansion : l'intelligence artificielle, le calcul quantique, les systèmes distribués, le traitement de flux de données, le calcul sur GPU et les algorithmes sublinéaires. Pour chaque domaine : le problème, les algorithmes clés, les complexités, et du code d'illustration.

---

Sommaire

1. Pourquoi ce chapitre ?
2. Algorithmes en IA/ML
3. Algorithmes quantiques
4. Algorithmes distribués
5. Streaming algorithms
6. Algorithmes GPU
7. Sublinear algorithms
8. Synthèse et perspectives

---

1. Pourquoi ce chapitre ?

Les 23 premiers chapitres couvrent le cœur classique de l'algorithmique — les fondations que tout ingénieur doit maîtriser. Ce chapitre répond à la question « et maintenant ? » : l'algorithmique vit une révolution tranquille portée par quatre forces :

1. L'explosion des données — impossible de tout lire ni tout stocker → streaming et sublinear.
2. Le parallélisme — les cœurs ne vont plus plus vite, ils se multiplient → GPU et distribué.
3. L'apprentissage automatique — les modèles sont entraînés par des algorithmes d'optimisation.
4. L'informatique quantique — un nouveau modèle de calcul qui change les complexités.

Un bon ingénieur algorithmique ne connaît pas seulement O, Θ, la DP et les graphes — il sait choisir le bon modèle de calcul pour le problème et les données du moment.

---

2. Algorithmes en IA/ML

Le problème

Apprendre une fonction f : X → Y à partir d'exemples étiquetés (supervisé) ou de structures dans les données (non supervisé). L'algorithmique y intervient à tous les étages : optimisation, matrice, graphe, tri.

Les algorithmes fondateurs

Descente de gradient (gradient descent)

On minimise une fonction de coût L(θ) en se déplaçant dans le sens opposé au gradient, pas à pas. C'est l'algorithme le plus important de l'IA moderne.

def gradient_descent(loss_grad, theta, lr=0.01, iters=1000):
    for _ in range(iters):
        theta -= lr * loss_grad(theta)
    return theta

Complexité : O(I × coût du gradient) avec I itérations. Les variantes — SGD (stochastic gradient descent), mini-batch, Adam — améliorent la vitesse et la stabilité.

Backpropagation

Pour un réseau de neurones, la rétropropagation calcule le gradient de la perte par rapport à chaque poids via la règle de la chaîne, en parcourant le réseau en sens inverse. C'est une application directe de la DP/des graphes (calcul des gradients en O(nb poids), une passe avant + une passe arrière).

Algorithmes d'apprentissage classiques

Le fond algorithmique caché

• Multiplication matricielle : les réseaux de neurones sont des GEMM géants → Strassen (O(n^2.807)) et cuBLAS sur GPU.
• Recherche de voisins : kd-trees, ball trees, hashing local sensible (LSH) pour les grandes bases.
• Graphes : PageRank (itération de Markov), propagation de labels, traversals sur grands graphes.
• Tri et statistiques : sélection des top-k, partitionnement des données d'entraînement.

Exemple : K-means en Python

import random

def kmeans(points, k, iters=100):
    centroids = random.sample(points, k)
    for _ in range(iters):
        clusters = [[] for _ in range(k)]
        for p in points:
            idx = min(range(k), key=lambda i: dist(p, centroids[i]))
            clusters[idx].append(p)
        new_centroids = [mean(c) for c in clusters if c]
        if new_centroids == centroids:
            break
        centroids = new_centroids
    return centroids, clusters

---

3. Algorithmes quantiques

Les idées physiques

L'informatique quantique manipule des qubits qui, contrairement aux bits, peuvent être en superposition (α|0⟩ + β|1⟩). Les algorithmes tirent parti de deux phénomènes :

• Intrication : des qubits corrélés agissent ensemble.
• Interférence : les amplitudes peuvent s'additionner (bonnes réponses) ou s'annuler (mauvaises réponses).

Un registre de n qubits encode 2^n amplitudes simultanément — d'où un parallélisme exponentiel en théorie. Le défi : lire le résultat sans détruire la superposition (la mesure est probabiliste).

Les algorithmes majeurs

Grover (recherche non structurée)

Trouve un élément dans une base non triée de taille N en O(√N) requêtes, contre O(N) classique. Application : recherche, inversion de fonctions, SAT par recherche.

Shor (factorisation)

Factorise un entier n en temps polynomial — O((log n)³). Or la sécurité du RSA repose sur l'hypothèse que la factorisation est difficile en classique. Shor ne l'a pas « brisé » pratiquement (besoin de millions de qubits logiques), mais il a reconfiguré la recherche en cryptographie post-quantique.

Autres familles

Quelle complexité ?

• BQP (bounded-error quantum polynomial time) : problèmes résolubles en temps polynomial avec probabilité d'erreur bornée. C'est la classe quantique « pratique ».
• La recherche quantique donne un gain quadratique (√N), pas exponentiel — la menace la plus immédiate est sur le hachage (√2^n au lieu de 2^n).

État des lieux (2026)

Les machines actuelles comptent 1000+ qubits physiques mais restent bruyantes (NISQ). Les algorithmes pratiques pour le futur proche : QAOA/VQE (optimisation et chimie), et des schémas de réduction d'erreur. L'algèbre modulaire, les lattices (crypto post-quantique) et le problème du logarithme discret sont les cibles de recherche majeures.

---

4. Algorithmes distribués

Le problème

Exécuter un algorithme sur plusieurs machines communiquant par le réseau. Deux enjeux : la performance (décomposer le travail) et la cohérence (garder des vues cohérentes malgré pannes).

Théorème CAP

Parmi Consistance, Availability et Partition tolerance, un système distribué ne peut garantir que deux sur trois. En pratique, les partitions sont inévitables → on choisit entre cohérence forte (CP) et disponibilité (AP).

Consensus

Plusieurs nœuds doivent se mettre d'accord malgré les pannes.

• Paxos (Lamport) : première famille d'algorithmes de consensus, difficile à implémenter correctement.
• Raft (Diego Ongaro) : consensus rédigé pour l'enseignement et l'implémentation — élection de leader + réplication de journal. Utilisé par etcd, Consul, CockroachDB.
• PBFT (Practical Byzantine Fault Tolerance) : tolère les pannes byzantines (comportements arbitraires) : n ≥ 3f+1 nœuds pour tolérer f pannes.

Modèles de calcul

MapReduce en miniature

from collections import defaultdict

def map_reduce(mapper, reducer, data):
    intermediate = defaultdict(list)
    for item in data:
        for k, v in mapper(item):
            intermediate[k].append(v)
    result = {}
    for k, values in intermediate.items():
        result[k] = reducer(k, values)
    return result

# Word count
mapper = lambda line: ((w, 1) for w in line.split())
reducer = lambda k, vs: sum(vs)

Défis algorithmiques distribués

• Tri distribué : external merge sort, TeraSort, sortie en partitions ordonnées.
• Comptage / top-k distribué : approximations par échantillonnage et sketches locaux.
• Graphes massifs : Pregel (BSP), éventail de parcours BFS/PageRank avec agrégation des messages.
• File d'attente et back-pressure : équilibrage de charge, watermarks.

---

5. Streaming algorithms

Le problème

Un flux infini (clics, logs, capteurs) arrive en un seul passage ; la mémoire disponible est très inférieure à la taille du flux. On ne peut pas stocker, et on ne passe qu'une fois (ou peu) sur chaque élément. On cherche des approximations avec des garanties probabilistes.

Bloom filter

Teste l'appartenance d'un élément à un ensemble avec 0 faux négatif et un petit taux de faux positifs. Principe : k fonctions de hachage mappent vers un bitmap de m bits ; à l'insertion on met les k bits à 1 ; au test, on renvoie vrai si tous les k bits sont à 1.

class BloomFilter:
    def __init__(self, m, k):
        self.m, self.k = m, k
        self.bits = bytearray(m)

    def _hashes(self, x):
        # simule k hashages indépendants
        return [(hash((x, i)) % self.m) for i in range(self.k)]

    def add(self, x):
        for h in self._hashes(x):
            self.bits[h] = 1

    def __contains__(self, x):
        return all(self.bits[h] for h in self._hashes(x))

Taux de faux positifs optimal : k = (m/n)·ln 2 → probabilité ≈ (1 − e^(−kn/m))^k.

HyperLogLog (HLL)

Estime le nombre d'éléments distincts (cardinalité) d'un flux en O(1) mémoire (typiquement quelques Ko, précision ~1-2 %). Principe : observer le nombre maximal de zéros de tête dans les hashs des éléments — plus la cardinalité est grande, plus on a de chances d'avoir une longue suite de zéros. Combiné avec le stochastic averaging (m registres) et une correction de biais.

Count-Min Sketch (CMS)

Estime la fréquence d'un élément dans un flux (réponse ≥ vraie fréquence, avec erreur additive εN). Principe : une grille de compteurs, d hachages ; à chaque occurrence, incrémenter les d compteurs ; la réponse est le minimum des d compteurs.

Stream Summary & Sampling

• Reservoir sampling : échantillon aléatoire uniforme de taille k sans connaître n (algorithme de Vitter).
• Misra-Gries / Space-Saving : top-k fréquents (heavy hitters) avec peu de compteurs.
• Exact distinct / approximate distinct : HLL vs algorithmes exacts (impossibles en mémoire bornée).

Le compromis central

Code : reservoir sampling

import random

def reservoir_sample(stream, k):
    reservoir = []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)
        else:
            j = random.randint(0, i)
            if j < k:
                reservoir[j] = item
    return reservoir

---

6. Algorithmes GPU

Le modèle de calcul

Le GPU exécute des milliers de threads en parallèle sur le même programme (SIMT). L'efficacité repose sur :

• Taux d'occupation : suffisamment de threads pour masquer la latence mémoire.
• Cohérence de divergence : les threads d'un même warp doivent suivre le même chemin de contrôle.
• Localité mémoire : accès coalescés (contigus) pour exploiter les lignes de cache.

Les algorithmes GPU fondamentaux

Réduction (sum/min/max)

Arbre binaire de réduction par niveaux : à chaque étape, chaque thread combine deux valeurs.

def gpu_reduce_style(arr):
    # version "séquentielle" du pattern de réduction par paires
    n = len(arr)
    while n > 1:
        half = (n + 1) // 2
        for i in range(half):
            if i + half < n:
                arr[i] += arr[i + half]
        n = half
    return arr[0]

Complexité : O(log n) « pas » de réduction avec n/2 threads par niveau (en pratique O(n) travail total, O(n/p) temps).

Scan (prefix sum) — Blelloch

Calculer les sommes de préfixes en deux passes : up-sweep (réduire) puis down-sweep (distribuer). Le scan parallèle est la brique des algorithmes de stream compaction, de tri par comptage parallèle et de many-to-many mapping.

Multiplication de matrices (GEMM)

Découpage en tuiles (tiling) : chaque bloc charge une tuile en mémoire partagée, puis accumule les produits. C'est l'opération centrale de l'apprentissage profond (cublas, cuDNN).

Tri parallèle

• Bitonic sort : O(n log² n) comparateurs, réseau fixe — adapté au GPU.
• Radix sort : parallélisable naturellement (counting sort par digits) — utilisé en pratique.
• Sample sort : pivot approximatif par échantillonnage, partitionnement en seaux.

Grille de référence

---

7. Sublinear algorithms

Le problème

Quand l'entrée est immense (exabytes), même O(n) est trop coûteux. Les algorithmes sublinéaires donnent une réponse approximative en ne lisant qu'une petite partie de l'entrée — souvent O(poly(log n)) ou O(√n) temps/mémoire. On distingue :

• Temps sublinéaire : algorithmes à échantillonnage et accès aléatoire (propriétés, métriques).
• Espace sublinéaire : streaming (section 5).
• Requêtes (query complexity) : nombre de lectures minimales nécessaire.

Property testing

Déterminer si un objet satisfait une propriété, ou en est ε-loin, en lisant O(1) échantillons.

• Test de tri : un tableau trié ? Lire O(1/ε) positions aléatoires suffit pour distinguer « trié » de « ε-loin d'être trié ».
• Test de graphe bipartite / connexité : échantillonnage de sommets.
• Bounded occurrence testing : propriétés dans des modèles à degré borné.

Échantillonnage et estimation

La borne fondamentale

Un algorithme sublinéaire en temps ne peut pas être exact sur toute entrée (il lit trop peu). D'où la théorie des bornes inférieures de complexité de requêtes : pour bien des problèmes, tout algorithme approché à facteur 1+ε nécessite Ω(f(n)) requêtes — savoir cette borne évite de chercher un algorithme exact sublinéaire inexistant.

---

8. Synthèse et perspectives

Le tableau d'ensemble

Les tendances à surveiller (2026+)

1. LLM et algorithmique : les tokens (attention, KV-cache) posent des problèmes algorithmiques nouveaux (indexation, récupération, déduplication, échantillonnage).
2. Quantique tolérant aux fautes : les machine à correction d'erreur (surface codes) détermineront la date de Shor pratique.
3. Data-centric AI : l'algorithmique des données (déduplication, curation, embeddings) devient un sujet de première classe.
4. Rust, WASM, Edge : l'exécution d'algorithmes près des données (edge computing) pose des contraintes de mémoire et de réseau.
5. Confidentialité : chiffrement homomorphe, MPC (secure multi-party computation), differential privacy — des algorithmes dont la complexité doit tenir compte de la confidentialité des données.
6. Approximation certifiée : les bornes théoriques (ε, δ) deviennent un argument marketing et produit.

Comment continuer après la formation

• Refaire les 100 exercices du chapitre 17 avec les templates du chapitre 23.
• S'entraîner sur les plateformes du chapitre 20.
• Lire les livres du chapitre 21 — le niveau universitaire y est couvert.
• Suivre les tendances de ce chapitre via les références.

Mot de la fin : les algorithmes sont un métier — le nôtre. Continuez à pratiquer, à lire, à coder. La meilleure façon de prédire l'avenir de l'algorithmique est encore de contribuer à l'écrire.