Problème algorithmique
Un problème algorithmique est un objet mathématique représentant un ensemble de questions que les ordinateurs pourraient éventuellement résoudre.
Par exemple, le problème de la factorisation : "Étant donné un entier positif n, trouve un facteur premier non trivial de n ."
est un problème de algorithmique. Les problèmes algorithmiques sont l’un des principaux objets d'étude en informatique théorique. Le domaine des algorithmes étudie les méthodes permettant de résoudre efficacement les problèmes de calcul. Le domaine complémentaire du complexité algorithmique< tente d'expliquer pourquoi certains problèmes de calcul sont intraitables pour les ordinateurs.
Un problème informatique peut être considéré comme une collection infinie d’instances avec une solution pour chaque instance. Par exemple, dans le problème de la factorisation, les instances sont les entiers n et les solutions les nombres premiers p décrivant des facteurs premiers non triviaux de n .
Il est classique de représenter à la fois les instances et les solutions par des chaînes binaires, à savoir des éléments de {0, 1}.
Par exemple, les nombres peuvent être représentés sous forme de chaînes binaires à l'aide du codage binaire. (Pour des raisons de lisibilité, nous identifions les nombres avec leurs codages binaires dans les exemples ci-dessous.)
