Меня смущает правильность и полнота алгоритмов.
Звуковой алгоритм никогда не вернет ложный результат. Возможно ли, что алгоритм ничего не возвращает?
Полный алгоритм будет адресован всем входам. Влияет ли результат, возвращаемый алгоритмом, на полноту алгоритма?
Например: если алгоритм сортировки будет принимать все входные данные и возвращать список, но он не гарантирует возврат отсортированного списка, это просто неправильный алгоритм, однако, он завершен?
Пусть S будет набором всех правильных ответов.
Звуковой алгоритм никогда не включает неправильный ответ в S, но он может пропустить несколько правильных ответов. => не обязательно "завершено".
Полный алгоритм должен получить каждый правильный ответ в S: включить полный набор правильных ответов. Но это может включать несколько неправильных ответов. Это может вернуть неправильный ответ для одного входа. => не обязательно "звук".
Так,
Звуковой алгоритм никогда не вернет ложный результат. Возможно ли, что алгоритм ничего не возвращает?
Это должно быть правильно. Но он ничего не может вернуть. (Пропущенная часть)
Например, если алгоритм сортировки будет принимать все входные данные и возвращать список, но он не гарантирует возвращение отсортированного списка, это просто ненадежный алгоритм, однако завершен ли он?
Смотря как.
Если возвращенные списки из алгоритма образуют множество S, оно завершается, потому что каждый правильный ответ включен. Это не обязательно означает, что каждый вывод правильный. Например, S = {b1, b2}. Предположим, что для входа a1 правильным выводом является b1; Для входа a2 правильный выход - b2. Если алгоритм возвращает b2 для a1, b1 для a2, он завершен, но не в порядке.
С другой стороны, если алгоритм всегда возвращает решение b1 для a1 и a2, оно, очевидно, не является полным.
Таким образом, вы не можете просто определить, является ли алгоритм полным или нет по его надежности, и наоборот.
Обратитесь к 7 Способам Подходить к Целостности и Полноте, также здесь.
Эта аналогия поможет вам понять концепцию.
Есть рыболовный конкурс. Цель состоит в том, чтобы поймать рыб весом более 1 кг. Есть два претендента, Сунада и Компила. Каждый использует свое озеро для ловли рыбы. В каждом озере точно одинаковое количество рыб (100 рыб), и среди этих рыб они имеют точно такое же количество рыб, вес которых превышает 1 кг (50 рыб).
Судья начинает соревнование со свистом. Они оба ловят многочисленных рыб до конца времени. Теперь речь идет о подсчете рыб, соответствующих правилу. Рефери начинает взвешивать всех рыб, пойманных Сунадой в первую очередь. Удивительно, но все рыбы, пойманные Сунадой, весят более 1 кг! Но он поймал только 45 рыб.
С другой стороны, Компила поймала 60 рыб. Кажется, Компила выигрывает, но судья еще не решил. Потому что может быть менее 45 рыб весом более 1 кг. После подсчета и взвешивания рефери говорит, что 50 рыб соответствуют правилу, которое делает Compila победителем.
Теперь по этой аналогии все рыбы, пойманные Сунадой, подчиняются правилу, которое делает его совершенно здоровым! Compila, с другой стороны, поймала всех рыб, которые соответствуют правилу, и это делает Compila идеально совершенной!