Quelle est la différence entre un algorithme, une langue et un problème?

Il semble que sur ce site, les gens corrigent souvent les autres pour avoir confondu "algorithmes" et "problèmes". Quelle est la différence entre ceux-ci? Comment savoir quand je devrais envisager des algorithmes et des problèmes? Et quel est leur lien avec le concept de langage dans la théorie des langages formels?

Pour des raisons de simplicité, je commencerai par examiner uniquement les problèmes de "décision", qui ont une réponse par oui ou par non. Les problèmes de fonction fonctionnent à peu près de la même manière, sauf qu'au lieu de oui / non, un mot de sortie spécifique est associé à chaque mot d'entrée.

Langue : une langue est simplement un ensemble de chaînes. Si vous avez un alphabet, tel que , est l'ensemble des mots ne contenant que les symboles de . Par exemple, est l'ensemble de toutes les séquences binaires de n'importe quelle longueur. Un alphabet n'a pas besoin d'être binaire, cependant. Cela peut être unaire, ternaire, etc.Σ * Σ { 0 , 1 } $\Sigma$$\Sigma^*$$\Sigma$$\{0,1 \}^*$

Une langue sur un alphabet est un sous-ensemble de .Σ $\Sigma$$\Sigma^*$

Problème : Un problème est une question sur une entrée à laquelle nous aimerions avoir une réponse. Plus précisément, un problème de décision est une question qui demande: "Notre entrée donnée remplit-elle la propriété ?$X$

Une langue est la réalisation formelle d'un problème. Lorsque nous voulons raisonner théoriquement sur un problème de décision, nous examinons souvent le langage correspondant. Pour un problème , la langue correspondante est:$X$

y $L = \{w \mid w$ est l'encodage d'une entrée au problème et la réponse à l'entrée y pour le problème X est "Oui" }$y$$X$$y$$X$$\}$

Déterminer si la réponse d'une entrée à un problème de décision est "oui" revient à déterminer si le codage de cette entrée sur un alphabet est dans la langue correspondante.

Algorithme : un algorithme est un moyen pas à pas de résoudre un problème. Notez qu’un algorithme peut être exprimé de nombreuses façons et dans plusieurs langues, et qu’il existe de nombreux algorithmes différents qui résolvent tous les problèmes.

Machine de Turing : Une machine de Turing est l'analogue formel d'un algorithme. Une machine de Turing sur un alphabet donné, pour chaque mot, s’arrêtera ou ne s’arrêtera pas dans un état d’acceptation. Ainsi, pour chaque machine de Turing , il existe une langue correspondante:$M$

s'arrête dans un état d'acceptation sur l'entrée w } .$L(M) = \{w \mid M$$w\}$

(Il existe une différence subtile entre les machines de Turing qui s'arrête sur toutes les entrées et s'arrête sur les entrées oui, qui définit la différence entre les classes de complexité et R E. )$\mathsf{R}$$\mathsf{RE}$

La relation entre les langues et les machines de Turing est la suivante

1. Chaque machine de Turing accepte exactement une langue

2. Il peut y avoir plus d'une machine de Turing qui accepte une langue donnée

3. Il se peut qu'aucune machine de Turing n'accepte une langue donnée.

Nous pouvons dire à peu près la même chose à propos des algorithmes et des problèmes: chaque algorithme résout un seul problème, mais il peut y avoir 0 ou plusieurs algorithmes résolvant un problème donné.

Complexité temporelle : L'une des sources de confusion les plus courantes entre algorithmes et problèmes concerne les classes de complexité. L'attribution correcte peut être résumée comme suit:

• Un algorithme a une complexité temporelle
• Un problème appartient à une classe de complexité

$f(n)$$f(n)$$n$

Les problèmes n'ont pas de temps d'exécution, puisqu'un problème n'est pas lié à un algorithme spécifique qui fonctionne réellement. Au lieu de cela, nous disons qu'un problème appartient à une classe de complexité, s'il existe un algorithme le résolvant avec une complexité temporelle donnée.

$\mathsf{P}, \mathsf{NP}, \mathsf{PSPACE}, \mathsf{EXPTIME}$$\mathsf{P}$$X$$X$$\mathsf{P}$$X$$X$$\mathsf{P}$