Vou dar a mesma resposta que dei na vez anterior em que esta pergunta foi feita.

Primeiro, entenda que não existe uma boa definição formal de “algoritmo” no momento da redação. A palavra-chave aqui é “formal”.

No entanto, existem pessoas inteligentes trabalhando nisso.

O que sabemos é que qualquer que seja um “algoritmo”, ele fica em algum lugar entre “função matemática” e “programa de computador”.

Uma função matemática é noção formal de um mapeamento de entradas para saídas. Assim, por exemplo, “ordenar” é um mapeamento entre uma sequência de itens ordenáveis e uma sequência de itens ordenáveis do mesmo tipo, que mapeia cada sequência para sua sequência ordenada. Esta função pode ser implementado usando diferentes algoritmos (por exemplo, merge sort, heap sort). Cada algoritmo, por sua vez, pode ser implementado usando programas diferentes (mesmo com a mesma linguagem de programação).

Portanto, o melhor controle que temos sobre o que é um “algoritmo” é que ele é algum tipo de classe de equivalência em programas, onde dois programas são equivalentes se eles fazem “essencialmente a mesma coisa”. Quaisquer dois programas que implementam o mesmo algoritmo devem computar a mesma função, mas o inverso não é verdadeiro.

Da mesma forma, há uma classe de equivalência entre algoritmos, onde dois algoritmos são equivalentes se eles computam a mesma função matemática .

A parte difícil em tudo isso é tentar capturar o que queremos dizer com “essencialmente a mesma coisa”.

Existem algumas coisas óbvias que devemos incluir. Por exemplo, dois programas são essencialmente iguais se diferirem apenas por renomeações de variáveis. A maioria dos modelos de linguagens de programação tem noções nativas de “equivalência” (por exemplo, redução beta e conversão eta no cálculo lambda), então devemos incluí-los também.

Qualquer relação de equivalência que escolhermos, isso nos dá alguma estrutura . Os algoritmos formam uma categoria em virtude do fato de serem a categoria quociente dos programas. Algumas relações de equivalência interessantes são conhecidas por dar origem a estruturas categóricas interessantes; por exemplo, a categoria de algoritmos recursivos primitivos é um objeto universal na categoria de categorias. Sempre que você vir uma estrutura interessante como essa, sabe que essa linha de investigação provavelmente será útil.

Comentários

• Obrigado por sua resposta precisa, apenas outra pergunta. Se considerarmos qualquer programa, independentemente do que faça, eles ainda recebem algumas entradas e seguem algumas instruções, e dão alguns resultados conforme são executados. Eles até podem ‘ não resolver nenhum problema (como chamamos), mas ainda é um mapeamento. poderiam ser algoritmos conhecidos, quero dizer qualquer programa?
• Se eu ‘ estou lendo você corretamente, você ‘ estou perguntando se uma definição formal de um ” algoritmo ” deve ou não conter a condição de que deve ser ” útil “. Eu diria ” não “, apenas porque é ‘ impossível formalizar isso noção.
• desculpe! meu inglês não é bom, então você diz ” não ” para quê? você admite que é ‘ impossível formalizar a utilidade de um programa e, apenas por definição, qualquer programa é um algoritmo? ou você diz que ‘ é necessário que consideremos a utilidade ao lado do algoritmo?
• Não ‘ acho que uma definição formal de um ” algoritmo ” deve exigir que seja útil, porque ” útil ” pode ‘ t ser formalmente definida.
• Sua resposta é a mais útil neste tópico +1. Acredito que por ” essencialmente a mesma coisa “, você quer dizer ” semanticamente equivalente “. Além disso, acho que todos os programas são essencialmente algoritmos (como diz o OP), uma vez que todos os programas são implementações que mapeiam alguma entrada para alguma saída, mesmo que esse mapeamento seja implícito. Como você afirmou, tudo depende da perspectiva.

Em última análise, a diferença é de perspectiva . Um programa é um programa: uma sequência de instruções em alguma linguagem, talvez uma linguagem de programação ou instruções em nível de máquina. Os algoritmos são geralmente descritos em um nível mais alto do que as instruções de máquina ou instruções de linguagem de programação, mas o nível de alto nível é bastante flexível. Por exemplo, em algumas circunstâncias, “Classifique o array e, em seguida, observe o $ k $ th elemento” é uma descrição perfeitamente boa de um algoritmo para localizar o $ k $ th maior objeto em um array; em outras circunstâncias, você pode querer especificar muito mais detalhes sobre como a classificação ocorre.

Como você disse, um algoritmo é algo como “um processo ou conjunto de regras a serem seguidas em cálculos ou outro problema -solução de operações, especialmente por um computador. ” Então, literalmente falando, todo programa é um algoritmo. Normalmente, porém, falamos de programas implementando algoritmos. Normalmente, ao descrever um algoritmo, evitamos os detalhes de baixo nível de exatamente como as coisas são implementadas, assumindo que um programador competente seria capaz de implementá-lo no idioma de sua escolha.

Comentários

