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

40

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?

jmite
la source
Un algorithme est un moyen de résoudre un problème.
reinierpost

Réponses:

53

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 } *ΣΣΣ{0,1}*

Une langue sur un alphabet est un sous-ensemble de .Σ *ΣΣ

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 XL={ww 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" }yXyX}

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)={wMw}

(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. )RRE

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.

P,NP,PSPUNECE,EXPTjeMEPXXPXXP

jmite
la source
1
N'hésitez pas à modifier cette réponse comme bon vous semble.
Jmite
Je pense qu'il serait bon de mentionner qu'il existe d'autres types de problèmes de calcul (par exemple, des problèmes de recherche).
Kaveh
1
Dit qui? Ce type de réflexion explique en partie pourquoi les gens avaient tant de difficulté à formaliser et à utiliser un algorithme avant l’intention de la machine de Turing. La thèse de Church-Turing dit qu'un algorithme est une machine de Turing et inversement, et que toutes les machines de Turing ne s'arrêtent pas.
Jmite
4
Mec, c'est la plus grande réponse que j'ai jamais vue. Vous venez de résumer toute l'informatique en 1 page.
CaptainCodeman
1
@ gnasher729 il existe un théorème qui dit qu'il peut être défini en termes de vérification, mais sa définition actuelle est en termes de complexité temporelle pour les machines non déterministes, d'où le nom NP: polynôme non déterministe
jmite