00 — Introduction aux Algorithmes : Cours complet

Niveau : Université / Ingénierie — Durée de lecture : ~45 min

---

Table des matières

1. Introduction générale
2. Histoire des algorithmes
3. Qu'est-ce qu'un algorithme ?
4. Propriétés fondamentales
5. Classification des algorithmes
6. Pourquoi apprendre les algorithmes
7. Compromis temps / mémoire
8. Algorithmes dans l'industrie
9. Premiers pas : un algorithme dans 5 langages
10. Résumé et points clés

---

1. Introduction générale

Un algorithme est au programmeur ce que le théorème est au mathématicien : un outil de raisonnement rigoureux et reproductible. Chaque logiciel que vous utilisez — moteur de recherche, GPS, réseau social, application bancaire — repose sur des algorithmes. Comprendre leurs fondements, leur histoire et leurs propriétés est la première étape d'une carrière d'ingénieur solide.

Ce chapitre pose les fondations. Nous y définissons rigoureusement la notion d'algorithme, parcourons son histoire multimillénaire, et étudions comment classer les algorithmes selon leur paradigme et leur domaine. Nous terminons par la question essentielle : pourquoi et comment les algorithmes façonnent l'industrie.

Le terme vient du nom du savant perse Abu Ja'far Muhammad ibn Musa Al-Khwarizmi (IXe siècle), dont l'œuvre « Al-jabr wa'l-muqabala » a donné naissance au mot algèbre, tandis que la latinisatin de son nom a donné algorithme.

---

2. Histoire des algorithmes

2.1 Les origines antiques : Euclide (~300 av. J.-C.)

L'algorithme d'Euclide pour calculer le PGCD (plus grand commun diviseur) est considéré comme le premier algorithme écrit. Il est élégant, correct, terministe et fini :

PGCD(a, b):
    tant que b ≠ 0 :
        temp = b
        b = a mod b
        a = temp
    retourner a

Exemple : PGCD(252, 105) → 252 mod 105 = 42, 105 mod 42 = 21, 42 mod 21 = 0 → retourne 21.

À retenir : Euclide a inventé la notion même de procédure répétitive correcte, plus de 2 000 ans avant les ordinateurs.

2.2 Al-Khwarizmi (~780-850) : le nom et la méthode

Al-Khwarizmi, mathématicien et astronome à la « Maison de la Sagesse » de Bagdad, formalise dans ses livres des méthodes pas-à-pas pour résoudre des équations et effectuer des calculs (multiplication, division, extraction de racines). Ses œuvres, traduites en latin au XIIe siècle, introduisent en Europe le système décimal indo-arabe et l'algèbre.

Le mot algorithme dérive de son nom latinisé, Algoritmi.

2.3 Ada Lovelace (1815-1852) : la première programmeuse

Dans ses notes sur la machine analytique de Charles Babbage, Ada Lovelace décrit un algorithme destiné à une machine pour calculer les nombres de Bernoulli. Elle comprend que la machine peut manipuler des symboles et non seulement des nombres — prémisse de l'informatique moderne.

2.4 Alan Turing (1912-1954) : la machine universelle

En 1936, Turing publie « On Computable Numbers », définissant la machine de Turing : un modèle abstrait de calcul universel capable d'exécuter tout algorithme. Ce résultat fonde la théorie de la calculabilité :