• Acho que a precisão do algoritmo está relacionada ao conceito de matemática, lambda-cálculo ou máquina de Turing, ainda não ‘ não sei o que é isso linguagem de abstração? matemática ou uma linguagem natural com muitas afirmações difusas
• @Ahmad Algoritmo é um conceito informal. Não tem definição formal. De certo modo, ‘ é como uma prova matemática, que é diferente de uma prova formal em um sistema de prova formal. Acreditamos que as provas informais podem ser ” desenvolvidas ” para provas formais em qualquer sistema de prova formal escolhido (forte o suficiente), assim como qualquer o algoritmo pode ser totalmente implementado em qualquer linguagem de programação (Turing-complete).

Algoritmos no Turing A mentalidade completa é geralmente especificada por entrada e saída. Os programas reais fazem mais; eles

• comunicam-se com o usuário,
• comunicam-se com outras máquinas,
• reagem ao ambiente,
• não encerram e ainda são úteis,

e muito mais. Essas coisas geralmente não são consideradas em algoritmos ou teoria da computação, mas são essenciais para a maioria dos programas.

Comentários

• Este é um ponto muito bom. Mas você quer dizer algo como ” geralmente especificado como um meio de mapear a entrada para a saída “? Apenas especificar a entrada e a saída não é ‘ o suficiente: por exemplo, mergesort e quicksort produzem a mesma saída de qualquer entrada, mas não ‘ t considerados ser o mesmo algoritmo.
• @DavidRicherby Eu estava pensando em especificação no sentido PL; não ‘ não especificamos mais nada, portanto, os algoritmos não podem fazer mais nada. Claro, temos que fornecer mais do que a especificação para descrever um algoritmo concreto.
• Boas observações, mas se admitirmos que no final qualquer programa é um algoritmo, eu não ‘ t saber como esses assuntos que você abordou são medidos em um algoritmo. Talvez um tópico de IA ?!
• Quem admitiria isso e por quê? E o que você quer dizer com medida aqui? (E eu certamente não ‘ vejo o ângulo de IA aqui.)
• @Raphael, posso admitir (olhando a sintaxe, todos os programas parecem semelhantes, eles são sequências de instruções ou mapeamento de entrada para saída), eu apenas não ‘ não sei como outros recursos de um programa (aqueles que você endereçou) podem ser extraídos dessa definição. por exemplo, a diferença entre classificação rápida e MATLAB ou Windows Media Player !!

• Um algoritmo é uma abordagem sistemática para resolver um problema específico.

• Um programa é um conjunto de instruções que um computador deve seguir.

Portanto, um programa nem mesmo precisa resolver um problema.Tenho certeza de que todos podemos pensar em vários programas que causaram mais problemas do que resolveram. Um programa pode ser uma implementação de muitos algoritmos ou um algoritmo pode ser implementado juntando vários programas. Um programa pode até não conter algoritmos. Por exemplo, o programa vazio que simplesmente sai, ou talvez até mesmo um Hello World, poderia ser considerado um programa sem algoritmo.

Visto que um algoritmo resolve um problema específico, ele se concentra em um conceito completo específico. Um algoritmo, portanto, fornece etapas abstratas para processar um conjunto de informações relacionadas em um conjunto diferente de informações derivadas. Um programa não exige que seus componentes sejam conceitualmente relacionados. Por exemplo, um programa pode ter um ovo de páscoa, mas algo apropriadamente chamado de algoritmo não. Você pode ter um vírus ou trojan escondido em um programa, mas não em um algoritmo. O mais próximo que um algoritmo pode chegar disso seria algo como uma porta dos fundos em um algoritmo de criptografia, em que a falha planejada é parte da relação de informações estabelecida pelo algoritmo.

E, por último, um programa, como é abreviação de um programa de computador, tautologicamente requer um computador. Um algoritmo não. Se eu separar sistematicamente as camisas, calças e meias da roupa antes de guardá-las, isso é um algoritmo. Ele lida com entradas e saídas relacionadas, pode ser descrito em um fluxograma e tem consequências calculáveis em termos de eficiência (por exemplo, o número de peças de roupa que devem ser comparadas para encontrar meias que combinam).

Um algoritmo é um conceito ou ideia. É uma abordagem formal para resolver um problema. Algoritmos podem ser expressos ou implementados em uma variedade de linguagens de programação (geralmente, quase qualquer linguagem pode implementar qualquer algoritmo). Para alguns exemplos, você deve ler os Algoritmos de classificação na Wikipedia.

Um programa de computador é uma sequência específica de instruções em uma linguagem de programação específica . Um programa pode conter a implementação de muitos algoritmos. O Excel é um programa, mas seus recursos de classificação são a manifestação de um algoritmo.

Um algoritmo é um conjunto de operações passo a passo independente a ser realizado para resolver um problema específico ou uma classe de problemas.

Um programa de computador é uma sequência de instruções que cumprem as regras de uma linguagem de programação específica, escritas para realizar uma tarefa específica com um computador.

Os algoritmos são gerais e devem ser traduzidos em um linguagem de programação específica (implementada).

Comentários

