Construction d'algorithmes

Il n'existe pas, hélas, de méthode universelle pour construire des algorithmes. Il y a cependant quelques grandes méthodes :

• la méthode incrémentale : c'est l'idée de résoudre un problème $P(n)$ à partir d'une solution de $P(n-1)$ ; c'est typiquement une méthode par récurrence, qui peut donner lieu aussi bien à des programmes itératifs qu'à des programmes récursifs ; dans le cas d'un problème d'optimisation, la méthode vorace consiste à construire une solution de $P(n)$ en prolongeant une solution de $P(n-1)$ par un choix localement optimal
• la méthode << diviser pour régner >> : c'est une méthode descendante, qui conduit à décomposer un problème en sous-problèmes et à construire une solution du problème en composant les solutions de ces sous-problèmes, typiquement en transformant un problème $P(n)$ en deux problèmes $P(n/2)$
• la programmation dynamique : c'est une méthode ascendante, utilisable pour des problèmes d'optimisation, qui consiste à construire la solution d'un problème à partir des solutions de tous les sous-problèmes ; elle s'applique quand toute sous-solution d'une solution optimale est optimale pour le sous-problème correspondant

On ne peut résister au plaisir de citer à ce propos les quatre préceptes du Discours de la Méthode de Descartes :

Le premier était de ne recevoir jamais aucune chose pour vraie que je ne la connusse évidemment être telle; c'est-à-dire, d'éviter soigneusement la précipitation et la prévention, et de ne comprendre rien de plus en mes jugements que ce qui se présenterait si clairement et si distinctement à mon esprit, que je n'eusse aucune occasion de le mettre en doute.

Le second, de diviser chacune des difficultés que j'examinerais, en autant de parcelles qu'il se pourrait, et qu'il serait requis pour les mieux résoudre.

Le troisième, de conduire par ordre mes pensées, en commençant par les objets les plus simples et les plus aisés à connaître, pour monter peu à peu comme par degrés jusques à la connaissance des plus composés, et supposant même de l'ordre entre ceux qui ne se précèdent point naturellement les uns les autres.

Et le dernier, de faire partout des dénombrements si entiers et des revues si générales, que je fusse assuré de ne rien omettre.