Numérique · Compétences informatiques
Algorithme
Un algorithme est une suite finie et précise d’instructions qui permet de résoudre un problème ou d’accomplir une tâche : à partir de données d’entrée, il produit un résultat en un nombre fini d’étapes.
Mis à jour le 4 min de lecture
Une recette de cuisine, la méthode de la division posée ou l’itinéraire calculé par un GPS sont des algorithmes : des marches à suivre suffisamment précises pour être exécutées sans réfléchir, par une personne ou par une machine. En informatique, un programme est la traduction d’un ou plusieurs algorithmes dans un langage de programmation.
Origine du mot
Le mot vient du nom du mathématicien persan Muhammad ibn Musa al-Khwarizmi (IXe siècle), actif à Bagdad, dont les ouvrages ont fait connaître en Europe le calcul avec les chiffres indo-arabes. Son nom latinisé, Algoritmi, a donné « algorisme » puis « algorithme ». L’un des plus anciens algorithmes connus est l'algorithme d’Euclide (vers 300 av. J.-C.), qui calcule le plus grand diviseur commun de deux nombres.
Les propriétés d’un algorithme
- Fini : il se termine après un nombre fini d’étapes.
- Précis : chaque étape est définie sans ambiguïté.
- Des entrées : les données de départ (zéro ou plusieurs).
- Une sortie : au moins un résultat.
- Effectif : chaque opération est réalisable.
- Correct : il donne le bon résultat pour toutes les entrées prévues.
Les structures de base
Tout algorithme se construit avec trois structures fondamentales, plus des variables pour mémoriser les valeurs :
| Structure | Rôle | Exemple en pseudo-code |
|---|---|---|
| Séquence | Exécuter des instructions dans l’ordre | prix ← 20 puis total ← prix × 3 |
| Condition (alternative) | Choisir selon un test | si note ≥ 10 alors afficher « admis » sinon afficher « ajourné » |
| Boucle (répétition) | Répéter tant qu’une condition est vraie ou un nombre de fois donné | pour i de 1 à 10 : afficher i × 7 |
Le pseudo-code est une écriture intermédiaire entre le français et un langage de programmation, utilisée pour concevoir un algorithme avant de le coder. On utilise aussi des organigrammes (logigrammes).
Exemples simples
Trouver le plus grand nombre d’une liste
- Prendre le premier nombre comme « maximum provisoire ».
- Pour chaque nombre suivant : s’il est plus grand que le maximum provisoire, il devient le nouveau maximum.
- À la fin de la liste, le maximum provisoire est le résultat.
Recherche dichotomique
Pour trouver un mot dans un dictionnaire de 100 000 mots, on ouvre au milieu, on regarde si le mot cherché est avant ou après, et on recommence dans la moitié concernée. On divise ainsi le problème par deux à chaque étape : 17 étapes au maximum suffisent, contre jusqu’à 100 000 en lisant les mots un par un. La condition : la liste doit être triée.
Algorithme d’Euclide
PGCD(a, b) : tant que b n’est pas nul, remplacer (a, b) par (b, reste de a ÷ b) ; le résultat est a. Exemple : PGCD(48, 18) → (18, 12) → (12, 6) → (6, 0) → 6.
Efficacité : la complexité
Deux algorithmes peuvent donner le même résultat avec des durées très différentes. La complexité mesure la façon dont le nombre d’opérations augmente avec la taille n des données. On la note avec la notation « grand O ».
| Complexité | Nom | Exemple | Pour n = 1 000 000 |
|---|---|---|---|
| O(1) | Constante | Lire un élément d’un tableau par sa position | 1 opération |
| O(log n) | Logarithmique | Recherche dichotomique | ≈ 20 |
| O(n) | Linéaire | Parcourir une liste | 1 million |
| O(n log n) | Quasi linéaire | Bons algorithmes de tri (tri fusion) | ≈ 20 millions |
| O(n²) | Quadratique | Tri par sélection, comparer chaque paire | 1 000 milliards |
| O(2ⁿ) | Exponentielle | Tester toutes les combinaisons | Impossible en pratique |
Ce tableau explique pourquoi le choix de l’algorithme compte souvent plus que la puissance de la machine.
Les grandes familles d’algorithmes
- Tri : ranger des données (tri par insertion, tri fusion, tri rapide).
- Recherche : retrouver une donnée (dichotomie, tables de hachage).
- Graphes : plus court chemin (algorithme de Dijkstra, 1959, utilisé dans le calcul d’itinéraire), réseaux.
- Cryptographie : chiffrer et signer (RSA, AES), qui protège les échanges sur internet.
- Compression : réduire la taille des fichiers (ZIP, JPEG, MP3).
- Apprentissage automatique : algorithmes qui ajustent un modèle à partir de données (voir apprentissage automatique).
Les « algorithmes » des plateformes
Dans le langage courant, « l’algorithme » de YouTube, TikTok ou d’un réseau social désigne le système de recommandation qui choisit les contenus montrés à chacun. Il s’agit d’un ensemble de modèles d'intelligence artificielle entraînés pour maximiser un objectif (temps passé, interactions). Ces systèmes soulèvent des questions de transparence ; en Europe, le règlement sur les services numériques (DSA) impose aux très grandes plateformes d’expliquer leurs principaux paramètres de recommandation et de proposer une option non fondée sur le profilage.
Questions fréquentes
Quelle différence entre algorithme et programme ?
L’algorithme est la méthode, indépendante de toute machine ; le programme est sa traduction dans un langage de programmation, exécutable par un ordinateur.
Un algorithme est-il forcément informatique ?
Non. Les algorithmes existent depuis l’Antiquité (Euclide) ; une recette ou une notice de montage en sont des exemples. L’informatique les a simplement rendus automatiques.
Comment apprendre l’algorithmique ?
En résolvant de petits problèmes en pseudo-code puis dans un langage simple comme Python ou Scratch. L’algorithmique est enseignée en mathématiques au lycée et dans la spécialité NSI (numérique et sciences informatiques).
Qu’est-ce qu’un algorithme glouton ?
Un algorithme qui fait à chaque étape le choix qui semble le meilleur sur le moment, sans revenir en arrière. Il est rapide mais ne garantit pas toujours la meilleure solution globale.