Problème algorithmique
Cet article est une ébauche concernant l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En informatique théorique, un problème est un objet mathématique qui représente une question ou un ensemble de questions. Le plus souvent ces problèmes sont de la forme : étant donné une un objet (l'instance), faire ceci ou répondre à telle question. Par exemple le problème de la factorisation est le problème suivant : étant donné un entier, trouver un facteur de cet entier.
On distingue en particulier deux types de problèmes[1] :
- les problèmes de décision, qui consistent à répondre oui ou non à une question (par exemple, cet entier est-il premier ?).
- les problème d'évaluation ou de construction, qui consiste à produire un nouvel objet.
Notes et références
- ↑ Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 1 (« Le modèle de calcul »)