• Certains problèmes sont indécidables (le problème de l'arrêt).
• Tout calcul effectuable par un ordinateur peut l'être par une machine de Turing.
• Il pose aussi le test de Turing en IA (1950).

2.5 Edsger Dijkstra (1930-2002) : l'ingénierie du logiciel

Dijkstra, Prix Turing 1972, apporte :

• L'algorithme du plus court chemin (Dijkstra, 1956) utilisé par tous les GPS.
• Le semaphore pour la synchronisation de processus.
• L'algorithme du plus court chemin... et surtout la défense de la rigueur : « Le test de la qualité de votre programme est la qualité de vos preuves. »

2.6 Donald Knuth (1938-) : l'encyclopédiste

Knuth, auteur de The Art of Computer Programming (TAOCP), a systématisé la science des algorithmes :

• Création de TeX (système de composition typographique).
• Notation Big-O popularisée pour l'analyse d'algorithmes.
• Notion de complexité en moyenne et dans le pire cas.
• Prix Turing 1974.

2.7 Chronologie synthétique

Diagramme en cours de génération...

---

3. Qu'est-ce qu'un algorithme ?

3.1 Définition formelle

Définition : Un algorithme est une suite finie et non ambiguë d'instructions élémentaires qui, étant donnée une entrée (input), produit une sortie (output) en un nombre fini d'étapes.

Une définition plus moderne (Cormen et al., Introduction to Algorithms) : « Un algorithme est toute procédure de calcul bien définie qui prend un ensemble de valeurs en entrée et produit un ensemble de valeurs en sortie. »

3.2 Algorithme vs Programme

3.3 Un premier algorithme : la recherche du maximum

ALGORITHME Maximum(liste):
    ENTREE : liste de n nombres
    SORTIE : le plus grand élément
    max = liste[0]
    POUR i de 1 à n-1 :
        SI liste[i] > max ALORS max = liste[i]
    RETOURNER max

Pour n éléments, cet algorithme effectue exactement n-1 comparaisons dans le meilleur et le pire cas : sa complexité est linéaire, notée O(n). (Analyse détaillée au chapitre 01.)

---

4. Propriétés fondamentales

Un bon algorithme vérifie cinq propriétés :

Complément : on ajoute souvent la correction (produit toujours le résultat attendu) et l'existence d'un résultat clair. Un algorithme correct mais exponentiel reste correct ; un algorithme linéaire mais faux ne sert à rien.

4.1 Terminaison : l'exemple du Collatz

La conjecture de Collatz : à partir de n, appliquer n/2 si pair, 3n+1 sinon. Personne n'a prouvé qu'elle se termine toujours pour tout n — pourtant elle se termine pour tout n testé (jusqu'à 10^20). C'est un exemple parfait de problème ouvert : un algorithme dont la terminaison est conjecturée mais non démontrée.

def collatz(n):
    steps = 0
    while n != 1:
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        steps += 1
    return steps

---

5. Classification des algorithmes

5.1 Par paradigme de conception

5.2 Par domaine d'application

5.3 Classification globale

Diagramme en cours de génération...

---

6. Pourquoi apprendre les algorithmes

6.1 Raisons fondamentales

1. Performance : un bon algorithme peut faire passer un calcul de plusieurs jours à quelques secondes. Exemple : trier 1 million d'éléments — O(n²) ≈ 1e12 opérations (≈ 20 min sur une machine à 1e9 op/s), O(n log n) ≈ 2e7 opérations (≈ 0,02 s).
2. Interviews d'ingénierie : Facebook, Google, Amazon, Apple, Netflix testent les fondamentaux algorithmiques.
3. Conception de systèmes : comprendre les structures de données permet de choisir la bonne pour chaque usage (base de données → B-Tree, cache → hash map, file d'attente → queue).
4. Compréhension des outils : savoir comment fonctionne git (graphes DAG), un planificateur de tâches (heap), un cache LRU (double linked list + hash map) démystifie le quotidien.
5. Rigueur intellectuelle : l'analyse de complexité forge un esprit quantitatif et critique.
6. Un domaine stable : les fondamentaux (tris, recherche, graphes) ne changent quasiment pas depuis 60 ans — c'est un savoir durable.

6.2 Exemple chiffré : l'impact du choix algorithmique

Considérons une liste de 10 millions d'éléments :

Le choix de l'algorithme est plus important que la puissance de la machine.

---

7. Compromis temps / mémoire

7.1 Le triangle du compromis

Diagramme en cours de génération...

7.2 Exemples classiques de trade-offs

7.3 Le concept de mémoïsation (précurseur)

Le compromis temps/mémoire est exploité massivement :

• Caches (CPU L1/L2/L3, Redis, Memcached) : échange mémoire contre temps.
• Memoization (programmation dynamique) : stocker les résultats intermédiaires.
• Index de base de données : tables de hachage/B-trees occupent de la mémoire pour accélérer les requêtes.
• Compression : l'inverse — échange temps contre espace.

Règle d'or : « Il n'y a pas de déjeuner gratuit. » Accélérer une opération coûte presque toujours de la mémoire (ou de la précision, ou de la complexité du code).

---

8. Algorithmes dans l'industrie

8.1 Études de cas

8.2 Comment les algorithmes produisent de la valeur

1. Échelle : gérer 1 milliard d'utilisateurs exige des algorithmes quasi-linéaires.
2. Latence : la recherche binaire et les hash tables transforment des recherches de secondes en microsecondes.
3. Coût : moins de cycles CPU = moins de serveurs = moins d'argent. Amazon a révélé que 100 ms de latence coûte 1 % de ventes.
4. Fiabilité : les graphes et les hash permettent la détection de fraudes, la réplication et la tolérance aux pannes.

8.3 Tendances récentes

• Machine Learning : SGD (descente de gradient stochastique), backpropagation, algorithmes d'optimisation.
• Systèmes distribués : consensus (Paxos, Raft), consistent hashing, gossip protocols.
• Big Data : MapReduce, external sort, bloom filters, sketch algorithms (HyperLogLog, Count-Min Sketch).
• Quantique : Shor (factorisation), Grover (recherche non structurée).

---

9. Premiers pas : un algorithme dans 5 langages

Implémentons l'algorithme du maximum dans les cinq langages de la formation.

9.1 Python

def maximum(liste):
    maxi = liste[0]
    for x in liste[1:]:
        if x > maxi:
            maxi = x
    return maxi

print(maximum([3, 7, 2, 9, 5]))  # 9

9.2 TypeScript

function maximum(liste: number[]): number {
  let maxi = liste[0];
  for (const x of liste.slice(1)) {
    if (x > maxi) maxi = x;
  }
  return maxi;
}
console.log(maximum([3, 7, 2, 9, 5])); // 9

9.3 Java

public static int maximum(int[] liste) {
    int maxi = liste[0];
    for (int i = 1; i < liste.length; i++) {
        if (liste[i] > maxi) maxi = liste[i];
    }
    return maxi;
}
// System.out.println(maximum(new int[]{3, 7, 2, 9, 5})); // 9

9.4 Go

func maximum(liste []int) int {
	maxi := liste[0]
	for _, x := range liste[1:] {
		if x > maxi {
			maxi = x
		}
	}
	return maxi
}
// fmt.Println(maximum([]int{3, 7, 2, 9, 5})) // 9

9.5 C++

int maximum(const std::vector<int>& liste) {
    int maxi = liste[0];
    for (size_t i = 1; i < liste.size(); ++i) {
        if (liste[i] > maxi) maxi = liste[i];
    }
    return maxi;
}
// std::cout << maximum({3, 7, 2, 9, 5}); // 9

9.6 Observations

• Le même algorithme s'exprime dans tous les langages : l'algorithmique est indépendante du langage.
• Chaque langage apporte ses nuances : typage (TS, Java, Go, C++), style fonctionnel vs impératif, gestion de la mémoire (GC vs manuelle en C++).
• La complexité ne change pas : toujours n-1 comparaisons, soit O(n).

---

10. Résumé et points clés

1. Un algorithme = suite finie, non ambiguë, d'instructions avec entrée, sortie et terminaison garantie.
2. L'histoire va d'Euclide (PGCD) → Al-Khwarizmi (méthodes) → Turing (calculabilité) → Dijkstra (plus court chemin) → Knuth (science des algorithmes).
3. Classer : par paradigme (diviser-régner, glouton, dynamique, backtracking…) et par domaine (tri, recherche, graphes, chaînes…).
4. Pourquoi apprendre : performance (O(n log n) vs O(n²) = ×10^5), interviews, conception système, rigueur.
5. Compromis temps/mémoire : chaque optimisation a un coût ; les caches et la mémoïsation en sont les applications industrielles.
6. Industrie : les algorithmes sont partout — de Google Search au GPS, de Git à la cryptographie bancaire.
7. Multi-langages : le même algorithme s'écrit en Python, TypeScript, Java, Go et C++.

Vocabulaire à retenir

---

Exercices d'auto-évaluation

1. Énoncez les cinq propriétés d'un algorithme avec un exemple pour chacune.
2. Citez trois contributions de Dijkstra et trois de Knuth.
3. Classez ces algorithmes par paradigme : merge sort, Dijkstra, Fibonacci par mémoïsation, N-Queens.
4. Pourquoi while True: viole-t-il la propriété de finitude ? Proposez une correction.
5. Citez un exemple de compromis temps/mémoire dans une application que vous utilisez quotidiennement.
6. Écrivez en pseudo-code un algorithme qui vérifie si une chaîne est un palindrome.

Passez ensuite au quiz pour valider vos acquis, puis aux TP pratiques.