• Mas o ponto principal da questão é que um programa (seja seu código-fonte ou o binário compilado ) é ” um conjunto de operações passo a passo independente a ser realizado para resolver um problema específico ou classe de problemas. ”
• Mas não é ‘ t. Um programa não é o ase operações, mas uma implementação delas: algo que as executa em um contexto particular. Por exemplo. o utilitário Unix sort não é um algoritmo de classificação, ele usa um algoritmo de classificação.

Um algoritmo está expressando nossa ideia ou solução para um problema específico em uma abordagem passo a passo. trata-se apenas de solução de problemas e abordagem compreensível para humanos, não para sistema de computador

Programa são instruções passo a passo implementadas para resolver problemas pelo sistema do computador. Ele deve ser compreensível não apenas pelo programador, mas também pelo computador.

Comentários

• Bem-vindo ao Computer Science Stack Exchange. Leia cs.stackexchange.com/tour.if você ainda não o fez.

As outras respostas aqui, eu acho, perdem um ponto importante. A definição de “algoritmo” que aprendi inclui o requisito de que o procedimento pare em todas as entradas . Naturalmente, isso torna “program” uma classe de procedimentos mais ampla do que “algoritmo”, uma vez que alguns programas param em todas as entradas e outros não.

Comentários

• Isso não é universal. A definição que aprendi não ‘ incluía esse requisito.

Aqui estão algumas maneiras de traçar a linha entre um algoritmo e um programa:

Finalidade significativa

Os programas são escritos com uma finalidade e representam uma tentativa de alcançar uma meta. Os algoritmos podem ser vistos como ferramentas para atingir esse objetivo.

Por exemplo, uma chave de fenda é um algoritmo para modificar o estado de um parafuso, mas a própria chave de fenda não tem um propósito para fazer isso.O objetivo está na cabeça do operador de chave de fenda que mantém o programa como se fosse colocar prateleiras.

Lógica de negócios

Este ponto está fortemente relacionado ao objetivo de um programa. Uma vez que os programas têm finalidades, eles inevitavelmente têm pedaços do mundo real, como datas específicas, medidas, tecnologias, nomes, etc.

Os algoritmos, por outro lado, não contêm lógica de negócios nem pedaços do mundo real e, em vez de operar em valores específicos operam em variáveis.

Por exemplo, nesse sentido, você pode comparar uma função matemática como f(x) = x^2 que é abstrata e opera em variáveis com uma receita culinária que contém valores precisos (pelo menos um para referência).

Resultado

Este ponto está fortemente relacionado à lógica de negócios de um programa. Um agente (como um usuário de navegador da web) consome o resultado de um programa, não o resultado de um algoritmo.

Por exemplo, o consumidor de uma receita culinária consome o bolo não o resultado de chantilly ou de forno aquecido.

Comentários

• Talvez seja melhor dizer isso a chave de fenda não ‘ tem a intenção de apertar os parafusos? No inglês cotidiano, certamente diríamos que uma chave de fenda tem o propósito de girar os parafusos: girar os parafusos é exatamente o que ela foi projetada para fazer.
• Além disso, eu ‘ Não tenho certeza do que você quer dizer com ” lógica de negócios ” (muitos programas não têm nada para fazer com negócios) ou dizendo que um algoritmo ” não contém lógica de negócios nem bits do mundo real “. Por exemplo, eu poderia perfeitamente formular um algoritmo de caminho mais curto em termos de cidades e estradas, em vez de vértices e bordas. O algoritmo ‘ não ” contém … bits do mundo real ” ?
• @DavidRicherby, você está certo, meu fraseado é ambíguo. O que eu quis dizer é um propósito significativo . Girar parafusos para apertar parafusos é inútil, assim como classificar uma matriz que nunca é usada. Por lógica de negócios, quero dizer toda a lógica do programa, exceto a lógica de utilitários e clichê de tecnologia, ou seja, toda a lógica que realmente implementa o propósito do programa, ou seja, a lógica de negócios de fazer um bolo é misturar ingredientes e assar e não inclui aprender a misturar ou assar que é reutilizada lógica de utilidade neste caso).
• @DavidRicherby, quanto a bits do mundo real , quero dizer atualização, ou seja, um programa diferente de um algoritmo precisa se comunicar de alguma forma com o mundo físico. Um algoritmo, por outro lado, pode ser um conceito puramente matemático.

I tenho quase certeza de que outras respostas são boas o suficiente para assumir a liderança, mas eis como vejo a diferença entre um algoritmo e um programa

• Um algoritmo consiste simplesmente nas etapas (independentes da máquina) que precisam ser seguidas em alguma ordem para resolver um problema.

• Um programa é um conjunto de instruções para um tipo específico de máquina para colocar um algoritmo em prática .

Por exemplo.

Digamos que você tenha um algoritmo que tem uma etapa para chegar a um determinado lugar antes de realizar alguma outra etapa. Agora, como essa etapa de alcance será realizada não está exatamente definida. Você pode optar por caminhar ou correr ou pegar um ônibus para fazer isso, mas isso depende de como você escolhe implementá-lo (que é o seu prog ram).

Você pode dizer que um algoritmo é uma abstração de um programa, ou seja, faltando os detalhes exatos, mas apresenta um plano para fazer algo .