Qual é a diferença entre um algoritmo, uma linguagem e um problema?

40

Parece que neste site, as pessoas geralmente corrigem outras por "algoritmos" e "problemas" confusos. Qual é a diferença entre estes? Como sei quando devo considerar algoritmos e problemas? E como eles se relacionam com o conceito de linguagem na teoria formal da linguagem?

jmite
fonte
Um algoritmo é uma maneira de resolver um problema.
Reinierpost

Respostas:

53

Para simplificar, começarei considerando apenas os problemas de "decisão", que têm uma resposta sim / não. Os problemas de função funcionam aproximadamente da mesma maneira, exceto em vez de sim / não, há uma palavra de saída específica associada a cada palavra de entrada.

Idioma : um idioma é simplesmente um conjunto de strings. Se você possui um alfabeto, como , é o conjunto de todas as palavras que contêm apenas os símbolos em . Por exemplo, é o conjunto de todas as seqüências binárias de qualquer tamanho. Um alfabeto não precisa ser binário, no entanto. Pode ser unário, ternário, etc.Σ Σ { 0 , 1 } ΣΣΣ{0,1}

Um idioma sobre um alfabeto é qualquer subconjunto de .Σ ΣΣ

Problema : Um problema é uma pergunta sobre alguma entrada que gostaríamos de responder. Especificamente, um problema de decisão é uma pergunta que pergunta: "Nossa entrada fornecida preenche a propriedade ?X

Uma linguagem é a realização formal de um problema. Quando queremos raciocinar teoricamente sobre um problema de decisão, geralmente examinamos o idioma correspondente. Para um problema , o idioma correspondente é:X

y X y X }L={ww é a codificação de uma entrada para o problema , e a resposta para a entrada para o problema é "Yes" yXyX}

Determinar se a resposta para uma entrada para um problema de decisão é "yes" é equivalente a determinar se uma codificação dessa entrada sobre um alfabeto está no idioma correspondente.

Algoritmo : Um algoritmo é uma maneira passo a passo de resolver um problema. Observe que um algoritmo pode ser expresso de várias maneiras e várias linguagens, e que existem muitos algoritmos diferentes para resolver qualquer problema.

Máquina de Turing : Uma máquina de Turing é o análogo formal de um algoritmo. Uma máquina de Turing sobre um determinado alfabeto, para cada palavra, irá ou não parar em um estado de aceitação. Assim, para cada máquina de Turing , existe um idioma correspondente:M

w }L(M)={wM pára em um estado de aceitação na entrada .w}

(Há uma diferença sutil entre as máquinas de Turing que param em todas as entradas e nas entradas yes, que define a diferença entre as classes de complexidade e .)R ERRE

A relação entre idiomas e máquinas de Turing é a seguinte

  1. Toda máquina de Turing aceita exatamente um idioma

  2. Pode haver mais de uma máquina de Turing que aceita um determinado idioma

  3. Pode não haver uma máquina de Turing que aceite um determinado idioma.

Podemos dizer aproximadamente a mesma coisa sobre algoritmos e problemas: todo algoritmo resolve um único problema, mas pode haver 0, ou muitos, algoritmos resolvendo um determinado problema.

Complexidade do tempo : Uma das fontes mais comuns de confusão entre algoritmos e problemas é em relação às classes de complexidade. A alocação correta pode ser resumida da seguinte forma:

  • Um algoritmo tem uma complexidade de tempo
  • Um problema pertence a uma classe de complexidade

Um algoritmo pode ter uma certa complexidade de tempo. Dizemos que um algoritmo tem uma complexidade limite superior, no pior caso, se o algoritmo parar no máximo em etapas para qualquer entrada do tamanho .f ( n ) nf(n)f(n)n

Os problemas não têm tempos de execução, pois um problema não está vinculado a um algoritmo específico que realmente é executado. Em vez disso, dizemos que um problema pertence a uma classe de complexidade, se existir algum algoritmo que resolva esse problema com uma dada complexidade de tempo.

P X X P X X PP,NP,PSPACE,EXPTIME etc. são todas classes de complexidade. Isso significa que eles contêm problemas, não algoritmos. Um algoritmo nunca pode estar em , mas se houver um algoritmo de tempo polinomial resolvendo um determinado problema , estará em . Também pode haver um monte de algoritmos de tempo exponencial que aceitam , mas como existe um único algoritmo de tempo polinomial que aceita , ele está em .PXXPXXP

jmite
fonte
11
Sinta-se à vontade para editar esta resposta como achar melhor.
jmite
Eu acho que seria bom mencionar que existem outros tipos de problemas computacionais (por exemplo, problemas de pesquisa).
Kaveh
11
Quem disse? Esse tipo de pensamento é parte do motivo pelo qual as pessoas tiveram tantos problemas para formalizar e algoritmo antes da intenção da Máquina de Turing. A tese de Church-Turing diz que um algoritmo É uma máquina de turing e vice-versa, e nem todas as máquinas de turing são interrompidas.
jmite
4
Cara, esta é a melhor resposta que eu já vi. Você acabou de resumir toda a ciência da computação em 1 página.
precisa saber é o seguinte
11
@ gnasher729 há um teorema que diz que pode ser definido em termos de verificação, mas de definição real é em termos de complexidade de tempo para não máquinas deterministas, daí o nome NP: nondeterministic polinomial
jmite