Algorithmes, programmes et complexité
Cours · informatique (MP2I/MPI), chapitre 3 · MP2I et MPI · le début du chapitre, la suite sur Adloun
3.1 Deux mots qu'on confond, et qu'il faut séparer
Un algorithme est une méthode : une suite finie d'opérations qui, à partir de données d'entrée, produit un résultat. Un programme en est une mise en œuvre dans un langage donné. La dichotomie est un algorithme ; les quinze lignes de C du chapitre chap:diviser en sont un programme, et les huit lignes d'OCaml en sont un autre — le même algorithme, deux programmes.
La distinction n'est pas scolaire. Elle décide de ce qu'on peut affirmer. « Cet algorithme fait comparaisons » est une propriété de la méthode, vraie dans tous les langages. « Ce programme s'exécute en 3 ms » est une propriété d'un programme sur une machine un jour donné. Les deux se mesurent, mais pas de la même façon, et l'un ne remplace jamais l'autre.
3.2 Paradigmes
- Impératif structuré : on décrit une suite d'actions qui modifient un état. Les boucles et l'affectation en sont les outils. C en est l'exemple du programme.
- Déclaratif fonctionnel : on décrit le résultat comme une expression, composée de fonctions, sans état modifié. OCaml en est l'exemple.
- Logique : on décrit les relations que le résultat doit satisfaire, et un moteur cherche ce qui les satisfait. Le programme ne le rencontre qu'une fois : à l'occasion des bases de données (chapitre chap:sql), où l'on écrit quelles lignes on veut, jamais comment les trouver.
« On ne présente pas de théorie générale sur les paradigmes de programmation, on se contente d'observer les paradigmes employés sur des exemples. » Et le saut inconditionnel — l'instruction GOTO — est explicitement hors programme : c'est une instruction qui permet d'aller n'importe où dans le code, et dont l'abandon est précisément ce qui a rendu la programmation structurée raisonnable.
/* Impératif : un état (s) que l'on modifie tour après tour. */
int s = 0;
for (int i = 0; i < n; i = i + 1) { s = s + t[i]; }
(* Fonctionnel : une expression, aucun état. *)
let rec somme = function [] -> 0 | x :: r -> x + somme r
-- Déclaratif : on dit CE QU'ON VEUT, pas comment l'obtenir.
SELECT SUM(valeur) FROM mesures;3.3 Compilé, interprété
Un langage compilé est traduit en entier, avant exécution, en un fichier que la machine sait exécuter. Un langage interprété est lu et exécuté au fil de la lecture par un autre programme, l'interpréteur.
| Compilé (C, OCaml) | Interprété (Python) | |
|---|---|---|
| Erreurs de type | détectées avant l'exécution | découvertes pendant |
| Vitesse | le code machine est direct | une couche s'interpose |
| Cycle de travail | compiler, puis lancer | lancer |
Le programme demande de connaître le passage « d'un fichier texte source en un fichier objet puis en un fichier exécutable », et la « différence entre fichiers d'interface et fichiers d'implémentation » — vue au chapitre chap:langage-c.
ocamlopt produit du code machine, ocamlc un bytecode interprété, et la boucle interactive ocaml se comporte comme un interpréteur. « Compilé » et « interprété » qualifient donc une mise en œuvre, pas un langage.
3.4 Les flottants, ou pourquoi
Un double occupe 64 bits, répartis en un signe, un exposant et une mantisse. Il représente donc un nombre de la forme , où ne compte qu'un nombre fini de bits. Les réels représentables sont en nombre fini ; tout le reste est arrondi au plus proche.
0.1 +. 0.2 = 0.3 (* false *)
0.1 +. 0.2 (* 0.30000000000000004 *)Ni ni ne s'écrivent exactement en base 2 — pas plus que ne s'écrit exactement en base 10. Chacun est arrondi, et les deux erreurs se cumulent.
Le programme demande d'« illustrer l'impact de la représentation par des exemples de divergence entre le calcul théorique d'un algorithme et les valeurs calculées par un programme ». En voici un second, plus inquiétant :
double x = 0.0;
for (int i = 0; i < 10; i = i + 1) { x = x + 0.1; }
/* x n'est PAS égal à 1.0 : c'est 0.9999999999999999 */Un algorithme dont la condition d'arrêt serait x == 1.0 ne s'arrêterait jamais. La boucle théorique termine ; le programme, non.
Exercices du chapitre
- Six boucles, six ordres de grandeur corrigé
- La taille d'une entrée n'est pas sa valeur corrigé
- L'exponentiation rapide, prouvée et comptée corrigé
- Trois Fibonacci, trois complexités corrigé
- Problème — Le tri par sélection, prouvé et compté corrigé
- Problème — Le compteur binaire, et son coût amorti corrigé