Décrire un problème
Ce qu’on appelle problème en informatique est exactement la notion intuitivement associée à ce mot : c’est une description de ce qu’on aimerait faire. Typiquement, un problème peut se poser sous la forme “j’ai ça, j’aimerais trouver une manière de faire ça”.
Un exemple de problème est le suivant : “Je suis vendeur à domicile, et j’aimerais visiter toutes les villes de Bretagne pour vendre mes produits. Comment puis-je faire cela en minimisant ma consommation d’essence ?”. Ce problème est un grand classique, que nous étudierons en détails dans le cours. Pour faire court, on le dénote classiquement par le problème du voyageur de commerce.
Des algorithmes pour résoudre des problèmes
Une fois le problème posé, il convient d’en chercher une solution. Ce qu’on appelle un algorithme est une manière de résoudre un problème, décrite à la manière d’une recette de cuisine. Un algorithme doit être sans équivoque, et doit permettre la résolution du problème si on le suit à la lettre.
En général, on écrit les algorithmes dans un pseudo-langage, c’est à dire un langage à mi-chemin entre langage naturel et langage de programmation, qui permet de décrire la procédure à suivre pour résoudre le problème associé. Toutefois (de manière un peu abusive), on utilise souvent un vrai langage de programmation à la syntaxe simple pour décrire les algorithmes, comme nous le ferons probablement par moments avec Python.
Il est important de remarquer que pour un problème donné, il peut y avoir plusieurs algorithmes pour le résoudre. Si on reprend l’analogie à la recette de cuisine, le problème “Cuire des patates” peut être résolu par un premier algorithme consistant à plonger les patates dans l’eau bouillante, ou par un second impliquant de la vapeur, etc. Toutefois, tous les algorithmes ne sont pas égaux. On verra un peu plus loin quelques pistes pour les différencier.
Des programmes pour réaliser des algorithmes
On a un problème à résoudre, on a une solution théorique pour y arriver, il ne reste donc plus qu’à le faire ! Un programme est un texte compréhensible par une machine qui, quand on l’exécute, résout le problème posé en appliquant l’algorithme.
Ici aussi, il est possible d’écrire de très nombreux programmes pour implémenter (mettre sur machine) un même algorithme. En voici quelques causes :
- Le langage de programmation choisi impliquera certaines adaptations de l’algorithme (par exemple, en C, il faudra se soucier de la mémoire).
- Il existe de nombreuses bibliothèques (ensemble de fonctions prédéfinies) pour réaliser une même tâche. Par exemple, si l’algorithme indique “afficher x à l’écran”, on aura généralement recours à une fonction préexistante pour y arriver (et elles sont nombreuses à faire ça).
- Un programme peut vouloir profiter d’éléments propres à la machine (par exemple la présence d’un processeur graphique).
- Plus fourbe, un même programme pourra être lu de plusieurs manières différentes (selon le système d’exploitation ou la machine par exemple).
Il faut aussi toujours garder à l’esprit qu’un algorithme est une manière théorique de résoudre un problème. Au contraire, un programme est une mise en pratique de l’algorithme. Un algorithme théoriquement parfait ne pourra parfois pas être implémenté pour des raisons de contraintes physiques (pas assez de mémoire sur la machine) ou temporelles (résoudre le problème prendrait des décennies).
Parfois, c’est l’algorithme qui est à mettre en cause, car il pourrait résoudre le problème de manière plus rapide en changeant une de ses parties. Parfois, c’est le programme qui a un bug ou qui utilise des fonctions sous-optimales. Enfin, c’est parfois le problème qui est connu pour ne pas pouvoir être résolu en un temps acceptable, et ce quel que soit l’algorithme choisi pour y répondre.
Formaliser un problème
Un problème n’est pas toujours simple à résoudre, ni même à formuler. Ce qu’on appelle formaliser un problème, c’est le reformuler pour en abstraire les éléments inutiles, afin de pouvoir plus facilement proposer des algorithmes pour sa résolution.
La solution la plus courante est de se ramener à un problème connu. Par exemple, reprenons l’exemple précédemment évoqué consistant à parcourir toutes les villes de Bretagne en minimisant la consommation de carburant. La Bretagne n’est pas vraiment importante ici. Ce qui nous intéresse, c’est plutôt de savoir quelles sont les villes, et quelles sont les routes les reliant. On peut donc abstraire la Bretagne par son réseau routier, représentable par un graphe dont les sommets sont les villes et les arêtes sont les routes (le poids associé aux arêtes est la longueur de la route).
De même, minimiser la consommation d’essence se traduit par parcourir le moins de route possible. On cherche donc une suite de sommets dans le graphe routier telle que la somme des poids est minimale. On peut donc reformuler le problème de la façon suivante : “Etant donné un graphe, quel est le chemin de longueur minimale passant par tous les sommets ?”.
Formaliser un problème a de nombreux avantages. D’une part, cela donne déjà des pistes sur le type d’algorithmes standards à utiliser (ici, on aura besoin entre autres d’un algorithme de parcours de graphe).
D’autre part, cela permet de plus facilement rechercher dans la littérature si une solution existe déjà. En effet, peut-être que personne n’a cherché le chemin le plus court pour parcourir toutes les villes de Bretagne, mais il est probable qu’un ingénieur ait cherché comment minimiser la distance parcourue par un bras mécanique devant planter 100 clous.
Comparer des algorithmes répondant au même problème
Comme nous l’avons évoqué précédemment, de nombreux algorithmes existent pour répondre à un même problème, et certains sont meilleurs que d’autres. Nous n’entrerons pas ici dans les détails de comment comparer leur efficacité, mais il nous semble important d’évoquer un point : évaluer les performances d’un algorithme ne se fait pas par des tests !
Pourquoi ? Tout simplement car pour pouvoir tester un algorithme (temps d’exécution, consommation mémoire…), il faut d’abord l’implémenter sur une machine. Et comme nous l’avons vu précédemment, il existe un nombre considérable de programmes permettant de réaliser le même algorithme. On prend alors le risque de ne pas comparer les algorithmes, mais leurs implémentations.
Pour comparer deux algorithmes, il va falloir recourir à des outils plus formels. Nous étudierons plus tard dans le cours la notion de complexité, qui permet d’estimer les performances d’un algorithme en fonction de la taille de son entrée.
Enfin, il est utile de savoir que tous les algorithmes ne sont pas strictement comparables (pas un toujours meilleur que l’autre). Par exemple, un des algorithmes sera peut-être plus rapide, mais l’autre utilisera moins de mémoire et s’appliquera donc à des problèmes plus gros (par exemple, en remplaçant la Bretagne par la France).
Trouver le niveau qui pêche
Nous avons vu que les problèmes n’étaient pas toujours solubles pour plusieurs raisons, pouvant intervenir au niveau du programme, de l’algorithme ou du problème en soi. Ici, nous évoquons quelques pistes qui vous permettront de comprendre quelle est la partie qui bloque la résolution du problème étudié :
- Au niveau du programme : Vous avez écrit des dizaines de lignes de code, voire peut-être des milliers. Il est très peu probable (en fait n’y pensez même pas) que tout fonctionne du premier coup. Une solution à ça est de tester votre code, morceau par morceau. L’article traitant des bonnes pratiques en programmation parle entre autres de la décomposition en fonctions simples. Vous avez une fonction f calculant la somme de trois nombres ? Ecrivez un test vérifiant bien que f(-1, 0, 5) = 4.
- Au niveau de l’algorithme : L’algorithme choisi est-il directement réalisable ou fait-il des suppositions théoriques ? (besoin de milliers de processeurs, mémoire infinie…). Est-ce qu’il peut terminer en un temps raisonnable ? L’outil principal pour évaluer la qualité d’un algorithme est sa complexité.
- Au niveau du problème : Est-ce que le problème a une solution ? Ou existe-t-il des résultats théoriques indiquant que le problème est aussi difficile à résoudre qu’un autre problème connu ? L’outil qui nous servira principalement pour répondre à ces question est la notion de classe de complexité.
Pour approfondir
- Tester ses programmes avec des tests unitaires
- Une discussion sur la preuve de programmes (complètement en dehors du cadre du cours, mais présente un domaine de recherche florissant)