Я слышал разные интерпретации звука и полной . Я понимаю, что полнота означает поиск решения, если оно есть. Что значит сказать, что алгоритм - это звук ?
Что значит сказать, что алгоритм является звуковым и полным?
algorithms
terminology
mutelogan
источник
источник
Ответы:
Это очень конкретные термины, связанные с логикой.
Вот некоторые отправные точки:
http://en.wikipedia.org/wiki/Soundness
http://en.wikipedia.org/wiki/Completeness_(logic)
По сути, надежность (алгоритма) означает, что алгоритм не дает никаких результатов, которые не соответствуют действительности. Если, например, у меня есть алгоритм сортировки, который иногда не возвращает отсортированный список, алгоритм не работает.
Полнота, с другой стороны, означает, что алгоритм обращается ко всем возможным входам и не пропускает ни одного. Таким образом, если мой алгоритм сортировки никогда не возвращал несортированный список, а просто отказывался работать со списками, содержащими число 7, он не был бы завершен.
Он полный и надежный, если он работает на всех входах (семантически действителен в мире программы) и всегда дает правильный ответ.
источник
Я нахожу ответ Эрика Дитриха немного запутанным. Следующее лучше:
Алгоритм является надежным, если в любое время он возвращает ответ, который является верным. Алгоритм завершен, если он гарантирует возвращение правильного ответа для любого произвольного ввода (или, если ответа не существует, он гарантирует возврат ошибки).
Два важных момента:
Для примера рассмотрим алгоритм сортировки A, который получает в качестве входных данных список чисел. Мы говорим, что A - это звук, если каждый раз, когда он возвращает результат, результатом является отсортированный список. Аналогично, мы говорим, что A завершено, если гарантирует возврат отсортированного списка в любое время, когда мы даем ему список чисел.
источник
Эти термины пришли из теории вычислений, поэтому они более значимы в контексте теории вычислений, чем в контексте разработки программного обеспечения.
В большинстве стандартных моделей вычислений проблемы вычислений представлены в виде языков . Язык - это набор строк. Таким образом, алгоритм - это просто система или процедура, которая решает, является ли данная строка членом какого-либо языка (возвращая true или false). С точки зрения разработки программного обеспечения, теория вычислений особенно касается функций, которые выглядят следующим образом, предполагая, что строки неизменны:
Мы называем эту функцию завершенной, если она возвращает true для каждого аргумента, который является членом языка. Мы называем это звуком, если он возвращает false для каждого аргумента, который не является членом языка.
Другими словами, он завершен, если он всегда возвращает true, когда мы хотим, чтобы он возвращал true, и звучит, если он всегда возвращает false, когда мы хотим, чтобы он возвращал false.
Как это переводится на другие виды функций? Оказывается, почти всегда можно вставить произвольное количество данных в строку и восстановить его внутри функции. Таким образом, ограничение типа аргумента и арности - не более чем теоретическое упрощение. Однако, ограничение на тип возвращаемого значения более важно. Проблемы, которые требуют логического результата, называются проблемами решения . Большая часть теории вычислений связана с проблемами решения; множества P и NP ограничены решением проблем (и NP, по крайней мере, не может быть разумно определен без этого ограничения). Проблема остановки - еще один пример хорошо изученной проблемы решения.
По моему мнению, эти термины не обобщают вне области проблем принятия решений, поэтому различие между ними не имеет особого смысла при обсуждении общей функции.
источник
Есть гораздо лучшие ответы на SO . По сути, вы предоставляете сбор данных и критерии для поиска. Звуковой алгоритм ловит только ту рыбу, которая соответствует критериям, но он может пропустить некоторые элементы данных. Алгоритм Complete создает расширенный набор запрашиваемых результатов, что означает, что вы получаете некоторый мусор поверх запрашиваемых результатов. Звуковой алгоритм более консервативный.
Статистик, вероятно, сказал бы, что звуковой алгоритм смещен в сторону ошибок типа I (он не принимает правильных кандидатов), тогда как полный алгоритм смещен в сторону ошибок типа II (чтобы принять ложных кандидатов).
источник