Donné un problème mathématique, avoir un algorithme qui le résout, c'est une suite d'instructions à appliquer mécaniquement, sans réfléchir, et qui conduit infailliblement à la solution. (Bon, bien sûr, la bonne définition, passe par une machine de Turing ou formulation équivalente de la calculabilité, voir par exemple le début de cette entrée ou encore les notes référencées depuis celle-ci, mais ce n'est pas ce qui m'intéresse ici, parce que je ne veux pas vraiment parler de maths.) Le mathématicien considère souvent qu'il a clos un problème lorsqu'il a trouvé un tel algorithme : parfois c'est abusé, par exemple quand l'algorithme n'est pas du tout applicable dans la pratique parce qu'il a une complexité colossale qui dépasse tout ce qu'on peut faire sur un ordinateur (ainsi la caricature du matheux qui considère qu'il a résolu une question parce qu'il l'a ramenée à l'étude algorithmique d'un nombre fini de cas, même si le nombre de cas dépasse le nombre d'atomes dans l'Univers). Mais il y a aussi, heureusement, des algorithmes qui sont vraiment applicables, même à la main sur des instances assez petites du problème.
Je regrette que notre système éducatif ne mette pas assez en valeur ce fait lorsque c'est le cas. Pourtant, l'étude d'algorithmes commence dès l'école primaire : quand on apprend aux enfants à ajouter, soustraire, multiplier et diviser des nombres écrits en décimal, on leur donne des algorithmes pour le faire (les algorithmes de multiplication et division sont d'ailleurs sous-optimaux, peut-être même pour une application manuelle, mais c'est une autre histoire). Autrement dit, il ne faut pas réfléchir pour les appliquer, seulement être patient et soigneux.
Je pense que ça devrait être quelque chose qu'on devrait souligner : il y a des problèmes de maths pour lesquels on vous demande de réfléchir, parce qu'on ne vous a pas enseigné un algorithme tout cuit qui produit infailliblement le résultat (il est vrai que les problèmes de maths jusqu'au lycée tendent à être tellement simples et surtout tellement formatés, que la réflexion disparaît presque complètement, mais il reste vrai qu'on n'a pas donné un algorithme qui traite tous les cas) ; et il y en a d'autres pour lesquels aucune réflexion n'est nécessaire, comme si on doit multiplier deux nombres de 30 chiffres décimaux, ce sera long et pénible, on aura intérêt à refaire plusieurs fois le calcul pour traquer les inévitables erreurs d'inattention, mais normalement on doit y arriver, on ne peut pas dire je ne sais pas, je ne trouve pas.
Or cette distinction n'est pas mise en valeur. Par exemple, au lycée (je ne sais pas exactement dans quelles classes, ça fait trop longtemps que j'y suis passé, les programmes ont dû changer douze fois), on apprend à calculer des dérivées (peu importe ici ce que c'est, mais c'est quelque chose qui transforme une fonction en une autre fonction) et des primitives (l'opération réciproque de la dérivée) de fonctions réelles sous forme symbolique : or il y a une différence cruciale, c'est que le calcul d'une dérivée est algorithmique, l'élève a tous les outils nécessaires pour calculer la dérivée de n'importe quelle expression, aussi compliquée fût-elle, faisant intervenir les fonctions élémentaires qu'il connaît, et il n'y a pas besoin de réfléchir ; alors que le calcul d'une primitive, lui, peut demander de l'astuce et de l'intelligence et peut échouer. (Bon, il s'avère qu'il y a bien un algorithme pour intégrer les fonctions élémentaires en forme élémentaire, et décider au passage quand c'est possible, mais il est compliqué, peu connu, et en tout cas n'est pas enseigné au lycée ; alors que l'algorithme de dérivation est enseigné, même si on ne dit pas exactement que c'est un algorithme.)
De même, toujours au lycée, il me semble qu'on ne met pas en valeur la différence entre une tâche comme « simplifier » ou « factoriser » une expression algébrique, et résoudre un système linéaire — le premier n'est pas algorithmique et d'ailleurs le but n'est pas toujours parfaitement clair (enfin, à un niveau un peu plus avancé, factoriser a un sens totalement clair, mais ce n'est pas exactement ce qu'on demande au lycée), tandis que la résolution d'un système linéaire par une méthode de pivot est algorithmique, et elle est enseignée au lycée, malheureusement sans qu'on souligne vraiment cet aspect algorithmique. (Peut-être que les choses ont un peu changé maintenant que l'informatique fait une timide apparition dans les classes.)
Maintenant, une chose qui me fascine, et qui est peut-être lié au fait qu'on n'attire pas assez leur attention sur le côté algorithmique, c'est la difficulté que peuvent avoir les étudiants à appliquer un algorithme. (Ces étudiants, que la cohérence n'étouffe pas, sont capables de se plaindre, quand on leur pose des problèmes nécessitant de la réflexion, que c'est trop conceptuel, et quand on leur pose des problèmes dont la solution est algorithmique, que c'est trop fastidieux, et dans les deux cas de se tromper. Mais passons.)
Quand je dis difficulté à appliquer un algorithme
, il y a
plusieurs aspects : rester bloqué sans rien faire à la question
(parfois alors qu'on a constaté que le même étudiant a été
capable d'appliquer l'algorithme sur un autre cas : ce n'est donc pas
qu'il ne l'a pas compris), essayer d'être plus malin que l'algorithme
et imaginer des optimisations qui sont fausses, ou, bien sûr, essayer
de l'appliquer et se tromper parce qu'on n'est pas soigneux.
Le dernier cas est particulièrement mystérieux. Je comprends qu'on se trompe en faisant des calculs, ça arrive à tout le monde, mais normalement, on doit pouvoir se forcer à aller lentement et à s'appliquer et ainsi arriver à un résultat certain, quitte à revérifier derrière (le mieux est bien sûr de refaire tout le calcul algorithmique en cachant la première application). Les algorithmes que j'ai demandé à mes étudiants d'appliquer lors des différents cours que j'ai enseignés n'étaient jamais terriblement compliqués. Pourtant, les taux d'erreurs sont stupéfiants.
Rien qu'à Télécom ParisPloum, par exemple, j'ai participé à l'enseignement d'un cours d'optimisation dont une grosse partie consistait à appliquer l'algorithme du simplexe pour la programmation linéaire, que le cours décrivait de façon applicable à la main (je ne me prononce pas sur la question de savoir si c'est quelque chose d'utile à enseigner : ce n'est pas moi qui ai conçu ce cours ni décidé le programme) ; les étudiants savaient qu'ils seraient interrogés sur l'algorithme du simplexe, qui, franchement, n'est pas terriblement compliqué, et beaucoup trouvaient le moyen de ne pas savoir mener les calculs. Un autre enseignement sur la théorie des langages contient une grosse moitié sur les langages rationnels et automates finis, et là aussi une bonne partie porte sur des algorithmes de base autour des automates finis (générer un automate à partir d'une expression régulière, déterminiser un automate, minimiser un automate — bon, je veux bien admettre que le dernier est un poil plus délicat), les étudiants savent qu'ils seront interrogés dessus, ce sont des algorithmes franchement simples et les cas sur lesquels on leur demande de les appliquer sont très petits et donc parfaitement gérables à la main, pourtant la proportion d'erreurs est colossale.
J'avoue ne pas comprendre. Ne pas savoir répondre à une question qui demande de la réflexion, ça se comprend, mais ne pas savoir appliquer un algorithme qui vous a été donné, c'est vraiment bizarre. On peut trouver ça fastidieux, mais quand il y a des points à un examen à la clé, a priori, les gens sont motivés.
Le cas qui m'a le plus épaté est dans un cours de théorie des jeux
que j'ai donné récemment et dont je
viens de finir de corriger les copies. (Les notes de cours
sont ici,
le sujet du
contrôle là
et son
corrigé là ;
je parle ci-dessous de la question 4 de l'exercice 2.) Je demandais
de calculer pour 0≤x≤5 et 0≤y≤5, la
valeur x⊗y
(produit de nim)
définie récursivement par : x⊗y est le plus
petit entier naturel qui n'est pas de la forme
(u⊗y)⊕(x⊗v)⊕(u⊗v)
pour u<x et v<y, où
l'opération “⊕” (somme de nim) est l'opération « ou exclusif » des
nombres écrits en binaire (et je précise que leurs notes de cours,
auxquelles les étudiants avaient le droit, contiennent une table
complète de a⊕b pour
0≤a,b≤15, donc ils n'avaient pas à passer par
l'écriture binaire, ils pouvaient juste consulter ces tables). Bref,
il s'agit d'exécuter à la main le code suivant (traduction
algorithmique de ce que je viens de dire en français, noter que
le ^ du C est exactement le ⊕ dont j'ai parlé) :
#include <stdio.h>
#include <assert.h>
int
main (void)
{
int nimprods[6][6];
for ( int x=0 ; x<6 ; x++ )
for ( int y=0 ; y<6 ; y++ )
{
int excluded[16];
for ( int z=0 ; z<16 ; z++ )
excluded[z] = 0;
for ( int u=0 ; u<x ; u++ )
for ( int v=0 ; v<y ; v++ )
{
int z = nimprods[u][y] ^ nimprods[x][v] ^ nimprods[u][v];
assert (z < 16);
excluded[z] = 1;
}
for ( int z=0 ; z<16 ; z++ )
if ( ! excluded[z] )
{
nimprods[x][y] = z;
printf ("%d (*) %d = %d\n", x, y, z);
break;
}
}
return 0;
}
Pour calculer le résultat suivant :
| ⊗ | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| 2 | 0 | 2 | 3 | 1 | 8 | 10 |
| 3 | 0 | 3 | 1 | 2 | 12 | 15 |
| 4 | 0 | 4 | 8 | 12 | 6 | 2 |
| 5 | 0 | 5 | 10 | 15 | 2 | 7 |
Même si on s'y prend de façon complètement naïve en suivant mécaniquement ce qui est ci-dessus, il y a 225 étapes de calcul (je veux dire, 225 valeurs (x,y,u,v) à considérer), ce qui n'est pas gigantesque, surtout s'agisant d'une question importante sur un contrôle de trois heures. L'exercice suivant donnait toutes sortes d'éléments pour simplifier les calculs (par exemple en remarquant que x⊗y = y⊗x, que x⊗0=0 ou encore que x⊗1=x, ou même que x⊗3=(x⊗2)⊕x) ou pour les vérifier (par exemple en sachant qu'à part la ligne et la colonne 0 tous les nombres de chaque ligne et colonne doivent être distincts), mais ce n'était pas nécessaire : j'avais moi-même vérifié que les calculs étaient parfaitement menables à la main, sans optimisation, en une poignée de minutes. Or sur 25 étudiants, pas un seul n'a réussi à mener les calculs à bien (celui qui a le mieux réussi a calculé 32 des 36 cases du tableau). Pourtant, j'ai des raisons de croire que, au moins pour la grande majorité d'entre eux, la question était claire, et ils savaient ce qu'ils devaient faire (je précise aussi que le concept de « plus petit nombre qui n'est pas sous la forme <truc> », qui peut être déstabilisant, a été pas mal rencontré dans le cours qu'ils ont eu, avec assez d'exemples). Leur problème a vraiment été d'appliquer l'algorithme sans se tromper, pas de le comprendre.
Voici la façon raisonnable d'appliquer l'algorithme ci-dessus à la main : on remplit le tableau case par case dans l'ordre de lecture ; pour chaque case (x,y), on parcourt toutes les lignes u strictement avant x et toutes les colonnes v strictement avant y, on note mentalement les trois valeurs situées aux trois coins du rectangle formé par les lignes u et x et les colonnes v et y (le quatrième coin étant la case qu'on cherche à remplir), pour chacun on fait la somme de nim des trois valeurs lues, ce qui se fait de tête en une fraction de seconde dès qu'on a l'habitude du binaire, et on note toutes les valeurs ainsi rencontrées, puis on recherche la plus petite qui ne l'a pas été.
On peut évidemment trouver que c'est idiot de faire exécuter des algorithmes par des humains, les ordinateurs sont là pour ça. Mais c'est un peu fallacieux : évidemment on ne va pas faire faire à des humains des cas vraiment compliqués des algorithmes, mais je pense qu'on ne comprend vraiment un algorithme que quand on sait en appliquer des cas simples à la main, et c'est quelque chose qu'on est effectivement amené à faire quand on développe l'algorithme, quand on cherche à le comprendre, ou quand on a besoin de débugguer une implémentation (même si on a un débuggueur pas à pas, on va souvent être amené à faire des étapes à la main pour confirmer qu'il se passe bien ce qu'on attendait, ou comprendre la différence). Je pense qu'un étudiant en informatique (et ceux dont je parle sont dans une filière spécialisée en mathématiques et informatique théorique) doit arriver à exécuter à la main du code tel que celui qui figure ci-dessus, et j'avoue que je suis un peu désemparé qu'aucun n'ait réussi.
Je serais presque tenté de militer pour l'inscription au concours d'entrée d'une épreuve d'« application mécanique d'algorithmes simples ».