Un problème, qui correspond quelque chose qu'on veut résoudre
algorithmiquement, est définit par les deux rubriques Donnée et
Résultat, auxquelles on peut ajouter une rubrique Contrainte
qui impose certaines restrictions sur la manière d'obtenir le résultat. La
description d'un algorithme commence donc par la description du problème à
résoudre.
Tous les problèmes définissables ne sont pas tous résolubles, on peut
schématiser les théorèmes mathématiques existants comme suit.
– Indécidabilité : Il existe des problèmes pour lesquels on ne sait pas s'il existe une solution algorithmique.
– Semi-décidabilité : Pour certains problèmes, il
existe des instances pour lesquelles un algorithme ne peut trouver de
solutions en temps fini.
– Complexité : Il existe un ensemble de problèmes
pour lesquels tout algorithme solution a une complexité
exponentielle voire hyper-exponentielle,
en O(2n), O(n 2n), O(kn) avec k>2,
O(n!), etc.
Remarque. parmi les problèmes exponentiels (en l'état
actuel des connaissances) est la classe des problèmes NP-complets. Les
solutions exactes y sont souvent recherchées par un parcours complet du
domaine (de taille exponentiel) des solutions.
– Accessibilité : Même si un problème a une solution
algorithmique, celui-ci peut être trop lent au regard des capacités de la
machine sur laquelle il va tourner. Une solution approchée peut
être recherchée par simplification et/ou résolution heuristique.
Quand on étudie un nouveau problème P1, on peut le ramener à un autre problème
P0 que l'on connait par des équivalences, par exemple en modélisant les
données de P1 avec celles de P0. Cela permet de réinvestir un algorithme pour
un problème qui ne lui était pas destiné auparavant et de définir des
classes (d'équivalence) de problèmes.
Avant de concevoir un nouvel algorithme, il est préférable de consulter ce qui
existe déjà.
Passer d'une complexité algorithmique en O(n3) à une complexité en
O(n2) sera toujours plus efficace en terme de vitesse d'exécution
que de passer d'un langage de haut niveau à la programmation en assembleur.
Mémoriser un ensemble d'algorithmes de référence n'est donc pas un effort
vain.