Что значит сказать, что алгоритм Sound и Complete?

Я слышал разные интерпретации звука и полного . Я понимаю, что полнота означает найти решение, если оно есть. Что означает сказать, что алгоритмом является звук .

Что значит сказать, что алгоритм Sound и Complete?

31 голос | спросил mutelogan 20 MarpmTue, 20 Mar 2012 22:25:29 +04002012-03-20T22:25:29+04:0010 2012, 22:25:29

4 ответа


47

Это очень специфические термины, связанные с логикой.

Вот несколько отправных точек:

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

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

В принципе, устойчивость (алгоритма) означает, что алгоритм не дает никаких результатов, которые не соответствуют действительности. Если, например, у меня есть алгоритм сортировки, который иногда не возвращает отсортированный список, алгоритм не звучит.

Полнота, с другой стороны, означает, что алгоритм адресует все возможные входы и не пропускает никаких. Итак, если мой алгоритм сортировки никогда не возвращал несортированный список, но просто отказался работать над списками, содержащими номер 7, он не был бы полным.

Он является полным и звуковым, если он работает на всех входах (семантически действителен в мире программы) и всегда правильно отвечает.

ответил Erik Dietrich 20 MarpmTue, 20 Mar 2012 22:48:21 +04002012-03-20T22:48:21+04:0010 2012, 22:48:21
14

Я считаю, что ответ Эрика Дитриха немного запутан. Лучше следующее:

Алгоритм звук , если в любое время он возвращает ответ, этот ответ верен. Алгоритм complete , если он гарантирует возврат правильного ответа для любого произвольного ввода (или, если ответа нет, он гарантирует возврат отказа).

Два важных момента:

  1. Звук - слабая гарантия. Он не обещает, что A закончится.
  2. Звук и полнота - это связанные понятия; они являются логическим обратным отношением друг к другу. Т.е. звук говорит, что если ответ вернется, то ответ будет правдой. Полнота говорит, что ответ верен, если он возвращается.

Рассмотрим для примера алгоритм сортировки A, который получает в качестве входного списка чисел. Мы говорим, что A является звуковым, если каждый раз, когда он возвращает результат, результатом которого является отсортированный список. Аналогично, мы говорим, что A является полным, если гарантии возвращают отсортированный список при каждом его перечислении.

ответил Daniel 15 FebruaryEurope/MoscowbFri, 15 Feb 2013 10:04:25 +0400000000amFri, 15 Feb 2013 10:04:25 +040013 2013, 10:04:25
2

Эти термины пришли из теории вычислений, поэтому они более значимы в контексте теории вычислений, чем в контексте разработки программного обеспечения.

В большинстве стандартных моделей вычислений вычислительные задачи представлены как языки . Язык - это набор строк. Таким образом, алгоритм представляет собой всего лишь систему или процедуру, которая решает, является ли данная строка членом какого-либо языка (путем возврата true или false). В терминах программной инженерии теория вычислений конкретно связана с функциями, которые выглядят так, предполагая, что строки неизменяемы:

boolean some_function(string argument){...}

Мы вызываем эту функцию complete , если она возвращает true для каждого аргумента, являющегося членом языка. Мы называем это sound , если он возвращает false для каждого аргумента, который не является членом языка.

Другими словами, он завершен, если он всегда возвращает true, когда мы хотим, чтобы он возвращал true и звучал, если он всегда возвращает false, когда мы хотим, чтобы он возвращал false.

Как это переводится на другие виды функций? Как оказалось, почти всегда можно записать произвольное количество данных в строку и восстановить ее внутри функции. Таким образом, ограничение типа аргументов и арности есть не что иное, как теоретическое упрощение. Однако ограничение на тип возврата является более важным. Проблемы, вызывающие логический результат, называются решения проблемы . Большая теория вычислений включает решения проблем; множества P и NP ограничены решениями (и NP, по крайней мере, не может быть разумно определена без этого ограничения). Проблема остановки - еще один пример сильно изученной проблемы решения.

Я считаю, что эти термины не обобщают вне области решения проблем, поэтому разница между ними не имеет смысла при обсуждении общей функции.

ответил Kevin 3 MaramThu, 03 Mar 2016 10:54:19 +03002016-03-03T10:54:19+03:0010 2016, 10:54:19
-2

есть гораздо лучшие ответы на SO . В принципе, вы предоставляете некоторый набор данных и критерии для поиска. Звуковой алгоритм ловит вас только рыбу, которая соответствует критериям, но может пропустить некоторые элементы данных. Полный алгоритм создает надмножество запрошенных результатов, что означает, что вы получаете некоторый мусор поверх запрошенных результатов. Звуковой алгоритм более консервативен.

Статистик, вероятно, скажет , что звуковым алгоритмом являются предвзятые ошибки типа I (это не принять правильных кандидатов), тогда как полный алгоритм предвзято относится к ошибкам типа II (чтобы принять ложных кандидатов).

 введите описание изображения здесь>> </a> </p></body></html>

ответил Valentin Tihomirov 1 FebruaryEurope/MoscowbMon, 01 Feb 2016 01:46:01 +0300000000amMon, 01 Feb 2016 01:46:01 +030016 2016, 01:46:01

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132