O que significa dizer que um algoritmo é Som e Completo?

Ouvi diferentes interpretações de som e completas . Entendo que integridade significa encontrar uma solução, se houver. O que significa dizer que um algoritmo é sólido .

O que significa dizer que um algoritmo é Som e Completo?

Estes são termos muito específicos, relacionados à lógica.

Aqui estão alguns pontos de partida:

http://en.wikipedia.org/wiki/Soundness

http://en.wikipedia.org/wiki/Completeness_(logic)

Basicamente, a solidez (de um algoritmo) significa que o algoritmo não produz nenhum resultado falso. Se, por exemplo, eu tenho um algoritmo de classificação que às vezes não retorna uma lista classificada, o algoritmo não é válido.

Completude, por outro lado, significa que o algoritmo trata de todas as entradas possíveis e não perde nenhuma. Portanto, se meu algoritmo de classificação nunca retornasse uma lista não classificada, mas simplesmente se recusasse a trabalhar em listas que continham o número 7, ele não estaria completo.

É completo e correto se funcionar em todas as entradas (semanticamente válidas no mundo do programa) e sempre acertar a resposta.

Acho a resposta de Erik Dietrich um pouco confusa. O seguinte é melhor:

Um algoritmo é som se, a qualquer hora ele retorna uma resposta, essa resposta é verdadeira. Um algoritmo é completo se garantir retornar uma resposta correta para qualquer entrada arbitrária (ou, se não houver resposta, garantir retornar a falha).

Dois pontos importantes:

1. A solidez é uma garantia fraca. Não promete que A terminará.
2. Solidez e completude são conceitos relacionados; De fato, eles são o inverso lógico um do outro. isto é, a solidez diz que, se uma resposta for retornada, essa resposta será verdadeira. A integridade diz que uma resposta é verdadeira se for retornada.

Considere, por exemplo, um algoritmo de classificação A que recebe como entrada uma lista de números. Dizemos que A é bom se toda vez que retorna um resultado, esse resultado é uma lista classificada. Da mesma forma, dizemos que A está completo se garantir a devolução de uma lista classificada a qualquer momento que fornecermos uma lista de números.

Esses termos vieram da teoria da computação, portanto, são mais significativos no contexto da teoria da computação do que no contexto da engenharia de software

Na maioria dos modelos padrão de computação, os problemas de computação são representados como linguagens . Um idioma é um conjunto de strings. Um algoritmo, então, é apenas um sistema ou procedimento que decide se uma determinada string é membro de alguma linguagem (retornando verdadeiro ou falso). Em termos de engenharia de software, a teoria da computação preocupa-se especificamente com funções que se parecem com isso, assumindo que as strings são imutáveis:

boolean some_function(string argument){...}

Chamamos essa função de completa se ela retornar verdadeira para todos os argumentos que são membros da linguagem. Chamamos isso de som se retornar falso para todo argumento que não seja membro da linguagem.

Em outras palavras, é completo se sempre retorna true quando queremos que retorne true, e soa se sempre retorna false quando queremos que retorne false.

Como isso se traduz em outros tipos de função? Como se vê, quase sempre é possível agrupar uma quantidade arbitrária de dados em uma string e reconstituí-la dentro da função. Portanto, a restrição ao tipo de argumento e à aridade nada mais é do que uma simplificação teórica. A restrição no tipo de retorno é mais importante, no entanto. Problemas que exigem um resultado booleano são chamados de problemas de decisão . Muita teoria da computação envolve problemas de decisão; os conjuntos P e NP são restritos a problemas de decisão (e NP, pelo menos, não poderia ser razoavelmente definido sem essa restrição). O problema da parada é outro exemplo de um problema de decisão muito estudado.

É minha opinião que esses termos não se generalizam fora do domínio dos problemas de decisão; portanto, a diferença entre eles não é realmente significativa ao discutir uma função geral.

Existem respostas muito melhores no SO . Basicamente, você fornece alguns critérios e coleta de dados para pesquisar. O algoritmo de som captura apenas o peixe que corresponde aos critérios, mas pode perder alguns itens de dados. O algoritmo completo produz um superconjunto de resultados solicitados, o que significa que você recebe algum lixo sobre os resultados solicitados. O algoritmo de som é mais conservador.

O estatístico provavelmente diria que o algoritmo do som é tendencioso para erros do tipo I (não aceita os candidatos corretos), enquanto o algoritmo completo é tendencioso para erros do tipo II (para aceitar os falsos candidatos).